改进对数组进行两次步进(在同一数组上嵌套循环)

Question

我有一个大的数据集，我想通过循环，以确定从时间点'D1'到未来'D2'的时间点的数据集的各种统计数据。基本上，我想在每次值之间的差大于10时向数据库添加值。例如:

Datum[] data = x;
for( Datum d1 : data ){
    Datum[] tail = y; //From d1 up to 10 elements ahead
    for( Datum d2 : tail ){
        //Calculate difference
        if( (d2.val - d1.val) > 10 ){
            //Insert into database
        }
    }
}

我的问题是，有没有更好的算法/方法来做到这一点?由于tail中的9个元素在外部循环的下一次迭代中被重用，我是否可以从中受益?我的目标是使它比(Big-O Notation) O(n²)小得多，但我无法理解它。通常，找到满足条件的D1, D2对意味着下一个D1元素也将有更大的匹配机会。我能利用这一点吗?

我想让这个尽可能高效，因为数据集太大了。

Answer 1

基于索引的for循环可能比迭代器执行得好得多，因为您可以直接为原始数组建立索引，避免复制到新数组。你会有更好的内存局部性，更少的错误共享的机会，等等。

Answer 2

你所拥有的是一个经典的扫描线算法，它是O(k*n)与k的"重叠"或内部循环运行的部分。在你的例子中，无论n是多少，它的最大值都是10

Datum[] data = x;
for(int i=0;i<data.length;i++ ){
    Datum d1=data[i];
    Datum[] tail = y; //From d1 up to 10 elements ahead
    for(int j=i+1;j<Math.min(i+10,data.length);i++){
        d2 = data[j];
        //Calculate difference
        if( (d2.val - d1.val) > 10 ){
            //Insert into database
            break;//inner loop
        }
    }
}

Answer 3

在你的情况下，我要做的第一件事是分析一个典型的数据集并找出时间的去向。这应该会给你一些提示，告诉你应该把优化的重点放在哪里。

假设计算与减法/比较一样简单，并且数组可以快速访问，那么您建议的优化保存到数据库的建议应该是下一个优先级。例如，与单个插入语句相比，写入文本文件并使用批量插入可以提供非常快的性能。如果您坚持使用单独的插入，并且使用JDBC，那么批处理更新将是一个很大的帮助，因为它们避免了与数据库通信的延迟。

如果仍然不够快，可以考虑将数组划分为N个分区，并让每个分区由一个单独的线程处理。如果处理受到CPU限制，这将特别有效。

最后，寻找代码级优化，例如通过使用索引来避免迭代器。如果写入数据库的条目数量少于迭代的元素数量，那么迭代器的创建可能是一个瓶颈。

如果元素的数量大于10，并且更重要的是，超过了cpu缓存所能容纳的数量，那么将扫描分解成更小的块将更有效。例如，与其从data2中扫描1000个元素，不如将其分成(比如说)10次扫描，每次扫描100个元素，每次扫描使用不同的d1值。这类似于以块方式实现矩阵乘法，并且可以更好地利用cpu缓存。

虽然你使用两个循环，这通常是一个O(N^2)算法，第二个循环有一个固定的大小- 10个元素，所以这减少到一个简单的常数因子-你做了大约10倍的工作。

Answer 4

有一个渐近更快的方法来解决这个问题，但我对它是否会在实践中运行得更快有严重的怀疑，因为你的窗口大小(10)是如此之小。如果您想增加这个大小(我将其称为k)，那么您可能需要考虑选择如下方法:

当你使用这个算法时，你需要维护一个包含k个元素的窗口，支持两种操作:

1. 插入新元素，移除旧元素
2. 返回所有大于某个值的元素。

一种方法是将所有元素存储在结合平衡二叉搜索树和队列的数据结构中。该队列包含所有k个元素，按照它们在原始序列中出现的顺序存储，这样当需要添加新元素时，我们就可以记住要删除哪个元素。平衡BST存储按排序顺序存储的每个元素的副本。这意味着您可以像这样实现上述操作:

1. 插入新元素，清除旧元素:将新元素添加到队列和BST中。然后，从队列中取出最老的元素，然后将其从BST中移除。运行时间:O(log k)，因为BST包含k个元素。
2. 返回所有大于某个值的元素:使用BST，在O(log n)时间内找到至少与该值相等的最小元素。然后，扫描整个BST并列出至少与该元素一样大的所有元素。这需要O(z)时间，其中z是找到的匹配总数。

总的来说，如果你有n个元素和总共z对需要插入到数据库中，这个算法将花费O(n log k + z)时间。要看到这一点，请注意，我们总共复制了n次操作(1)，每次花费O(log k)时间。我们还对操作(2)进行n次复制，这需要O(n log k)时间来找到后继操作，然后在所有迭代中花费O(z)总时间来列出所有匹配对。

与你最初发布的O(nk)算法相比，该算法的渐近运行时间很好。假设匹配的数量不是"非常大"(比如，在k的数量级上)，当你增加n和k时，这将会快得多。

如果你存储的值是一个小范围内的整数(比如，0 - 10,000)，你可以通过用一个针对整数优化的数据结构替换平衡的BST来进一步加快速度，比如van Emde Boas树，这将把它减少到O(n log log k + z).再次，这只会更快渐近，如果你保持k常数为10，这几乎肯定不值得。

希望这对你有帮助!