将语料库字典排序为有序字典的最快方法 - Python。

Question

给定这样的语料库/文本：

Resumption of the session
I declare resumed the session of the European Parliament adjourned on Friday 17 December 1999 , and I would like once again to wish you a happy new year in the hope that you enjoyed a pleasant festive period .
Although , as you will have seen , the dreaded ' millennium bug ' failed to materialise , still the people in a number of countries suffered a series of natural disasters that truly were dreadful .
You have requested a debate on this subject in the course of the next few days , during this part @-@ session .
In the meantime , I should like to observe a minute ' s silence , as a number of Members have requested , on behalf of all the victims concerned , particularly those of the terrible storms , in the various countries of the European Union .

我可以这样做来获得一个单词频率字典：

>>> word_freq = Counter()
>>> for line in text.split('\n'):
...     for word in line.split():
...             word_freq[word]+=1
... 

但如果目的是从最高到最低频率实现有序字典，我需要这样做：

>>> from collections import OrderedDict
>>> sorted_word_freq = OrderedDict()
>>> for word, freq in word_freq.most_common():
...     sorted_word_freq[word] = freq
... 

假设我有10亿个键在Counter对象中，通过迭代most_common()将会具有遍历语料库（非唯一实例）一次和词汇表（唯一键）的复杂度。

注意：Counter.most_common()将调用一个临时的sorted()，请参见https://hg.python.org/cpython/file/e38470b49d3c/Lib/collections.py#l472

鉴于此，我看到了以下使用numpy.argsort()的代码：

>>> import numpy as np
>>> words = word_freq.keys()
>>> freqs = word_freq.values()
>>> sorted_word_index = np.argsort(freqs) # lowest to highest
>>> sorted_word_freq_with_numpy = OrderedDict()
>>> for idx in reversed(sorted_word_index):
...     sorted_word_freq_with_numpy[words[idx]] = freqs[idx]
... 

哪个更快？

有没有其他更快的方法从Counter中获取这样的OrderedDict？

除了OrderedDict，还有其他Python对象可以实现相同的按键排序的键值对吗？

假设内存不是问题。给定120GB的RAM，保留10亿个键值对应该不会有太大问题，假设平均每个键有20个字符，而每个值只有一个整数。

- alvas

---

内存和速度可能也是问题。我想在这两个方面都采用某种归并排序会是最好的选择。在https://dev59.com/G0jSa4cB1Zd3GeqPGpdZ中有一些关于最佳排序方法的讨论。 - user4322779

假设内存不是问题。 - alvas

可能一万亿个键值对也不会占用太多的内存，对吧？ - alvas

好的，如果它们每个都是1字节（这很不可能），那么它只有1 TB... - Thomas

在Apache Spark集群上执行此操作将非常快，因为它可以并行化。 由于其键定向，必须将键与值交换以按值排序。有关此内容的讨论，请参见https://dev59.com/jWAf5IYBdhLWcg3wbSQh。请参阅编程指南中的https://spark.apache.org/docs/1.2.0/programming-guide.html#working-with-key-value-pairs。这里是Spark赢得Daytona Grey基准测试的公告：https://spark.apache.org/news/spark-wins-daytona-gray-sort-100tb-benchmark.html。 - user4322779

Answer 1

Pandas中的Series对象是一组键值对数组（可以具有非唯一键），可能会引起兴趣。它有一个sort方法，可按值进行排序，并在Cython中实现。这里有一个对长度为一百万的数组进行排序的示例：

In [39]:
import pandas as pd
import numpy as np

arr = np.arange(1e6)
np.random.shuffle(arr)
s = pd.Series(arr, index=np.arange(1e6))
%timeit s.sort()
%timeit sorted(arr)

1 loops, best of 3: 85.8 ms per loop
1 loops, best of 3: 1.15 s per loop

如果你有一个普通的Python dict，你可以通过调用以下方法来构建一个Series：

my_series = pd.Series(my_dict)

然后按值排序

my_series.sort()

- JoeCondron

Answer 2

提高速度的一种方法是以最优方式填充计数器。

例如，使用您的txt（802个字符）。

mycounter=Counter(txt.split())

这将以三分之一的时间产生与您的 word_counter 相同的结果。

如果需要从文件逐行读取文本，则使用：

word_freq=Counter()
for line in txt.splitlines():
    word_freq.update(line.split())

同样地，有序字典可以不用循环创建：

mydict = OrderedDict(sorted(mycounter.items(), key=operator.itemgetter(1), reverse=True))

在这里我和most_common一样使用sorted进行调用（如您提供的链接）。 并直接将已排序的项目列表传递给OrderedDict构建器。

当我在ipython中查看mycounter时，我会按照排序顺序获取值：

In [160]: mycounter
Out[160]: Counter({'the': 13, ',': 10, 'of': 9, 'a': 7, '.': 4, 'in': 4, 'to': 3, 'have': 3, 'session': 3, ''': 3, 'on': 3, 'you': 3, 'I': 3, 'that': 2, 'requested': 2, 'like': 2, 'European': 2, 'this': 2, 'countries': 2, 'as': 2, 'number': 2, 's': 1, 'various': 1, 'wish': 1, 'will': 1, 'Parliament': 1, 'meantime': 1, 'Resumption': 1, 'natural': 1, 'days': 1, 'debate': 1, 'You': 1, 'Members': 1, 'next': 1, '@-@': 1, 'hope': 1, 'enjoyed': 1, 'December': 1, 'victims': 1, 'particularly': 1, 'millennium': 1, .... 'behalf': 1, 'were': 1, 'failed': 1})

这是因为它的__repr__方法调用了most_common。这也是来自你提供的链接。

items = ', '.join(map('%r: %r'.__mod__, self.most_common()))

经过进一步测试，我发现直接调用sorted并不能节省时间：

In [166]: timeit mycounter.most_common()
10000 loops, best of 3: 31.1 µs per loop

In [167]: timeit sorted(mycounter.items(),key=operator.itemgetter(1),reverse=True)
10000 loops, best of 3: 30.5 µs per loop

In [168]: timeit OrderedDict(mycounter.most_common())
1000 loops, best of 3: 225 µs per loop

在这种情况下，直接加载字典也无法节省时间。您的迭代同样有效：

In [174]: %%timeit 
   .....: sorteddict=OrderedDict()
   .....: for word,freq in word_freq.most_common():
    sorteddict[word]=freq
   .....: 
1000 loops, best of 3: 224 µs per loop

对于这个示例，使用np.argsort并没有帮助（从时间上考虑）。仅调用argsort比使用most_common更慢。

In [178]: timeit np.argsort(list(mycounter.values()))
10000 loops, best of 3: 34.2 µs per loop

大部分时间都花在将列表转换为数组上了，x=np.array(list(mycounter.values()))。使用np.argsort(x)会更快。这也适用于许多numpy的功能。当处理数组时，numpy是快速的。但是将列表转换为数组时会有许多开销。

我可以通过以下一行代码使用numpy创建有序字典：

OrderedDict(np.sort(np.array(list(mycounter.items()), dtype='a12,i'), order='f1')[::-1])

或者分为多个部分：

lla = np.array(list(mycounter.items()),dtype='a12,i')
lla.sort(order='f1')
OrderedDict(lla[::-1])

我从items()中制作了一个结构化数组，通过第二字段进行排序，然后制作字典。没有节省时间。请参见https://dev59.com/Vo3da4cB1Zd3GeqP4cew#31837513，以查看另一个最近使用order对结构化数组进行排序的示例。

- hpaulj