Как повысить производительность при работе с двумя картами в Java - PullRequest
Новая
       148

Как повысить производительность при работе с двумя картами в Java

2 голосов
/ 14 июля 2020

У меня есть две карты - Map<String, List<String>> input и еще одна Map<String, List<String>> output.

карта ввода 

{A=[Apple.txt, Axe.txt, Aid.txt], B=[Ball.txt, Boy.txt,Box.txt], C=[Cow.txt,Cob.txt]}

карта вывода 

{A=[Apple.txt, Axe.txt, Aid.txt], B=[Ball.txt, Boy.txt]}

Мне нужно чтобы найти отсутствующую пару "ключ-значение" для выходной карты. 

 expected output - B= [Box.txt], C=[Cow.txt,Cob.txt]

Мне нужно определить, что в выходной карте отсутствует Box.txt для ключа B и отсутствует пара "C".

Мой текущий подход: я использую один forEach (временная сложность O(n)) и один поток набора записей (временная сложность: O(m)) для двух карт, которые вызывают O(n*m) временную сложность. 

inputMap.forEach((key,value) ->
    {
    final List<Path> countrifiedFolderList = outputFileMap.entrySet().stream()
            .filter(entry -> entry.getKey().contains(key))
            .filter(files -> !files.getValue().contains(inputFile)).map(Map.Entry::getKey)
            .collect(Collectors.toList());

    if (!countrifiedFolderList.isEmpty())
    {....do processing
    }

Мне нужно усилить проблему производительности, так как карта содержит огромное количество данных. Мне нужно получить результат менее чем за O (n * m) временную сложность.

Ответы [ 3 ]

1 голос
/ 14 июля 2020

Почему бы и нет: 

map1.keySet().containsAll(map2.keySet());

Обновление

С одним потоком: 

Map<String, List> result = input.entrySet().stream()
        .filter(entry -> !output.keySet().contains(entry.getKey()) ||
                !output.get(entry.getKey()).containsAll(entry.getValue()))
        .map(entry -> {
                List<String> expected = new ArrayList<>(entry.getValue());
                List<String> current = output.get(entry.getKey());
                expected.removeAll(current != null ? current : List.of());
                return Map.entry(entry.getKey(), expected);
            })
        .collect(Collectors.toMap(Entry::getKey, Entry::getValue));

Если вы хотите измерить производительность, я бы Предлагаем провести микротест, используя вашу структуру данных, размер выборки, оборудование и т. д. c. Если вас интересует микротест, я бы предложил использовать JMH .

0 голосов
/ 15 июля 2020

Несколько вещей, которые могли бы немного упростить решение, были бы, учитывая, что карта output является Map<String, Set<String>>, а затем в качестве окончательного результата можно рассматривать ключи, которые полностью присутствуют в выходной карте, как пустые []. 

Map<String, List<String>> lookUpExclusives(Map<String, List<String>> input,
                                                  Map<String, Set<String>> output) {
    return input.entrySet().stream()
            .collect(Collectors.toMap(Map.Entry::getKey,
                    e -> e.getValue().stream()
                            .filter(val -> !output.getOrDefault(e.getKey(),
                                    Collections.emptySet()).contains(val))
                            .collect(Collectors.toList())));
}

Это вернет {A=[], B=[Box.txt], C=[Cow.txt, Cob.txt]} из метода. С точки зрения сложности, это будет M количество раз для каждого элемента в значении записи входной карты и для каждой из N записей, так что и O(N*M), но это должно быть максимально возможная оптимизация сложности выполнения.

Теперь, когда у вас есть эта сложная среда выполнения, вы можете дополнительно связать другую потоковую операцию для фильтрации записей, которые не имеют соответствующих значений, оставшихся в результате (например, A=[] ). Этого можно достичь, добавив следующий код к вышеуказанному конвейеру после первого collect: 

.entrySet().stream()
.filter(e -> !e.getValue().isEmpty())
.collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

Это приводит к сложности только как O(N*M) + O(N), что может быть эффективно выражено как * Только 1020 *. Преимущество здесь в том, что вы получаете результат в формате, который вы ожидали, например, {B=[Box.txt], C=[Cow.txt, Cob.txt]}.

0 голосов
/ 15 июля 2020

Если это TreeMaps, то их ключи уже отсортированы. Вы можете пройти оба списка вместе за O (n). Решение Oboe - лучшее, что вы получите с HashMaps, и будет O (n * log2 (m)).

...