메모리를 할당하지 않고 배열을 정렬하는 방법이 있습니까?

매우 큰 컬렉션 (매우 수백/낮은 수천 개의 항목)을 매우 자주 정렬해야합니다. 즉 60fps의 모든 프레임입니다 (Unity를 사용하고 있습니다). 각 항목의 키 계산이 일종의 캐시이므로 캐시해야합니다.메모리를 할당하지 않고 배열을 정렬하는 방법이 있습니까?

내가 시도한 다양한 접근 방법 : IComparer와

List.Sort(), 키마다 계산 : 슈퍼 슬로우
SortedList : 훨씬 더 빨리,하지만 생성 GC의 allocs (30킬로바이트/프레임) : 왜? 그들은 열쇠 박스 (나는 오래 사용하고 있습니까?) 키/값 쌍이 할당 되었습니까? 클래스에서 long을 래핑하면 GC가 절반으로 줄어들므로 내 추측은 "both"입니다. 쌍에 대한 1 할당, 값 유형 인 경우 키에 대한 하나 할당 ...
Array.Sort (keyArray , valueArray) : 끔찍한! 느린 &은 256KB의 GC/프레임을 생성합니다!

SortedList가 작업에 이상적 이었기 때문에 부끄럽습니다. GC가없는 대안이 있습니까?

출처

2014-09-08 benblo

각 프레임에 있어야하는 것이 중요합니까? 어쩌면 당신은 [coroutines] (http://docs.unity3d.com/ScriptReference/Coroutine.html) – user3557327

* any * memory, no.를 사용하여 여러 프레임에서 계산할 수 있습니다. 어떤 종류의 정렬을 수행하려면 적어도 스왑 변수가 필요합니다. 사용 된 메모리는 알고리즘에 따라 다르며 삽입 또는 선택 정렬에서는 메모리가 거의 필요하지 않으며 빠른 정렬이 빠르며 메모리도 거의 사용되지 않습니다. 직접 구현하고 .NET이 사용하는 모든 것에 대해 어떻게 작동하는지 확인할 수 있습니다! – BradleyDotNET

[This] (http://www.sorting-algorithms.com)에서 시작할 수 있습니다. –

계산 키가 너무 느리면 key 속성을 항목 클래스에 추가하고 정렬 전에 계산 한 다음 IComparer 키를 사용하여 첫 번째 방법을 사용하면됩니다.

출처

2014-09-08 17:45:39

예이 방법을 시도했지만 List.Sort 자체가 매우 느립니다. – benblo

메모리를 할당하지 않고 배열을 정렬하는 방법이 있습니까?

답변

관련 문제