Лучший способ сортировки длинного списка строк

Question

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

Строки могут быть числовыми, альфа-, буквенно-цифровыми и т. Д. Меня не интересует поведение сортировки, такое как алфавитно-цифровая сортировка v/s.

Некоторые способы ниже, о которых я могу думать.

1. Использование кода ex: .Net Framework's Arrays.Sort(). Я думаю, что это работает, так это то, что хэш-коды для строк вычисляются, а строка вставляется в правильное положение, используя двоичный поиск.

2. Использование базы данных (например: MS-sql). Я этого не делал. Я не знаю, насколько это было бы эффективно.

3. Использование структуры данных дерева префиксов, таких как trie. Сортировка требует обхода всех trieNodes trie tree с использованием DFS (поиск глубины первого поиска) - O (| V | + | E |). (Поиск принимает O (l) время, где l - длина строки для сравнения).

Любые другие способы или структуры данных?

Answer 1

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

Если индекс отсутствует, база данных все равно сможет вам помочь. Если вы выберете только первые k строк для некоторого небольшого постоянного числа k, например 100. Когда вы используете ORDER BY с предложением LIMIT, он позволяет SQL Server использовать специальную оптимизацию с именем TOP N SORT, которая выполняется в линейном времени, а не O (n log (n)) времени.

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

Answer 2

Я нашел this paper, который использует структуру данных trie для эффективного сортировки больших наборов строк. Однако я не рассматривал это подробно.

Answer 3

Radix sort также может быть хорошим вариантом, если строки не очень длинны, например. Список имен

Answer 4

Предположим, у вас есть большой список строк, и длина списка является Н.

Использование сравнения на основе алгоритма сортировки, как, пирамидальная сортировка слиянием или Quicksort даст вам

где n - размер списка, а d - максимальная длина для всех строк в списке.

В этом случае мы можем попытаться использовать сортировку Radix. Пусть b - основание и d - длина максимальной строки, тогда мы можем показать, что время работы с использованием сортировки по методу radix равно .

Кроме того, если строки говорят строчные английский алфавиты время работы является

Источник: MIT Opencourse алгоритмы лекция проф. Эрик Демейн.