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

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

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

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

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

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

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

[L, D, L, L, D]

Буквы и цифры не обязательно чередуются в регулярном шаблоне - они могут появляться в любом произвольном порядке
После сортировки - числа возрастают, буквы спускаются.

Итак, для примера выше выходной файл

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

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

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

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

Ответ 1

Вот оптимизированный подход с использованием 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 ²) и просто использует встроенную функцию 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

Ответ 2

Посмотрите ma, no iter:

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]

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

Ответ 3

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

f1 = iter(sorted(filter(lambda x:     isinstance(x, str), lst), reverse=True))
f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst)))

[next(f1) if isinstance(x, str) else next(f2) for x in lst]
# ['c', 1, 'b', 2, 'a', 3]

Ответ 4

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

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

Ответ 5

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

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]

Ответ 6

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

[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']