Блог

Главная - Вопросы по программированию - Как повысить производительность с помощью этого словаря наборов, созданного с помощью Numpy?

Как повысить производительность с помощью этого словаря наборов, созданного с помощью Numpy?

#python #numpy #dictionary #set #hashtable

#python #numpy #словарь #набор #хеш-таблица

Вопрос:

Допустим, у нас есть 10 миллионов носков, и каждый из них имеет цвет sockcolor[i] и хранится в drawer[i] . Я хотел бы подсчитать, сколько разных цветов есть в каждом из 20 ящиков.

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

Следующий код работает, но он довольно медленный (~ 10 секунд для 10 миллионов носков).

Как мы могли бы использовать методы Numpy (векторизация?) или избежать for цикла, чтобы ускорить это вычисление?

 import numpy as np
N = 10*1000*1000
drawer = np.random.randint(0, 20, N)            # 20 drawers
sockcolor = np.random.randint(0, 100*1000, N)   # 100k different colors
d = {}

for i, k in enumerate(drawer):
    if k not in d:  # can be simplified with collections.defaultdict but no gain here
        d[k] = set()
    d[k].add(sockcolor[i])

for k, s in d.items():
    print(k, len(s))

Вывод:

 16 99323
7 99330
0 99339
17 99364
14 99272
12 99303
11 99334
6 99362
19 99287
10 99282
4 99280
18 99325
3 99316
15 99303
5 99280
13 99357
2 99328
9 99290
1 99293
8 99293

Комментарии:

1. numpy не предназначен для наборов и словарей. Разве вы не можете организовать свои данные в виде простого вектора?

2. @zvone здесь наборы используются как инструмент для дедупликации

3. Но почему numpy используется? Здесь нет никакой реальной выгоды от этого.

4. @zvone потому что в моем реальном варианте использования мои данные поступают из массивов numpy, поэтому я бы не хотел преобразовывать их в обычный список python, потому что это ничего не добавит.

Ответ №1:

По сути, у вас уже есть отображение из ящиков в цвета носков, но они рандомизированы, и вы хотите упорядочить их по номеру ящика.

Проще всего сначала отсортировать их по номерам ящиков:

 drawer_sort = np.argsort(drawer)
drawer = drawer[drawer_sort]
sockcolor = sockcolor[drawer_sort]

Теперь, когда они отсортированы, нет необходимости искать дубликаты номеров ящиков, вам просто нужно найти индексы, по которым меняются номера ящиков, чтобы сформировать диапазоны, которые являются следующими:

 changes, = np.where(drawer[1:]-drawer[:-1])
starts = np.concatenate([[0], changes 1])
ends = np.concatenate([changes, [len(drawer)]])

Теперь вы можете создать свой словарь:

 result = {drawer[start]: sockcolor[start:end] for start, end in zip(starts, ends)}

Таким образом, единственная итерация, выполняемая в Python, — это последняя строка, которая будет действительно быстрой, если имеется небольшое количество различных drawer значений (в вашем случае не более 20).

Результат все еще может иметь повторяющиеся sockcolor значения, но это легко решается в numpy:

 result = {drawer: np.unique(sockcolors) for drawer, sockcolors in result.items()}

Ответ №2:

Ваша медлительность возникает из-за того, что вы не используете встроенные функции ваших последовательностей. Выполняйте итерацию по отдельным socks только один раз. Вместо этого назначьте цвета носков (а не индексы отдельных носков) ящикам. Затем создайте набор из содержимого каждого ящика: одна оптовая операция, а не инкрементная set.add , что относительно медленно для ваших целей.

Метки: ,