알고리즘 (예 : k-means)이 실행되는 데 걸리는 시간을 어떻게 알 수 있습니까?

예를 들어, 1 백만 데이터 포인트에서 k-means 알고리즘을 실행하고 있습니다. 각 점은 128 차원이고 1000 개의 클러스터가 필요합니다. Wikipedia는 복잡도가 n^(dk + 1) log (n)이라고 말하며, 여기서 d는 차원 수, k 개의 클러스터 수 및 n 개의 인스턴스 수입니다. 8Gb RAM, 2.6GHz Intel Core i5 MacBook Pro에서 실행되는 시간은 어떻게 예측할 수 있습니까? 이 추정치를 계산하는 가장 좋은 방법은 무엇입니까? 이론적으로 계산할 수있는 방법이 있습니까? 아니면 더 작은 세트에 대해 몇 가지 실험을 수행하고 소요 시간을 확인해야합니까?
내가 멈추지 않을 때 알지 못해 몇 시간이나 며칠을 지내기 전에 대략적인 견적을 듣고 싶습니다. 도움을 주셔서 감사합니다. 정말 감사 :).알고리즘 (예 : k-means)이 실행되는 데 걸리는 시간을 어떻게 알 수 있습니까?

ps. 나는 비단뱀 자리를 사용하고있다.

출처

2014-10-15 Lana Hoffman

'1M^128k '은 약'10^768000'입니다. 우주 시대 '<10^27' 나노초와 비교하십시오. 분명히 최적의 솔루션을 찾을 수 없습니다. 근사치를 얻어야합니다. – zch

scipy는 실용적인 라이브러리이며 아마도 복잡도가 높은 알고리즘을 사용하지 않을 것입니다. 그런 경우에는 실험이 필요합니다. – zch

실험을해라. k-means는 일반적으로 많이 사용되며, 점근선이 제안하는 것보다 훨씬 빠르기 때문에 인기가 있습니다.

출처

2014-10-15 16:31:19

big-O 상수에는 숨어있는 많은 기계 관련 및 알고리즘 관련 세부 사항이 있으므로 이론적으로는 (기계 및 SciPy 용으로는) 추정 할 수 없습니다.

그러나 "작은 세트에 대해 몇 가지 실험을 해보십시오"라는 말처럼 실험적으로 상수를 찾을 수있는 방법은 없습니다.

출처

2014-10-15 22:55:13 HEKTO

답변 해 주셔서 감사합니다. 좋아, 나는 몇 가지 실험을 할 것이다. 그러나 kmeans 알고리즘뿐만 아니라 복잡성을 알고있는 알고리즘에 대해서도 매우 견적을 얻을 수 있기를 바랍니다. 내 프로세서가 2.6e9 사이클을 수행 할 수 있기 때문에 (내재적으로 1 사이클 당 1 회의 연산을 가정 할 때), 알고리즘은 2.6e9로 나눈 큰 -O를 취할 것입니다. 도와 주셔서 다시 한번 감사드립니다. –

주기 당 하나의 작업 - 너무 낙관적입니다. "http://en.wikipedia.org/wiki/Cycles_per_instruction"을보십시오 ... 또한 메모리 액세스 - 빠른 다중 레벨 캐시 (L1/L2/L3)가 있지만 주 메모리에 대한 액세스는 수백 사이클이 걸릴 수 있습니다 . – HEKTO

알고리즘 (예 : k-means)이 실행되는 데 걸리는 시간을 어떻게 알 수 있습니까?

답변

관련 문제