c++ sort 속도 더 늘릴 수 있는 방법 없을까?

[익명(114.202)]

클래스로 정의된 변수 백만개를 vector로 가져와서 특정 조건에 따라서 정렬하고 find로 찾으려고 하거든?

근데 find 자체는 얼마 안걸리는데 이동생성자 복사생성자 다 만들고 reserve로 공간 확보해주고 다 해도

일정 속도 이상은 안나오더라

내가 할기론 sort가 퀵정렬 쓰는걸로 알고있는데 그러면 속도가 O(log(n))에 수렴하는거잖아?

이것보다 빠르게 하는건 진짜 수학자인거 아니면 불가능에 가깝냐?

[익명(1.177)]

DBMS써 천재들이 만든 알고리즘이 거기 다 녹아있음

[익명(114.202)]

다른 라이브러리 안끌어오고 c++ 자체로만 한다고 봤을때는 힘드냐?

[나트륨찡(alphauri)]

너가 쓴 글에 오류가 두개나 있음

[나트륨찡(alphauri)]

c++ sort는 퀵정렬과 힙정렬을 하이브리드한 인트로소트라고 함

[나트륨찡(alphauri)]

그 시간복잡도는 O(nlogn)이 정확한 수식임 (O는 대문자)

[나트륨찡(alphauri)]

퀵소트는 O(n^2)임

[나트륨찡(alphauri)]

수학적으로 O(nlogn)에 수렴하는 게 아니라 그 이하라고 보는 게 정확함 수학적으로 O(nlogn)/nlogn이 수렴한다고 한다

[나트륨찡(alphauri)]

수학적으로 어떤 함수들은 O(nlogn)/nlogn 이 수렴하지 않을 수도 있음 그런데도 O(nlogn)이 성립하기도 함

[나트륨찡(alphauri)]

오류가 다섯개나 있네 공부 열심히 하도록..

[나트륨찡(alphauri)]

인트로소트는 불안정정렬의 종류 중 하나임 따라서 c++은 안정정렬을 느린 다른 함수로 지원함

[나트륨찡(alphauri)]

이건 팁

[fft(89.246)]

클래스로 정의가 되어있다면 data사이에 빈공간이 있을수있음. primitve 벡터써서 cache hit 최대로 높이셈.