7
대학 프로젝트의 경우, 요소 집합과 해당 요소 간의 관계 모음이 주어질 때 등가성 클래스를 계산하는 몇 가지 알고리즘을 구현해야했습니다 .(Dis) 언어 내부로 인해 하나의 알고리즘이 다른 알고리즘보다 빠르게 작동 함을 증명하십시오.
우리는 Union-Find 알고리즘과 그 최적화 (깊이 별, 크기별 조합)를 구현하도록 지시 받았다. 우연히 (알고리즘의 정확성에 필요한 것이라고 생각한 일을하면서) 알고리즘을 최적화하는 다른 방법을 발견했습니다.
유니온 깊이만큼 빠르지 만 닫힙니다. 나는 내 인생에서 왜 그렇게 빠르는지 알 수 없었기 때문에, 알아낼 수없는 조교 중 한 사람과상의했다.
이 프로젝트는 자바에 있었고, 내가 사용하는 데이터 구조체는 나중에 프로젝트의 평가에서, 나는 그것이 아마 자바 '와 어떤 관계가 있다고 들었다 정수의 간단한 배열 (객체가 아닌 int)를 기반으로 한 캐싱 ',하지만 캐싱이 어떻게 영향을 미치는지에 대해서는 온라인으로 찾을 수 없습니다.
알고리즘의 복잡도를 계산하지 않고 가장 좋은 방법은 무엇이겠습니까? 자바의 방식으로 인해 내 최적화가 빠르다는 것을 증명하거나 반증 할 수 있습니까? 그것을 다른 (낮은 수준의) 언어로 구현합니까? 그러나 누가 그 언어가 똑같은 일을하지 않을 것이라고 말하는가? 내가 자신을 분명하게 희망
,
감사
JIT와 GC 및 컴퓨터 하드웨어 아키텍처에 대한 이해를 시작하기까지 1 년이라는 긴 연구 프로젝트와 같은 소리가납니다 ... –