Преобразование массива NumPy в набор занимает слишком много времени

Ответ 1

TL; DR: Функция set() создает набор, используя протокол итерации Pythons. Но повторение (на уровне Python) над массивами NumPy настолько медленное, что с помощью tolist() для преобразования массива в список Python перед тем, как выполнить итерацию (намного) быстрее.

Чтобы понять, почему итерация массивов NumPy настолько медленная, важно знать, как объекты Python, списки Python и массивы NumPy хранятся в памяти.

Объекту Python нужны некоторые свойства бухгалтерии (например, счетчик ссылок, ссылка на его класс,...) и значение, которое оно представляет. Например, целое число ten = 10 может выглядеть так:

Синий круг - это "имя", которое вы используете в интерпретаторе Python для переменной ten, а нижний объект (экземпляр) - это то, что на самом деле представляет собой целое число (поскольку свойства бухгалтерского учета здесь не очень важны, я проигнорировал их в изображения).

A Python list - это просто набор объектов Python, например mylist = [1, 2, 3] будет сохранен следующим образом:

В этот раз список ссылается на целые числа Python 1, 2 и 3, а имя mylist просто ссылается на экземпляр list.

Но массив myarray = np.array([1, 2, 3]) не сохраняет объекты Python как элементы:

Значения 1, 2 и 3 хранятся непосредственно в экземпляре NumPy array.

С помощью этой информации я могу объяснить, почему итерация по array намного медленнее по сравнению с итерацией по list:

Каждый раз, когда вы получаете доступ к следующему элементу в list, list просто возвращает сохраненный объект. Это очень быстро, потому что элемент уже существует как объект Python (ему просто нужно увеличить счетчик ссылок на единицу).

С другой стороны, когда вам нужен элемент array, ему необходимо создать новый "ящик" Python для значения со всеми материалами бухгалтерского учета до его возврата. Когда вы перебираете массив, ему нужно создать один блок Python для каждого элемента в вашем массиве:

Создание этих блоков происходит медленно, и основная причина, по которой повторение массивов NumPy происходит намного медленнее, чем повторение наборов Python (списки/кортежи/наборы/словари), которые хранят значения и их поле:

import numpy as np
arr = np.arange(100000)
lst = list(range(100000))

def iterateover(obj):
    for item in obj:
        pass

%timeit iterateover(arr)
# 20.2 ms ± 155 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit iterateover(lst)
# 3.96 ms ± 26.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Конструктор set "просто выполняет итерацию над объектом.

Одна вещь, на которую я не могу ответить, - это почему метод tolist намного быстрее. В конце каждое значение в результирующем списке Python должно находиться в "Python box", поэтому не так много работы, которую может tolist избежать. Но я точно знаю, что list(array) медленнее, чем array.tolist():

arr = np.arange(100000)

%timeit list(arr)
# 20 ms ± 114 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit arr.tolist()
# 10.3 ms ± 253 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Каждая из них имеет O(n) сложность выполнения, но константные факторы очень разные.

В вашем случае вы сравнили set() с tolist() - это не очень хорошее сравнение. Было бы разумнее сравнить set(arr) с list(arr) или set(arr.tolist()) с arr.tolist():

arr = np.random.randint(0, 1000, (10000, 3))

def tosets(arr):
    for line in arr:
        set(line)

def tolists(arr):
    for line in arr:
        list(line)

def tolists_method(arr):
    for line in arr:
        line.tolist()

def tosets_intermediatelist(arr):
    for line in arr:
        set(line.tolist())

%timeit tosets(arr)
# 72.2 ms ± 2.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit tolists(arr)
# 80.5 ms ± 2.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit tolists_method(arr)
# 16.3 ms ± 140 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%timeit tosets_intermediatelist(arr)
# 38.5 ms ± 200 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Итак, если вы хотите set, вам лучше использовать set(arr.tolist()). Для больших массивов может иметь смысл использовать np.unique, но поскольку ваши строки содержат только 3 элемента, которые, вероятно, будут медленнее (для тысяч элементов это может быть намного быстрее!).

В комментариях, которые вы задали о numba и да, это правда, что numba может ускорить это. Numba поддерживает типизированные наборы (только числовые типы), но это не значит, что он будет всегда быстрее.

Я не уверен, как numba (re) реализует set, но поскольку они напечатаны, вероятно, они также избегают "ящиков Python" и сохраняют значения непосредственно внутри set:

Наборы сложнее, чем list, поскольку они включают в себя hash es и пустые слоты (Python использует открытую адресацию для наборов, поэтому я предполагаю, что numba тоже).

Как и NumPy array, numba set сохраняет значения напрямую. Поэтому, когда вы конвертируете NumPy array в numba set (или наоборот), ему не нужно будет использовать "Python boxes" вообще, поэтому, когда вы создаете set в numba nopython, это будет намного быстрее, чем операция set(arr.tolist()):

import numba as nb
@nb.njit
def tosets_numba(arr):
    for lineno in range(arr.shape[0]):
        set(arr[lineno])

tosets_numba(arr)  # warmup
%timeit tosets_numba(arr)
# 6.55 ms ± 105 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Это примерно в пять раз быстрее, чем подход set(arr.tolist()). Но важно подчеркнуть, что я не возвращал set из функции. Когда вы возвращаете a set из функции numba nopython в Python Numba создает набор python, включая "создание ящиков" для всех значений в наборе (что-то скрывает numba).

Просто FYI: тот же самый бокс/распаковка происходит, если вы передаете list функции Numba nopython или возвращаете списки из этих функций. Итак, какая операция O(1) в Python - это операция O(n) с Numba! Вот почему обычно лучше передавать массивы NumPy функции numba nopython (которая есть O(1)).

Я предполагаю, что если вы вернете эти наборы из функции (на самом деле это невозможно сейчас, потому что numba не поддерживает списки наборов в настоящее время), она будет медленнее (потому что она создает набор numba и позже преобразует его в набор python) или только немного быстрее (если преобразование numbaset → pythonset действительно, очень быстро).

Лично я бы использовал numba для наборов только в том случае, если мне не нужно возвращать их из функции и выполнять все операции над множеством внутри функции и, только если все операции над множеством поддерживается в режиме nopython. В любом другом случае я бы не использовал numba здесь.

Просто обратите внимание: from numpy import * следует избегать, вы скрываете несколько встроенных функций python, когда вы это делаете (sum, min, max,...), и это ставит много вещей в ваши глобальные. Лучше использовать import numpy as np. np. перед вызовами функций делает код более понятным и не так много печатает.

Ответ 2

Вот способ ускорить работу: избегать цикла и использовать многопроцессорную пул pool.map

from multiprocessing.dummy import Pool as ThreadPool
import multiprocessing

pool = ThreadPool(multiprocessing.cpu_count()) # get the number of CPU
y = pool.map(set,x) # apply the function to your iterable
pool.close()
pool.join()