Блог

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

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

Дело о такси, Самые обиженные пескари
, Дело о такси, самые обиженные пескари
, Дело о такси
, перетасовывает миллион, Дело о такси, перетасовывает миллионный город.

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

Дело о такси Самые обиженные гольяны
, Дело о такси Самые обиженные гольяны, привет
, Дело о такси перетасовывает миллион
, Дело о такси перетасовывает миллионный город.

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

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

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

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

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

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

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

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

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

Редактировать:

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

Все они реализованы очень похоже:

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

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

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

Я запустил их все с помощью этого:

 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");
}
  

Мой файл похож на тот, который опубликовал OP, но сделан значительно длиннее, с неанаграммой примерно в 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>
• Был способ указать значение по умолчанию в a HashMap и способ получения и увеличения (поэтому вместо 2 будет только один поиск)

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

Мораль истории в том, что big O — это еще не все. Вам нужно учитывать накладные расходы и размер n . В этом случае n довольно мало, а накладные расходы a HashMap значительны. С более длинными строками это, вероятно, изменится, но, к сожалению, мне не хочется выяснять, где находится точка безубыточности.

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

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

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

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

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

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

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

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

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

Примечания:

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

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

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