Как эффективно создавать итерации с помощью большого списка списков в python?

У меня есть мои данные как таковые:

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

Конечная цель заключается в создании scipy разреженной матрицы, например:

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]))

но цикл через большой список списков довольно неэффективен.

Итак, , как я могу эффективно просматривать большой список списков?

Есть ли другой способ создать scipy-матрицу из data без циклирования всех функций и меток?

Ответы

Ответ 1

Преобразование словаря словарей в массив 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')

Ответ 2

Набор данных довольно велик, поэтому я не считаю целесообразным создание временного массива numpy (при использовании 32-битных целых чисел матрица 1e5 x 5e6 потребует ~ 2 терабайта памяти).

Я предполагаю, что вы знаете верхнюю границу для количества меток.

Код может выглядеть так:

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 возвращает индекс столбца метки. Если окажется, что использовать словарь для хранения индекса в 5 миллионов ярлыков, который должен делать база данных жесткого диска, нецелесообразно. Словарь можно создавать онлайн, поэтому предыдущее знание всех ярлыков не требуется.

Итерация через 100 000 функций займет разумное время, поэтому я думаю, что это решение может работать, если набор данных достаточно редок. Удачи!

Ответ 3

s там другой способ создания scipy матрицы из данных без цикла через все функции и метки?

Я не думаю, что есть сокращение, которое уменьшает общее количество поисков. Вы начинаете со словаря Counters (подкласса dict), поэтому оба уровня вложенности являются неупорядоченными коллекциями. Единственный способ вернуть их в требуемом порядке - это выполнить поиск 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() вместо понимания списка (сопоставление может использовать внутреннюю длину 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]