Массив строк содержит только анаграммы? - PullRequest
5 голосов
/ 04 октября 2011

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

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

A Cab Deed Huffiest Lolls Loll
Действие кабины Хаффист Лоллс Минноу
Действие Каба тасует миллион Миллионов
Действие такси тасует миллион город

Программа должна вернуть True. Для ввода:

Кабо-деяние Хаффайст Лоллс Лолл
Акция Такси Хаффист Лоллс Минноу привет
Действие Каба тасует миллион Миллионов
Действие такси тасует миллион город

вывод должен быть False (из-за второй строки, конечно).

Теперь то, что я подумал, довольно просто:

  • Я создаю 2 HashMap: ref и cur.
  • Я разбираю первую строку текста, заполняя исх. Я буду считать только буквы алфавита.
  • для каждой строки, я разбираю строку в cur и проверяю, есть ли cur.equals (ref): если да, возвращает false
  • если я дойду до конца текста, это означает, что каждая строка является анаграммой каждой другой строки, поэтому я возвращаю true.

И ... это было бы так. Я попробовал это с вводом текста в 88000 строк, и он работает довольно быстро.

Есть комментарии? Предложения? Оптимизации?

Большое спасибо за помощь.

Ответы [ 3 ]

5 голосов
/ 04 октября 2011

Другой вариант:

  1. Убрать из строки все символы, которые вас не интересуют (пунктуация, пробел)
  2. Сделать его строчными
  3. Сортироватьстрока
  4. Сравнить со строкой ссылки (с .equals)

Я подозреваю, что ваш путь быстрее, хотя.

РЕДАКТИРОВАТЬ:

С@nibot не согласен с тем, что я даже предложил это, и я не из тех, кто спорит взад и вперед без доказательств, вот три решения .

Они все реализованы очень схожим образом:

  1. Преобразование строки в нижний регистр
  2. Игнорирование неалфавитных символов
  3. ?
  4. Проверка результата 3. совпадает с результатом первой строки

The?часть является одной из:

  • Создание HashMap символов
  • Сортировка символов
  • Создание массива 26-int (окончательное решение хеш-таблицы,но работает только для латинского алфавита)

Я запустил их все с этим:

public static void time(String name, int repetitions, Function function,
        int expectedResult) throws Exception {
    long total = 0;
    for (int i = 0; i < repetitions; i++) {
        System.gc();
        long start = System.currentTimeMillis();
        int result = function.call();
        long end = System.currentTimeMillis();
        if (result != expectedResult) {
            System.out.println("Oops, " + name + " is broken");
            return;
        }
        total += end - start;
    }
    System.out.println("Executution of " + name + " took "
            + (total / repetitions) + " ms on average");
}

Мой файл похож на тот, который опубликовал ОП, но сделал значительно дольше, снеанаграмма около 20 строк от конца, чтобы гарантировать, что все алгоритмы работают.

Я последовательно получаю результаты, подобные этому:

Execution of testWithHashMap took 158 ms on average
Execution of testWithSorting took 76 ms on average
Execution of testWithArray took 56 ms on average

Один HashMap может быть значительно улучшен, если:

  • Был способ сделать HashMap<char, int>
  • Был способ указать значение по умолчанию в HashMap и способполучить-и-увеличить (так что будет только один поиск вместо 2)

Но их нет в стандартной библиотеке, поэтому я их игнорирую (как и большинство программистов, использующихЯва).

Мораль этой истории в том, что большой О - это не все.Необходимо учитывать накладные расходы и размер n .В этом случае n довольно мало, а издержки HashMap значительны.С более длинными линиями это, вероятно, изменится, но, к сожалению, мне не хочется выяснять, где находится точка безубыточности.

И если вы все еще не верите мне, учтите, что GCC использует сортировка вставок в некоторых случаях в стандартной библиотеке C ++.

3 голосов
/ 04 октября 2011

Предполагая, что ваш HashMap является отображением из (символ) -> (количество вхождений в строке), у вас это в значительной степени есть.

Я предполагаю, что вы должны игнорировать пробел и пунктуациюи обрабатывать прописные и строчные буквы как одинаковые.Если вы не используете никаких языков, кроме английского, то HashMap является излишним: вы можете просто использовать массив из 26 отсчетов, представляющих A..Z.Если вам нужно поддерживать Unicode, тогда проблема, конечно, намного сложнее, поскольку вам нужно не только иметь дело с, возможно, тысячами различных типов букв, но вы также должны определить «букву» (к счастью, существуют данные о свойствах символов, которыепомогает в этом) и 'строчные / прописные буквы' (обратите внимание, что в некоторых языках нет регистра, некоторые могут отображать две строчные буквы в одну заглавную или наоборот ...).Не говоря о нормализации:)

2 голосов
/ 04 октября 2011

Встраивание ответа @Karl Knechtel (и решение проблемы поддержки нескольких алфавитов):

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

  • Создайте одну реализацию интерфейса AnagramKey, которая внутренне использует int[] для представления количества символов.

  • Создайте вторую реализацию интерфейса AnagramKey, которая использует HashMap<Character, Integer> для представления количества символов.

  • Создайте соответствующие фабричные интерфейсы.

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

Примечания:

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

  2. Плотность безубыточностипри котором int[] использует меньше места, чем HashMap<Character, Integer> асимптотически около 1 символа из 15 по всему диапазону символов в вашем массиве счетчиков.(Каждая запись в HashMap с этими типами ключ / значение занимает область из 15 32-битных слов.) И это не учитывает накладные расходы узла HashMap и узла хеш-массива ...

  3. Если вы установите ограничения на длину анаграмм, вы можете сэкономить больше места, используя short[] или даже byte[] для подсчета символов.

...