Есть ли что-то быстрее, чем Collections.sort() в Java?

Question

Я сделал алгоритм срединного фильтра, и я хочу его оптимизировать. В настоящее время занимает около 1 секунды, чтобы фильтровать строки 2MM (файл читается в ArrayList elements), и я пытаюсь уменьшить его до меньшего (возможно, в половине случаев?). Я использую 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 
      } 
     } 

Что происходит, что я перекручивание через elements ArrayList для filterSize я предоставил. Затем я добавляю элементы во временный (tempElements) arraylist, сортирую его с помощью Collections.sort() (это то, чего я хочу избежать), найдите медианное значение и добавьте его в мой конечный выходный arraylist. Затем я очищаю arraylist tempElements и продолжаю проходить через мой цикл, пока я не смогу фильтровать больше из-за отсутствия элементов (меньше filterSize).

Я просто ищу способ оптимизировать его и получить его быстрее. Я попытался использовать TreeSet, но я не могу получить значение из индекса из него.

Благодаря

Answer 1

Реализации Java Collections.sort() так быстро, как он получает, когда дело доходит до сортировки (двойной шарнирной быстрой сортировки).

Проблема здесь не в подробных подробностях, а в том, что вы сортируете вообще! Вам нужно только найти медиану, и для этого существуют линейные алгоритмы (сортировка является логарифмически-линейной). См. selection для некоторого вдохновения. Возможно, вам придется закодировать его самостоятельно, так как я не думаю, что в java-библиотеке есть доступная публичная реализация.

Другая вещь, которую я предлагаю, - использовать массив фиксированного размера (созданный один раз) вместо ArrayList. Поскольку вы заранее знаете размер фильтра, который даст вам небольшое ускорение скорости.

Кроме того, я не вижу, как избегать циклов помогает производительность в любом случае. Если вы не профилировали его и не доказали, что это правильно, я бы просто написал наиболее читаемый код.

И, наконец, TreeSet или любой другой вид сортированной структуры данных не поможет ни потому, что временная сложность является логарифмической для n вставки.

Answer 2

В качестве альтернативы отличным ответ Джованни Ботта:

Предположим, что у вас есть массив [7, 3, 8, 4, 6, 6, 2, 4, 6] и filterSize из 4. Тогда наш первый темп массив будет [7, 3, 8, 4] и мы можем сортировать его, чтобы получить [3, 4, 7, 8]. Когда мы вычисляем наш следующий временный массив, мы можем сделать это в линейной (или лучше?) Время следующим образом:

1. удалить 7
2. вставку 6 в отсортированном положении

Мы можем повторить это для все массивы temp после первоначального сортировки. Если вы тратите много времени на сортировку подмассивов, это может быть неплохим способом. Фокус в том, что он увеличивает требуемое хранилище, поскольку вам нужно запомнить порядок удаления записей, но это не должно быть большой проблемой (я бы не подумал).