Эффективная сортировка многих строк параллельно для представления

Question

Я столкнулся с проблемой, когда у меня есть массивный список информации (287 843 элементов), которые необходимо сортировать для отображения. Что более эффективно, для использования самоорганизующегося красно-черного двоичного дерева, чтобы сортировать их или строить массив, а затем сортировать? Мои ключи - это строки, если это помогает. Этот алгоритм должен использовать несколько процессорных ядер.

Спасибо!

Answer 1

Это действительно зависит от особенностей вашей установки. Если у вас многоядерный аппарат, вы можете, скорее всего, отсортировать строки очень быстро, используя parallel version of quicksort, в котором каждый рекурсивный вызов выполняется параллельно друг другу. Со многими ядрами это может занять уже быструю сортировку и сделать ее значительно быстрее. Другие алгоритмы сортировки, такие как сортировка слияния, также могут быть распараллелены, хотя параллельная quicksort имеет то преимущество, что требует меньше дополнительной памяти. Поскольку вы знаете, что вы сортируете строки, вы также можете посмотреть в parallel radix sort, что потенциально может быть чрезвычайно быстрым.

Большинство двоичных деревьев поиска не могут быть многопоточными, поскольку операции по балансировке часто требуют одновременного изменения нескольких частей дерева, поэтому сбалансированное красное/черное дерево не может быть лучшим подходом здесь. Тем не менее, вы можете посмотреть в concurrent skiplist, который представляет собой структуру данных, которая может быть выполнена для эффективной работы параллельно. Есть несколько новых деревьев двоичного поиска, предназначенных для параллелизма, которые иногда превосходят skiplist (here is one such data structure), хотя я ожидаю, что будет меньше существующих реализаций и обсуждения этих новых структур.

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

Надеюсь, это поможет!

Answer 2

Предполагая, что вы читаете этот список из файла или какого-либо другого источника данных, кажется совершенно правильным прочитать все это в массиве, а затем отсортировать его. Если у вас есть какой-то GUI-интерфейс, кажется еще более целесообразным выполнять чтение и сортировку в потоке, имея графический интерфейс в состоянии ожидания. Сохранение дерева значений звучит осуществимо только в том случае, если вы собираетесь делать много удалений/вставок, что сделает массив менее полезным в этом случае.

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