python - 按降序对列表 : numbers in ascending, 字母进行排序

Question

本题其实改编自one previously asked by Mat.S (image)。虽然被删了，但我觉得这是个好问题，所以重新发一下，要求更明确，有自己的解决方案。

---

给定一个字母和数字列表，假设

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

执行此操作的好方法是什么？

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

如果你正在处理更大的列表，它会更优化地使用复杂度为 O(n²) 的 bisect 并只使用内置的 python sort() 复杂度为 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 的最新方法比其他方法快 1ms:

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