3

我需要基于多键快速找到一些值。键由：组成， < Int userId, String measureName, Date startDate, Date endDate > 值是双精度。

问题是我必须要求指示一天的值，而不是日期范围。因此，如果我要求 a userId、 ameasureName和 a ，数据结构必须回答日期介于startDate和之间的值endDate（日期范围之间没有重叠）。

我不明白哪个是更好的数据结构来实现这一点。哈希表？树图？多键映射？范围地图？帮助！:)

4

4 回答 4

3

我认为您应该使用 TreeMap 和以下方法： http://docs.oracle.com/javase/6/docs/api/java/util/TreeMap.html#floorEntry( K) http://docs.oracle.com/ javase/6/docs/api/java/util/TreeMap.html#higherEntry(K) 但在比较函数中仅使用一个日期 - startDate 或 endDate。由于这些范围不重叠，这应该不是问题，并使 TreeMap 中提到的方法可用。

例如：如果您决定使用比较endDate（以及除其他日期以外的其他字段），则应使用方法floorEntry

于 2013-03-12T21:58:01.717 回答
0

我推荐一些 Map 作为 User/Measurement 部分键。该值将是一个排序的元组数组（日期范围，floatval）。在此数组中，您对包含日期的日期范围执行二进制搜索。

于 2013-03-12T22:15:10.013 回答
0

最好使用带有自定义键对象的 TreeMap。你会有类似的东西：

...
TreeMap<MyMultiKey,Double> map = ...

class MyMultiKey implements Comparable<MyMultiKey>{
...
}

假设MyMultiKey's 的compareTo方法被实施以正确订购您的多键，您可以在MyMultiKey每次想要搜索特定日期时创建一个新实例，map.floorKey(MyMultiKey m)并map.higherKey(MyMultiKey m)确保您找到一个包含该日期的开始和结束时间的键您在新的密钥实例中指定。

于 2013-03-12T22:03:21.173 回答
0

Map和 order的组合List呢？该地图有一个复合键userIdand measureName，值是日期范围和 double 的排序列表value：

Map<Key,List<Entry>> data = new HashMap<>();
List<Entry> entries = data.get(new Key(userId, measureName));
int i = Collections.binarySearch(entries, new Entry(searchDate,searchDate, 0.0));
double value = i < 0 ? 0.0 : entries.get(i).value;

Key必须实现hashCode()和equals()使用其成员userId和measureName. Entry如果一个范围是另一个范围的一部分，则必须实现Comparable<Entry>wherecompareTo()必须返回 0（startDate 比较 <= 0 并且 endDate 比较 >= 0 或 0 如果 startDate 比较 >= 0 并且 endDate 比较 <= 0）否则比较 startDate+ (endDate-startDate)/2 （范围的中间）与 double 无关value。

如果您主要阅读而不修改此结构，它应该很快。如果使用较多，比较将被编译为本机。如果该功能仅适用于单个用户并进行度量，则可以仅使用排序列表，如果仅适用于单个用户，则可以创建 Map<UserId<Map<MeasureName,List<Entry>>>>类似的结构。

首先尝试一个简单的解决方案，前后测量，仅在需要时进行性能优化。

于 2013-03-12T22:49:54.443 回答