将语料库词典排序为 OrderedDict 的最快方法 - python
Fastest way to sorting a corpus dictionary into an OrderedDict - python
给定一个 corpus/texts 这样的：
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
...
想象一下，我在 Counter 对象中有 10 亿个键，遍历 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对象实现相同的排序键值对吗？
假设内存不是问题。给定 120 GB 的 RAM，保留 10 亿个键值对应该没有太大问题吧？假设 10 亿个键的每个键平均有 20 个字符，每个值有一个整数。
提高速度的一个步骤是以最佳方式填充计数器。
例如，使用您的 txt（802 个字符）。
mycounter=Counter(txt.split())
产生与您的 word_counter 相同的结果，但只用了 1/3 的时间。
或者如果您必须从文件中逐行读取文本，则使用：
word_freq=Counter()
for line in txt.splitlines():
word_freq.update(line.split())
类似地，可以在没有循环的情况下创建有序字典：
mydict = OrderedDict(sorted(mycounter.items(), key=operator.itemgetter(1), reverse=True))
这里我调用 sorted 的方式与 most_common 相同（根据您的 link）。我正在将已排序项目的列表直接传递给 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。同样，这是来自您的 link。
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：
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() 中创建一个结构化数组，按第二个字段对其进行排序，然后创建字典。虽然没有节省时间。有关使用 order 对结构化数组进行排序的另一个最新示例，请参阅 。
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()
给定一个 corpus/texts 这样的：
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
...
想象一下，我在 Counter 对象中有 10 亿个键，遍历 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对象实现相同的排序键值对吗？
假设内存不是问题。给定 120 GB 的 RAM，保留 10 亿个键值对应该没有太大问题吧？假设 10 亿个键的每个键平均有 20 个字符，每个值有一个整数。
提高速度的一个步骤是以最佳方式填充计数器。
例如，使用您的 txt（802 个字符）。
mycounter=Counter(txt.split())
产生与您的 word_counter 相同的结果，但只用了 1/3 的时间。
或者如果您必须从文件中逐行读取文本，则使用：
word_freq=Counter()
for line in txt.splitlines():
word_freq.update(line.split())
类似地，可以在没有循环的情况下创建有序字典：
mydict = OrderedDict(sorted(mycounter.items(), key=operator.itemgetter(1), reverse=True))
这里我调用 sorted 的方式与 most_common 相同（根据您的 link）。我正在将已排序项目的列表直接传递给 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。同样，这是来自您的 link。
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：
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() 中创建一个结构化数组，按第二个字段对其进行排序，然后创建字典。虽然没有节省时间。有关使用 order 对结构化数组进行排序的另一个最新示例，请参阅
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()