Определения
- Использование генераторов:
def filter_fromiter(arr, k):
return np.fromiter((x for x in arr if x < k), dtype=arr.dtype)
Использование булевой маскировки:
def filter_mask(arr, k):
return arr[arr < k]
Использование
np.where():
def filter_where(arr, k):
return arr[np.where(arr < k)]
Использование
np.nonzero() def filter_nonzero(arr, k):
return arr[np.nonzero(arr < k)]
Использование пользовательских реализаций на основе Cython:
- однопроходной
filter_cy() - двухпроходной
filter2_cy()
%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True
cimport numpy as cnp
cimport cython as ccy
import numpy as np
import cython as cy
cdef long NUM = 1048576
cdef long MAX_VAL = 1048576
cdef long K = 1048576 // 2
cdef int smaller_than_cy(long x, long k=K):
return x < k
cdef size_t _filter_cy(long[:] arr, long[:] result, size_t size, long k):
cdef size_t j = 0
for i in range(size):
if smaller_than_cy(arr[i]):
result[j] = arr[i]
j += 1
return j
cpdef filter_cy(arr, k):
result = np.empty_like(arr)
new_size = _filter_cy(arr, result, arr.size, k)
return result[:new_size].copy()
cdef size_t _filtered_size(long[:] arr, size_t size, long k):
cdef size_t j = 0
for i in range(size):
if smaller_than_cy(arr[i]):
j += 1
return j
cpdef filter2_cy(arr, k):
cdef size_t new_size = _filtered_size(arr, arr.size, k)
result = np.empty(new_size, dtype=arr.dtype)
new_size = _filter_cy(arr, result, arr.size, k)
return result
Использование пользовательской реализации на основе Numba
- однопроходной
filter_np_nb() - двухпроходной
filter2_np_nb()
import numba as nb
@nb.jit
def filter_func(x, k=K):
return x < k
@nb.jit
def filter_np_nb(arr):
result = np.empty_like(arr)
j = 0
for i in range(arr.size):
if filter_func(arr[i]):
result[j] = arr[i]
j += 1
return result[:j].copy()
@nb.jit
def filter2_np_nb(arr):
j = 0
for i in range(arr.size):
if filter_func(arr[i]):
j += 1
result = np.empty(j, dtype=arr.dtype)
j = 0
for i in range(arr.size):
if filter_func(arr[i]):
result[j] = arr[i]
j += 1
return result
Контрольные показатели времени
Генераторный метод filter_fromiter() намного медленнее других (примерно на 2 порядка и поэтому в диаграммах он опущен).
Синхронизация будет зависеть как от размера входного массива, так и от процента отфильтрованных элементов.
Как функция размера ввода
Первый график обращается к таймингу как функции от размера ввода (для ~ 50% отфильтрованных элементов):
В целом, подход, основанный на Numba, всегда самый быстрый, за ним следует подход Cython. Внутри них двухпроходные подходы являются самыми быстрыми для средних и больших входов. В NumPy подходы на основе np.where() и np.nonzero() в основном одинаковы (за исключением очень маленьких входов, для которых np.nonzero() кажется немного медленнее), и оба они быстрее, чем нарезка логической маски, за исключениемдля очень маленьких входов (ниже ~ 100 элементов), где булева маска нарезки быстрее. Более того, для очень маленьких входных данных решение на основе Cython медленнее, чем на основе NumPy.
Как функция заполнения
Второй график обращается к временным интервалам как функция элементов, проходящих черезфильтр (для фиксированного входного размера ~ 1 миллиона элементов):
Первое наблюдение состоит в том, что все методы являются самыми медленными при приближении к ~ 50%заполнение с меньшим или большим заполнением они быстрее и быстрее всего не заполняются (наибольший процент отфильтрованных значений, наименьший процент прохождения значений, как показано на оси х графика). Опять же, и версии Numba, и Cython обычно быстрее, чем аналоги на основе NumPy, причем Numba почти всегда работает быстрее всех, а Cython побеждает Numba в самой правой части графика. Заметное исключение из этого - когда заполнение близко к 100%, когда однопроходные версии Numba / Cython в основном копируются ок. дважды, и решение для нарезки логической маски в конечном итоге превосходит их. Подходы с двумя проходами имеют увеличение предельной скорости при увеличении объема заполнения. Внутри NumPy подходы на основе np.where() и np.nonzero() снова в основном совпадают. При сравнении решения на основе NumPy решения np.where() / np.nonzero() превосходят срезы булевой маски почти всегда, за исключением крайней правой части графика, где срезы булевых масок становятся самыми быстрыми.
(Полнаякод доступен здесь )
Замечания по памяти
Генераторный метод filter_fromiter() требует только минимального временного хранения независимо от размера ввода. По памяти это самый эффективный метод. Аналогичной эффективностью памяти являются двухпроходные методы Cython / Numba, поскольку размер вывода определяется во время первого прохода.
Что касается памяти, то однопроходные решения для Cython и Numba требуютвременный массив размера ввода. Следовательно, это наименее эффективные методы памяти.
Для решения среза булевой маски требуется временный массив размера ввода, но типа bool, который в NumPy равен 1 биту, так что это ~В 64 раза меньше размера по умолчанию массива NumPy в типичной 64-битной системе.
Решение, основанное на np.where(), имеет те же требования, что и булева маска на первом шаге (внутри np.where()), которая преобразуется в серию int с (обычно int64 на 64-носистема) на втором этапе (вывод np.where()). Этот второй шаг, следовательно, имеет переменные требования к памяти, в зависимости от количества фильтруемых элементов.
Замечания
- метод генератора также является наиболее гибким, когда речь идет оПри указании другого условия фильтрации
- решение Cython требует указания типов данных, чтобы оно было быстрым
- как для Numba, так и для Cython, условие фильтрации может быть указано как универсальная функция (и поэтомуне обязательно должны быть жестко закодированы), но это должно быть указано в их соответствующей среде, и следует позаботиться о том, чтобы убедиться, что это правильно скомпилировано для скорости, или если наблюдаются существенные замедления
- однопроходные решения DOтребуется дополнительный
.copy() прямо перед возвратом, чтобы не тратить впустую память - методы NumPy делают NOT , возвращающие представление ввода, но копию, в результате расширенного индексирования:
arr = np.arange(100)
k = 50
print('`arr[arr > k]` is a copy: ', arr[arr > k].base is None)
# `arr[arr > k]` is a copy: True
print('`arr[np.where(arr > k)]` is a copy: ', arr[np.where(arr > k)].base is None)
# `arr[np.where(arr > k)]` is a copy: True
print('`arr[:k]` is a copy: ', arr[:k].base is None)
# `arr[:k]` is a copy: False
(РЕДАКТИРОВАНИЕ: включены решения и исправления на основе np.nonzero())d утечки памяти в однопроходных версиях Cython / Numba, включая двухпроходные версии Cython / Numba - на основе комментариев @ShadowRanger, @PaulPanzer и @ max9111.)