Я попробовал несколько решений с использованием наборов и заставил каждое из них запускаться 10 миллионов раз для тестирования с использованием вашего примерного массива:
private static String[] input = {"tea", "ate", "eat", "apple", "java", "vaja", "cut", "utc"};
Во-первых, метод, который я использовал для вызова этих алгоритмов:
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
for (int x = 0; x < 10000000; x++) {
Set<String> confirmedAnagrams = new HashSet<>();
for (int i = 0; i < (input.length / 2) + 1; i++) {
if (!confirmedAnagrams.contains(input[i])) {
for (int j = i + 1; j < input.length; j++) {
if (isAnagrams1(input[i], input[j])) {
confirmedAnagrams.add(input[i]);
confirmedAnagrams.add(input[j]);
}
}
}
}
output = confirmedAnagrams.toArray(new String[confirmedAnagrams.size()]);
}
long endTime = System.currentTimeMillis();
System.out.println("Total time: " + (endTime - startTime));
System.out.println("Average time: " + ((endTime - startTime) / 10000000D));
}
Затем я использовал алгоритмы, основанные на HashSet символов. Я добавляю каждый символ каждого слова в HashSet, и если HashSet не будет длиной начальных слов, это будет означать, что они не являются анаграммами.
Мои алгоритмы и время их выполнения:
Алгоритм 1:
private static boolean isAnagrams1(String x, String y) {
if (x.length() != y.length()) {
return false;
} else if (x.equals(y)) {
return true;
}
Set<Character> anagramSet = new HashSet<>();
for (int i = 0; i < x.length(); i++) {
anagramSet.add(x.charAt(i));
anagramSet.add(y.charAt(i));
}
return anagramSet.size() != x.length();
}
Это имеет время выполнения:
Total time: 6914
Average time: 6.914E-4
Алгоритм 2
private static boolean isAnagrams2(String x, String y) {
if (x.length() != y.length()) {
return false;
} else if (x.equals(y)) {
return true;
}
Set<Character> anagramSet = new HashSet<>();
char[] xAr = x.toCharArray();
char[] yAr = y.toCharArray();
for (int i = 0; i < xAr.length; i++) {
anagramSet.add(xAr[i]);
anagramSet.add(yAr[i]);
}
return anagramSet.size() != x.length();
}
Имеет время выполнения:
Total time: 8752
Average time: 8.752E-4
Алгоритм 3
Для этого алгоритма я решил отправить Set, поэтому я создаю его только один раз для каждого цикла и очищаю после каждого теста.
private static boolean isAnagrams3(Set<Character> anagramSet, String x, String y) {
if (x.length() != y.length()) {
return false;
} else if (x.equals(y)) {
return true;
}
for (int i = 0; i < x.length(); i++) {
anagramSet.add(x.charAt(i));
anagramSet.add(y.charAt(i));
}
return anagramSet.size() != x.length();
}
Имеет время выполнения:
Total time: 8251
Average time: 8.251E-4
Алгоритм 4
Этот алгоритм не мой, он принадлежит Pratik Upacharya, который тоже ответил на вопрос, чтобы я мог сравнить:
private static boolean isAnagrams4(String stringOne, String stringTwo) {
char[] first = stringOne.toLowerCase().toCharArray();
char[] second = stringTwo.toLowerCase().toCharArray();
// if length of strings is not same
if (first.length != second.length) {
return false;
}
int[] counts = new int[26];
for (int i = 0; i < first.length; i++) {
counts[first[i] - 97]++;
counts[second[i] - 97]--;
}
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
return false;
}
}
return true;
}
Имеет время выполнения:
Total time: 5707
Average time: 5.707E-4
Конечно, эти времена выполнения различаются для каждого запуска теста, и для правильного тестирования требуется больший набор примеров и, возможно, больше его итераций.
* Отредактировано, поскольку я допустил ошибку в своем первоначальном методе, алгоритм Pratik Upacharya's кажется более быстрым.
person
Propagandian
schedule
06.07.2016
char[]обратно вString, а затем выполнятьcharAt(), вы можете напрямую сравнивать символы в массивах. - person QBrute schedule 06.07.2016