Ini adalah teks yang panjang. Tolong bersamaku. Mendidih, pertanyaannya adalah: Apakah ada algoritma jenis radix di tempat yang bisa diterapkan ?

Pendahuluan

Saya punya banyak sekali string dengan panjang tetap kecil yang hanya menggunakan huruf "A", "C", "G" dan "T" (ya, Anda sudah menebaknya: DNA ) yang ingin saya urutkan.

Saat ini, saya menggunakan std::sortyang menggunakan introsort di semua implementasi umum STL . Ini bekerja dengan sangat baik. Namun, saya yakin itu jenis radix cocok dengan masalah saya yang diatur dengan sempurna dan harus bekerja jauh lebih baik dalam praktek.

Detail

Saya telah menguji asumsi ini dengan implementasi yang sangat naif dan untuk input yang relatif kecil (pada urutan 10.000) ini benar (well, setidaknya lebih dari dua kali lebih cepat). Namun, runtime menurun secara drastis ketika ukuran masalah menjadi lebih besar ( N > 5.000.000).

Alasannya jelas: radix sort membutuhkan penyalinan seluruh data (sebenarnya lebih dari sekali dalam implementasi naif saya). Ini berarti bahwa saya telah memasukkan ~ 4 GiB ke dalam memori utama saya yang jelas membunuh kinerja. Bahkan jika tidak, saya tidak mampu menggunakan memori sebanyak ini karena ukuran masalah sebenarnya menjadi lebih besar.

Gunakan Kasing

Idealnya, algoritma ini harus bekerja dengan panjang tali antara 2 dan 100, untuk DNA dan juga DNA5 (yang memungkinkan karakter wildcard tambahan "N"), atau bahkan DNA dengan kode ambiguitas IUPAC (menghasilkan 16 nilai berbeda). Namun, saya menyadari bahwa semua kasus ini tidak dapat ditutup, jadi saya senang dengan peningkatan kecepatan yang saya dapatkan. Kode dapat memutuskan secara dinamis algoritma mana yang akan dikirim.

Penelitian

Sayangnya, artikel Wikipedia tentang radix sort tidak berguna. Bagian tentang varian di tempat adalah sampah lengkap. Bagian NIST-DADS pada jenis radix ada di sebelah tidak ada. Ada makalah yang terdengar menjanjikan yang disebut Efficient Adaptive In-Place Radix Sorting yang menggambarkan algoritma "MSL". Sayangnya, makalah ini juga mengecewakan.

Secara khusus, ada beberapa hal berikut.

Pertama, algoritma tersebut mengandung beberapa kesalahan dan membuat banyak yang tidak dapat dijelaskan. Secara khusus, itu tidak merinci panggilan rekursi (saya hanya berasumsi bahwa itu menambah atau mengurangi beberapa pointer untuk menghitung nilai shift dan mask saat ini). Selain itu, ia menggunakan fungsi dest_groupdan dest_addresstanpa memberikan definisi. Saya gagal melihat bagaimana menerapkan ini secara efisien (yaitu, dalam O (1); setidaknyadest_address tidak sepele).

Last but not least, algoritma mencapai di tempat dengan menukar indeks array dengan elemen di dalam array input. Ini jelas hanya bekerja pada array numerik. Saya perlu menggunakannya pada string. Tentu saja, saya hanya bisa mengetikan pengetikan yang kuat dan melanjutkan dengan asumsi bahwa memori akan mentolerir saya menyimpan indeks di tempat yang bukan miliknya. Tapi ini hanya berfungsi selama saya bisa memasukkan string saya ke dalam 32 bit memori (dengan asumsi integer 32 bit). Itu hanya 16 karakter (abaikan saja saat itu 16> log (5.000.000)).

Makalah lain oleh salah satu penulis tidak memberikan deskripsi yang akurat sama sekali, tetapi memberikan runtime MSL sebagai sub-linear yang salah datar.

Untuk merangkum : Apakah ada harapan untuk menemukan implementasi referensi kerja atau setidaknya pseudocode / deskripsi yang baik dari jenis radix yang bekerja di tempat yang bekerja pada string DNA?

Nah, ini adalah implementasi sederhana dari jenis radix MSD untuk DNA. Ini ditulis dalam D karena itu bahasa yang paling saya gunakan dan karena itu paling tidak mungkin membuat kesalahan konyol, tapi itu bisa dengan mudah diterjemahkan ke bahasa lain. Ada di tempat tetapi membutuhkan 2 * seq.lengthmelewati array.

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);
   }
}

Jelas, ini adalah jenis khusus untuk DNA, yang bertentangan dengan yang umum, tetapi harus cepat.

Edit:

Saya ingin tahu apakah kode ini benar-benar berfungsi, jadi saya menguji / menuduhnya sambil menunggu kode bioinformatika saya berjalan. Versi di atas sekarang benar-benar diuji dan berfungsi. Untuk 10 juta sekuens masing-masing 5 pangkalan, ini sekitar 3x lebih cepat dari introsort yang dioptimalkan.

Saya belum pernah melihat jenis radix di tempat, dan dari sifat jenis radix saya ragu bahwa itu jauh lebih cepat daripada jenis luar tempat selama array sementara masuk ke dalam memori.

Alasan:

Penyortiran tidak membaca linear pada array input, tetapi semua penulisan akan hampir acak. Dari N tertentu ke atas ini bermuara pada cache miss per write. Cache yang hilang ini yang memperlambat algoritme Anda. Jika sudah terpasang atau tidak tidak akan mengubah efek ini.

Saya tahu bahwa ini tidak akan menjawab pertanyaan Anda secara langsung, tetapi jika pengurutan adalah hambatan Anda mungkin ingin melihat algoritma pengurutan dekat sebagai langkah preprocessing (halaman wiki pada soft-heap dapat membantu Anda memulai).

Itu bisa memberikan dorongan lokalitas cache yang sangat bagus. Jenis radix buku teks out-of-place kemudian akan tampil lebih baik. Tulisan masih akan hampir acak tetapi setidaknya mereka akan mengelompok di sekitar potongan memori yang sama dan dengan demikian meningkatkan rasio hit cache.

Saya tidak tahu apakah itu berhasil dalam prakteknya.

Btw: Jika Anda hanya berurusan dengan string DNA: Anda dapat mengompres char menjadi dua bit dan mengemas data Anda cukup banyak. Ini akan mengurangi kebutuhan memori dengan faktor empat selama representasi naif. Mengatasi menjadi lebih rumit, tetapi ALU CPU Anda memiliki banyak waktu untuk dihabiskan selama semua cache-misses.

Anda tentu dapat menjatuhkan persyaratan memori dengan menyandikan urutan dalam bit. Anda melihat permutasi jadi, untuk panjang 2, dengan "ACGT" itu 16 negara, atau 4 bit. Untuk panjang 3, itu 64 negara, yang dapat dikodekan dalam 6 bit. Jadi sepertinya 2 bit untuk setiap huruf dalam urutan, atau sekitar 32 bit untuk 16 karakter seperti yang Anda katakan.

Jika ada cara untuk mengurangi jumlah 'kata' yang valid, kompresi lebih lanjut dapat dilakukan.

Jadi untuk urutan panjang 3, seseorang dapat membuat 64 ember, mungkin berukuran uint32, atau uint64. Inisialisasi ke nol. Ulangi daftar 3 urutan char yang sangat besar, dan buat kode seperti di atas. Gunakan ini sebagai subskrip, dan tambahkan ember itu.
Ulangi ini sampai semua urutan Anda telah diproses.

Selanjutnya, buat ulang daftar Anda.

Ulangi 64 ember secara berurutan, untuk hitungan yang ditemukan di ember itu, hasilkan banyak contoh urutan yang diwakili oleh ember itu.
ketika semua bucket telah diiterasi, Anda memiliki array yang diurutkan.

Urutan 4, menambahkan 2 bit, sehingga akan ada 256 ember. Urutan 5, menambahkan 2 bit, sehingga akan ada 1024 ember.

Pada titik tertentu jumlah ember akan mendekati batas Anda. Jika Anda membaca urutan dari file, alih-alih menyimpannya di memori, lebih banyak memori yang tersedia untuk bucket.

Saya pikir ini akan lebih cepat daripada melakukan penyortiran di situ karena ember cenderung masuk ke dalam set kerja Anda.

Ini adalah retas yang menunjukkan tekniknya

#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;
}

Jika kumpulan data Anda sangat besar, maka saya akan berpikir bahwa pendekatan buffer berbasis disk akan lebih baik:

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

Saya juga akan mencoba pengelompokan menjadi jumlah ember yang lebih besar, misalnya, jika string Anda:

GATTACA

panggilan MSB pertama akan mengembalikan bucket untuk GATT (256 total ember), dengan begitu Anda membuat lebih sedikit cabang buffer berbasis disk. Ini mungkin atau mungkin tidak meningkatkan kinerja, jadi bereksperimenlah dengannya.

Saya akan pergi mengambil risiko dan menyarankan Anda beralih ke implementasi heap / heapsort . Saran ini dilengkapi dengan beberapa asumsi:

1. Anda mengontrol pembacaan data
2. Anda dapat melakukan sesuatu yang berarti dengan data yang diurutkan segera setelah Anda 'mulai' mendapatkannya diurutkan.

Keindahan heap / heap-sort adalah Anda bisa membangun heap saat membaca data, dan Anda bisa mulai mendapatkan hasil saat Anda membangun heap.

Mari kita mundur. Jika Anda sangat beruntung bahwa Anda dapat membaca data secara tidak sinkron (yaitu, Anda dapat memposting beberapa jenis permintaan baca dan diberi tahu ketika beberapa data siap), dan kemudian Anda dapat membuat bongkahan tumpukan sementara Anda menunggu potongan data yang akan datang - bahkan dari disk. Seringkali, pendekatan ini dapat mengubur sebagian besar biaya setengah dari penyortiran Anda di belakang waktu yang dihabiskan untuk mendapatkan data.

Setelah data dibaca, elemen pertama sudah tersedia. Tergantung di mana Anda mengirim data, ini bisa menjadi luar biasa. Jika Anda mengirimnya ke pembaca asinkron lain, atau model 'acara' paralel, atau UI, Anda dapat mengirim bongkahan dan bongkahan saat Anda pergi.

Yang mengatakan - jika Anda tidak memiliki kontrol atas bagaimana data dibaca, dan itu dibaca secara sinkron, dan Anda tidak menggunakan data yang diurutkan sampai sepenuhnya ditulis - abaikan semua ini. :(

Lihat artikel Wikipedia:

• Heapsort
• Tumpukan biner

" Radix sorting tanpa ruang tambahan " adalah kertas yang membahas masalah Anda.

Kinerja-bijaksana Anda mungkin ingin melihat algoritma pengurutan perbandingan string yang lebih umum.

Saat ini Anda akhirnya menyentuh setiap elemen dari setiap string, tetapi Anda bisa melakukan yang lebih baik!

Khususnya, jenis burst sangat cocok untuk kasus ini. Sebagai bonus, karena burstsort didasarkan pada percobaan, ia bekerja dengan sangat baik untuk ukuran alfabet kecil yang digunakan dalam DNA / RNA, karena Anda tidak perlu membangun segala jenis node pencarian ternary, hash atau skema kompresi node trie lainnya ke dalam implementasi trie. Mencoba mungkin berguna untuk tujuan akhir seperti array akhiran Anda juga.

Implementasi tujuan umum yang layak dari burstsort tersedia di source forge di http://sourceforge.net/projects/burstsort/ - tetapi tidak ada di tempat.

Untuk tujuan perbandingan, implementasi C-burstsort tercakup pada http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006.pdf tolok ukur 4-5x lebih cepat daripada jenis quicksort dan radix untuk beberapa beban kerja yang khas.

Anda akan ingin melihat Pemrosesan Urutan Genom skala besar oleh Drs. Kasahara dan Morishita.

String yang terdiri dari empat huruf nukleotida A, C, G, dan T dapat dikodekan secara khusus ke dalam Integer untuk pemrosesan yang jauh lebih cepat. Urutan Radix adalah di antara banyak algoritma yang dibahas dalam buku ini; Anda harus dapat menyesuaikan jawaban yang diterima untuk pertanyaan ini dan melihat peningkatan kinerja yang besar.

Anda mungkin mencoba menggunakan trie . Menyortir data hanya iterasi melalui dataset dan memasukkannya; struktur secara alami diurutkan, dan Anda dapat menganggapnya mirip dengan B-Tree (kecuali alih-alih membuat perbandingan, Anda selalu menggunakan tipuan penunjuk).

Perilaku cache akan mendukung semua node internal, jadi Anda mungkin tidak akan memperbaikinya; tetapi Anda juga bisa mengutak-atik faktor percabangan dari trie Anda (memastikan bahwa setiap node cocok menjadi satu baris cache, alokasikan trie node yang mirip dengan heap, sebagai array yang berdekatan yang mewakili level-order traversal). Karena percobaan juga merupakan struktur digital (O (k) yang menyisipkan / menemukan / menghapus elemen dengan panjang k), Anda harus memiliki kinerja kompetitif untuk jenis radix.

Saya akan memecah representasi string yang penuh sesak. Burstsort diklaim memiliki lokalitas yang jauh lebih baik daripada jenis radix, menjaga penggunaan ruang ekstra dengan mencoba burst di tempat mencoba klasik. Kertas asli memiliki ukuran.

Radix-Sort tidak sadar cache dan bukan algoritma sortir tercepat untuk set besar. Anda dapat melihat:

• ti7qsort . ti7qsort adalah sortir tercepat untuk integer (dapat digunakan untuk string ukuran kecil-tetap).
• Sebaris QSORT
• Penyortiran string

Anda juga dapat menggunakan kompresi dan mengkodekan setiap huruf dari DNA Anda menjadi 2 bit sebelum disimpan ke dalam array sortir.

dsimcha MSB radix sort terlihat bagus, tetapi Nils semakin dekat ke jantung masalah dengan pengamatan bahwa cache lokalitas adalah apa yang membunuh Anda pada ukuran masalah besar.

Saya menyarankan pendekatan yang sangat sederhana:

1. Perkiraan secara empiris ukuran terbesar muntuk jenis radix yang efisien.
2. Baca blok m elemen sekaligus, radix sortir, dan tuliskan (ke buffer memori jika Anda memiliki cukup memori, tetapi jika perlu file), hingga Anda menghabiskan input Anda.
3. Mergesort blok yang diurutkan yang dihasilkan.

Mergesort adalah algoritma penyortiran yang paling ramah terhadap cache yang saya ketahui: "Baca item berikutnya dari array A atau B, lalu tulis item ke buffer output." Ini berjalan secara efisien tape drive . Memang membutuhkan 2nruang untuk mengurutkan nitem, tetapi taruhan saya adalah bahwa lokalitas cache yang jauh lebih baik yang Anda lihat akan membuat itu tidak penting - dan jika Anda menggunakan jenis radix yang tidak ada di tempat, Anda tetap membutuhkan ruang tambahan itu.

Harap dicatat akhirnya bahwa mergesort dapat diimplementasikan tanpa rekursi, dan sebenarnya melakukannya dengan cara ini memperjelas pola akses memori linier yang sebenarnya.

Sepertinya Anda telah memecahkan masalah, tetapi sebagai catatan, tampaknya satu versi dari jenis radix yang dapat diterapkan adalah "Jenis Bendera Amerika". Dijelaskan di sini: Rekayasa Radix Sort . Gagasan umum adalah melakukan 2 operan pada setiap karakter - pertama hitung berapa banyak dari masing-masing karakter yang Anda miliki, sehingga Anda dapat membagi array input menjadi nampan. Kemudian lalui lagi, menukar setiap elemen ke tempat sampah yang benar. Sekarang secara rekursif mengurutkan setiap nampan pada posisi karakter berikutnya.

Pertama, pikirkan tentang pengkodean masalah Anda. Singkirkan string, ganti dengan representasi biner. Gunakan byte pertama untuk menunjukkan panjang + penyandian. Atau, gunakan representasi panjang tetap pada batas empat byte. Maka jenis radix menjadi jauh lebih mudah. Untuk jenis radix, hal yang paling penting adalah untuk tidak memiliki penanganan eksepsi di hot spot loop batin.

OK, saya berpikir sedikit tentang masalah 4-nary. Anda menginginkan solusi seperti pohon Judy untuk ini. Solusi berikutnya dapat menangani string panjang variabel; untuk panjang tetap hanya menghapus bit panjang, yang sebenarnya membuatnya lebih mudah.

Alokasikan blok 16 pointer. Bit pointer paling tidak signifikan dapat digunakan kembali, karena blok Anda akan selalu selaras. Anda mungkin menginginkan pengalokasi penyimpanan khusus untuk itu (memecah penyimpanan besar menjadi blok-blok kecil). Ada beberapa jenis blok:

• Pengkodean dengan 7 bit panjang string panjang variabel. Ketika mereka mengisi, Anda menggantinya dengan:
• Posisi mengkodekan dua karakter berikutnya, Anda memiliki 16 pointer ke blok berikutnya, diakhiri dengan:
• Pengkodean bitmap dari tiga karakter terakhir dari sebuah string.

Untuk setiap jenis blok, Anda perlu menyimpan informasi yang berbeda di LSB. Karena Anda memiliki string panjang variabel, Anda perlu menyimpan end-of-string juga, dan jenis blok terakhir hanya dapat digunakan untuk string terpanjang. Bit 7 panjang harus diganti dengan kurang ketika Anda masuk lebih dalam ke struktur.

Ini memberi Anda penyimpanan string yang diurutkan dengan cepat dan sangat efisien memori. Ini akan berperilaku seperti trie . Agar ini berfungsi, pastikan untuk membangun unit test yang cukup. Anda ingin cakupan semua transisi blok. Anda ingin memulai hanya dengan jenis blok kedua.

Untuk kinerja yang lebih banyak lagi, Anda mungkin ingin menambahkan tipe blok yang berbeda dan ukuran blok yang lebih besar. Jika blok selalu berukuran sama dan cukup besar, Anda dapat menggunakan bit lebih sedikit untuk pointer. Dengan ukuran blok 16 pointer, Anda sudah memiliki byte gratis di ruang alamat 32-bit. Lihatlah dokumentasi pohon Judy untuk jenis blok yang menarik. Pada dasarnya, Anda menambahkan kode dan waktu rekayasa untuk trade-off ruang (dan runtime)

Anda mungkin ingin memulai dengan radix langsung 256 lebar untuk empat karakter pertama. Itu memberikan tradeoff ruang / waktu yang layak. Dalam implementasi ini, Anda mendapatkan overhead memori yang jauh lebih sedikit dibandingkan dengan trie sederhana; kira-kira tiga kali lebih kecil (saya belum mengukur). O (n) tidak masalah jika konstanta cukup rendah, seperti yang Anda perhatikan ketika membandingkan dengan quicksort O (n log n).

Apakah Anda tertarik menangani dobel? Dengan urutan pendek, akan ada. Menyesuaikan blok untuk menangani jumlah memang sulit, tetapi ini bisa sangat menghemat ruang.