기호의 빈도를 정렬하기 위해 계산식 또는 다른 대안을 사용해야합니까?

Question

기호 배열 (256 아스키 기호)과 해당 frequncies 배열 (기호 일부는 0 번 기호)을 갖습니다. 복잡성은 정렬을 위해 계산 방식을 사용하는 것이 현명하고 더 많은 코드 행을 가져올 것입니다 (코드는 어셈블리, tasm으로 작성됩니다).

Answer 1

입력이 long-ish (문자열 또는 256보다 훨씬 긴 버퍼) 인 경우 카운팅 정렬이 우수해야합니다.

---

그것은

그것은 구현 확실히 간단하고, O (1) 복잡성을 가지고 정렬에 계산 정렬을 사용하는 것이 현명 바람직 복잡 할 것이다. 큰 입력이 가능하거나 일반적인 경우 카운팅 정렬은 매우입니다.

비록 작은 입력이 일반적이라면 카운팅 정렬은 여전히 ​​전체 카운트 배열을 지우고 다시 스캔하는 데 시간을 소비해야하며이 비용은 더 작은 입력에 대해 축소되지 않습니다.

CPU에 따라 (예 : 카운트 어레이를 지우는 빠른 memset), 256 심볼로 계산하는 것은 64만큼 작은 입력에 적합 할 수 있습니다. TASM을 언급 했으므로 x86과 x86-16. 최신 x86은 SSE 상점이나 rep stosd을 사용하여 매우 빠른 memset을가집니다. (256 비트 또는 512 바이트 (16 비트 카운터의 경우)는 충분히 커서 rep stos을 사용하는 것은 끔찍한 생각이 아니며, 시작 오버 헤드는 대부분 벡터 루프와 동일한 속도가되도록 감산됩니다.

64 개 이하 qsort 또는 mergesort가 더 잘 수행 할 것인지 확신하지 못합니다. 16 개 정도의 요소 (및 qsort/merge-sort의 기본 경우) 아래에서 성능을 위해 InsertionSort를 원할 수도 있습니다.

SSSE3 (pshufb 용)이 설치된 최신 x86에서는 바이트 단위의 정렬 네트워크에서 SSE2 pminub/pmaxub를 비교기로 사용할 수 있습니다 (물론이 지침은 16 비트 모드에서 작동합니다). 32 비트 요소의 경우 Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms을 참조하고 Fast in-register sort of bytes?을 참조하십시오.

또는 부분 정렬에 SIMD를 사용하면 InsertionSort의 스왑 수가 줄어 듭니다. 어쩌면 약간의 부하, pminub/pmaxub 및 상점, 많은 또는 임의의 셔플없이.

어떤 솔루션 소요됩니다 더 많은 코드 라인

ASM에서, 소스 코드의 라인은 가장 유용한 척도이다. (모든 라인이 명령어로 어셈블 된 것은 아니며 일부는 레이블 또는 지시문입니다.)

명령어 개수는 때로는 관련이 있지만 일부 명령어는 다른 명령어보다 느리고 주문 방법 및 입력 입력이 다른 명령어의 출력에 의존하는지 여부와 관련이 있습니다.

성능에 신경 쓰지 않고 코드 크기를 고려한다면 기계어 코드의 바이트 수를 살펴 봐야합니다. x86 명령어는 가변 길이입니다.

코드 크기에 대해서만 만 신경 쓰고 성능이 전혀 아닐 경우 풍선 정렬 또는 점프 정렬을 고려할 수 있습니다. (조기 체크가 없으면 항상 최대 횟수가 반복됩니다). 유쾌하게 느린 JumpDown sort in 19-bytes of x86-32 machine code을보십시오.코드가 몇 바이트 만 있으면 xchg -with-mem (암시 적 lock 접두어)을 사용하지 않고도 바꿀 수 있습니다. 보다 일반적인 "버블 정렬"구현은 like this (8 비트 정수의 경우 TASM)으로 보입니다.

그러나 당신은 또한 코드의 더 몇 바이트 Insertion Sort을 구현할 수, 그것은 일반적으로 잘 수행은

(다른 O (N^거품 또는 선택을 추천) 알고리즘에 비해)