可翻转数据结构的模式名称？

Question

我在想一个命名约定，准确地表达我正在设计的课程内正在进行的操作。在次要记录中，我试图在两个几乎相同的用户API之间做出决定。

这里的情况：

我建立一个科学的应用，其中中心数据结构的一个有三个阶段：1）的积累，2）分析，和3）查询执行。

在我的情况下，它是一个空间建模结构，内部使用KDTree在三维空间中划分点集合。每个点描述周围环境的一个或多个属性，对测量本身具有一定的置信度。

在向集合添加（可能大量的）测量之后，对象的所有者将查询它以获得适用字段内某个新数据点处的插值测量。

的API会是这个样子（代码是在Java中，但是这并不重要;代码分为三个部分，为清楚起见）：

// SECTION 1: 
// Create the aggregation object, and get the zillion objects to insert... 
ContinuousScalarField field = new ContinuousScalarField(); 
Collection<Measurement> measurements = getMeasurementsFromSomewhere(); 

// SECTION 2: 
// Add all of the zillion objects to the aggregation object... 
// Each measurement contains its xyz location, the quantity being measured, 
// and a numeric value for the measurement. For example, something like 
// "68 degrees F, plus or minus 0.5, at point 1.23, 2.34, 3.45" 
foreach (Measurement m : measurements) { 
    field.add(m); 
} 

// SECTION 3: 
// Now the user wants to ask the model questions about the interpolated 
// state of the model. For example, "what's the interpolated temperature 
// at point (3, 4, 5) 
Point3d p = new Point3d(3, 4, 5); 
Measurement result = field.interpolateAt(p); 

对于我的特定问题领域，它将可能在第2节中执行少量的增量工作（将点分割成平衡的KD树）。

并且在第3节中会出现少量工作（执行一些线性插值）。

但是，有一个巨大的工作量（构建内核密度估计和执行快速高斯变换，利用泰勒级数和埃尔米特功能，但这是完全跑题了）必须执行和3 之间部分2

有时过去，我只是使用lazy-evaluation来构造数据结构（在这种情况下，它将在第一次调用“interpolateAt”方法时使用），但如果用户调用“字段”。再次添加（）“方法，我必须完全放弃这些数据结构并从头开始。

在其他项目中，我要求用户显式调用“object.flip（）”方法，从“append mode”切换到“query mode”。这样设计的好处在于，用户可以更好地控制硬核计算开始时的确切时刻。但对于API消费者来说，跟踪对象的当前模式可能是一件令人讨厌的事情。此外，在标准用例中，调用者在开始发出查询后从不向该集合添加另一个值;数据聚合几乎总是完全在查询准备之前。

你们是如何处理像这样的数据结构设计的？

你喜欢让一个对象懒洋洋地执行它的重载分析，当新数据进入集合时抛弃中间数据结构吗？或者你是否要求程序员显式地将数据结构从追加模式转换为查询模式？

你知道这样的对象的任何命名约定吗？有没有我没有想到的模式？

---

上编辑：

似乎有关于我在示例中使用的类，命名为“ContinuousScalarField”一些困惑和好奇。

您可以通过阅读这些维基百科页面得到什么，我谈论的是一个不错的主意：

• http://en.wikipedia.org/wiki/Scalar_field

• http://en.wikipedia.org/wiki/Vector_field

比方说，你想创建一个地形图（这不是我确切的问题，但它在概念上非常相似）。因此，您需要在一平方英里范围内进行一千次高度测量，但您的测量设备的海拔正负10米误差。

一旦你收集了所有的数据点，你喂他们进入不仅插值值的模式，但也考虑到每次测量的误差。

提请地形图，您查询您要画一个像素的每个点的高程模型。

至于单一类是否应该负责这两个追加和处理查询的问题，我不是100％肯定，但我认为是这样。

下面是一个类似的例子：HashMap和TreeMap类允许添加和查询对象。没有单独的接口用于添加和查询。

两个类也类似于我的例子中，因为内部数据结构具有以支持查询机制在持续的基础上得以维持。 HashMap类必须定期分配新内存，重新散列所有对象，并将对象从旧内存移动到新内存。 TreeMap必须使用红黑树数据结构持续保持树平衡。

唯一的区别是，我的类将表现最佳，如果它可以执行所有的计算，一旦知道数据集被关闭。

Answer 1

我一般喜欢有一个明确的变化，而不是懒洋洋地重新计算的结果。这种方法使公用事业的性能更加可预测，并且减少了我为提供良好的用户体验所做的工作量。例如，如果这发生在用户界面中，那么我需要担心会弹出一个沙漏等？哪些操作会阻塞可变的时间量，并且需要在后台线程中执行？

这就是说，不是明确地改变一个实例的状态，我会建议Builder Pattern产生一个新的对象。例如，您可能有一个聚合器对象，可以在添加每个示例时执行少量工作。然后，而不是你建议的void flip()方法，我会有一个Interpolator interpolator()方法获得当前聚合的副本，并执行所有的重型数学。您的interpolateAt方法将位于此新的Interpolator对象上。

如果您的使用模式允许，您可以通过保持对创建的插补器的引用并将其返回给多个调用者来进行简单缓存，只有在聚合器被修改时才清除它。

责任的这种分离有助于产生更好的可维护性和可重复使用的面向对象的程序。一个可以在要求的Point处返回Measurement的对象非常抽象，也许很多客户可以使用Interpolator作为实现更一般接口的策略。

---

我认为您添加的类比是误导性的。考虑另一种比喻：

Key[] data = new Key[...]; 
data[idx++] = new Key(...); /* Fast! */ 
... 
Arrays.sort(data); /* Slow! */ 
... 
boolean contains = Arrays.binarySearch(data, datum) >= 0; /* Fast! */ 

这工作就像一组，而实际上，它比Set实现（这与哈希表或者平衡树实现）更好的性能。

平衡树可以被看作是一种有效的实现插入排序的。每次插入后，树都处于排序状态。平衡树的可预测时间要求是由于排序的成本分散在每个插入上，而不是发生在某些查询上，而不是发生在其他查询上。

哈希表的重新哈希确实会导致性能不太稳定，因此不适合某些应用程序（可能是实时微控制器）。但即使重新哈希操作仅依赖于表的加载因子，而不是插入和查询操作的模式。

为了您的比喻严格不放，你就必须“排序”（做多毛数学）的聚合与您添加的每个点。但是，这听起来像是成本过高，并导致建设者或工厂方法模式。这让您的客户清楚何时需要为冗长的“分类”操作做好准备。

Answer 2

你的对象应该有一个角色和责任。在你的情况下，ContinuousScalarField是否应该负责插值？

也许你可能会更好做这样的事情：

IInterpolator interpolator = field.GetInterpolator(); 
Measurement measurement = Interpolator.InterpolateAt(...); 

我希望这是有道理的，但没有完全理解你的问题域，很难给你一个更加一致的答案。

Answer 3

如果一个对象有两种模式是这样，我会建议暴露两个接口给客户端。如果对象处于追加模式，则确保客户端只能使用IAppendable实现。要翻到查询模式，您需要向Asapableable添加一个方法，如AsQueryable。要返回，请调用IQueryable.AsAppendable。

你可以在同一个对象上实现IAppendable和IQueryable，并且在内部以相同的方式跟踪状态，但是有两个接口使得客户端清楚了对象的状态，并强制客户端刻意地制造（昂贵的）开关。

Answer 4

你可以有一个状态变量。有一个启动高级处理的方法，只有当状态位于SECTION-1时才会起作用。它将设置状态为SECTION-2，然后在SECTION-3完成计算后。如果程序要求插入给定点，它将检查状态是否为SECTION-3。如果不是，它将要求开始计算，然后插入给定的数据。

通过这种方式，您可以同时完成两个任务 - 程序将在第一次插入点的请求时执行其计算，但也可以提前请求。例如，如果您想在一夜之间运行计算，这将非常方便，而无需请求插值。

Answer 5

“我刚刚用懒惰评估，以构建数据结构” - 好

再次“如果用户调用‘field.add（）’方法，我已经完全抛弃那些数据结构并从头开始。“ - 有趣

“的标准使用情况下，主叫方从来没有开始发出查询后，又增加了收藏价值” - 哎呦，虚惊一场，其实并不有趣。

由于懒惰的eval适合您的用例，请坚持下去。这是一个非常使用的模型，因为它非常可靠并且非常适合大多数用例。 （a）用例改变（混合添加和插值）或（b）性能优化。

由于用例更改不太可能发生，因此您可能会考虑拆分插值的性能影响。例如，在空闲时间，你能预先计算一些值吗？或者每次添加都有可以更新的摘要？

此外，高度有状态（并非非常有意义）flip方法对您班级的客户来说并不是那么有用。但是，将插值分解为两部分可能对他们有帮助 - 并帮助您进行优化和状态管理。

例如，您可以将插值分解为两种方法。

public void interpolateAt(Point3d p); 
public Measurement interpolatedMasurement(); 

此借用关系数据库打开和取范式。打开游标可以做很多初步工作，并且可能会开始执行查询，您不知道。获取第一行可以完成所有工作，或者执行准备好的查询，或者简单地获取第一个缓冲行。你不知道。你只知道这是一个两部分的操作。 RDBMS开发人员可以自由优化，因为他们认为合适。

Answer 6

你宁愿让一个对象懒洋洋地履行其重型分析， 扔掉中间数据结构，当新数据来自 到集合？或者你是否要求程序员明确地将数据结构从append-mode翻转成查询模式？

我更喜欢使用数据结构，使我可以通过每增加一点“更多的工作”逐步增加数据结构，并在每次提取时逐步提取需要的“多一点工作”所需的数据。

也许，如果你在你的区域的右上角一些“interpolate_at（）”调用，你只需要做在右上角， 涉及点计算，它不会伤害任何东西将其他3个象限“开放”给新增加的部分。 （依次递归KDTree）。

唉，这并不总是可行的 - 有时添加更多数据的唯一方法是丢弃所有以前的中间和最终结果，并重新从头开始重新计算所有内容。

使用我设计的界面的人 - 特别是我 - 是人性化和易错的。 所以我不喜欢使用物体，那些人必须记得以某种方式做事情，否则事情就会出错 - 因为我总是忘记那些事情。

如果一个对象必须走出它的数据之前在“计算后的状态”， 即一些“do_calculations（）”函数必须可以在interpolateAt前（）函数获取有效数据运行， 我更喜欢让interpolateAt（）函数检查，如果它已经在该州， 运行“do_calculations（）”，如有必要， 更新对象的状态，然后再返回我希望的结果。

有时候我听到人们描述了这样一个数据结构“冻结”的数据或“结晶”的数据或“编译”或“把数据转换成不可变的数据结构”。 一个例子是将（可变的）StringBuilder或StringBuffer转换为（不可变的）字符串。

我可以想像，对于某些类型的分析，您希望有所有提前时间的数据， 并拉出一些插值所有数据已经​​把之前会给错误结果。 在这种情况下，我倾向于设置“add_data（）”函数失败或抛出异常 ，如果它调用interpolateAt（）后调用它（错误地）。

我会考虑定义一个惰性计算“interpolated_point”对象不真正评估数据向右走，但只告诉在未来某个时候，在这一点上的数据将需要该程序。 集合实际上没有冻结，所以没关系，继续添加更多的数据，那么， 直到点东西实际上是从一些“interpolated_point”对象， 在内部触发提取第一个真正的价值“do_calculations（）”函数并冻结对象。 如果你不仅知道所有的数据，而且还知道所有需要插值的点，那么它可能会加快速度。 然后，您可以丢弃距离插值点“远”的数据，并且仅在插值点附近的区域执行重载计算。

对于其它类型的分析，你可以跟你的数据是最好的，但是当更多的数据进来后，要使用新的数据在以后的分析。 如果要做到这一点的唯一方法是抛弃所有的中间结果并重新计算一切从零开始，那么这就是你必须做的。 （最好是对象自动处理，而不是每次都要记住调用一些“clear_cache（）”和“do_calculations（）”函数）。