java - Guava Multimaps.filterKeys与NavigableMap.subMap()相比性能较差

我有一个番石榴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

最佳答案

您观察到过滤比迭代子图慢的观察是正确的。解释是，过滤确实涉及评估每个密钥，您怀疑。

这是过滤方法所固有的。 filterKeys方法无法在提供的过滤器中查看以确定其作用。因此，有必要将过滤器应用于所有键。

现在，如果编译器对方法和过滤器的工作有深刻的了解，那么从理论上讲它就有可能将过滤器转换为更有效的方法。不幸的是，并非如此，因此有必要使用更加繁琐的子图方法...如果在具有多个键的地图上进行操作时希望获得良好的性能。

关于java - Guava Multimaps.filterKeys与NavigableMap.subMap()相比性能较差，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53682912/