2

我使用大量中小型文档（~2 meg）数据文件，并试图确定基于时间戳查找值的最快方法。

如果我正在查找“查找时间戳 X 的数据”，这将很简单，但我通常希望“查找时间戳在日期 X 之前或日期之前的最新数据”。

以下是具体细节：假设您有一个由 300 座房屋组成的集群，每座房屋偶尔都会收到邮件。您正在监控他们收到的邮件类型。假设您关心 15 类邮件。

感兴趣的问题是“在日期 D 或之前递送到房子的最新邮件类别是什么？”

A. 被引用的数据文件具有以下形式：

<data>
 <house house_ID = "XXX" mail_category="YYY" timestamp="ZZZ"/>
 <house house_ID = "XXX" mail_category="YYY" timestamp="ZZZ"/>
 <house house_ID = "XXX" mail_category="YYY" timestamp="ZZZ"/>
 <house house_ID = "XXX" mail_category="YYY" timestamp="ZZZ"/>
 ...
</data>

B. 数据文件不一定是排序的。如果这对最佳实践产生了影响，请在您的回答中说明。

C. 即使在数据文件中跟踪了大约 300 所房屋，我的工作只需要来自 60 个特定房屋的数据。

D. 信息存在 100 个日期，大多数房屋在这 100 个日期中的 3-20 个收到邮件。

E. 邮件可以全天投递。所以在某一天，一个人可以先得到第 1 类，然后得到第 2 类，最后在晚上得到第 8 类。

F. 对于典型的数据文档，可能会要求大约 10 次给定房屋的信息。

这里有两条可能的路径，以及我对每一条的想法。我希望其中一位 XSLT3 超级程序员会有更好的选择。

解决方案 1：大地图 地图通常是许多 XSLT3 速度问题的首选解决方案，但我不确定它们对这个问题的适用程度如何，因为您似乎必须创建一个巨大的地图，其中大部分是您实际上不需要的。

我尝试过的草图如下：

<xsl:variable name="sorted_data" select="saxon:sort(houses I want from data, by date)"/>
<xsl:variable name="dates" select="distinct-values($sorted_data/date:date(@timestamp))"/>
<xsl:variable name="mail.map.pieces" as="map(*)*">
 <xsl:for-each-group select="$sorted_data" group-by="$house_number">
   <xsl:iterate select="current-group">
      Use iteration to form one map for every possible date/house, reading data file once.
      map has form  map{concat($date'--'$house_number) := last_mail_type}
      Note that this internal piece requires a bit of extra computation because you need a map for _every_ date in $dates, but the set being iterated over only contains nodes for dates on which the house received mail.
   </xsl:iterate>
  </xsl:for-each-group>
</xsl:variable>

<xsl:variable name="mail.map" select="map:new($mail.map.pieces)"/>

问题是构建这个地图需要 60 * 100 map{} 命令，其中只有 10% 会被使用。也有几个电话来处理失踪天数的问题。

解决方案 2：小地图

使用地图的另一个选项是将给定房屋的所有邮件数据与该房屋 ID 相关联，然后稍后进行搜索/过滤：

<xsl:variable name="sorted_data" select="saxon:sort(houses I want from data, by date)"/>
<xsl:variable name="dates" select="distinct-values($sorted_data/date:date(@timestamp))"/>
<xsl:variable name="mail.map.pieces" as="map(*)*">
 <xsl:for-each-group select="$sorted_data" group-by="$house_number">
  <xsl:sequence select="map{house_numer := current-group()}/>
 </xsl: for-each-group
</xsl:variable>
<xsl:variable name="mail.map" select="map:new($mail.map.pieces)"/>

稍后，要回答给定日期的问题，您需要在与该房屋相关的少量数据中进行选择：

房子 x = map:get($mail.map, x)[current()/date le d][last()]/@mail_category 在日期 d 之前的最新邮件类别

这显然需要较少的工作来创建地图，但由于额外的过滤，每次检索数据需要更多的工作。还有一个问题是“大地图”解决方案允许我将房屋/日期直接连接到我想要的值[邮件类型]，而这种方法需要我将键值连接到节点，所以会有是从该节点读出邮件类别信息的附加成本。

与解决方案 1 相比，它的最后一个优势是它很容易涵盖“在时间 T或之前的最新邮件类型是什么”的替代问题[因此，它不是基于日期，而是基于实际时间戳。]

解决方案 3：密钥 另一种选择是使用密钥，将给定房屋的所有邮件都键入其 house_id。从理论上讲，这应该与“小地图”选项非常相似。您使用一个键来检索您想要的房子的邮件，然后您过滤以选择最近但在所需日期之前或之前的邮件。

但是，在构造部分存在差异。这些地图需要针对每个组进行一次操作，然后对每个房屋进行一次地图操作。我期望的密钥的构建需要更少的时间。

另一方面，键仅适用于文档模式。如果原始文档没有排序，那么我需要对文档进行排序并在内存中创建一个新文档来处理。我不能简单地在排序的节点序列上构建一个键。我不知道在内存中创建此文档的相对成本，但我想这比在解决方案 2 中构建地图所需的时间要多。

如果原始文档已经排序，那么key可能会更快？

4

1 回答 1

0

抱歉，您已经非常仔细地考虑和时间来提出这个问题，我真的很想给予同等的关注和关注来回答它，但我没有时间。

当然，映射和键的问题在于它们只进行相等匹配。我不知道您是否对使用扩展感兴趣，但它看起来像是 Saxon 9.5 中引入的“范围键”的一个很好的例子：请参阅http://www.saxonica.com/documentation/index.html#！功能/撒克逊/键映射

这里有两个主要思想：首先，它允许将一个键用作映射，因此您可以遍历所有键值。其次，它提供了映射条目的保证顺序，因此您可以按键顺序进行遍历。

这应该允许您以一点点独创性构建例如一个地图，该地图为特定周的所有邮政投递建立索引，然后按日期顺序扫描这些。我认为这可以为您的问题提供非常有效的解决方案。

于 2013-09-16T22:04:52.650 回答