python - 为什么在 Python 中 filter(sorted(xs)) 比 sorted(filter(xs)) 快？

Question

排序应该是O(n log n)并且过滤应该是O(n)。为什么我首先获得更好的排序性能，而过滤会减小列表的大小，从而在将 n 传递给排序之前减少它？

考虑这个问题，其中文本（属性：“Grass Skiing”的维基百科条目）被过滤为包含“i”的单词并排序。

排序（过滤器（xs））

$ python -m timeit -s 'text = "Grass skiing, skiing on grass is a method for training for alpine skiing Both grass skiing and alpine skiing have become established as sports in their own right The skis used for grass skiing are short with rolling treads or wheels These skis are attached to the skiers boots Depending on the skill of the grass skier high speeds and jumps can be navigated".split(" ")' 'sorted(filter(lambda s: s.find("i") >= 0, text))'

20000 loops, best of 5: 14.7 usec per loop

过滤器（排序（xs））

$ python -m timeit -s 'text = "Grass skiing, skiing on grass is a method for training for alpine skiing Both grass skiing and alpine skiing have become established as sports in their own right The skis used for grass skiing are short with rolling treads or wheels These skis are attached to the skiers boots Depending on the skill of the grass skier high speeds and jumps can be navigated".split(" ")' 'filter(lambda s: s.find("i") >= 0, sorted(text))'

100000 loops, best of 5: 2.74 usec per loop

标签： python

Answer 1

正如评论中的评论者指出的那样，结果filter(sorted(xs))是惰性的并导致迭代器，但sorted(filter(xs))急切并导致集合类型。要强制计算过滤器（在前一种情况下），请将计算包装在集合类型中，例如 alist或tuple: tuple(filter(sorted(xs))。

进行此更改后，我的测试用例按预期运行：

排序（过滤器（xs））

$ python -m timeit -s 'text = "Grass skiing, skiing on grass is a method for training for alpine skiing Both grass skiing and alpine skiing have become established as sports in their own right The skis used for grass skiing are short with rolling treads or wheels These skis are attached to the skiers boots Depending on the skill of the grass skier high speeds and jumps can be navigated".split(" ")' 'sorted(filter(lambda s: s.find("i") >= 0, text))'
20000 loops, best of 5: 16 usec per loop

过滤器（排序（xs））

$ python -m timeit -s 'text = "Grass skiing, skiing on grass is a method for training for alpine skiing Both grass skiing and alpine skiing have become established as sports in their own right The skis used for grass skiing are short with rolling treads or wheels These skis are attached to the skiers boots Depending on the skill of the grass skier high speeds and jumps can be navigated".split(" ")' 'list(filter(lambda s: s.find("i") >= 0, sorted(text)))'
20000 loops, best of 5: 18.3 usec per loop