Guava Multimaps.filter показывает низкую производительность по сравнению с NavigableMap.subMap () - PullRequest
Новая
       33

Guava Multimaps.filter показывает низкую производительность по сравнению с NavigableMap.subMap ()

0 голосов
/ 08 декабря 2018

У меня есть Guava TreeMultimap, который отображает Date ключи на какое-то значение.

Я хочу иметь возможность отфильтровать это map, чтобы найти, где ключ находится в определенном диапазоне дат.

Поскольку map отсортировано, должно быть возможно сделать это очень быстро, не оценивая все ключи, но когда я впервые написал это, используя Multimaps.filterKeys, это было намного медленнее, чем ожидалось, предполагая, что оно оцениваеткаждый ключ.Когда я переписал это для использования NavigableMap.subMap(), производительность была фантастической, и там, где я ожидал, это будет.

Синтаксис Multimaps.filterKeys гораздо приятнее, и это то, что я хотел бы использовать, тем более что яуже работает с Multimap.

Пожалуйста, посмотрите минимизированный пример того, что я делаю ниже: 

import java.text.MessageFormat;
import java.util.Date;
import java.util.concurrent.TimeUnit;
import com.google.common.collect.Multimaps;
import com.google.common.collect.Range;
import com.google.common.collect.TreeMultimap;

public class MapPerformanceTest
{
    public static void main(final String[] args)
    {
        System.out.println("Populating Map...");

        final TreeMultimap<Date, Integer> map = TreeMultimap.create();

        for (int i = 0; i < 20000000; i++)
        {
            map.put(new Date(i), i);
        }

        final Date[] range = {new Date(10), new Date(20)};

        System.out.println("Map Populated");
        System.out.println();

        long tempTime = -System.nanoTime();

        System.out.println(MessageFormat.format("Multimaps.filterKeys() attempt #1 returned {0} keys in {1} milliseconds",
                Multimaps.filterKeys(map, Range.closed(range[0], range[1])).size(),
                TimeUnit.MILLISECONDS.convert(tempTime + System.nanoTime(), TimeUnit.NANOSECONDS)));

        tempTime = -System.nanoTime();

        System.out.println(MessageFormat.format("NavigableMap.subMap() attempt #1 returned {0} keys in {1} milliseconds",
                map.asMap().subMap(range[0], true, range[1], true).size(), TimeUnit.MILLISECONDS.convert(tempTime + System.nanoTime(), TimeUnit.NANOSECONDS)));

        tempTime = -System.nanoTime();

        System.out.println(MessageFormat.format("NavigableMap.subMap() attempt #2 returned {0} keys in {1} milliseconds",
                map.asMap().subMap(range[0], true, range[1], true).size(), TimeUnit.MILLISECONDS.convert(tempTime + System.nanoTime(), TimeUnit.NANOSECONDS)));

        tempTime = -System.nanoTime();

        System.out.println(MessageFormat.format("Multimaps.filterKeys() attempt #2 returned {0} keys in {1} milliseconds",
                Multimaps.filterKeys(map, Range.closed(range[0], range[1])).size(),
                TimeUnit.MILLISECONDS.convert(tempTime + System.nanoTime(), TimeUnit.NANOSECONDS)));
    }
}

Вывод: 

Multimaps.filterKeys() attempt #1 returned 11 keys in 1,418 milliseconds
NavigableMap.subMap() attempt #1 returned 11 keys in 1 milliseconds
NavigableMap.subMap() attempt #2 returned 11 keys in 0 milliseconds
Multimaps.filterKeys() attempt #2 returned 11 keys in 946 milliseconds

1 Ответ

0 голосов
/ 08 декабря 2018

Ваше наблюдение, что фильтрация медленнее, чем итерация подкарты, является правильным.И объяснение состоит в том, что фильтрация включает оценку каждого ключа, как вы подозреваете.

Это присуще фильтрующему подходу.Метод filterKeys не может заглянуть внутрь поставляемого фильтра, чтобы определить, что он делает.Поэтому необходимо , чтобы применить фильтр ко всем ключам.

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

...