java - 每周显示数据趋势的更好算法方法

Question

假设我有一个包含开始日期和结束日期的项目列表。我也有一系列的周，变化（可能超过几个月、几年等）我想显示一个图表，每周显示 4 个值：

1. 项目启动
2. 关闭的项目
3. 开工项目总数
4. 关闭的项目总数

我可以遍历每周值的范围，并且每周遍历我的项目列表并计算每周这 4 个趋势中的每一个的值。这将具有算法复杂性O(nm)，n是周列表的长度，并且m是项目列表的长度。那不是很好。有没有更有效的方法，如果有，会是什么？

如果它是相关的，我正在用 Java 编码

Answer 1

我不确定“项目”和“总计”之间的区别是什么，但这里有一个简单的 O(n log n) 方法来计算每周启动和关闭的项目数量：

1. 对于每个项目，将其起点和终点添加到列表中。
2. 按升序对列表进行排序。
3. 遍历列表，拉出时间点，直到您达到下一周发生的时间点。此时，“projects started”是您已达到的起点总数，“projectsended”是您已达到的终点总数：报告这些计数器，并将它们都重置为零。然后在下周继续处理。

顺便说一句，如果有几个星期没有任何项目开始或结束，此过程将跳过它们。如果您想将这些周报告为总计“0, 0”，那么每当您输出一个总计非零的周时，请确保您首先输出尽可能多的“0, 0”周以填补自最后一个非零总周。（这很容易做到，只需在lastNonzeroWeek每次输出非零总周时设置一个变量。）

Answer 2

虽然用户 yurib 说的是真的，但有一个更有效的解决方案。在内存中保留两个数组projects_started和projects_ended，大小均为 52。循环遍历您的项目列表，并为每个项目增加两个列表中的相应值。就像是：

projects_started[projects[i].start_week]++;
projects_ended[projects[i].end_week]++;

在循环之后，您拥有制作图表所需的所有数据。复杂度为 O(m)。

编辑：好的，所以最大周数显然会有所不同，但如果它小于一些可笑的数字（超过一百万），那么这个算法仍然有效。只需将 52 替换为n. 时间复杂度为 O(m)，空间复杂度为 O(n)。

编辑：为了确定开始和结束的总项目的价值，您必须遍历您现在拥有的两个数组并将值相加。您可以在填充图表时执行此操作：

for (int i = 0; i < n)
{
    total_started_in_this_week += projects_started[i];
    total_ended_in_this_week += projects_ended[i];
    // add new item to the graph
}

Answer 3

首先，我想实际上性能不会成为问题。这看起来像是“过早优化”的情况。你应该先做，然后做对，然后快速做。

我建议您使用maps，这将使您的代码更具可读性并外包实现细节（如性能）。

创建一个HashMapfrom int（代表周数） to Set<Project>，然后遍历您的项目并为每个项目将其放入地图中正确的位置。之后，遍历地图的键集（= 所有非空周）并对每个键进行处理。