input 3차원 좌표 x, y, z(각 0~255 사이) n개
data 이름이 붙은 3차원 좌표쌍 (a, b, c) 약 150개(각 0~255 사이)
문제 input의 좌표와 가장 가까운 좌표의 이름 출력
맨첨엔 n개의 좌표를 data만큼 비교해서 가장 가까운거 출력함(소요시간 n*150)
비효율적이다 싶어서 계산한 값을 map에 박아넣고 이미 계산끝난 값은 map에서 꺼내옴
이미 계산끝난값에 대해선 빠르게 가져올수있지 않을까 싶었으나 map의 부하가 너무 커서 오히려 실행시간 증가됨
각 구역을 블록화해서 블록에 가까운 값들만 계산해보는 방법도 있었으나 블록을 작게 쪼개면 추가 탐색해야되고 크게 쪼개면 탐색할게 많아서 처리시간이 차이가 없거나 더 딜레이가됨..
방법이 없을까
그거 불가능함. 걍 빠르게 할거면 배치 사이즈를 줄이는게 맞음.
블록화하면 데이터 대표성 아작나서 성능이 극단적으로 낮아짐. 로컬리 웨잇 느낌으로 쓰는 경우 아니면, 걍 셔플을 돌리고 배치를 줄이는게 나음.
ㅇㅋㅇㅋ 걍 이대로가 낫겠네 그럼
https://klyro.sarl/yvynb
전에도 같은거 묻지 않았나? 진짜 빡세게 해야하는거면 Line sweep 찾아보고
https://en.m.wikipedia.org/wiki/Sweep_line_algorithm
150개면 그냥 다 계산하는게 아무래도 편할거같은데..
ㅇㅇ 그때 방법론 다 적용해봤는데 왠지 모르게 실행시간이 더 늘어짐..
좀더 구체적으로 N이 얼마고 속도요구치가 얼만데.. Latency보다 Bandwidth가 중요하면 GPU라도 쓰던가
n은 약 10만정도임.. GPU 함 알아봐야겠네 ㄱㅅ
https://www.acmicpc.net/problem/2261
이거 아니냐?
https://velog.io/@hamdoe/hnsw-algorithm
임의의 N차원이긴 한데, kNN의 경우엔 실제로 저 알고리즘을 쓰는데
블록 단위가 아니라 좀 다른 묶음으로 대표값을 찾는 방법들은 만아요
icpc 저 문제라면 kd-tree로 검색하면 될 것
ㄱㅅㄱㅅ