Сортировка строк путем сравнения (например, стандартная функция QuickSort + strcmp) может быть немного медленной, особенно для длинных строк с общим префиксом (функция сравнения занимает O(s) времени, где s — длина строки), поэтому стандартное решение имеет сложность O(s * nlog n). Известны ли более быстрые алгоритмы?
Эффективный алгоритм сортировки строк
comment
Это заставляет ваш код работать медленно? Если нет, не беспокойтесь об этом.
- person beatgammit schedule 07.08.2011
comment
Я не первый раз сталкиваюсь с этой проблемой, но да, на данный момент эта сортировка является частью, на которую моя программа тратит много времени.
- person Piotr Turek schedule 07.08.2011
Ответы (3)
Если вы знаете, что строка состоит только из определенных символов (что почти всегда так), вы можете использовать вариант BucketSort или RadixSort.
person
phimuemue
schedule
07.08.2011
Я сделал гибридное решение, чтобы сначала отсортировать суффиксы строк с помощью быстрой сортировки, а затем остальные с помощью radixsort. Это работает довольно быстро. Я не хотел использовать чистую сортировку по основанию, так как некоторые строки длинные, но суффиксы довольно разные, поэтому не помешало бы отсортировать их с помощью быстрой сортировки. Я думаю, что есть еще возможности для улучшения, но пока этого решения достаточно. Спасибо
- person Piotr Turek; 07.08.2011
Вы можете построить trie, который, я думаю, должен быть O(s*n).
person
Oliver Charlesworth
schedule
07.08.2011
@tyz: Вставка в дерево должна быть
O(s), и вам нужно сделать это n раза.
- person Oliver Charlesworth; 07.08.2011
Я должен подумать об этом, в простой реализации это кажется немного голодным по памяти.
- person Piotr Turek; 07.08.2011
@Piotr: На данный момент ваш вопрос касается только вычислительной сложности. Другие проблемы, такие как сложность памяти или эффективность кэша, часто могут доминировать!
- person Oliver Charlesworth; 07.08.2011
Пожалуйста, найдите «Sedgewick Multikey quick sort» (Седжвик написал известные учебники по алгоритмам на C и Java). Его алгоритм относительно прост в реализации и достаточно быстр. Это позволяет избежать проблемы, о которой вы говорите выше. Существует алгоритм пакетной сортировки, который претендует на более высокую скорость, но я не знаю ни одной реализации.
Есть статья Быстрая сортировка строк в C# и F#, который описывает алгоритм и содержит ссылку на код Седжвика, а также на код C#. (раскрытие: это статья и код, который я написал на основе статьи Седжвика).
person
Stefan Savev
schedule
10.10.2015
