我有一本字典如下:如何维护Python中的字典堆?
{'abc':100,'xyz':200,'def':250 .............}
它与键的字典作为一个实体的名称和值是实体的数量。我需要返回字典中的前10个元素。
我可以写一个堆做到这一点,但我不知道该怎么办值键映射为一定值将是相等的。
是否有任何其他的数据结构来做到这一点?
我有一本字典如下:如何维护Python中的字典堆?
{'abc':100,'xyz':200,'def':250 .............}
它与键的字典作为一个实体的名称和值是实体的数量。我需要返回字典中的前10个元素。
我可以写一个堆做到这一点,但我不知道该怎么办值键映射为一定值将是相等的。
是否有任何其他的数据结构来做到这一点?
使用heapq
你可能想要做这样的事情:
heap = [(-value, key) for key,value in the_dict.items()]
largest = heapq.nsmallest(10, heap)
largest = [(key, -value) for value, key in largest]
注意,因为heapq
只实现最小堆最好是颠倒值,使更大的值愈小。
该解决方案将是堆的尺寸小较慢,例如:
>>> import random
>>> import itertools as it
>>> def key_generator():
... characters = [chr(random.randint(65, 90)) for x in range(100)]
... for i in it.count():
... yield ''.join(random.sample(characters, 3))
...
>>> the_dict = dict((key, random.randint(-500, 500)) for key, _ in zip(key_generator(), range(3000)))
>>> def with_heapq(the_dict):
... items = [(-value, key) for key, value in the_dict.items()]
... smallest = heapq.nsmallest(10, items)
... return [-value for value, key in smallest]
...
>>> def with_sorted(the_dict):
... return sorted(the_dict.items(), key=(lambda x: x[1]), reverse=True)[:10]
...
>>> import timeit
>>> timeit.timeit('with_heapq(the_dict)', 'from __main__ import the_dict, with_heapq', number=1000)
0.9220538139343262
>>> timeit.timeit('with_sorted(the_dict)', 'from __main__ import the_dict, with_sorted', number=1000)
1.2792410850524902
随着3000的值,它只是略快于sorted
版本,这是O(nlogn)
而不是O(n + mlogn)
。如果我们增加了字典的大小,以10000 heapq
版本变得更快:
>>> timeit.timeit('with_heapq(the_dict)', 'from __main__ import the_dict, with_heapq', number=1000)
2.436316967010498
>>> timeit.timeit('with_sorted(the_dict)', 'from __main__ import the_dict, with_sorted', number=1000)
3.585728168487549
的时机可能也取决于你所运行的计算机上。你可能应该知道哪种解决方案最适合你的情况。如果效率不重要,我会建议使用sorted
版本,因为它更简单。
+1,但heapify的调用是多余的,事实上,'heapq.nlargest(the_dict。项目())'是你所需要的。 – 2013-02-10 08:09:29
如果字典仍然不变,然后,而不是试图直接或通过collections.Counter创建heapq,你可以尝试使用该值作为以相反的顺序关键字典项目进行排序,然后从它那里得到的前10种元素。您需要重新从元组
>>> some_dict = {string.ascii_lowercase[random.randint(0,23):][:3]:random.randint(100,300) for _ in range(100)}
>>> some_dict
{'cde': 262, 'vwx': 175, 'xyz': 163, 'uvw': 288, 'qrs': 121, 'mno': 192, 'ijk': 103, 'abc': 212, 'wxy': 206, 'efg': 256, 'opq': 255, 'tuv': 128, 'jkl': 158, 'pqr': 291, 'fgh': 191, 'lmn': 259, 'rst': 140, 'hij': 192, 'nop': 202, 'bcd': 258, 'klm': 145, 'stu': 293, 'ghi': 264, 'def': 260}
>>> sorted(some_dict.items(), key = operator.itemgetter(1), reverse = True)[:10]
[('stu', 293), ('pqr', 291), ('uvw', 288), ('ghi', 264), ('cde', 262), ('def', 260), ('lmn', 259), ('bcd', 258), ('efg', 256), ('opq', 255)]
字典如果您正在使用heapq,创造了堆,你需要nlogn
操作,如果你是,如果你heapify列表插入元素或logn
建立一个堆,接着mlogn
操作以取出顶部m
元件
如果要排序的项目,Python的排序算法保证在最坏的情况下O(nlogn)
(参照TIM Sort)和取前10个元素将是一个恒定的操作
实际上构建堆是'O(n)'而不是'O(nlogn)'。从文档:“heapify(x)#将列表转换为堆,就地,**线性时间**” – Bakuriu 2013-02-10 06:57:30
为了得到前10个元素,假设数字是排在第二位:
from operator import itemgetter
topten = sorted(mydict.items(), key=itemgetter(1), reverse = True)[0:10]
如果你想按值进行排序,然后键入只是将其更改为
key=itemgetter(1,0)
。
对于数据结构,堆听起来像你想要什么。只要将它们保存为元组,并比较数字项。
想象一下,一个字典,像这样(有= 1和z = 26的a-z
映射):
>>> d={k:v for k,v in zip((chr(i+97) for i in range(26)),range(1,27))}
>>> d
{'g': 7, 'f': 6, 'e': 5, 'd': 4, 'c': 3, 'b': 2, 'a': 1, 'o': 15, 'n': 14, 'm': 13, 'l': 12, 'k': 11, 'j': 10, 'i': 9, 'h': 8, 'w': 23, 'v': 22, 'u': 21, 't': 20, 's': 19, 'r': 18, 'q': 17, 'p': 16, 'z': 26, 'y': 25, 'x': 24}
现在你可以这样做:
>>> v=list(d.values())
>>> k=list(d.keys())
>>> [k[v.index(i)] for i in sorted(d.values(),reverse=True)[0:10]]
['z', 'y', 'x', 'w', 'v', 'u', 't', 's', 'r', 'q']
还指出,一些值映射将是平等的。现在,让我们更新d
所以它具有与映射1-26字母A-Z
:
>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(26)),range(1,27))})
现在无论A-Z
和a-z
地图1-26
:
>>> d
{'G': 7, 'F': 6, 'E': 5, 'D': 4, 'C': 3, 'B': 2, 'A': 1, 'O': 15, 'N': 14, 'M': 13, 'L': 12, 'K': 11, 'J': 10, 'I': 9, 'H': 8, 'W': 23, 'V': 22, 'U': 21, 'T': 20, 'S': 19, 'R': 18, 'Q': 17, 'P': 16, 'Z': 26, 'Y': 25, 'X': 24, 'g': 7, 'f': 6, 'e': 5, 'd': 4, 'c': 3, 'b': 2, 'a': 1, 'o': 15, 'n': 14, 'm': 13, 'l': 12, 'k': 11, 'j': 10, 'i': 9, 'h': 8, 'w': 23, 'v': 22, 'u': 21, 't': 20, 's': 19, 'r': 18, 'q': 17, 'p': 16, 'z': 26, 'y': 25, 'x': 24}
与副本映射
所以,唯一合理的结果是去返回值键列表:
>>> [[k[x] for x,z in enumerate(v) if z==i ] for i in sorted(d.values(),reverse=True)[0:10]]
[['Z', 'z'], ['Z', 'z'], ['Y', 'y'], ['Y', 'y'], ['X', 'x'], ['X', 'x'], ['W', 'w'], ['W', 'w'], ['V', 'v'], ['V', 'v']]
而且你可以在这里使用heapq:
[[k[x] for x,z in enumerate(v) if z==i ] for i in heapq.nlargest(10,v)]
你没有说明你想与重复的结果做什么,所以我想你想消除这些重复,而结果列表是保持了N久。
这确实是:
def topn(d,n):
res=[]
v=d.values()
k=d.keys()
sl=[[k[x] for x,z in enumerate(v) if z==i] for i in sorted(v)]
while len(res)<n and sl:
e=sl.pop()
if e not in res:
res.append(e)
return res
>>> d={k:v for k,v in zip((chr(i+97) for i in range(26)),range(1,27))}
>>> d.update({k:v for k,v in zip((chr(i+65) for i in range(0,26,2)),range(1,27,2))})
>>> topn(d,10)
[['z'], ['Y', 'y'], ['x'], ['W', 'w'], ['v'], ['U', 'u'], ['t'], ['S', 's'], ['r'], ['Q', 'q']]
Bakuriu的答案是正确的(使用heapq.nlargest)。
但是,如果你有兴趣在正确的算法使用,quickselect采用了类似的原理来快速排序,并且由同一人发明:C.A.R.霍尔。
然而,它并不完全对数组进行排序:完成后,如果您要求排在前n个元素,则它们位于数组的前n个位置,但不一定按排序顺序排列。
与快速排序一样,它首先选择一个元素并旋转数组,使得所有a [:j]小于或等于[j],并且所有[j + 1:]都大于a [ J]。
接下来,如果j == n,那么最大的元素是[:j]。如果j> n,则快速选择仅在枢轴左侧的元素上递归调用。如果j < n那么quickselect被调用到枢轴右侧的元素上,以从这些元素中提取n-j-1个最大的元素。
由于quickselect被递归调用仅在阵列的一侧(与快速排序,其被递归调用两个),它工作在线性时间(如果输入被随机排序,并且没有重复键)。这也有助于将递归调用转换为while循环。
这是一些代码。为了帮助理解它,outer while循环中的不变量是元素xs [:lo]保证位于n最大的列表中,并且元素xs [hi:]保证不会在n中最大。
import random
def largest_n(xs, n):
lo, hi = 0, len(xs)
while hi > n:
i, j = lo, hi
# Pivot the list on xs[lo]
while True:
while i < hi and xs[i] >= xs[lo]:
i += 1
j -= 1
while j >= lo and xs[j] < xs[lo]:
j -= 1
if i > j:
break
xs[i], xs[j] = xs[j], xs[i]
# Move the pivot to xs[j]
if j > lo:
xs[lo], xs[j] = xs[j], xs[lo]
# Repeat on one side or the other based on the location of the pivot.
if n <= j:
hi = j
else:
lo = j + 1
return xs[:n]
for k in xrange(100):
xs = range(1000)
random.shuffle(xs)
xs = largest_n(xs, 10)
assert sorted(xs) == range(990, 1000)
print xs
在最糟糕的情况下,快速选择可以直到O(n^2),尽管除非所选中心点是最大元素,否则不会太频繁地发生。我有中位数和快速选择实施,我也想堆做一个比较。为了克服快速选择,你可以从列表中取3个左右的随机数,并将它们的中位数作为关键点。 – gizgok 2013-02-12 04:24:47
如何以下,应该是O(LEN(XS))。
您只需将前n个元素与剩余元素中最大的元素交换即可。
def largest_n(xs, n):
for i in range(n):
for j in range(i+1,len(xs)):
if xs[j] > xs [i]:
xs[i], xs[j] = xs[j], xs[i]
return xs[:n]
'前10个元素'是否意味着最大的10个值? – dawg 2013-02-10 07:05:18
是的,这意味着最大的价值 – gizgok 2013-02-10 07:08:25
如何处理重复项?我的意思是,我们应该简单地忽略它们,就好像它们是不同的值,还是应该只保留一个重复的值? – Bakuriu 2013-02-10 07:23:50