Быстрый способ превратить словарь в (плотную) матрицу - PullRequest
Новая
       12

Быстрый способ превратить словарь в (плотную) матрицу

2 голосов
/ 03 июня 2019

У меня есть список словарей, значения которых всегда целые, а ключи - некоторые строки.Мы можем интерпретировать это как матрицу, где каждый словарь является строкой, а каждый столбец соответствует ключу, принадлежащему по крайней мере одному из словарей.Словари представляют полиномы, где ключи являются мономами, а значения - коэффициентами.

Например, [{'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 обучения, поэтому использование этого не идеально.Кроме того, 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's matrix конструктор вместо np.zeros, но он мало что меняет.Кажется, что инициализация матрицы нулей, а затем редактирование строк - не самый быстрый способ сделать это.Вычисление матрицы строка за строкой, а затем объединение результатов дает ту же скорость.

Есть ли очевидный способ ускорить этот процесс (при сохранении низких накладных расходов)?

1 Ответ

0 голосов
/ 04 июня 2019

Если, согласно этой части вопроса:

Это в основном соответствует sklearn.feature_extraction.DictVectorizer. Я работаю в Sagemath, который не поставляется с Sci-Kit обучения, поэтому с помощью это не идеально.

желательно установить 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 могут помочь ускорить это.

...