Radix-сортировка для строк произвольной длины - PullRequest
Новая
       50

Radix-сортировка для строк произвольной длины

1 голос
/ 10 сентября 2010

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

Ответы [ 5 ]

2 голосов
/ 10 сентября 2010

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

Вставка, поиск и удаление - все O(k * log(a)), где a - размер вашего алфавита (количество возможных значений для символа). Так как a является константой, то же самое происходит и с log(a), поэтому вы получите алгоритм сортировки O(n * k).

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

1 голос
/ 10 сентября 2010
0 голосов
/ 10 сентября 2010

Редактировать: в этих утверждениях, которые я делал ранее, есть точка, но в целом эта точка неверна.

Сортировка по радикалам - это неправильная сортировка для большого числа строк.Для таких вещей, как 

I really like squirrels. Yay, yay, yay!
I really like blue jays. Yay, yay, yay!
I really like registers. Yay, yay, yay!

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

Используйте быструю сортировку, слияние или тому подобное.(Быстрая сортировка обычно работает лучше и занимает меньше памяти, но во многих примерах производительность O (N ^ 2) в худшем случае почти не встречается на практике; Mergesort работает не так хорошо, но обычно реализуется для обеспечения стабильности, и этолегко сделать часть в памяти и часть на диске.) То есть, использовать встроенную функцию сортировки.

Редактировать: Ну, получается, что по крайней мере на очень больших файлах с длинными повторениями вВ начале (например, исходный код) и со многими одинаковыми строками (фактически 100-кратными повторениями) сортировка по основанию начинает конкурировать с быстрой сортировкой.Я удивлен!Но, в любом случае, вот код, который я использовал для реализации радикальной сортировки.Он написан на Scala, а не на C #, но я написал его в довольно итеративном стиле, поэтому должно быть достаточно очевидно, как все работает.Единственные два хитрых бита в том, что (a(i)(ch) & 0xFF) предназначен для извлечения 0-255 байт из массива массивов байтов (байты подписаны), что counts.scanLeft(0)(_ + _) формирует накопленную сумму отсчетов, начиная с нуля (а затем indices.clone.take(257) принимает все, кроме последнего), и что Scala допускает несколько списков параметров (поэтому я отделил всегда предоставленный аргумент от аргументов, которые имеют значения по умолчанию, которые используются в рекурсии).Вот оно: 

def radixSort(a: Array[Array[Byte]])(i0: Int = 0, i1: Int = a.length, ch: Int = 0) {
  val counts = new Array[Int](257)
  var i = i0
  while (i < i1) {
    if (a(i).length <= ch) counts(0) += 1
    else { counts((a(i)(ch)&0xFF)+1) += 1 }
    i += 1
  }
  val indices = counts.scanLeft(0)(_ + _)
  val starts = indices.clone.take(257)
  i = i0
  while (i < i1) {
    val bucket = if (a(i).length <= ch) 0 else (a(i)(ch)&0xFF)+1
    if (starts(bucket)+i0 <= i && i < starts(bucket)+i0+counts(bucket)) {
      if (indices(bucket) <= i) indices(bucket) = i+1
      i += 1
    }
    else {
      val temp = a(indices(bucket)+i0)
      a(indices(bucket)+i0) = a(i)
      a(i) = temp
      indices(bucket) += 1
    }
  }
  i = 1
  while (i < counts.length) {
    if (counts(i)>1) {
      radixSort(a)(i0+starts(i),i0+starts(i)+counts(i),ch+1)
    }
    i += 1
  }
}

И время таково, что при 7М строках исходного кода (100-кратное дублирование по 70 тыс. Строк) радикальная сортировка связывает встроенную библиотечную сортировку и выигрывает после этого.

0 голосов
/ 10 сентября 2010

Сколько их, миллион?

Встроенное List<string>.Sort() в среднем принимает O (n * log (n)).

log2 (10 ^ 6) ~ = 20, что не намного медленнее, чем O (n) для 10 ^ 6 элементов.Если ваши строки длиннее 20 символов, сортировка по основанию O (n * k) будет «медленнее».

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

0 голосов
/ 10 сентября 2010

Перегрузки String.Compare () используют такое сравнение строк.Посмотрите, что вам нужно, чтобы передать это в свой алгоритм сортировки.

ОБНОВЛЕНИЕ

Это реализация: 

[MethodImpl(MethodImplOptions.InternalCall)]
internal static extern int nativeCompareString(int lcid, string string1, int offset1, int length1, string string2, int offset2, int length2, int flags);

Трудно победитьвстроенная неуправляемая реализация с собственной реализацией.

...