python - 在列表中查找元素索引的最快方法

Question

我有一组样本(比如 X)，其中包含一些特征(比如 Y)，我需要在这些样本上运行一些机器学习算法(比如 PCA)。一种方法是生成矩阵(样本、特征)。我构建矩阵的方法包括 2 个步骤:

1. 获取整个数据集的所有特征值。我们称它为游泳池吧。
2. 对于样本，对于样本中的每个值，找到该值在池中的索引。索引的值存在为 1，不存在为 0。

例如:考虑下面的例子

sample1 = A, B, D
sample2 = A, C, E
sample3 = A, C, D

1. 生成的池 = A、B、C、D、E

2. 生成矩阵

   • 样本 1 => 1, 1, 0, 1, 0
   • 样本 2 => 1, 0, 1, 0, 1
   • 样本 3 => 1, 0, 0, 1, 0

生成这个矩阵的挑战在于，数据非常庞大。行数为 465337，列数为 35526155。

生成池大约需要 20 分钟，尽管速度很慢，但我可以接受。但是在生成矩阵的向量(即行)时，我必须为正在考虑的样本的所有值获取池中该值的索引。

这需要很长时间。有没有更好的方法来查找元素的索引？如果程序本身不是最优的，请让我知道生成矩阵的更好方法。

此外，我只是存储索引并从中构建 CSR 矩阵而不是密集矩阵。

Answer 1

正如我在评论中提到的，您想使用 sklearn.feature_extraction.text.CountVectorizer为此，使用 binary=True 参数，因为您实际上不需要计数。你这会创建你的编码并输出一个稀疏矩阵来启动!

但是，如果您对您的方法的潜在问题感兴趣，从根本上说，问题是您使用的是序列类型，列表，其中.index 方法是线性时间 操作。当您尝试使用您的列表时，您会感受到这个事实的痛苦。这是一个草图，说明如何仅使用字典更有效地执行此操作:

In [15]: tokens = list('qwertydfgndjfkgnf')

In [16]: pool = {}

In [17]: for t in tokens:
    ...:     pool.setdefault(t, len(pool))
    ...:

In [18]: pool
Out[18]:
{'d': 6,
 'e': 2,
 'f': 7,
 'g': 8,
 'j': 10,
 'k': 11,
 'n': 9,
 'q': 0,
 'r': 3,
 't': 4,
 'w': 1,
 'y': 5}

In [19]: tokens.index('g') # ew, O(n) time complexity
Out[19]: 8

In [20]: pool['g'] # nice! O(1) time complexity
Out[20]: 8

这个池现在包含从 token 到索引的编码。访问索引在这里是恒定时间操作。这将显着提高性能。事实上，由于我们只是开始制作一个 dict，而不是从一个 set 转换为一个 list，这将减少你的常数因子增加了很多。

请注意，以上内容本质上是 sklearn 对象正在执行的操作。

https://github.com/scikit-learn/scikit-learn/blob/ab93d65/sklearn/feature_extraction/text.py#L745

但是请注意，他们使用了一个 defaultdict，它针对这类事情进行了优化，并采用了以下令人愉快的小方法:

In [24]: from collections import defaultdict

In [25]: pool = defaultdict()

In [26]: pool.default_factory = pool.__len__

In [27]: for t in tokens:
    ...:     pool[t]
    ...:

In [28]: pool
Out[28]:
defaultdict(<method-wrapper '__len__' of collections.defaultdict object at 0x1088aa9f8>,
            {'d': 6,
             'e': 2,
             'f': 7,
             'g': 8,
             'j': 10,
             'k': 11,
             'n': 9,
             'q': 0,
             'r': 3,
             't': 4,
             'w': 1,
             'y': 5})

它们还构建了稀疏表示，因为它们遍历文档，因此它们实际上只对数据集进行一次遍历。所以 sklearn 对象与你将要得到的一样优化。 sklearn 源代码实际上非常平易近人，值得一试的是，它们仅使用纯 python 完成了哪些工作，没有 Cython 扩展或其他任何东西。