加速两个数组之间的线性时间比较

Question

我的代码现在有一个速度瓶颈。下面的函数比较两个数组(position和size)，并产生一个新的position元素数组，该数组小于size。这在O(n)时间内运行，但被调用了很多次。对于这个特殊的案例，我能做得更好吗?

代码:

function findValidDimensions(positions, sizes) {
    var forwardDimensions = [];
    var backwardDimensions = [];
    for (var i = 0; i < sizes.length; i++) {
        if (positions[i] < sizes[i]) {
            forwardDimensions.push(i);
        }
        if (positions[i] > 1) {
            backwardDimensions.push(i);
        }
    }
    // we can go forward or backward
    return {
        "forward": forwardDimensions,
        "backward": backwardDimensions
    }
}

Answer 1

除非有可以避免查看的元素(从您的备用描述来看，这听起来不太可能)，否则查看n元素将花费O(n)时间。

Answer 2

据我所知，如果你使用一个大数组，你的方法的复杂性是大的，最好的搜索模式是堆或b树:)

Some ref:

https://en.wikipedia.org/wiki/Heap_%28data_structure%29

https://en.wikipedia.org/wiki/B-tree