0

所以我有一个程序，其中包含一组记录。该集合可能有几件或数十万件。每条记录的一位数据是时间戳。我需要消除一组中的所有项目，但其中一个在 15 秒内。最有效的方法是什么？

目前，我创建了该集合的副本。然后我遍历集合，将第一个项目与其他所有项目进行比较，然后重复。如果在 15 秒内找到匹配项，我会将其从重复集中删除。然后将重复集写出到文件中。

显然这是可行的，但我终于意识到这是非常低效的。对于大型集，这似乎需要很长时间，假设它没有发生其他问题。有人可以为我提供一种更智能、更快、更有效（或只是适当）的方式来用 Java 执行此操作吗？我意识到，因为记录包含时间戳，所以对它们进行排序可能会有很大帮助。我想把这一切都包含在程序中，所以我想我需要研究排序和比较器。

我只是无法完全解决这个问题。我想出了一些其他的想法来改进我的代码，但我不禁觉得我仍然完全错误。感谢您的任何建议。

哦，这是为了工作，而不是学校或任何东西，所以任何帮助表示赞赏。

4

4 回答 4

5

现在，您描述的算法在O(n 2 )时间内运行。

现在，如果您需要更快的算法，您可以做的是

  • 对您的集合进行排序（如果 java 没有基类排序函数，我会感到惊讶）O(n * lg(n))
  • 15 秒内的所有“匹配”将彼此相邻
  • 您只需要遍历每个元素一次只检查相邻元素O(n)

如果你这样做，那么你的算法可能会更易于管理O(n * lg(n))时间复杂度

这里有一些关于 Java 的 Array.sort() 的信息

于 2013-01-11T19:30:40.800 回答
1

您可以继续使用 Set，只需确保从一开始就对其进行排序，例如TreeSet（或ConcurrentSkipListSet，如果您有多个线程）。要么你实现 Comparable 以便比较时间戳，要么你提供一个 Comparator 来做同样的事情。

这将保证您不能有重复项（就像您之前那样），并且还可以简化您的代码。插入 TreeSet 也会花费你 O(n log n) 的时间。

从这里开始，您可以继续使用 Sam I am 建议的方法：迭代器将按元素升序遍历它，您只需将每个元素与前一个元素和下一个元素进行比较。

顺便说一句，您不需要将所有内容复制到另一个 Set，只需确保使用迭代器的 remove 方法，而不是 TreeSet 的 remove：遍历 Collection，在循环中删除时避免 ConcurrentModificationException

于 2013-01-11T20:43:10.563 回答
0

如果您有地图，请说：

Map<Long, List<MyClass>> map;

其中关键是时间戳，那么你可以这样做：

// Value of wanted elements
List<MyClass> ret = new ArrayList<MyClass>();

// Go over all timestamps: if a timestamp is wanted, add all
// corresponding elements
for (Map.Entry<Long, List<MyClass>> entry: map.entrySet())
    if (wanted(entry.getKey()))
        ret.addAll(entry.getValue());

// Return
return ret;
于 2013-01-11T20:28:42.820 回答
0

我还没有测试过性能，但我可能实现的一种方法是创建一个 Set 并覆盖相关对象类型的 equals() 方法。

public boolean equals( Object o )
{
  return( Math.abs( this.getTimestampSeconds() - o.getTimestampSeconds() ) < 15 );
}

通过这样做，当您将每一行添加到集合中时，对于任何给定的 15 秒时间片，您最终只会得到一个条目。

* 编辑 **

我不会对常规域对象执行此覆盖。我可能只会在某种门面对象中执行此操作——它是专门为此目的而创建的。

另外，正如其他人所说。这假定您的输入列表按升序时间戳排序。

于 2013-01-11T22:07:28.567 回答