Java 8 Streams - как сравнить элементы? - PullRequest
Новая
       98

Java 8 Streams - как сравнить элементы?

2 голосов
/ 02 декабря 2019

Я хочу найти анаграммы в файле .txt с помощью Java Stream. Вот что у меня есть: 

try (InputStream is = new URL("http://wiki.puzzlers.org/pub/wordlists/unixdict.txt").openConnection().getInputStream();
     BufferedReader reader = new BufferedReader(new InputStreamReader(is));
     Stream<String> stream = reader.lines()) {

И метод для анаграмм: 

public boolean isAnagram(String firstWord, String secondWord) {
    char[] word1 = firstWord.replaceAll("[\\s]", "").toCharArray();
    char[] word2 = secondWord.replaceAll("[\\s]", "").toCharArray();
    Arrays.sort(word1);
    Arrays.sort(word2);
    return Arrays.equals(word1, word2);
}

Как проверить, является ли слово в unixdict.txt анаграммой с использованием Java 8 Stream? Можно ли сравнить одно слово со всеми словами в потоке?

Ответы [ 2 ]

6 голосов
/ 02 декабря 2019

Когда вы хотите найти все анаграммы, не рекомендуется пытаться сравнивать одно слово со всеми другими словами, так как в конечном итоге вы сравниваете каждое слово с каждым другим словом, которое известно как квадратичное сложность времени . Для обработки 1000 слов вам потребуются миллионы сравнений, для обработки 100 000 слов - 10 000 000 000 сравнений и т. Д.

Вы можете изменить метод isAnagram, чтобы обеспечить ключ поиска для структур данных, таких как HashMap: 

static CharBuffer getAnagramKey(String s) {
    char[] word1 = s.replaceAll("[\\s]", "").toCharArray();
    Arrays.sort(word1);
    return CharBuffer.wrap(word1);
}

Класс CharBuffer оборачивает массив char[] и предоставляет необходимые методы equals и hashCode без копирования содержимого массива, что делает его предпочтительным для создания нового String.

В качестве примечания, .replaceAll("[\\s]", "") можно было бы упростить до .replaceAll("\\s", ""), и то, и другое исключило бы все пробельные символы, но пример ввода вашего вопроса вообще не имеет пробельных символов. Чтобы удалить все несловарные символы, такие как апострофы и амперсанды, вы можете использовать s.replaceAll("\\W", "").

Затем вы можете обработать все слова, чтобы найти анаграммы за один линейный проход, например 

URL srcURL = new URL("http://wiki.puzzlers.org/pub/wordlists/unixdict.txt");
try(InputStream is = srcURL.openStream();
    BufferedReader reader = new BufferedReader(new InputStreamReader(is));
    Stream<String> stream = reader.lines()) {

    stream.collect(Collectors.groupingBy(s -> getAnagramKey(s)))
        .values().stream()
        .filter(l -> l.size() > 1)
        .forEach(System.out::println);
}

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

stream.collect(Collectors.groupingBy(s -> getAnagramKey(s)))
    .values().stream()
    .filter(l -> l.size() > 1)
    .sorted(Collections.reverseOrder(Comparator.comparingInt(List::size)))
    .limit(10)
    .forEach(System.out::println);
0 голосов
/ 02 декабря 2019

Я думаю, что лучшим вариантом может быть использование сборщика нескольких карт для преобразования потока в Guava multimap с использованием отсортированной версии строки в качестве ключа к карте. См. Самый простой способ создания MultiMap из гуавы из потока java8 , чтобы узнать, как это сделать. Если вам нужны только полученные наборы анаграмм, вы можете использовать multimap.asMap().entrySet().stream()... для фильтрации и сбора результатов в соответствии с вашими потребностями.

...