如何高效地遍历Python中大型列表的列表？

Question

我有这样的数据：

data = {'x':Counter({'a':1,'b':45}), 'y':Counter({'b':1, 'c':212})}

在这里，我的标签是data的键，而内部字典的键是特征：

all_features = ['a','b','c']
all_labels = ['x','y']

我需要创建一个这样的列表的列表：

[[data[label][feat] for feat in all_features] for label in all_labels]

[输出]：

[[1, 45, 0], [0, 1, 212]]

我的len(all_features)大约是5,000,000，而len(all_labels)大约是100,000。

最终的目的是创建一个稀疏矩阵，比如说：

from collections import Counter
from scipy.sparse import csc_matrix
import numpy as np


all_features = ['a','b','c']
all_labels = ['x','y']

csc_matrix(np.array([[data[label][feat] for feat in all_features] for label in all_labels]))

但是，遍历一个很大的列表的列表效率不高。

所以我该如何高效地处理这个大的列表的列表呢？

有没有其他方法可以从data创建稀疏矩阵，而不需要遍历所有的特征和标签？

Answer 1

有没有其他方法可以从数据中创建scipy矩阵，而不需要遍历所有的特征和标签呢？

我觉得没有什么捷径可以减少查找的总次数。你一开始是用一个字典（字典的一个子类）来存储计数器，所以这两层嵌套都是无序的集合。要把它们按要求的顺序放回去，唯一的方法就是对每个数据点进行一次 data[label][feat] 的查找。

不过，你可以通过确保每个标签的 data[label] 查找只进行一次，来大约把时间缩短一半：

>>> counters = [data[label] for label in all_labels]
>>> [[counter[feat] for feat in all_features] for counter in counters]
[[1, 45, 0], [0, 1, 212]]

你还可以尝试用 map() 来加快运行速度，而不是用列表推导式（使用map可以利用内部的length_hint来预先设置结果数组的大小）：

>>> [map(counter.__getitem__, all_features) for counter in counters]
[[1, 45, 0], [0, 1, 212]]

最后，确保把代码放在一个函数里运行（在CPython中，局部变量的查找速度比全局变量快）：

def f(data, all_features, all_labels):
    counters = [data[label] for label in all_labels]
    return [map(counter.__getitem__, all_features) for counter in counters]

Answer 2

这个数据集非常大，所以我觉得构建一个临时的numpy数组不太实际（如果使用32位整数，一个10万行乘以500万列的矩阵大约需要2TB的内存）。

我假设你知道标签的上限数量。

代码可能看起来像这样：

import scipy.sparse
n_rows = len(data.keys())
max_col = int(5e6)
temp_sparse = scipy.sparse.lil_matrix((n_rows, max_col), dtype='int')

for i, (features, counts) in enumerate(data.iteritems()):
    for label, n in counts.iteritem():
        j = label_pos[label]
        temp_sparse[i, j] = n
csc_matrix = temp_sparse.csc_matrix(temp_matrix)

其中label_pos会返回标签的列索引。如果发现用字典来存储500万个标签的索引不太实际，那么可以考虑使用硬盘数据库。这个字典可以在线创建，所以不需要事先知道所有的标签。

遍历10万个特征需要花费合理的时间，所以我认为如果数据集足够稀疏，这个解决方案是可行的。祝你好运！

Answer 3

把一个字典里面的字典转换成numpy或者scipy数组，确实不太好玩。如果你事先知道了all_features和all_labels，那么从一开始就用scipy的稀疏COO矩阵来保存你的计数可能会更好。

无论是否可行，你都需要把特征和标签的列表保持有序，这样查找会更快。所以我假设接下来的操作不会改变这两个数组：

all_features = np.array(all_features)
all_labels = np.array(all_labels)
all_features.sort()
all_labels.sort()

现在我们来提取data中的标签，按照字典中存储的顺序，看看每个标签在all_labels中对应的位置：

labels = np.fromiter(data.iterkeys(), all_labels.dtype, len(data))
label_idx = np.searchsorted(all_labels, labels)

接下来，我们来统计每个标签有多少个特征，并由此计算出你的稀疏数组中会有多少个非零项：

label_features = np.fromiter((len(c) for c in data.iteritems()), np.intp,
                             len(data))
indptr = np.concatenate(([0], np.cumsum(label_features)))
nnz = indptr[-1]

现在，我们提取每个标签的特征和它们对应的计数：

import itertools
features_it = itertools.chain(*(c.iterkeys() for c in data.itervalues()))
features = np.fromiter(features_it, all_features.dtype, nnz)
feature_idx = np.searchsorted(all_features, features)
counts_it = itertools.chain(*(c.itervalues() for c in data.itervalues()))
counts = np.fromiter(counts_it, np.intp, nnz)

根据我们得到的信息，我们可以直接创建一个CSR矩阵，标签作为行，特征作为列：

sps_data = csr_matrix((counts, feature_idx, indptr),
                      shape=(len(all_labels), len(all_features)))

唯一的问题是，这个稀疏数组的行并不是按照all_labels的顺序排列的，而是按照我们遍历data时的顺序。不过我们有feature_idx来告诉我们每个标签的位置，我们可以通过以下方式重新排列这些行：

sps_data = sps_data[np.argsort(label_idx)]

是的，这个过程有点麻烦，令人困惑，而且可能速度不快，但它能工作，并且在内存使用上会比你在问题中提到的方案更高效：

>>> sps_data.A
array([[  1,  45,   0],
       [  0,   1, 212]], dtype=int64)
>>> all_labels
array(['x', 'y'], 
      dtype='<S1')
>>> all_features
array(['a', 'b', 'c'], 
      dtype='<S1')