0

任务是实现周期性值的缓存。更具体地说 - 这些是与银行帐户相关的一些记录。每条记录都有一个日期和一天内的某个位置。因此,每条记录都可以通过这些属性进行比较。缓存必须包含与查询期间相关的记录列表。当执行更长时期的查询时,也可以合并缓存的值。

让我们考虑几个例子。某些特定帐户的历史记录有 10 条记录(日期格式为 MM/dd/yyyy:

01/01/2012 
02/01/2012 
03/01/2012 
04/01/2012 
05/01/2012 
06/01/2012 
07/01/2012 
08/01/2012 
09/01/2012 
10/01/2012

示例 1

第一个查询是针对 02/15/2012 - 03/15/2012 期间的。

查询结果将是一条记录:

03/01/2012

缓存应包含记录:键“02/15/2012 - 03/15/2012”,值 [“03/01/2012”]

该时期或子时期(即 02/16/2012-03/15/2012)的所有查询都应从缓存中返回“03/01/2012”。

执行的第二个查询是 01/15/2012 - 02/16/2012 期间。

查询结果将是两条记录:

02/01/2012
03/01/2012

有以下几点需要说明:

1) 对底层数据存储的查询应仅在 01/15/2012 - 02/14/2012 期间执行。这是因为缓存已经包含 2012 年 2 月 15 日的所有条目。

2) 单个缓存条目的边界将随其存储的记录数一起更新。

因此,缓存应包含一条记录:键“01/15/2012 - 03/15/2012”,值 [“02/01/2012”,“03/01/2012”]。

然后对子周期的任何查询都应该通过键找到缓存条目,然后从缓存中选择所需的记录。

示例 2

当前缓存状态为:

Entry 1: "01/15/2012 - 03/15/2012" => ["02/01/2012", "03/01/2012"]
Entry 2: "04/15/2012 - 05/15/2012" => ["05/01/2012"]
Entry 3: "07/02/2012 - 09/02/2012" => ["08/01/2012", "09/01/2012"]

查询在 01/01/2012 - 10/01/2012 期间执行。结果包含所有历史记录:

01/01/2012 
02/01/2012 
03/01/2012 
04/01/2012 
05/01/2012 
06/01/2012 
07/01/2012 
08/01/2012 
09/01/2012 
10/01/2012

缓存应包含单个条目:键“01/01/2012”、值 [“01/01/2012”、“02/01/2012”、“03/01/2012”、“04/01/2012”、 “05/01/2012”、“06/01/2012”、“07/01/2012”、“08/01/2012”、“09/01/2012”、“10/01/2012”]。


我正在挑战这个任务一个星期,找不到任何漂亮的简单算法来处理这样的缓存。

任何帮助表示赞赏。

4

1 回答 1

0

我认为间隔树可能适合您的需要 -这是一个 Java 实现。区间树存储区间,可以通过区间查询(比如可以存储[1, 5], [2, 7], [6, 10],在[3, 5]上查询,返回[1, 5] ], [2, 7] 即与查询重叠的所有区间)。您存储的是点而不是间隔,但只需将您的点存储为足够小的非重叠间隔,您就可以开始了。

因为这是一个缓存,所以您可能希望将您的键和值存储在SoftReferences中——这将允许垃圾收集器在您遇到OutOfMemoryError.

于 2013-04-17T14:56:12.520 回答