문제

이것은 긴 텍스트입니다.양해해 주시기 바랍니다.요약하면 질문은 다음과 같습니다. 실행 가능한 내부 기수 정렬 알고리즘이 있습니까??

예비의

나는 엄청나게 많은 것을 가지고 있습니다. 작은 고정 길이 "A", "C", "G" 및 "T" 문자만 사용하는 문자열(예, 짐작하셨을 것입니다: DNA) 정렬하고 싶은 항목입니다.

현재 나는 std::sort 사용하는 내향적인 모든 일반적인 구현에서 STL.이것은 꽤 잘 작동합니다.그러나 나는 확신한다. 기수 정렬 내 문제 세트에 완벽하게 맞고 작동해야합니다 많이 실제로는 더 좋습니다.

세부

나는 매우 순진한 구현과 상대적으로 작은 입력(약 10,000)에 대해 이 가정을 테스트했습니다. 이는 사실이었습니다(적어도 두 배 이상 빠르다).그러나 문제의 크기가 커지면 런타임이 엄청나게 저하됩니다(N > 5,000,000).

그 이유는 분명합니다.기수 정렬을 사용하려면 전체 데이터를 복사해야 합니다(실제로 순진한 구현에서는 두 번 이상).이는 메인 메모리에 4GiB 정도를 넣었다는 뜻이며, 이로 인해 분명히 성능이 저하됩니다.그렇지 않더라도 실제로는 문제의 크기가 더 커지기 때문에 이렇게 많은 메모리를 사용할 여유가 없습니다.

사용 사례

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

연구

불행히도, 기수 정렬에 관한 Wikipedia 기사 쓸모가 없습니다.내부 변형에 대한 섹션은 완전히 쓰레기입니다.그만큼 기수 정렬에 대한 NIST-DADS 섹션 존재하지 않는 것 옆에 있습니다.라는 유망한 논문이 있습니다. 효율적인 적응형 내부 기수 정렬 이는 "MSL" 알고리즘을 설명합니다.불행하게도 이 논문 역시 실망스럽습니다.

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

첫째, 알고리즘에는 몇 가지 실수가 포함되어 있으며 설명할 수 없는 부분이 많이 남아 있습니다.특히 재귀 호출에 대해 자세히 설명하지 않습니다(단순히 현재 시프트 및 마스크 값을 계산하기 위해 일부 포인터를 늘리거나 줄인다고 가정합니다).또한, 다음과 같은 기능을 사용합니다. 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 개의베이스의 1 천만 시퀀스의 경우 최적화 된 introsort보다 약 3 배 빠릅니다.

다른 팁

나는 내부 기수 정렬을 본 적이 없으며 기수 정렬의 특성상 임시 배열이 메모리에 맞는 한 외부 정렬보다 훨씬 빠른지 의심됩니다.

이유:

정렬은 입력 배열에서 선형 읽기를 수행하지만 모든 쓰기는 거의 무작위입니다.특정 N 이상에서는 쓰기당 캐시 미스가 발생합니다.이 캐시 미스는 알고리즘 속도를 저하시킵니다.그것이 제자리에 있든 없든 이 효과는 변하지 않습니다.

이것이 귀하의 질문에 직접적으로 답변해 주지는 않는다는 것을 알고 있지만, 정렬에 병목 현상이 발생한다면 다음을 살펴보는 것이 좋습니다. 근처 정렬 알고리즘을 전처리 단계 (소프트 힙의 wiki 페이지에서 시작하실 수 있습니다).

이는 매우 좋은 캐시 지역성을 향상시킬 수 있습니다.그러면 교과서에서 벗어난 기수 정렬이 더 잘 수행됩니다.쓰기는 여전히 거의 무작위이지만 적어도 동일한 메모리 청크 주위에 클러스터되어 캐시 적중률이 높아집니다.

하지만 실제로 효과가 있을지는 모르겠습니다.

그런데:DNA 문자열만 다루는 경우:문자를 두 비트로 압축하여 데이터를 상당히 많이 압축할 수 있습니다.이는 순진한 표현에 비해 메모리 요구 사항을 4배로 줄여줍니다.주소 지정은 더욱 복잡해지지만 어쨌든 CPU의 ALU는 모든 캐시 누락 중에 소비할 시간이 많습니다.

시퀀스를 비트 단위로 인코딩하면 메모리 요구 사항을 확실히 낮출 수 있습니다.길이 2의 경우 16개 상태 또는 4비트인 "ACGT"의 순열을 보고 있습니다.길이 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 개의 총 버킷)을 반환합니다. 따라서 디스크 기반 버퍼의 분기를 줄입니다. 이것은 성능을 향상 시키거나 개선하지 않을 수도 있으므로 실험하십시오.

나는 사지로 나가서 힙으로 전환 할 것을 제안 할 것입니다.Heapsort 구현. 이 제안에는 몇 가지 가정이 제공됩니다.

  1. 데이터 읽기를 제어합니다
  2. 정렬 된 데이터를 '시작'하자마자 정렬 된 데이터로 의미있는 일을 할 수 있습니다.

힙/힙소의 아름다움은 데이터를 읽는 동안 힙을 만들 수 있으며 힙을 구축 한 순간에 결과를 얻을 수 있다는 것입니다.

물러 서자. 운이 좋을 정도로 데이터를 비동기 적으로 읽을 수 있다면 (즉, 일부 데이터가 준비 될 때 어떤 종류의 읽기 요청을 게시하고 알림을받을 수 있습니다) 다음 데이터 청크는 디스크에서도 들어올 것입니다. 종종이 접근법은 데이터를 얻는 데 소요 된 시간 뒤에 정렬의 절반의 대부분을 묻을 수 있습니다.

데이터를 읽으면 첫 번째 요소가 이미 사용 가능합니다. 데이터를 보내는 위치에 따라 이것은 좋을 수 있습니다. 다른 비동기식 리더 또는 병렬 '이벤트'모델 또는 UI로 보내는 경우 갈 때 덩어리와 청크를 보낼 수 있습니다.

즉, 데이터를 읽는 방법을 제어 할 수없고 동기식으로 읽히는 방법을 제어 할 수 없으며 완전히 기록 될 때까지 정렬 된 데이터를 사용하지 않으면이 모든 것을 무시하십시오. :(

Wikipedia 기사를 참조하십시오.

성능 측면에서 좀 더 일반적인 문자열 비교 정렬 알고리즘을 살펴보는 것이 좋습니다.

현재는 모든 문자열의 모든 요소를 ​​만져야 하지만 더 잘할 수 있습니다!

특히, 버스트 정렬 이 경우에는 매우 적합합니다.보너스로, 버스트 정렬은 시도를 기반으로 하기 때문에 DNA/RNA에 사용되는 작은 알파벳 크기에 대해 엄청나게 잘 작동합니다. 트라이 구현.이러한 시도는 접미사 배열과 같은 최종 목표에도 유용할 수 있습니다.

버스트 정렬의 적절한 범용 구현은 소스 포지에서 사용할 수 있습니다. http://sourceforge.net/projects/burstsort/ - 하지만 제자리에 있지는 않습니다.

비교 목적으로 C-burstsort 구현은 다음에서 다룹니다. http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf 일부 일반적인 워크로드에 대해 퀵 정렬 및 기수 정렬보다 4~5배 더 빠르게 벤치마크합니다.

당신은보고 싶을 것입니다 대규모 게놈 서열 처리 Drs에 의해. 카사하라와 모시 티타.

4 개의 뉴클레오티드 문자 A, C, G 및 T로 구성된 문자열은 정수로 특별히 인코딩 될 수 있습니다. 많이 더 빠른 처리. Radix 정렬은이 책에서 논의 된 많은 알고리즘 중 하나입니다. 이 질문에 대한 수용된 답변을 조정하고 큰 성능 향상을 볼 수 있어야합니다.

"여분의 공간이없는 라디습니다"문제를 해결하는 논문입니다.

당신은 a를 사용해 볼 수 있습니다 트리. 데이터를 정렬하면 단순히 데이터 세트를 통해 반복되고 삽입됩니다. 구조는 자연스럽게 분류되며 B- 트리와 유사하다고 생각할 수 있습니다 (비교하는 대신 제외하면 언제나 포인터 간접을 사용하십시오).

캐싱 동작은 모든 내부 노드를 선호하므로 아마도 개선하지 않을 것입니다. 그러나 트리의 분기 계수와도 함께 할 수 있습니다 (모든 노드가 단일 캐시 라인에 맞는지 확인하고 힙과 유사한 트리 노드를 레벨 주문 트래버스를 나타내는 연속 어레이로 할당하십시오). 시도는 또한 디지털 구조 (O (k) 길이 k의 요소에 대한 삽입/찾기/삭제)이므로 Radix 정렬에 경쟁력있는 성능을 가져야합니다.

나는 할 것이다 파열 문자열의 포장 된 표현. BurstSort는 Radix 정렬보다 훨씬 더 나은 지역을 가지고 있다고 주장되며, 고전적인 시도 대신 버스트 시도로 추가 공간 사용을 유지합니다. 원본 용지의 측정 값이 있습니다.

Radix-Sort는 캐시 의식이 아니며 큰 세트의 가장 빠른 정렬 알고리즘이 아닙니다. 당신은 다음을 볼 수 있습니다 :

또한 압축을 사용하고 DNA의 각 문자를 2 비트로 인코딩하기 전에 정렬 배열에 저장할 수 있습니다.

Dsimcha의 MSB radix 정렬은 멋져 보이지만 캐시 지역이 큰 문제 크기로 당신을 죽이는 것이 무엇인지 관찰하면서 문제의 핵심에 가까워집니다.

매우 간단한 접근법을 제안합니다.

  1. 경험적으로 가장 큰 크기를 추정합니다 m Radix 정렬이 효율적입니다.
  2. 블록을 읽습니다 m 한 번에 요소가 분류하고 입력을 소진 할 때까지 (메모리가 충분하면 메모리 버퍼에, 그렇지 않으면 파일에) 작성하십시오.
  3. MERGESORT 결과 정렬 된 블록.

Mergesort는 가장 캐시 친화적 인 정렬 알고리즘입니다. "배열 A 또는 B에서 다음 항목을 읽은 다음 출력 버퍼에 항목을 작성하십시오." 효율적으로 실행됩니다 테이프 드라이브. 필요합니다 2n 정렬 할 공간 n 항목이지만 내 베팅은 당신이 볼 수있는 많은 개선 된 캐시 지역이 중요하지 않게 만들 것이라는 점입니다.

마지막으로 Mergesort는 재귀없이 구현할 수 있으며 실제로이를 수행하면 실제 선형 메모리 액세스 패턴을 분명히합니다.

문제를 해결 한 것처럼 보이지만 레코드의 경우, 실행 가능한 내부 라디습니다. 여기에 설명되어 있습니다. 엔지니어링 radix 정렬. 일반적인 아이디어는 각 문자에 대해 2 개의 패스를 수행하는 것입니다. 먼저 각각의 각각의 각각 수를 세므로 입력 배열을 쓰레기통으로 세분화 할 수 있습니다. 그런 다음 다시 이동하여 각 요소를 올바른 빈으로 바꾸십시오. 이제 각 빈을 다음 캐릭터 위치에 다시 정렬하십시오.

먼저 문제의 코딩에 대해 생각해보세요.문자열을 제거하고 이진 표현으로 바꾸십시오.첫 번째 바이트를 사용하여 길이+인코딩을 나타냅니다.또는 4바이트 경계에서 고정 길이 표현을 사용하십시오.그러면 기수 정렬이 훨씬 쉬워집니다.기수 정렬의 경우 가장 중요한 것은 내부 루프의 핫스팟에서 예외 처리를 하지 않는 것입니다.

좋아, 나는 4진 문제에 대해 좀 더 생각해 보았다.당신은 다음과 같은 솔루션을 원합니다 주디 트리 이를 위해.다음 솔루션은 가변 길이 문자열을 처리할 수 있습니다.고정 길이의 경우 길이 비트를 제거하면 실제로 더 쉬워집니다.

16개 포인터의 블록을 할당합니다.블록은 항상 정렬되므로 포인터의 최하위 비트를 재사용할 수 있습니다.이를 위해 특별한 저장소 할당자가 필요할 수 있습니다(큰 저장소를 작은 블록으로 나누기).다양한 종류의 블록이 있습니다:

  • 가변 길이 문자열의 7개 길이 비트로 인코딩합니다.채워지면 다음과 같이 교체합니다.
  • 위치는 다음 두 문자를 인코딩합니다. 다음으로 끝나는 다음 블록에 대한 16개의 포인터가 있습니다.
  • 문자열의 마지막 세 문자에 대한 비트맵 인코딩입니다.

각 종류의 블록에 대해 LSB에 서로 다른 정보를 저장해야 합니다.가변 길이 문자열이 있으므로 문자열 끝도 저장해야 하며 마지막 종류의 블록은 가장 긴 문자열에만 사용할 수 있습니다.7개의 길이 비트는 구조에 더 깊이 들어가면서 더 적은 것으로 대체되어야 합니다.

이를 통해 정렬된 문자열을 상당히 빠르고 메모리 효율적으로 저장할 수 있습니다.이는 다음과 같이 다소 동작합니다. 트라이.이 작업을 수행하려면 충분한 단위 테스트를 구축해야 합니다.모든 블록 전환을 다루기를 원합니다.두 번째 종류의 블록으로만 시작하려고 합니다.

성능을 더욱 높이기 위해 다양한 블록 유형과 더 큰 크기의 블록을 추가할 수 있습니다.블록의 크기가 항상 동일하고 충분히 크면 포인터에 더 적은 비트를 사용할 수 있습니다.16개 포인터의 블록 크기를 사용하면 32비트 주소 공간에 이미 1바이트의 여유 공간이 있습니다.흥미로운 블록 유형에 대해서는 Judy 트리 문서를 살펴보세요.기본적으로 공간(및 런타임) 균형을 위해 코드와 엔지니어링 시간을 추가합니다.

처음 4개 문자에 대해 256개의 넓은 직접 기수로 시작하는 것이 좋습니다.이는 적절한 공간/시간 절충안을 제공합니다.이 구현에서는 간단한 트라이를 사용할 때보다 메모리 오버헤드가 훨씬 적습니다.약 3배 정도 작습니다(측정해 본 적이 없습니다).O(n)은 O(n log n) 퀵정렬과 비교할 때 알 수 있듯이 상수가 충분히 낮으면 문제가 되지 않습니다.

더블 핸들링에 관심이 있으신가요?짧은 시퀀스가 ​​​​있을 것입니다.개수를 처리하도록 블록을 조정하는 것은 까다롭지만 매우 공간 효율적일 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top