내부 기수 정렬

내부 기수 정렬

---

긴 글입니다. 저를 참아주세요. 삶은 기수 정렬 알고리즘이 있습니까?

---

예비

나는 정렬하고 싶은 문자 "A", "C", "G"및 "T"(예, 당신은 짐작했습니다 : DNA ) 만 사용하는 작은 고정 길이 문자열이 많이 있습니다 .

현재 STL 의 모든 일반적인 구현에서 introsort 를 사용 std::sort하는을 사용합니다 . 이것은 꽤 잘 작동합니다. 그러나 기수 정렬이 내 문제 세트에 완벽하게 부합하고 실제로 훨씬 더 잘 작동한다고 확신합니다 .

세부

나는 매우 순진한 구현 으로이 가정을 테스트했으며 비교적 작은 입력 (약 10,000 정도)에 대해서는 이것이 사실입니다 (최소한 두 배 이상 빠름). 그러나 문제 크기가 커지면 런타임이 크게 저하됩니다 ( N > 5,000,000).

그 이유는 명백합니다. 기수 정렬은 전체 데이터를 복사해야합니다 (실제로 순진한 구현에서는 두 번 이상). 이것은 ~ 4GiB를 메인 메모리에 넣어 성능을 저하시키는 것을 의미합니다. 그렇지 않은 경우에도 문제 크기가 실제로 더 커지기 때문에이 많은 메모리를 사용할 여유가 없습니다.

사용 사례

이상적으로이 알고리즘은 DNA 및 DNA5 (추가 와일드 카드 문자 "N"허용) 또는 IUPAC 모호성 코드 (16 개의 고유 한 값)가있는 DNA의 경우 2에서 100 사이의 모든 문자열 길이에서 작동해야합니다 . 그러나 이러한 모든 경우를 다룰 수는 없다는 점을 알고 있으므로 속도 향상에 만족합니다. 코드는 어떤 알고리즘을 디스패치할지 동적으로 결정할 수 있습니다.

연구

불행하게도 기수 정렬에 대한 Wikipedia 기사 는 쓸모가 없습니다. 전체 변형에 대한 섹션은 완전 쓰레기입니다. 기수 정렬 의 NIST-DADS 섹션 은 존재하지 않는 옆에 있습니다. 알고리즘“MSL”을 설명하는 Efficient Adaptive In-Place Radix Sorting 이라는 유망한 소리의 논문이 있습니다. 불행하게도이 논문 역시 실망 스럽다.

특히 다음과 같은 것들이 있습니다.

첫째, 알고리즘에는 몇 가지 실수가 포함되어 있으며 설명 할 수없는 부분이 많습니다. 특히, 재귀 호출을 자세히 설명하지 않습니다 (단순히 현재 시프트 및 마스크 값을 계산하기 위해 포인터를 늘리거나 줄이는 것으로 가정합니다). 또한, 기능 사용 dest_group과 dest_address정의를 제공하지 않고 있습니다. 나는 이것을 효율적으로 구현하는 방법을 보지 못했습니다 (즉, O (1); 적어도 dest_address사소하지는 않습니다).

마지막으로,이 알고리즘은 배열 인덱스를 입력 배열 내부의 요소와 교체하여 적절한 위치에 도달합니다. 이것은 분명히 숫자 배열에서만 작동합니다. 문자열에 사용해야합니다. 물론, 나는 강한 타이핑을 망쳐 놓고 메모리가 내 인덱스가 아닌 인덱스를 저장할 수 있다고 가정 할 수 있습니다. 그러나 이것은 32 비트 정수로 가정하여 문자열을 32 비트 메모리로 압축 할 수있는 한 작동합니다. 16 자에 불과합니다 (16> log (5,000,000) 인 순간 무시).

저자 중 한 사람의 다른 논문은 전혀 정확한 설명을 제공하지는 않지만 MSL의 런타임을 하위 선형으로 제공하여 잘못 전개됩니다.

요약 : DNA 문자열에서 작동하는 작업 기준 구현 또는 작업 가능한 기수 정렬에 대한 의사 코드 / 설명을 찾는 희망이 있습니까?

---

자, 여기 DNA를위한 MSD 기수 정렬의 간단한 구현이 있습니다. D 언어로 작성되었습니다. 왜냐하면 제가 가장 많이 사용하는 언어이므로 어리석은 실수를 할 가능성이 가장 적지 만 다른 언어로 쉽게 번역 될 수 있습니다. 제자리에 있지만 2 * seq.length어레이를 통과 해야 합니다.

void radixSort(string[] seqs, size_t base = 0) {
    if(seqs.length == 0)
        return;

    size_t TPos = seqs.length, APos = 0;
    size_t i = 0;
    while(i < TPos) {
        if(seqs[i][base] == 'A') {
             swap(seqs[i], seqs[APos++]);
             i++;
        }
        else if(seqs[i][base] == 'T') {
            swap(seqs[i], seqs[--TPos]);
        } else i++;
    }

    i = APos;
    size_t CPos = APos;
    while(i < TPos) {
        if(seqs[i][base] == 'C') {
            swap(seqs[i], seqs[CPos++]);
        }
        i++;
    }
    if(base < seqs[0].length - 1) {
        radixSort(seqs[0..APos], base + 1);
        radixSort(seqs[APos..CPos], base + 1);
        radixSort(seqs[CPos..TPos], base + 1);
        radixSort(seqs[TPos..seqs.length], base + 1);
   }
}

분명히 이것은 일반적인 것이 아니라 DNA와 관련이 있지만 빠르지 않아야합니다.

편집하다:

이 코드가 실제로 작동하는지 궁금해서 자신의 생체 정보 코드가 실행되기를 기다리는 동안 테스트 / 디버깅했습니다. 위의 버전은 실제로 테스트되어 작동합니다. 각각 5 개의 염기로 구성된 천만 개의 시퀀스에 대해 최적화 된 도입부보다 약 3 배 빠릅니다.

---

나는 기수 정렬을 본 적이 없으며 기수 정렬의 특성상 임시 배열이 메모리에 들어가는 한 소외 정렬보다 훨씬 빠르다고 의심합니다.

이유:

정렬은 입력 배열에서 선형 읽기를 수행하지만 모든 쓰기는 거의 임의적입니다. 특정 N 이상에서 이것은 쓰기 당 캐시 미스로 귀결됩니다. 이 캐시 미스로 인해 알고리즘 속도가 느려집니다. 제자리에 있는지 여부는이 효과를 변경하지 않습니다.

이것이 귀하의 질문에 직접 대답하지는 않지만 정렬이 병목 현상 인 경우 전처리 단계 로 정렬 알고리즘 근처를 살펴보고 싶을 수도 있습니다 (소프트 힙의 wiki 페이지가 시작될 수 있습니다).

캐시 로컬 성이 향상 될 수 있습니다. 그러면 교과서에서 벗어난 기수 정렬이 더 잘 수행됩니다. 쓰기는 여전히 거의 임의적이지만 적어도 동일한 메모리 청크 주위에 클러스터링되어 캐시 적중률이 증가합니다.

그래도 실제로 작동하는지는 알 수 없습니다.

Btw : DNA 문자열 만 다루는 경우 : 문자를 두 비트로 압축하고 데이터를 많이 포장 할 수 있습니다. 이렇게하면 기본 표현에 비해 메모리 요구 사항이 4 배 줄어 듭니다. 어드레싱은 더 복잡해 지지만, CPU의 ALU는 모든 캐시 미스 기간 동안 많은 시간을 소비합니다.

---

시퀀스를 비트 단위로 인코딩하여 메모리 요구 사항을 확실히 제거 할 수 있습니다. 16 개의 상태 또는 4 비트 인 "ACGT"를 사용하여 길이 2에 대한 순열을보고 있습니다. 길이 3의 경우 64 개 상태이며 6 비트로 인코딩 할 수 있습니다. 따라서 시퀀스의 각 문자에 대해 2 비트 또는 16 문자에 대해 약 32 비트처럼 보입니다.

유효한 '단어'의 수를 줄이는 방법이 있다면 추가 압축이 가능할 수 있습니다.

따라서 길이가 3 인 시퀀스의 경우 크기가 uint32 또는 uint64 인 64 개의 버킷을 만들 수 있습니다. 그것들을 0으로 초기화하십시오. 매우 큰 3 개의 문자 시퀀스 목록을 반복하고 위와 같이 인코딩하십시오. 이것을 첨자로 사용하고 해당 버킷을 늘리십시오.
모든 시퀀스가 ​​처리 될 때까지이 과정을 반복하십시오.

다음으로 목록을 재생성하십시오.

64 개의 버킷을 순서대로 반복하여 해당 버킷에서 발견 된 수에 대해 해당 버킷으로 표시되는 시퀀스의 많은 인스턴스를 생성합니다.
모든 버킷이 반복되면 정렬 된 배열이 있습니다.

4의 시퀀스는 2 비트를 추가하므로 256 개의 버킷이 있습니다. 5의 시퀀스는 2 비트를 추가하므로 1024 개의 버킷이 있습니다.

어느 시점에서 버킷 수가 한계에 도달합니다. 파일에서 시퀀스를 메모리에 보관하지 않고 읽는 경우 버킷에 더 많은 메모리를 사용할 수 있습니다.

버킷이 작업 세트에 맞을 가능성이 있기 때문에 현장에서 정렬하는 것보다 이것이 더 빠를 것이라고 생각합니다.

기술을 보여주는 해킹입니다.

#include <iostream>
#include <iomanip>

#include <math.h>

using namespace std;

const int width = 3;
const int bucketCount = exp(width * log(4)) + 1;
      int *bucket = NULL;

const char charMap[4] = {'A', 'C', 'G', 'T'};

void setup
(
    void
)
{
    bucket = new int[bucketCount];
    memset(bucket, '\0', bucketCount * sizeof(bucket[0]));
}

void teardown
(
    void
)
{
    delete[] bucket;
}

void show
(
    int encoded
)
{
    int z;
    int y;
    int j;
    for (z = width - 1; z >= 0; z--)
    {
        int n = 1;
        for (y = 0; y < z; y++)
            n *= 4;

        j = encoded % n;
        encoded -= j;
        encoded /= n;
        cout << charMap[encoded];
        encoded = j;
    }

    cout << endl;
}

int main(void)
{
    // Sort this sequence
    const char *testSequence = "CAGCCCAAAGGGTTTAGACTTGGTGCGCAGCAGTTAAGATTGTTT";

    size_t testSequenceLength = strlen(testSequence);

    setup();


    // load the sequences into the buckets
    size_t z;
    for (z = 0; z < testSequenceLength; z += width)
    {
        int encoding = 0;

        size_t y;
        for (y = 0; y < width; y++)
        {
            encoding *= 4;

            switch (*(testSequence + z + y))
            {
                case 'A' : encoding += 0; break;
                case 'C' : encoding += 1; break;
                case 'G' : encoding += 2; break;
                case 'T' : encoding += 3; break;
                default  : abort();
            };
        }

        bucket[encoding]++;
    }

    /* show the sorted sequences */ 
    for (z = 0; z < bucketCount; z++)
    {
        while (bucket[z] > 0)
        {
            show(z);
            bucket[z]--;
        }
    }

    teardown();

    return 0;
}

---

데이터 세트가 너무 크면 디스크 기반 버퍼 방식이 가장 좋을 것이라고 생각합니다.

sort(List<string> elements, int prefix)
    if (elements.Count < THRESHOLD)
         return InMemoryRadixSort(elements, prefix)
    else
         return DiskBackedRadixSort(elements, prefix)

DiskBackedRadixSort(elements, prefix)
    DiskBackedBuffer<string>[] buckets
    foreach (element in elements)
        buckets[element.MSB(prefix)].Add(element);

    List<string> ret
    foreach (bucket in buckets)
        ret.Add(sort(bucket, prefix + 1))

    return ret

예를 들어 문자열이 다음과 같은 경우 더 많은 수의 버킷으로 그룹화하는 방법을 실험합니다.

GATTACA

첫 번째 MSB 호출은 GATT에 대한 버킷 (총 버킷 256 개)을 반환하여 디스크 기반 버퍼의 분기를 줄입니다. 이는 성능을 향상시킬 수도 있고 향상시키지 않을 수도 있으므로 실험 해보십시오.

---

I'm going to go out on a limb and suggest you switch to a heap/heapsort implementation. This suggestion comes with some assumptions:

1. You control the reading of the data
2. You can do something meaningful with the sorted data as soon as you 'start' getting it sorted.

The beauty of the heap/heap-sort is that you can build the heap while you read the data, and you can start getting results the moment you have built the heap.

Let's step back. If you are so fortunate that you can read the data asynchronously (that is, you can post some kind of read request and be notified when some data is ready), and then you can build a chunk of the heap while you are waiting for the next chunk of data to come in - even from disk. Often, this approach can bury most of the cost of half of your sorting behind the time spent getting the data.

Once you have the data read, the first element is already available. Depending on where you are sending the data, this can be great. If you are sending it to another asynchronous reader, or some parallel 'event' model, or UI, you can send chunks and chunks as you go.

That said - if you have no control over how the data is read, and it is read synchronously, and you have no use for the sorted data until it is entirely written out - ignore all this. :(

See the Wikipedia articles:

• Heapsort
• Binary heap

---

Performance-wise you might want to look at a more general string-comparison sorting algorithms.

Currently you wind up touching every element of every string, but you can do better!

In particular, a burst sort is a very good fit for this case. As a bonus, since burstsort is based on tries, it works ridiculously well for the small alphabet sizes used in DNA/RNA, since you don't need to build any sort of ternary search node, hash or other trie node compression scheme into the trie implementation. The tries may be useful for your suffix-array-like final goal as well.

A decent general purpose implementation of burstsort is available on source forge at http://sourceforge.net/projects/burstsort/ - but it is not in-place.

For comparison purposes, The C-burstsort implementation covered at http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf benchmarks 4-5x faster than quicksort and radix sorts for some typical workloads.

---

You'll want to take a look at Large-scale Genome Sequence Processing by Drs. Kasahara and Morishita.

Strings comprised of the four nucleotide letters A, C, G, and T can be specially encoded into Integers for much faster processing. Radix sort is among many algorithms discussed in the book; you should be able to adapt the accepted answer to this question and see a big performance improvement.

---

"Radix sorting with no extra space" is a paper addressing your problem.

---

You might try using a trie. Sorting the data is simply iterating through the dataset and inserting it; the structure is naturally sorted, and you can think of it as similar to a B-Tree (except instead of making comparisons, you always use pointer indirections).

Caching behavior will favor all of the internal nodes, so you probably won't improve upon that; but you can fiddle with the branching factor of your trie as well (ensure that every node fits into a single cache line, allocate trie nodes similar to a heap, as a contiguous array that represents a level-order traversal). Since tries are also digital structures (O(k) insert/find/delete for elements of length k), you should have competitive performance to a radix sort.

---

I would burstsort a packed-bit representation of the strings. Burstsort is claimed to have much better locality than radix sorts, keeping the extra space usage down with burst tries in place of classical tries. The original paper has measurements.

---

Radix-Sort is not cache conscious and is not the fastest sort algorithm for large sets. You can look at:

• ti7qsort. ti7qsort is the fastest sort for integers (can be used for small-fixed size strings).
• Inline QSORT
• String sorting

You can also use compression and encode each letter of your DNA into 2 bits before storing into the sort array.

---

dsimcha's MSB radix sort looks nice, but Nils gets closer to the heart of the problem with the observation that cache locality is what's killing you at large problem sizes.

I suggest a very simple approach:

1. Empirically estimate the largest size m for which a radix sort is efficient.
2. Read blocks of m elements at a time, radix sort them, and write them out (to a memory buffer if you have enough memory, but otherwise to file), until you exhaust your input.
3. Mergesort the resulting sorted blocks.

Mergesort is the most cache-friendly sorting algorithm I'm aware of: "Read the next item from either array A or B, then write an item to the output buffer." It runs efficiently on tape drives. It does require 2n space to sort n items, but my bet is that the much-improved cache locality you'll see will make that unimportant -- and if you were using a non-in-place radix sort, you needed that extra space anyway.

Please note finally that mergesort can be implemented without recursion, and in fact doing it this way makes clear the true linear memory access pattern.

---

It looks like you've solved the problem, but for the record, it appears that one version of a workable in-place radix sort is the "American Flag Sort". It's described here: Engineering Radix Sort. The general idea is to do 2 passes on each character - first count how many of each you have, so you can subdivide the input array into bins. Then go through again, swapping each element into the correct bin. Now recursively sort each bin on the next character position.

---

First, think about the coding of your problem. Get rid of the strings, replace them by a binary representation. Use the first byte to indicate length+encoding. Alternatively, use a fixed length representation at a four-byte boundary. Then the radix sort becomes much easier. For a radix sort, the most important thing is to not have exception handling at the hot spot of the inner loop.

OK, I thought a bit more about the 4-nary problem. You want a solution like a Judy tree for this. The next solution can handle variable length strings; for fixed length just remove the length bits, that actually makes it easier.

Allocate blocks of 16 pointers. The least significant bit of the pointers can be reused, as your blocks will always be aligned. You might want a special storage allocator for it (breaking up large storage into smaller blocks). There are a number of different kinds of blocks:

• Encoding with 7 length bits of variable-length strings. As they fill up, you replace them by:
• Position encodes the next two characters, you have 16 pointers to the next blocks, ending with:
• Bitmap encoding of the last three characters of a string.

For each kind of block, you need to store different information in the LSBs. As you have variable length strings you need to store end-of-string too, and the last kind of block can only be used for the longest strings. The 7 length bits should be replaced by less as you get deeper into the structure.

This provides you with a reasonably fast and very memory efficient storage of sorted strings. It will behave somewhat like a trie. To get this working, make sure to build enough unit tests. You want coverage of all block transitions. You want to start with only the second kind of block.

For even more performance, you might want to add different block types and a larger size of block. If the blocks are always the same size and large enough, you can use even fewer bits for the pointers. With a block size of 16 pointers, you already have a byte free in a 32-bit address space. Take a look at the Judy tree documentation for interesting block types. Basically, you add code and engineering time for a space (and runtime) trade-off

You probably want to start with a 256 wide direct radix for the first four characters. That provides a decent space/time tradeoff. In this implementation, you get much less memory overhead than with a simple trie; it is approximately three times smaller (I haven't measured). O(n) is no problem if the constant is low enough, as you noticed when comparing with the O(n log n) quicksort.

Are you interested in handling doubles? With short sequences, there are going to be. Adapting the blocks to handle counts is tricky, but it can be very space-efficient.

참고URL : https://stackoverflow.com/questions/463105/in-place-radix-sort