Guava Multimaps.filterKeys 与 NavigableMap.subMap() 相比表现不佳
Guava Multimaps.filterKeys poor performance vs NavigableMap.subMap()
我有一个 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
您认为过滤比迭代子图慢的观察是正确的。正如您怀疑的那样,解释是过滤 确实 涉及评估每个键。
这是过滤方法所固有的。 filterKeys
方法无法查看提供的过滤器内部以确定其作用。因此,有必要 将过滤器应用于所有键。
现在,如果编译器对方法和过滤器的作用有深入的了解,理论上它可以将过滤转换为更高效的东西。不幸的是它没有,所以有必要使用更麻烦的子图方法......如果你想要在具有许多键的地图上操作时获得良好的性能。
我有一个 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
您认为过滤比迭代子图慢的观察是正确的。正如您怀疑的那样,解释是过滤 确实 涉及评估每个键。
这是过滤方法所固有的。 filterKeys
方法无法查看提供的过滤器内部以确定其作用。因此,有必要 将过滤器应用于所有键。
现在,如果编译器对方法和过滤器的作用有深入的了解,理论上它可以将过滤转换为更高效的东西。不幸的是它没有,所以有必要使用更麻烦的子图方法......如果你想要在具有许多键的地图上操作时获得良好的性能。