저는 두 개의 드문 드문 한 행렬 A와 B를가집니다. A는 120000 * 5000이고 B는 30000 * 5000입니다. B의 각 행과 A의 모든 행 사이의 유클리드 거리를 찾아서 B의 선택된 행과 가장 가까운 거리에있는 A의 5 행을 찾아야합니다. 매우 큰 데이터이므로 CSR을 사용하고 있습니다. 메모리 오류. 그것은 A의 각 행에 대해 (x_b - x_a)^2를 5000 번 계산하고이를 합계 한 다음 sqrt를 얻는 것이 분명합니다. 이 과정은 11 일 동안 매우 오랜 시간이 걸립니다! 이 작업을보다 효율적으로 수행 할 수있는 방법이 있습니까? B 행의 가장 낮은 거리에 5 행이 필요합니다.두 개의 커다란 CSR 행렬의 행 사이의 유클리드 거리를 찾으십시오.
저는 K-Nearest Neighbors를 구현하고 있습니다. A는 제 트레이닝 세트이고 B는 테스트 세트입니다.
음 - 파이썬 대신 네이티브 코드로 실행되도록 코드를 '벡터화'할 수 있는지 여부는 잘 모르겠습니다. numpy와 scipy를 가속화하는 속임수는 항상 그것을 얻고 있습니다.
1GHz CPU에서 기본 코드로 해당 코드를 실행할 수 있고 clock cicle에 대해 1FP 명령을 사용하면 10 시간 이내에 완료됩니다.(5000 * 2 * 30000 * 120000)/1024 ** 3
곱하기 + acummulate (Intel AVX 확장, 대부분의 CPU에서 사용 가능)와 1.5Ghz x 2 CPU 물리적 코어 x 4 방향 SIMD 명령어 겸손한 코어 i5 머신에서 2 x 100 %로 1 시간으로 내려갈 수 있습니다. 하지만 그렇게하려면 네이티브 코드에서 전체 SIMD 최적화가 필요합니다. (비록이 경로를 선택했다면 SO에 대한 추가 질문은 사람들이 SIMD 코딩에 손을 대지 않도록 도움을 줄 수 있습니다 :-)) - 인터페이싱 C에서 Scipy를 사용하는이 코드는 cython을 사용하여 어렵지 않습니다 (예 : 위의 10 시간 그림을 얻으려면 해당 부분 만 필요합니다)
지금 ... 알고리즘 최적화 및 보관 : Python
사실, 모두 A의 행으로부터 거리를 계산할 필요가 없습니다. 5 개의 하단 행의 정렬 된 목록을 유지하면되고, 제곱의 합계가 다섯 번째로 가까운 행 (지금까지), 당신은 단지 그 행에 대한 계산을 중단합니다.
당신은 파이썬 'heapq 작업을 사용할 수 있습니다
import heapq
import math
def get_closer_rows(b_row, a):
result = [(float("+inf"), None) * 5]
for i, a_row in enumerate(a):
distance_sq = 0
count = 0
for element_a, element_b in zip(a_row, b_row):
distance_sq += element_a * element_b
if not count % 64 and distance_sq > result[4][0]:
break
count += 1
else:
heapq.heappush(result, (distance, i))
result[:] = result[:5]
return [math.sqrt(r) for r in result]
closer_rows_to_b = []
for row in b:
closer_rows_to_b.append(get_closer_rows(row, a))
참고 auxiliar "카운트가"모든 곱셈에 대한 값 비싼 검색하고 비교를 피하기 위해. 이제 정규 Python 대신 pypy를 사용하여이 코드를 실행할 수 있다면 JITting의 이점을 충분히 누릴 수 있다고 생각합니다. 순수 Python으로 코드를 실행하면 시간이 지남에 따라 눈에 띄게 개선 될 수 있습니다 (예 : non numpy/scipy 벡터화 된 코드).