4

我有一组带时间戳的值，我想将它们放在一个排序集中。

public class TimedValue {
    public Date time;
    public double value;

    public TimedValue(Date time, double value) {
        this.time = time;
        this.value = value;
    }
}

对这个集合进行排序的业务逻辑表明，值必须按值降序排列，除非它比最新值早 7 天以上。

所以作为一个测试，我想出了下面的代码......

DateFormat dateFormatter = new SimpleDateFormat("MM/dd/yyyy");
TreeSet<TimedValue> mySet = new TreeSet<TimedValue>(new DateAwareComparator());
mySet.add(new TimedValue(dateFormatter.parse("01/01/2009"), 4.0 )); // too old
mySet.add(new TimedValue(dateFormatter.parse("01/03/2009"), 3.0)); // Most relevant
mySet.add(new TimedValue(dateFormatter.parse("01/09/2009"), 2.0));

如您所见，最初第一个值比第二个值更相关，但是一旦将最终值添加到集合中，第一个值已经过期并且应该是最不相关的。

我最初的测试表明这应该可以工作......随着更多值的添加，TreeSet 将动态地重新排序整个列表。

但即使我看到它，我也不确定我是否相信它。

添加每个元素时，排序集合是否会重新排序整个集合？以这种方式使用排序集合是否有任何问题（即性能）？在添加所有值之后手动对列表进行排序会更好吗（我猜会是这样）？



追问： 正如很多人（甚至在某种程度上我）怀疑的那样，排序的集合不支持这种“动态重新排序”的方式。我相信我最初的测试是偶然的。当我向集合中添加更多元素时，“顺序”很快就崩溃了。感谢所有伟大的回应，我重构了我的代码以使用你们许多人建议的方法。

4

8 回答 8

10

我看不到您的比较器如何甚至检测到更改，除非它记得它当前看到的最新值 - 这听起来像是一种注定会以眼泪收场的方法。

我建议你按照以下方式做一些事情：

  • 在无序集（或列表）中收集数据
  • 查找最新值
  • 根据该值创建一个比较器，这样使用该比较器的所有比较都将是固定的（即，它永远不会基于相同的输入值返回不同的结果；比较器本身是不可变的，尽管它取决于构造函数中最初提供的值)
  • 使用该比较器创建一个排序集合（以任何看起来最好的方式，具体取决于您想用它做什么）
于 2009-05-26T20:13:57.963 回答
4

我建议不要这样做，原因如下：

  1. 由于它基本上是幕后的红黑树（不一定必须在每次插入时从头开始重建），因此您可能很容易在树的错误部分得到值（使大部分 TreeSet API 无效） .
  2. 该行为未在规范中定义，因此即使它现在正在工作，以后也可能会改变。
  3. 将来，当远程接触此代码时出现任何奇怪的错误时，您会花时间怀疑这就是原因。

我建议在搜索之前重新创建/重新排序 TreeSet，或者（我的偏好）在搜索之前迭代集合并删除任何太旧的对象。如果您想用一些内存换取速度，您甚至可以保留第二个按日期排序并由相同对象支持的列表，这样您过滤 TreeSet 所需要做的就是根据时间从 TreeSet 中删除对象-排序列表。

于 2009-05-26T20:23:43.310 回答
3

我不相信 JDK 库甚至 3rd 方库是为了处理结果不一致的比较器而编写的。我不会依赖这个工作。如果您的 Comparator 在一次调用时可以为两个值返回不等于并且如果稍后调用可以为相同的两个值返回相等的值，我会更担心。

仔细阅读合同Comparator.compare()。您的 Comparator 是否满足这些约束？

详细地说，如果您的 Comparator 在您调用一次时返回两个值不相等，但后来又返回这两个值相等，因为后来将一个值添加到集合中并更改了 Comparator 的输出，则定义“设置”（无重复）变为撤销。

Jon Skeet 在他的回答中的建议是很好的建议，并且可以避免担心这类问题。确实，如果您的 Comparator 没有返回一致的值，equals()那么您可能会遇到大问题。每次添加某些内容时，已排序的集合是否会重新排序，我不会依赖，但是更改顺序会发生的最糟糕的事情是您的集合不会保持排序状态。

于 2009-05-26T20:08:01.157 回答
2

我有 99% 的把握这不会奏效。如果 Set 中的一个值突然改变了它的比较行为，它有可能（实际上很可能）再也找不到了；ieset.contains(value)将返回false，因为搜索算法将在某一时刻进行比较并在错误的子树中继续，因为该比较现在返回的结果与插入值时的结果不同。

于 2009-05-26T20:13:38.307 回答
2

不，这行不通。

如果您在集合中使用可比较的键，则两个键之间的比较结果必须随着时间的推移保持相同。

在二叉树中存储键时，选择路径中的每个分支作为比较操作的结果。如果后面的比较返回了不同的结果，就会采用不同的fork，并且不会找到之前存储的key。

于 2009-05-26T20:15:15.947 回答
1

我认为 Comparator 的不变性质应该是基于每个排序的，所以只要你在给定排序操作的持续时间内保持一致，你就可以（只要没有任何项目跨越7 天边界中间排序）。

但是，您可能希望更清楚地表明您正在专门询问 TreeSet，我想它会在您添加新项目时重用以前排序的信息以节省时间，所以这有点特殊。TreeSet javadocs 专门遵循 Comparator 语义，因此您可能不受官方支持，但您必须阅读代码才能很好地了解您是否安全。

我认为，当您需要对数据进行排序时，最好进行一次完整的排序，将单个时间用作“现在”，这样如果您的排序需要足够长的时间使其成为可能，您就不会冒险跳过该边界。

于 2009-05-26T20:13:41.083 回答
1

记录可能会在排序过程中从 <7 天更改为 >7 天，因此您所做的事情违反了比较器的规则。当然，这并不意味着它不会起作用：如果您确切地知道内部发生的事情，许多被记录为“不可预测”的事情实际上会起作用。

我认为教科书的答案是：内置排序不可靠。您必须编写自己的排序函数。

至少，我会说当日期超出边界时，您不能依赖 TreeSet 或任何“排序结构”神奇地自行恢复。如果您在显示之前重新排序，充其量这可能会起作用，并且不要依赖更新之间保持正确的任何内容。

在最坏的情况下，不一致的比较可能会严重破坏排序。你无法保证这不会让你陷入无限循环或其他致命的黑洞。

所以我想说：阅读 Sun 的源代码，了解您计划使用的任何类或函数，看看您是否能弄清楚会发生什么。测试是好的，但是有一些潜在的棘手的情况很难测试。最明显的是：如果在排序过程中，一条记录超出了日期边界怎么办？也就是说，它可能会查看记录一次并说它 <7，但下一次它看到它是 >7。这可能是个坏消息。

我想到了一个明显的技巧：在将记录添加到结构时将日期转换为年龄，而不是动态地。这样它就不能在排序内改变。如果结构的寿命超过几分钟，请在适当的时间重新计算年龄，然后重新排序。我怀疑有人会说您的程序不正确，因为您说记录不到 7 天，而实际上它是 7 天、0 小时、0 分钟和 2 秒。即使有人注意到，他们的手表有多准确？

于 2009-05-26T20:27:53.317 回答
1

如前所述，比较器无法为您执行此操作，因为违反了传递性。基本上，为了能够对项目进行排序，您必须能够比较它们中的每一个（独立于其余部分），这显然是您无法做到的。因此，您的方案基本上要么不起作用，要么会产生不一致的结果。

也许更简单的东西对你来说就足够了：

  • 根据需要应用使用值的简单比较器
  • 并从您的列表/集合中删除所有比最新早 7 天的元素。基本上，每当添加一个新项目时，您都会检查它是否是最新的，如果是，则删除那些比这个大 7 天的项目。

如果您还从列表中删除项目，这将不起作用，在这种情况下，您需要将所有已删除的项目保留在单独的列表中（顺便说一下，您将按日期排序）并将它们添加回原始列表如果删除后 MAX(date) 较小。

于 2009-05-26T20:59:06.577 回答