在Python中从频率字典构建一个列表的列表

Question

我需要帮助找到一个快捷方式，从一个频率字典中构建一个按频率排序的列表。我能够通过将每个元素附加到一个列表中，然后将每个列表附加到“列表的列表”中来构建一个列表的列表（仅在频率为1-3时容易），但是如果我有高达100或更多的频率呢？！必须有更好的方法。

dictionary = {'ab':2, 'bc':3, 'cd':1, 'de':1, 'ef':3, 'fg':1, 'gh':2}
list_1 = []
list_2 = []
list_3 = []
list_of_lists = []

for key, value in dictionary.items():
    if value == 1:
            list_1.append(key)
for key, value in dictionary.items():
    if value == 2:
            list_2.append(key)
for key, value in dictionary.items():
    if value == 3:
            list_3.append(key)

list_of_lists.append(list_1)
list_of_lists.append(list_2)
list_of_lists.append(list_3)

print list_of_lists

在Python中，复制的格式如下：

[['de', 'cd', 'fg'], ['ab', 'gh'], ['ef', 'bc']]

这正是我想要的，但对于包含100,000多个单词和100+频率的语料库来说，这种方法不起作用。请帮助我找到一种更好、更简便的方法来构建我的列表。

- Jackie

Answer 1

---

解决方案1 - 通过列表的逆映射（所要求的）

您正在寻找类似于直方图但是相反的东西。

def inverseHistogram(valueFreqPairs):
    maxFreq = max(p[1] for p in valueFreqPairs)+1
    R = [[] for _ in range(maxFreq)]
    for value,freq in valueFreqPairs:
        R[freq] += [value]
    return R

演示：

>>> inverseHistogram(dictionary.items())
[[], ['de', 'cd', 'fg'], ['ab', 'gh'], ['ef', 'bc']]

---

解决方案2 - 通过defaultdict模式实现反向映射（更加简洁）

如果您愿意使用字典来组织反向映射（这似乎更加优雅），那么这将会更好。这是我个人的做法。

reverseDict = collections.defaultdict(list)
for value,freq in dictionary.items():
    reverseDict[freq].append(value)

演示：

>>> dict(reverseDict)
{1: ['de', 'cd', 'fg'], 2: ['ab', 'gh'], 3: ['ef', 'bc']}

附注：如果您的频率稀疏，例如您的输入是{'onlyitem':999999999}，那么这也将为您节省空间，因此避免了制作比您的内存更大的列表，从而锁定您的计算机。

- ninjagecko

---

谢谢ninjagecko，看来我也需要查一下直方图！ - Jackie

Answer 2

最好的方法：将它们全部放入字典中。

result = {}

for key, value in dictionary.iteritems():
  if not value in result:
    result[value] = []
  result[value].append(key)

稍微简单一些：

from collections import defaultdict
result = defaultdict(list)

for key, value in dictionary.iteritems():
  result[value].append(key)

或者创建一个列表：

result = [[]] * max(dictionary.values())

for key, value in dictionary.iteritems():
  result[value-1].append(key)

- bluepnume

---

如果频率值稀疏，以这种方式创建列表可能不是最佳选择。 - Rafał Rawicki

我认为OP希望以这种方式实现...一个列表，其中所有元素都存储在相应的偏移量处。 - hochl

谢谢你，bluepnume。这里的第三个解决方案会生成一个列表，而这是我以后需要的形式（我将通过调用它的索引来使用每个列表）。 - Jackie

在这里，对列表进行乘法运算是行不通的。它不会创建max(d.v())个新列表，而只是创建了max(d.v())个相同列表的副本。换句话说，result中的每个子列表都是相同的--试一下就知道了。 - DSM

Answer 3

dict_of_lists = {}

for key, value in dictionary.items():
    if value in dict_of_lists:
        dict_of_lists[value].append(key)
    else:
        dict_of_lists[value] = [key]

list_of_lists = dict_of_lists.values()

- Rafał Rawicki

---

请记住，仅使用dict.values()并不能保证结果以任何有意义的方式排序。 - bluepnume

没问题。如果你想要对它们进行排序：list_of_lists = map(lambda x: x[1], sorted(dict_of_lists.items()))。 - Rafał Rawicki

由于我是新手程序员，“map”对我来说不是很清楚。我会进行一些研究并尝试弄清楚它...谢谢，Rafal！ - Jackie

是的，它不是语言的基本元素，但当你写更多的代码时，map、filter、lambda等非常方便。 - Rafał Rawicki

Answer 4

你可以简单地做这样的事情：

dictionary = {'a1':2, ..., 'g':100}
MAX_FREQUENCE = max([dictionary[k] for k in dictionary]) //find the max frequency
list_of_lists=[[] for x in range(MAX_FREQUENCE] //generate empty list of lists
for k in dictionary:  
    dictionary[d[k]-1].append(k)

-1 是因为 list_of_lists 从0开始。在代码中动态构建列表的语法：[f(x) for x in iterable] 称为列表推导式。

- Zenon

---

如果频率超过100，这个能用吗？我不知道最大频率是多少。 - Jackie

Answer 5

你可以使用默认字典来存储你的数据：

import collections

dictionary={'ab':2, 'bc':3, 'cd':1, 'de':1, 'ef':3, 'fg':1, 'gh':2}
lists_by_frequency=collections.defaultdict(list)
for s, f in dictionary.iteritems():
        lists_by_frequency[f].append(s)
list_of_lists=[[] for i in xrange(max(lists_by_frequency)+1)]
for f, v in lists_by_frequency.iteritems():
        list_of_lists[f]=v
print lists_by_frequency
print list_of_lists

输出：

defaultdict(<type 'list'>, {1: ['de', 'cd', 'fg'], 2: ['ab', 'gh'], 3: ['ef', 'bc']})
[[], ['de', 'cd', 'fg'], ['ab', 'gh'], ['ef', 'bc']]

正如您所看到的，每个组都存储在其频率的索引处。如果频率至少为1，则可以从最终结果中减去1，以便您不会在偏移量为零的位置得到空列表。

- hochl

Answer 6

函数式编程方式：

import collections

dictionary = {'ab':2, 'bc':3, 'cd':1, 'de':1, 'ef':3, 'fg':1, 'gh':2}

ldict = collections.defaultdict(list)
map(lambda (k, v): ldict[v].append(k), dictionary.iteritems())
list_of_lists = map(lambda x: ldict[x], xrange(0, max(ldict)+1))

print(list_of_lists)

这个解决方案使用了与hochl的解决方案相同的方法。它是功能性的：因此它更短 - 但通常需要更长的时间来理解它。:-)

评论：在我看来，它之所以“长”，是因为对于这种用途，dict / defaultdict构造函数太过有限。

- Andreas Florath