Сортировка списка: числа в порядке возрастания, буквы в нисходящем

Этот вопрос фактически адаптирован из ранее заданного Mat.S ( изображение ). Хотя он был удален, я подумал, что это хороший вопрос, поэтому я переписываю его с более ясными требованиями и своим собственным решением.


Учитывая список букв и цифр, скажем,

['a', 2, 'b', 1, 'c', 3] 

Требование состоит в том, чтобы сортировать числа по возрастанию и буквы в нисходящем, не изменяя относительное положение букв и цифр. Под этим я имею в виду, если несортированный список:

 [L, D, L, L, D] # L -> letter; # D -> digit 

Затем отсортированный список также должен быть

 [L, D, L, L, D] 
  1. Буквы и цифры не обязательно чередуются по регулярному шаблону – они могут появляться в любом произвольном порядке

  2. После сортировки – числа возрастают, буквы спускаются.

Таким образом, для примера выше выход

 ['c', 1, 'b', 2, 'a', 3] 

Другой пример:

  In[]: [5, 'a', 'x', 3, 6, 'b'] Out[]: [3, 'x', 'b', 5, 6, 'a'] 

Что было бы хорошим способом сделать это?

Ниже приведен оптимизированный подход с использованием defaultdict() и bisect() :

 In [14]: lst = [5, 'a', 'x', 3, 6, 'b'] In [15]: from collections import defaultdict In [16]: import bisect In [17]: def use_dict_with_bisect(lst): d = defaultdict(list) for i in lst: bisect.insort(d[type(i)], i) # since bisect doesn't accept key we need to reverse the sorted integers d[int].sort(reverse=True) return [d[type(i)].pop() for i in lst] .....: 

Демо:

 In [18]: lst Out[18]: [5, 'a', 'x', 3, 6, 'b'] In [19]: use_dict_with_bisect(lst) Out[19]: [3, 'x', 'b', 5, 6, 'a'] 

В случае, если вы имеете дело с более крупными списками, более оптимизировано отказаться от использования bisect который имеет сложность в отношении O (n 2 ), и просто использовать встроенную функцию sort() python с сложностью Nlog (n).

 In [26]: def use_dict(lst): d = defaultdict(list) for i in lst: d[type(i)].append(i) d[int].sort(reverse=True); d[str].sort() return [d[type(i)].pop() for i in lst] 

Сравнительный анализ с другими ответами, в которых показан последний подход с использованием dict и встроенной sort , почти на 1 мс быстрее, чем другие подходы:

 In [29]: def use_sorted1(lst): letters = sorted(let for let in lst if isinstance(let,str)) numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) return [letters.pop() if isinstance(elt,str) else numbers.pop() for elt in lst] .....: In [31]: def use_sorted2(lst): f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) return [next(f1) if isinstance(x, str) else next(f2) for x in lst] .....: In [32]: %timeit use_sorted1(lst * 1000) 100 loops, best of 3: 3.05 ms per loop In [33]: %timeit use_sorted2(lst * 1000) 100 loops, best of 3: 3.63 ms per loop In [34]: %timeit use_dict(lst * 1000) # <-- WINNER 100 loops, best of 3: 2.15 ms per loop 

Вот эталон, показывающий, как использование bisect может замедлить процесс для длинных списков:

 In [37]: %timeit use_dict_with_bisect(lst * 1000) 100 loops, best of 3: 4.46 ms per loop 

Посмотри, нет, нет.

 lst = ['a', 2, 'b', 1, 'c', 3] letters = sorted(let for let in lst if isinstance(let,str)) numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True) lst = [(letters if isinstance(elt,str) else numbers).pop()for elt in lst] 

Я ищу способ превратить это в (ужасный) однострочный лайнер, но пока не повезло – предложения приветствуются!

Я взломал это, создав два генератора, а затем убрав из них условно:

 In [116]: f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True)) In [117]: f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst))) In [118]: [next(f1) if isinstance(x, str) else next(f2) for x in lst] Out[118]: ['c', 1, 'b', 2, 'a', 3] 

В одной строке:

 list(map(list, sorted(zip(lst[::2], lst[1::2]), key=lambda x: x[1] if hasattr(x[0], '__iter__') else x[0]))) 

Полностью не рекомендуется, но мне было весело кодировать его.

 from collections import deque from operator import itemgetter lst = ['a', 2, 'b', 1, 'c', 3] is_str = [isinstance(e, str) for e in lst] two_heads = deque(map(itemgetter(1), sorted(zip(is_str, lst)))) [two_heads.pop() if a_str else two_heads.popleft() for a_str in is_str] 

Почему бы нам просто не отсортировать список в порядке возрастания, а обеспечить, чтобы числа приходили перед буквами:

 [D, D, L, L, L] # L -> letter; # D -> digit 

Мы можем добиться этого таким образом:

 >>> lst = [5, 'a', 'x', 3, 6, 'b'] >>> sorted(lst, key=lambda el: (isinstance(el, str), el)) [3, 5, 6, 'a', 'b', 'x'] 

Затем мы просматриваем исходный массив слева направо и, если встретимся с номером, мы выбираем элемент из начала отсортированного массива, иначе с конца. Таким образом, полное подробное решение будет:

 def one_sort(lst): s = sorted(lst, key=lambda el: (isinstance(el, str), el)) res = [] i, j = 0, len(s) for el in lst: if isinstance(el, str): j -= 1 res.append(s[j]) else: res.append(s[i]) i += 1 return res lst = [5, 'a', 'x', 3, 6, 'b'] print(one_sort(lst)) # [3, 'x', 'b', 5, 6, 'a'] 

Гораздо более короткое, но загадочное решение будет:

 def one_sort_cryptic(lst): s = sorted(lst, key=lambda el: (isinstance(el, str), el)) return [s.pop(-isinstance(el, str)) for el in lst] lst = [5, 'a', 'x', 3, 6, 'b'] print(one_sort_cryptic(lst)) # [3, 'x', 'b', 5, 6, 'a']