Я предположил следующие варианты решения:
- Оптимизировать однопоточный код.
- Разбить исполнение на потоки.
- Использовать JIT-компилятор.
- Использовать GPU.
- Использовать "более быстрые" языки программирования.
О том, что я не попробовал:
Т.к. в конкретной задаче мы создает список уникальных значений и проходы по нему занимают основное время, то использование GPU может сильно ускорить задачу. Надеюсь, специалисты по Tensorflow, numba и пр. смогут написать пример быстрее, чем я разберусь. О проблематике подобных вычислений на GPU
На C, Asm и пр. я не писал больше 10 лет и желания вспоминать - нет. ИМХО результат должен быть, как минимум, не сильно хуже варианта №3. Ну и т.к. речь в вопросе о Python, то этот вариант за рамками, я думаю.
Для тестирования я выделил из кода автора главное:
from timeit import default_timer as timer
import itertools as itr
import pandas as pd
import numpy as np
arr = list(itr.combinations(range(1,26),6))
similar = 4
def FilterSimilarRecords(df, similar):
r_set_list = list()
bool_list = list()
for r in df.values:
r_set = set(r)
f = True
for x in r_set_list:
if (len(x & r_set)) > similar:
f = False
break
if (f):
bool_list.append(True)
r_set_list.append(r_set)
else:
bool_list.append(False)
return ~np.array(bool_list)
time_start = timer()
df = pd.DataFrame(arr)
result = df[FilterSimilarRecords(df, similar)]
time_delta = timer() - time_start
print('Execution time:', time_delta)
print(result)
Результат: 72s [171468 rows x 6 columns]
1. Оптимизация однопоточного кода:
Исходя из тестов отдельных блоков задачи, наиболее быстрым однопоточным вариантом стал:
from timeit import default_timer as timer
import itertools as itr
import pandas as pd
arr = list(itr.combinations(range(1,26),6))
similar = 4
def FilterSimilarRecords(records, similar):
unique = []
nonunique = []
# unique = deque() # Аналогичный результат.
# nonunique = deque()
for r in records:
r = set(r)
for u in unique:
if (len(u & r)) > similar:
nonunique.append(r)
break
else:
unique.append(r)
return nonunique
time_start = timer()
filtered = pd.DataFrame(FilterSimilarRecords(arr, similar))
time_delta = timer() - time_start
print('Execution time:', time_delta)
print(filtered)
Результат: 65s [171468 rows x 6 columns]
2. Разбить исполнение на потоки:
Многопоточность - не помогает. Специфика задачи такова, что процессор остается не нагружен, а узким местом является доступ к памяти. Соответственно, мы наблюдаем снижение производительности из-за накладных расходов на организацию многопоточности.
Исходя из тестов отдельных блоков задачи, наиболее быстрым многопоточным вариантом стал:
from multiprocessing.dummy import Pool
from timeit import default_timer as timer
import itertools as itr
import pandas as pd
arr = list(itr.combinations(range(1,26),6))
class FilterSimilarRecords:
pool = Pool(16)
unique = []
nonunique = []
similar = 4
is_unique = True
def run(self, arr):
for a in arr:
self.is_unique = True
self.record = set(a)
self.pool.map(self.apply, self.unique)
if self.is_unique:
self.unique.append(self.record)
else:
self.nonunique.append(self.record)
return self.nonunique
def apply(self, u):
if (len(u & self.record)) > self.similar:
self.is_unique = False
raise StopIteration
time_start = timer()
result = FilterSimilarRecords().run(arr)
filtered = pd.DataFrame(result)
time_delta = timer() - time_start
print('Execution time:', time_delta)
print(filtered)
Результат: 392s [171468 rows x 6 columns]
C try, except - результат аналогичен.
3. Использовать JIT-компилятор:
Наиболее быстрый из протестированних на CPU. np.array
- медленнее. Буду рад, если кто-нибудь реализует на GPU. У меня "с наскока" ничего хорошего не вышло.
from timeit import default_timer as timer
import itertools as itr
import numpy as np
import pandas as pd
import numba
arr = np.array(list(itr.combinations(range(1,26),6)))
similar = 4
@numba.njit(target='cpu')
def FilterSimilarRecords(arr, similar):
unique = list()
nonunique = list()
for a in range(arr.shape[0]):
r = set(arr[a])
for u in range(len(unique)):
if (len(unique[u] & r)) > similar:
nonunique.append(arr[a])
break
else:
unique.append(r)
return nonunique
time_start = timer()
filtered = pd.DataFrame(FilterSimilarRecords(arr, similar))
time_delta = timer() - time_start
print('Execution time:', time_delta)
print(filtered)
Результат: 50s [171468 rows x 6 columns]