Оперативный вид основания

197
задан Ry- 14 April 2014 в 04:44
поделиться

14 ответов

Ну, вот простая реализация вида основания MSD для DNA. Это записано в 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, в противоположность тому, чтобы быть общим, но это должно быть быстро.

Редактирование:

я стал любопытным, работает ли этот код на самом деле, таким образом, я тестировал/отлаживал его при ожидании моего собственного кода биоинформатики для выполнения. Версия выше теперь на самом деле тестируется и работает. Для 10 миллионов последовательностей 5 оснований каждый это о 3x быстрее, чем оптимизированный introsort.

58
ответ дан phuclv 23 November 2019 в 05:16
поделиться

Похоже на решение проблемы но для записи, кажется, что одна версия осуществимого оперативного вида основания является "американским Видом Флага". Это описано здесь: Технический Вид Основания . Общее представление состоит в том, чтобы сделать 2, передает каждый символ - сначала рассчитывают, сколько из каждого Вы имеете, таким образом, можно подразделить входной массив на мусорные ведра. Тогда пройдите снова, подкачав каждый элемент в корректное мусорное ведро. Теперь рекурсивно вид каждое мусорное ведро на следующей позиции символа.

1
ответ дан AShelly 23 November 2019 в 05:16
поделиться

Во-первых, думайте о кодировании своей проблемы. Избавьтесь от строк, замените их двоичным представлением. Используйте первый байт для указания на length+encoding. С другой стороны, используйте представление фиксированной длины на четырехбайтовой границе. Тогда вид основания становится намного легче. Для вида основания самая важная вещь не состоит в том, чтобы иметь обработки исключений в горячей точке внутреннего цикла.

хорошо, я думал немного больше о проблеме с 4 не. Вы хотите решение как дерево Judy для этого. Следующее решение может обработать строки переменной длины; поскольку фиксированная длина просто удаляет биты длины, который на самом деле облегчает.

Выделяют блоки 16 указателей. Младший значащий бит указателей может быть снова использован, поскольку Ваши блоки всегда будут выровненные. Вы могли бы хотеть специальное средство выделения устройства хранения данных для него (разбивание большого устройства хранения данных в меньшие блоки). Существует много различных видов блоков:

  • Кодирование 7 битами длины строк переменной длины. Как они заполняются, Вы заменяете их:
  • Положение кодирует следующие два символа, у Вас есть 16 указателей на следующие блоки, заканчивающиеся:
  • Растровое кодирование последних трех символов строки.

Для каждого вида блока, необходимо хранить различную информацию в LSBs. Поскольку у Вас есть строки переменной длины, необходимо сохранить конец строки также, и последний вид блока может только использоваться для самых длинных строк. 7 битов длины должны быть заменены меньше, поскольку Вы становитесь более глубокими в структуру.

Это предоставляет Вам довольно быстрое и очень память эффективное устройство хранения данных отсортированных строк. Это будет вести себя несколько как trie. Для получения этой работы удостоверьтесь, что создали достаточно модульных тестов. Вы хотите покрытие всех переходов блока. Вы хотите запуститься только со второго вида блока.

еще для большего количества производительности, Вы могли бы хотеть добавить различные типы блока и больший размер блока. Если блоки всегда являются тем же размером и достаточно большой, можно использовать даже меньше битов для указателей. С размером блока 16 указателей у Вас уже есть байт, свободный в 32-разрядном адресном пространстве. Смотрите на документацию дерева Judy для интересных типов блока. В основном Вы добавляете код и техническое время для пространства (и время выполнения) компромисс

, Вы, вероятно, хотите запуститься с 256 широких прямых оснований для первых четырех символов. Это обеспечивает достойный компромисс пространства/времени. В этой реализации Вы получаете намного меньше памяти наверху, чем с простым trie; это приблизительно в три раза меньше (я не имел размеры). O (n) не является никакой проблемой, если константа является достаточно низкой, как Вы заметили при сравнении O (n, регистрируют n), quicksort.

Интересно, Вы в обработке удваиваетесь? С короткими последовательностями, там будут. Адаптация блоков для обработки количеств хитра, но это может быть очень эффективно пространством.

1
ответ дан 11 revs, 2 users 67% 23 November 2019 в 05:16
поделиться

вид основания MSB dsimcha выглядит хорошим, но Nils ближе добирается до сути проблемы с наблюдением, что местность кэша - то, что уничтожает Вас в больших проблемных размерах.

я предлагаю очень простой подход:

  1. Опытным путем оценивают самый большой размер m, для которого вид основания эффективен.
  2. блоки Read m элементы за один раз, основание сортирует их и выписывает им (к буферу памяти, если у Вас есть достаточно памяти, но иначе в файл), пока Вы не исчерпываете свой вход.
  3. Сортировка с объединением получающиеся отсортированные блоки.

Сортировка с объединением является самым благоприятным для кэша алгоритмом сортировки, о котором я знаю: "Read следующий объект или от массива A или от B, затем запишите объект в буфер вывода". Это работает эффективно на ленточные накопители . Это действительно требует 2n пространство к виду n объекты, но моя ставка - то, что очень улучшенная местность кэша, которую Вы будете видеть, сделает это неважным - и если Вы использовали неоперативный вид основания, Вам было нужно то дополнительное пространство так или иначе.

обратите внимание наконец, что сортировка с объединением может быть реализована без рекурсии и на самом деле выполнения его, этот путь ясно дает понять истинный линейный шаблон доступа к памяти.

1
ответ дан j_random_hacker 23 November 2019 в 05:16
поделиться

Вы могли бы попытаться использовать trie. Сортировка данных просто выполняет итерации через набор данных и вставляет его; структура естественно отсортирована, и можно думать о ней как подобной B-дереву (кроме вместо того, чтобы делать сравнения, Вы всегда косвенность указателя использования).

Кэширующееся поведение будет способствовать всем внутренним узлам, таким образом, Вы, вероятно, не улучшите это; но можно играть с коэффициентом ветвления trie также (удостоверьтесь, что каждый узел вписывается в единственную строку кэша, выделите trie узлы, подобные "куче" как непрерывный массив, который представляет обход порядка уровня). Так как попытки являются также цифровыми структурами (O (k), вставляют/находят/удаляют для элементов длины k), у Вас должна быть конкурентоспособная производительность к виду основания.

3
ответ дан Tom 23 November 2019 в 05:16
поделиться

Я собираюсь рискнуть и предложить, чтобы Вы переключились на "кучу" / пирамидальная сортировка реализация. Это предложение идет с некоторыми предположениями:

  1. Вы управляете чтением данных
  2. , можно сделать что-то значимое с отсортированными данными, как только Вы 'начинаете' получать отсортированный.

красота "кучи"/пирамидальной сортировки состоит в том, что можно создать "кучу", в то время как Вы считываете данные, и можно начать получать результаты момент, Вы создали "кучу".

Позволяют нам отступить. Если Вам так повезло, что можно считать данные асинхронно (то есть, Вы можете отправить некоторый запрос чтения и уведомляетесь, когда некоторые данные готовы), и затем можно создать блок "кучи", в то время как Вы ожидаете следующего блока данных для вхождения - даже от диска. Часто, этот подход может проложить большую часть стоимости под землей половины Вашей сортировки позади времени, проведенного, получив данные.

, Как только Вам считали данные, первый элемент уже доступен. В зависимости от того, где Вы отправляете данные, это может быть большим. Если Вы отправляете его другому асинхронному читателю, или некоторой параллельной модели 'события' или UI, можно отправить блоки и блоки, когда Вы идете.

, Который сказал - если Вы не имеете никакого контроля над тем, как данные считаны, и они читаются синхронно, и Вам не нравятся отсортированные данные, пока они полностью не выписаны - игнорируют все это.: (

См. статьи Wikipedia:

6
ответ дан Peter Mortensen 23 November 2019 в 05:16
поделиться

Я был бы burstsort упакованное разрядное представление строк. Burstsort, как утверждают, имеет намного лучшую местность, чем виды основания, подавляя использование дополнительного пространства с пакетными попытками вместо классических попыток. Исходная бумага имеет измерения.

3
ответ дан Darius Bacon 23 November 2019 в 05:16
поделиться

Если бы Ваш набор данных является столь большим, то я думал бы, что находящийся на диске буферный подход будет лучшим:

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 общих блоков), тот способ, которым Вы делаете меньше ответвлений находящегося на диске буфера. Это может или не может улучшить производительность, таким образом экспериментировать с нею.

6
ответ дан FryGuy 23 November 2019 в 05:16
поделиться

Можно, конечно, отбросить требования к памяти путем кодирования последовательности в битах. Вы смотрите на перестановки так, для длины 2, с "ACGT", это - 16 состояний, или 4 бита. Для длины 3, это - 64 состояния, которые могут быть закодированы в 6 битах. Таким образом, это похоже на 2 бита для каждой буквы в последовательности, или приблизительно 32 бита для 16 символов как Вы сказали.

, Если существует способ сократить количество допустимых 'слов', дальнейшее сжатие может быть возможным.

Так для последовательностей длины 3, можно было создать 64 блока, возможно, размерный uint32 или uint64. Инициализируйте их для обнуления. Выполните итерации через свой очень очень большой список 3 символьных последовательностей и закодируйте их как выше. Используйте это в качестве нижнего индекса и увеличьте тот блок.
Повторение это, пока все Ваши последовательности не были обработаны.

Затем, повторно создают Ваш список.

Выполняют итерации через эти 64 блока в порядке, для количества, найденного в том блоке, генерируют это много экземпляров последовательности, представленной тем блоком.
, когда все блоки были выполнены с помощью итераций, у Вас есть свой сортированный массив.

последовательность А 4, добавляют 2 бита, таким образом, было бы 256 блоков. Последовательность 5, добавляют 2 бита, таким образом, было бы 1 024 блока.

В какой-то момент количество блоков приблизится к Вашим пределам. При чтении последовательностей из файла, вместо того, чтобы сохранить их в памяти, больше памяти было бы доступно для блоков.

я думаю, что это было бы быстрее, чем выполнение вида на месте, поскольку блоки, вероятно, будут соответствовать в Вашем рабочем наборе.

Вот взлом, который показывает технику

#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;
}
8
ответ дан phuclv 23 November 2019 в 05:16
поделиться

Я никогда не видел оперативный вид основания, и от природы вида основания я сомневаюсь, что это намного быстрее, чем неуместное вид, пока временный массив вписывается в память.

Причина:

сортировка делает линейное чтение на входном массиве, но все записи будут почти случайны. От определенного N вверх это сводится к неудачному обращению в кэш на запись. Это неудачное обращение в кэш - то, что замедляет Ваш алгоритм. Если это существует или не не изменит этот эффект.

я знаю, что это не ответит на Ваш вопрос непосредственно, но если сортировка является узким местом, можно хотеть взглянуть на почти сортировка алгоритмы как шаг предварительной обработки (страница Wiki на мягкой "куче" могла запустить Вас).

, Который мог дать очень хорошее повышение местности кэша. Учебник, неуместный вид основания, будет тогда работать лучше. Записи все еще будут почти случайны, но по крайней мере они будут кластеризировать вокруг тех же блоков памяти и увеличения как такового отношение удачного обращения в кэш.

я понятия не имею, удается ли это на практике все же.

Btw: Если Вы имеете дело со строками DNA только: можно сжать символ в два бита и упаковать данные довольно много. Это сократит требование к памяти фактором четыре по наивному представлению. Обращение становится более сложным, но ALU Вашего ЦП имеет много времени для расходов во время всех неудачных обращений в кэш так или иначе.

20
ответ дан Nils Pipenbrinck 23 November 2019 в 05:16
поделиться

Radix-Sort не учитывает кеширование и не является самым быстрым алгоритмом сортировки для больших наборов. Вы можете посмотреть:

Вы также можете использовать сжатие и кодировать каждую букву вашей ДНК на 2 бита перед сохранением в массив сортировки.

2
ответ дан 23 November 2019 в 05:16
поделиться

С точки зрения производительности вам, возможно, захочется взглянуть на более общие алгоритмы сортировки сравнения строк.

В настоящее время вам приходится касаться каждого элемента каждой строки, но вы можете добиться большего!

В частности, для этого случая очень хорошо подходит пакетная сортировка . В качестве бонуса, поскольку пакетная сортировка основана на попытках, она смехотворно хорошо работает для небольших размеров алфавита, используемых в ДНК / РНК, поскольку вам не нужно строить какой-либо тройной узел поиска, хэш или другую схему сжатия trie-узла в реализацию trie. Попытки также могут быть полезны для вашей конечной цели, подобной массиву суффиксов.

Приличная реализация burstsort общего назначения доступна в кузнице исходного кода по адресу http://sourceforge.net/projects/burstsort/ ] - но это не на месте.

Для сравнения, реализация C-burstsort, описанная на http://www.cs.mu.oz.au/~rsinha/papers/SinhaRingZobel-2006. pdf выполняет тесты в 4-5 раз быстрее, чем быстрая сортировка и сортировка по основанию для некоторых типичных рабочих нагрузок.

4
ответ дан 23 November 2019 в 05:16
поделиться

Вы захотите взглянуть на Крупномасштабную обработку последовательности генома докторами Касахарой и Моришитой.

Строки, состоящие из четырех нуклеотидных букв A, C, G и T, могут быть специально закодированы в Интегралы для гораздо более быстрой обработки. Сорт Радикс - один из многих алгоритмов, обсуждаемых в книге; вы должны уметь адаптировать принятый ответ на этот вопрос и увидеть значительное улучшение производительности.

4
ответ дан 23 November 2019 в 05:16
поделиться

« Радиксная сортировка без лишнего пробела » - это документ, посвященный вашей проблеме.

4
ответ дан 23 November 2019 в 05:16
поделиться
Другие вопросы по тегам:

Похожие вопросы: