从字典中获取元素乘以它们的频率

这

lst=[]
for key, freq in d.items():
  for _ in range(freq):
    lst.append(key)

是渐近最优的: lst 需要具有完全和计数元素。没有办法低于这个标准。您在每个元素上花费的摊销固定时间( append 是摊销的恒定时间操作)。

这是 不 O(n)。时间复杂性并不像“嵌套循环数=n的幂”那么简单。这里会有什么?如果我给你的话,不可能是字典里的项目数 {1: k} ,这将需要O(k)来运行,尽管n固定为1。一直考虑,直到你的循环去哪里——你的一个循环运行n次,但内部循环运行的频率与n无关。

相反,这是O(计数和),正如所说,它是渐近最优的(尽管就输入大小而言仍然相当糟糕(指数))。你真的想重复每一个键吗 value 时间?

这并不意味着它实际上是最优的——正如Roman所证明的那样,常数因子可以减少。例如,您还可以通过对值求和来计算列表需要多长时间,然后创建一个具有适当容量的列表,这样就不需要重新分配。

无论哪种方式,您提出的第二个解决方案还是Roman提出的解决方案都不会比您当前的解决方案快。

结合 itertools .[chain, starmap, repeat] :

from itertools import chain, starmap, repeat

d = {1:2, 2:4, 3:5}
lst = list(chain.from_iterable(starmap(repeat, d.items())))
print(lst)

[1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]

使用列表理解的另一种选择:

lst = [i for k,v in d.items() for i in [k]*v]

有点加长的dict的计时 d = {1:2, 2:4, 3:5, 4:6, 5:7, 7:10, 8:8, 9:10, 10:15} :

In [341]: %timeit list(Counter(d).elements())
2.51 µs ± 48.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [342]: %timeit [i for k,v in d.items() for i in [k]*v]
1.92 µs ± 25.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

In [343]: %timeit list(chain.from_iterable(starmap(repeat, d.items())))
1.51 µs ± 18.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

我找到了一个解决方案,它比 O(N**2) 。

https://docs.python.org/3/library/collections.html#collections.Counter

不确定确切的时间复杂性

from collections import Counter as c
d = {1:2, 2:4, 3:5}
counter_dict = c(d)
list(counter_dict.elements())

#output
[1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]