<p>在这里画草图。其中<code>N = len(data_list)</code>和<code>S = sqrt(N)</code>使用<code>O(S)</code>额外内存并占用最坏情况下的<code>O(N*log(N))</code>时间:</p>
<ul>
<li><p>对于原始数据中长度为<code>S</code>的每个连续切片,将该切片复制到临时列表中,使用<code>.sort()</code>对其进行适当排序,然后将结果写入唯一的临时文件。总共将有大约<code>S</code>个临时文件</p></li>
<li><p>将这些临时文件馈送到<code>heapq.merge()</code>。这是一个生成器,只跟踪当前跨<code>S</code>输入的<code>S</code>最小值,因此此部分也有<code>O(S)</code>内存负担</p></li>
<li><p>删除临时文件</p></li>
</ul>
<p>您可以使用的内存越多,所需的临时文件就越少,运行速度也就越快</p>
<h2>削减常数因子</h2>
<p>正如评论中所指出的,次二次时间算法的希望渺茫。但是,您可以通过减少数据的传递次数来减少原始算法中的常数因子。这里有一种方法,在每次传递数据时生成下一个<code>K</code>条目。不过,总的来说,它仍然是二次时间</p>
<pre><code>def sorted_nocopy_generator(data_list, K=100):
import itertools
from bisect import insort
assert K >= 1
total = 0
too_small = None
while total < len(data_list):
active = [] # hold the next K entries
entry2count = {}
for entry in data_list:
if entry in entry2count:
entry2count[entry] += 1
elif ((too_small is None or too_small < entry) and
(len(active) < K or entry < active[-1])):
insort(active, entry)
entry2count[entry] = 1
if len(active) > K: # forget the largest
del entry2count[active.pop()]
for entry in active:
count = entry2count[entry]
yield from itertools.repeat(entry, count)
total += count
too_small = active[-1]
</code></pre>
<h2>消除最坏的情况</h2>
<p>正如@btilly的回答一样,上面代码中最糟糕的情况可以通过使用max堆来避免。然后将新条目添加到<code>active</code>具有最坏情况时间<code>O(log(K))</code>,而不是<code>O(K)</code></p>
<p>幸运的是,<code>heapq</code>模块已经提供了一些可用于此目的的东西。但是,处理重复数据就成了一件令人头痛的事情——没有公开max heap<code>heapq</code>所使用的隐藏式堆</p>
<p>因此,下面的特殊情况是感兴趣的最小<code>K</code>项中的最大项,使用<code>.count()</code>(如在原始程序中)进行完整传递以计算有多少个</p>
<p>但是,它不需要对每个</em>惟一元素执行该操作,而只需要对每个<code>K</code>元素执行一次</p>
<p>额外内存使用与<code>K</code>成正比</p>
<pre><code>def sorted_nocopy_generator(data_list, K=100):
import itertools
from heapq import nsmallest
assert K >= 1
too_small = None
ntodo = len(data_list)
while ntodo:
if too_small is None:
active = nsmallest(K, data_list)
else:
active = nsmallest(K, (x for x in data_list
if x > too_small))
too_small = active[-1]
for x in active:
if x == too_small:
break
yield x
ntodo -= 1
count = data_list.count(too_small)
yield from itertools.repeat(too_small, count)
ntodo -= count
assert ntodo >= 0
</code></pre>