java - 有没有比 Java 中的 Collections.sort() 更快的东西？

Question

我做了一个中值滤波算法，想优化一下。目前过滤 2MM 行(读入 ArrayList elements 的文件)大约需要 1 秒，我正在尝试将其减少到更少(可能是一半时间？)我正在使用 ArrayLists 作为我的算法并尽量减少嵌套循环的使用以避免时间增加，但我仍然无法达到低于 0.98 秒的最高点。

这是执行中值滤波器的代码片段:

//Start Filter Algorithm 2
        int index=0;
        while(index<filterSize){
            tempElements.add(this.elements.get(index+counter)); //Add element to a temporary arraylist
            index+=1;
            if(index==filterSize){
                outputElements.add(tempElements.get((filterSize-1)/2)); //Add median Value to output ArrayList
                tempElements.clear(); //Clear temporary ArrayList
                index = 0; //Reset index
                counter+=1; //Counter increments by 1 to move to start on next element in elements ArrayList                    
            }
            if(elementsSize-counter <filterSize){
                break; //Break if there is not enough elements for the filtering to work
            }
        }

我正在为我提供的 filterSize 遍历 elements 数组列表。然后我将元素添加到临时 (tempElements) arraylist，使用 Collections.sort() 对其进行排序(这是我想要避免的)，找到中值并将它添加到我的最终输出数组列表中。然后我清除 tempElements arraylist 并继续执行循环，直到由于缺少元素(小于 filterSize)而无法再进行过滤。

我只是在寻找一种优化它并使其更快的方法。我尝试使用 TreeSet，但无法从中获取索引处的值。

谢谢

Answer 1

Java Collections.sort() 实现在排序(双枢轴快速排序)时速度最快。

这里的问题不在于具体的细节，而在于您要进行排序!您只需要找到中位数，并且有线性算法(排序是对数线性的)。参见 selection一些灵感。您可能需要自己编写代码，因为我认为 Java 库没有任何可用的公共(public)实现。

我建议的另一件事是使用固定大小的数组(创建一次)而不是 ArrayList。由于您事先知道过滤器的大小，这会给您带来小幅速度提升。

此外，我看不出避免 for 循环如何以任何方式提高性能。除非您分析它并证明它是正确的做法，否则我会尽可能编写最易读的代码。

最后，TreeSet 或任何其他类型的排序数据结构也无济于事，因为 n 插入的时间复杂度是对数线性的。