Самый быстрый способ объединения двух строк

Question

Я ищу быстрый способ сделать объединение (в терминах теории множеств) символов двух строк. Например, 'copy' union 'creepy' должен указывать 'copyre'. Мне нужно получить все буквы, используемые в файле, состоящем из много коротких строк (думаю, 50 вершин вершин).

На данный момент я:

• взять строку чтения из файла
• перебирать свои письма и искать для каждого из них в наборе используемых букв (хранится в виде отсортированного строки) с помощью двоичного поиск.

Это должно обрабатывать символы юникода, поэтому создание таблицы с булерами и маркировка каждой из появившихся букв не сработает. Любые идеи, как сделать это быстрее?

Answer 1

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

алгоритм будет выглядеть следующим образом:

for (int i = 0; i < len; i++) 
    bits[mem[i]] = true; 

Это линейное время. Думаю, это не улучшится. Возможно, вы сможете получить некоторый постоянный коэффициент, используя умное выравнивание и распараллеливание ЦП, что зависит от размера проблемы.

Answer 2

Возьмите первую строку, и поместите каждый символ в нем несколько хеш-хэдов, как java.util.HashSet.

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

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

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

Одним из примеров такого целочисленного набора является Zach Tellman's data.int-map для Clojure. Он описывается как «Простой порт Окасаки и Гилла« Быстрое слияние целых карт », который можно найти по адресу http://ittc.ku.edu/~andygill/papers/IntMap98.pdf». Работа Окасаки и Гилла, похоже, реализована в Хаскелле.

Возможно, существуют аналогичные эффективные реализации целых множеств на других языках.

Answer 3

Когда вы говорите о размерах ввода с верхней границей чего-то вроде 50 символов юникода (и я предполагаю, что ваш средний случай намного меньше), тогда выходит много алгоритмических опций. Обычно мы смотрим на голые металлические микро-оптимизации. При таких минимальных размерах ввода пузырь-сортировка может фактически превосходить quicksort.

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

Если вы можете предварительно отсортировать обе строки заранее (например: уже хранить отсортированные строки в вашем файле), то вы, вероятно, сможете улучшить, так как объединение одного из двух отсортированных строк можно найти в одном линейном проходе (просто используйте два указателя/индексы). Это предполагает, что вы можете отсортировать все это заранее за пределами этого критического цикла.

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

Далее может быть многопоточность, но для этого маршрута вам, вероятно, нужна дополнительная работа для каждого потока, чем вычисление соединения между двумя подростковыми строками. Накладные расходы на планирование, вероятно, перевесят преимущества здесь, поэтому вы хотите, чтобы каждая нить/параллельная итерация вычисляла объединения нескольких (возможно, довольно многих, например, сотен) строк.

Answer 4

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

An (непроверенные) пример в Java будет

String copy = "copy"; 
String creepy = "creepy"; 
char[] chars = (copy + creepy).toCharArray(); 

java.util.Arrays.sort(chars); //puts duplicates side by side 

int currentChar = -1; //no risk of initial collision since chars >= 0 
int setSize = 0;  //set size, pointer when "compacting" the set 

//ignore duplicates, reuses the char[] - garbage in the end! 

for (int pos = 0; pos < chars.length; pos++) { 
    if (currentChar != (int)chars[pos]) { 
     chars[setSize] = chars[pos]; 
     setSize++; 
     currentChar = chars[pos]; 
    } 
} 

// please note that Strings are both immutable 
// and can be held in memory for long times, don't allocate them for 
// intermediate results if you can avoid it. 

String result = new String(java.util.Arrays.copyOf(chars, setSize));