时间戳

首页 > 解决方案 > 将字典转换为（密集）矩阵的快速方法

python - 将字典转换为（密集）矩阵的快速方法

问题描述

我有一个字典列表，值总是整数，键是一些字符串。我们可以将其解释为一个矩阵，其中每个字典是一行，每一列对应一个键，该键属于至少一个字典。字典表示多项式，其中键是单项式，值是系数。

比如[{'x':1, 'y':1, 'z':2}, {'x': 2}, {'y':1, 'z':3}]对应矩阵：

[ 1 1 2,
  2 0 0,
  0 1 3 ]

我经常做这个操作，我需要一个高性能的解决方案。矩阵不是很大，所以我需要一个最小化开销的解决方案。目前，一些计算将大约三分之一的时间花在字典的向量化上。

这基本对应sklearn.feature_extraction.DictVectorizer。我在 sagemath 工作，它不附带 sci-kit learn，所以使用它并不理想。进一步DictVectorizer构建稀疏矩阵，然后将其转换为密集矩阵。我自己尝试过这种方法，但由于额外的开销很大，结果会变慢。

我目前的算法如下：

def dictionary_vectorizer(list_of_dicts):
    # Make a list of all the keys occurring in the dictionaries
    keys = set()
    for dic in list_of_dicts:
        for key in dic.keys():
            keys.add(key)

    # Create a mapping keys -> column_index
    key_map = {key: index for index, key in enumerate(keys)}

    output = np.zeros((len(list_of_dicts), len(keys)))
    for row_number, dic in enumerate(list_of_dicts):
        for key, value in dic.items():
            output[row_number, key_map[key]] = value

    return output

在我的实际代码中，我使用 sagemath 的matrix构造函数而不是 np.zeros，但它并没有太大变化。似乎初始化一个零矩阵，然后编辑行并不是最快的方法。逐行计算矩阵，然后将结果连接起来给出相同的速度。

有没有一种明显的方法可以加快速度（同时保持低开销）？

标签： pythonnumpysage

解决方案

如果，根据问题的这一部分：

这基本对应sklearn.feature_extraction.DictVectorizer。我在 sagemath 工作，它不附带 sci-kit learn，所以使用它并不理想。

希望将 scikit-learn 安装到 SageMath 中，然后根据 Sage 的安装方式，在终端中运行可能就足够了：

$ sage --pip install scikit-learn

然后可以在 Sage 中执行以下操作：

sage: data = [{'x':1, 'y':1, 'z':2}, {'x':2}, {'y':1, 'z':3}]
sage: data
[{'x': 1, 'y': 1, 'z': 2}, {'x': 2}, {'y': 1, 'z': 3}]

sage: from sklearn.feature_extraction import DictVectorizer
sage: v = DictVectorizer(dtype=int, sparse=False)
sage: X = v.fit_transform(data)
sage: print(X)
[[1 1 2]
 [2 0 0]
 [0 1 3]]

如果目标只是加快问题中的代码，跳过键到列索引映射的创建可能会使事情变得稍微快一些，虽然不是很大。

def dictionary_vectorizer(list_of_dicts):
    # List all keys occurring in the dictionaries
    keys = set(key for dic in list_of_dicts for key in dic)
    # Initialize zero array of correct shape
    output = np.zeros((len(list_of_dicts), len(keys)))
    # Set nonzero entries
    for row_number, dic in enumerate(list_of_dicts):
        for col_number, key in enumerate(keys):
            if key in dic:
                output[row_number, col_number] = dic[key]
    return output

如果该函数应用于共享相同单项式的大量数据，则分离出对键的检测可能是有意义的。

可以考虑重新使用相同的数组，将其作为参数传递，以节省创建新 numpy 数组的成本。不确定这会有多大帮助。

如果使用字典列表受到限制，人们可能还会考虑更改数据生成步骤。

Cython 或 Pythran 可能有助于进一步加快这一进程。

推荐阅读