Другой вариант:
- Убрать из строки все символы, которые вас не интересуют (пунктуация, пробел)
- Сделать его строчными
- Сортироватьстрока
- Сравнить со строкой ссылки (с
.equals
)
Я подозреваю, что ваш путь быстрее, хотя.
РЕДАКТИРОВАТЬ:
С@nibot не согласен с тем, что я даже предложил это, и я не из тех, кто спорит взад и вперед без доказательств, вот три решения .
Они все реализованы очень схожим образом:
- Преобразование строки в нижний регистр
- Игнорирование неалфавитных символов
- ?
- Проверка результата 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
может быть значительно улучшен, если:
Но их нет в стандартной библиотеке, поэтому я их игнорирую (как и большинство программистов, использующихЯва).
Мораль этой истории в том, что большой О - это не все.Необходимо учитывать накладные расходы и размер n .В этом случае n довольно мало, а издержки HashMap
значительны.С более длинными линиями это, вероятно, изменится, но, к сожалению, мне не хочется выяснять, где находится точка безубыточности.
И если вы все еще не верите мне, учтите, что GCC использует сортировка вставок в некоторых случаях в стандартной библиотеке C ++.