улучшение производительности

Question

У меня есть матрица с 383 миллионами строк, мне нужно отфильтровать эту матрицу на основе списка значений (index_to_remove). Эта функция выполняется несколько раз за одну итерацию. Есть ли более быстрая альтернатива:

def remove_from_result(matrix, index_to_remove, inv=True):
    return matrix[np.isin(matrix, index_to_remove, invert=inv)]

Answer 1

Более быстрое внедрение

Это скомпилированная версия, использующая набор в качестве решения для понимания списка @Matt Messersmith. Это в основном замена более медленного метода np.isin. У меня были некоторые проблемы со случаем, когда index_to_remove является скалярным значением, и я реализовал отдельную версию для этого случая.

Код

import numpy as np
import numba as nb

@nb.njit(parallel=True)
def in1d_vec_nb(matrix, index_to_remove):
  #matrix and index_to_remove have to be numpy arrays
  #if index_to_remove is a list with different dtypes this 
  #function will fail

  out=np.empty(matrix.shape[0],dtype=nb.boolean)
  index_to_remove_set=set(index_to_remove)

  for i in nb.prange(matrix.shape[0]):
    if matrix[i] in index_to_remove_set:
      out[i]=False
    else:
      out[i]=True

  return out

@nb.njit(parallel=True)
def in1d_scal_nb(matrix, index_to_remove):
  #matrix and index_to_remove have to be numpy arrays
  #if index_to_remove is a list with different dtypes this 
  #function will fail

  out=np.empty(matrix.shape[0],dtype=nb.boolean)
  for i in nb.prange(matrix.shape[0]):
    if (matrix[i] == index_to_remove):
      out[i]=False
    else:
      out[i]=True

  return out


def isin_nb(matrix_in, index_to_remove):
  #both matrix_in and index_to_remove have to be a np.ndarray
  #even if index_to_remove is actually a single number
  shape=matrix_in.shape
  if index_to_remove.shape==():
    res=in1d_scal_nb(matrix_in.reshape(-1),index_to_remove.take(0))
  else:
    res=in1d_vec_nb(matrix_in.reshape(-1),index_to_remove)

  return res.reshape(shape)

Пример

data = np.array([[80,1,12],[160,2,12],[240,3,12],[80,4,11]])
test_elts= np.array((80))

data[isin_nb(data[:,0],test_elts),:]

Tmings

test_elts = np.arange(12345)
data=np.arange(1000*1000)

#The first call has compilation overhead of about 300ms
#which is not included in the timings
#remove_from_result:     52ms
#isin_nb:                1.59ms

Answer 2

Время выполнения вашей функции фильтрации выглядит как линейное w.r.t. размер вашего ввода matrix. Обратите внимание, что фильтрация со списком со списком с set определенно линейна, и ваша функция работает примерно в два раза быстрее, чем фильтр со списком со тем же входным сигналом на моем компьютере. Вы также можете видеть, что если вы увеличиваете размер в X раз, время выполнения также увеличивается в X раз:

In [84]: test_elts = np.arange(12345)

In [85]: test_elts_set = set(test_elts)

In [86]: %timeit remove_from_result(np.arange(1000*1000), test_elts)
10 loops, best of 3: 81.5 ms per loop

In [87]: %timeit [x for x in np.arange(1000*1000) if x not in test_elts_set]
1 loop, best of 3: 201 ms per loop

In [88]: %timeit remove_from_result(np.arange(1000*1000*2), test_elts)
10 loops, best of 3: 191 ms per loop

In [89]: %timeit [x for x in np.arange(1000*1000*2) if x not in test_elts_set]
1 loop, best of 3: 430 ms per loop

In [90]: %timeit remove_from_result(np.arange(1000*1000*10), test_elts)
1 loop, best of 3: 916 ms per loop

In [91]: %timeit [x for x in np.arange(1000*1000*10) if x not in test_elts_set]
1 loop, best of 3: 2.04 s per loop

In [92]: %timeit remove_from_result(np.arange(1000*1000*100), test_elts)
1 loop, best of 3: 12.4 s per loop

In [93]: %timeit [x for x in np.arange(1000*1000*100) if x not in test_elts_set]
1 loop, best of 3: 26.4 s per loop

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

1. Если у вас есть доступ к чему-то вроде pyspark (который вы можете получить, используя EMR на AWS, если вы готовы заплатить несколько долларов), вы могли бы сделать это намного быстрее. Проблема довольно смущающая, параллельная. Вы можете разделить входные данные на K кусков, дать каждому работнику элементы, которые должны быть смешаны, и кусочек, настроить фильтр каждого работника, а затем собрать / объединить в конце. Или вы можете даже попробовать использовать multiprocessing, но вам нужно быть осторожным с памятью (multiprocessing похож на C fork(), он порождает подпроцессы, но каждый из них клонирует ваше текущее пространство памяти ).

2. Если ваши данные имеют некоторую структуру (как будто они отсортированы), вы можете быть умнее в этом и получить сублинейную алгоритмическую сложность. Например, если вам нужно удалить относительно небольшое количество элементов из большого отсортированного массива, вы можете просто выполнить поиск бина по каждому элементу для удаления. Это будет выполняться за время O (m log n), где m - количество удаляемых элементов, а n - размер вашего большого массива. Если m относительно мало (по сравнению с n), вы находитесь в бизнесе, так как тогда вы будете близки к O (log n). Есть еще более умные способы справиться с этой конкретной ситуацией, но я выбрал этот, так как это довольно легко объяснить. Если вы знаете что-нибудь о распределении ваших данных, вы могли бы быть в состоянии лучше, чем линейное время.

НТН.