Сортировать большую коллекцию, показывая прогресс

Question

Каков наилучший способ сортировки коллекции при обновлении индикатора выполнения?В настоящее время у меня есть код, подобный этому:

for (int i = 0; i < items.size(); i++)
{
    progressBar.setValue(i);

    // Uses Collections.binarySearch:
    CollectionUtils.insertInOrder(sortedItems, item.get(i));
}

Это показывает прогресс, но индикатор выполнения замедляется по мере увеличения количества элементов в sortedItems.У кого-нибудь есть лучший подход?В идеале я хотел бы использовать интерфейс, подобный Collections.sort(), чтобы я попробовал разные алгоритмы сортировки.

Любая помощь была бы отличной!

---

Для справки: этот код извлекает множество документов (1-10 миллионов) из Lucene и запускает для них пользовательский компаратор.Сортировка их путем записи данных обратно на диск будет слишком медленной, чтобы быть практичной.Большая часть затрат заключается в чтении элемента с диска и последующем запуске компаратора по элементам.У моего ПК много памяти, поэтому нет проблем, связанных с подкачкой на диск и т. Д.

В конце концов, я остановился на решении Стивена, поскольку оно было очень чистым и позволило мне легко добавить многопоточный алгоритм сортировки.

Answer 1

Вы хотите быть осторожным здесь.Вы решили использовать алгоритм, который постепенно создает отсортированную структуру данных, чтобы (я так понимаю) вы могли отображать индикатор выполнения.Однако при этом вы , возможно, выбрали метод сортировки, который значительно медленнее, чем оптимальная сортировка.(Оба вида будут O(NlogN), но это больше производительности, чем поведение big-O ...)

Если вы обеспокоены тем, что это может быть проблемой, сравните время для сортировки типичной коллекции, используя TreeMap и Collections.sort.Последний работает, копируя входную коллекцию в массив, сортируя массив и затем копируя его обратно.(Это лучше всего работает, если входная коллекция представляет собой ArrayList. Если вам не нужен результат как изменяемая коллекция, вы можете избежать окончательного копирования обратно, используя вместо этого Collection.toArray, Arrays.sort и Arrays.asList.)

Альтернативной идеей может быть использование объекта Comparator, который отслеживает количество вызовов, которые он вызывал, и использовать его для отслеживания прогресса сортировки.Вы можете использовать тот факт, что компаратор, как правило, будет вызываться примерно N*log(N) раз, хотя вам может потребоваться откалибровать его по фактическому используемому алгоритму ¹ .

Кстати,подсчет звонков в компаратор даст вам лучшее представление о прогрессе, чем при подсчете вставок.Вы не получите скорость прогресса, которая будет замедляться по мере приближения к завершению сортировки.

(У вас будут разные потоки, считывающие и записывающие счетчик, поэтому вам нужно учитывать синхронизацию. Объявление счетчика как volatile будет работать за счет дополнительного трафика памяти. Вы также можете просто проигнорироватьпроблема, если вы рады, что индикатор выполнения иногда отображает устаревшие значения ... в зависимости от вашей платформы и т. д.)

---

^{1 - с этим связана проблема.Существуют некоторые алгоритмы, в которых количество сравнений может существенно различаться в зависимости от исходного порядка сортируемых данных.Для такого алгоритма нет способа откалибровать счетчик, который будет работать в «не средних» случаях.}

Answer 2

Почему бы не реализовать собственную сортировку слиянием (что и делает Collections.sort) и обновить индикатор выполнения в ключевых точках алгоритма (скажем, после каждого слияния более 5% массива)?

Answer 3

Можете ли вы использовать неопределенный индикатор выполнения?Это все еще дает некоторую обратную связь пользователю, что что-то происходит.Ваш код будет выглядеть следующим образом:

progessbar.setIndeterminate(true);
ArrayList sorted = new ArrayList(items);
Colletions.sort(sorted);

progessBar.setString("Hey you're done!");

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

Answer 4

Один простой подход к индикатору выполнения это.

Вы можете фиксировать количество вызовов, чтобы обновлять ход выполнения независимо от размера элемента, используя мод. Например,

public void run(int total) {
    int updateInterval = total / 10;
    System.out.println("interval = " + updateInterval);
    for(int i = 0; i < total; i++) {
        if(i % updateInterval == 0) {
            printProgress((float)i / total * 100f);
        }
        // do task here
    }
}

private void printProgress(float value) {
    System.out.println(value + "%");
}

Это будет обновлять индикатор выполнения 10 раз (или 9 - проверять граничные условия), будет ли размер 10 или 10 миллионов.

Это всего лишь пример, измените значения соответствующим образом.

Answer 5

Возможно, я что-то пропустил, потому что никто другой не упомянул об этом, но похоже, что типы времени выполнения вашего исходного объекта List не являются реализацией RandomAccess и, следовательно, ваш вызов Collections.binarySearch выполняетсяв O (N) время.Это немного замедлит процесс, очень заметно, когда вы вдвое увеличите количество элементов для сортировки.

И, более того, если вы используете, например, LinkedList для sortedItems, тогдавставка также O (n).

Если это так, то вполне логично, что при переходе от 1 млн. до 2 млн. элементов ожидаемое время также примерно удваивается.

Длядиагностировать, какой из 2 List объектов проблематичен

1. Если индикатор выполнения медленный с самого начала, это items;попробуйте использовать другой контейнер, что-нибудь из дерева или hash-y
2. Если индикатор выполнения становится все медленнее и медленнее, когда он приближается к 100%, это sortedItems;тот же совет, что и выше

Обратите внимание, что замедление может вызывать List s.Также это не имеет ничего общего с индикатором выполнения.Проблема, которую вы описали, является алгоритмической в ​​отношении сортировки, а не обновления индикатора выполнения.

Answer 6

Проблема здесь заключается в физическом механизме сортировки - когда sortedItems увеличивается, insertInOrder, по определению, займет больше времени, так как это, скорее всего, операция O(n lg n) + O(n) (использование двоичного поиска для поиска следующего наименьшего элемента а затем вставив элемент). Неизбежно, что по мере увеличения вашей коллекции вставка следующего элемента в нужное место займет больше времени.

Единственный способ аппроксимировать индикатор выполнения, время которого линейно увеличивается, состоит в использовании некоторого приближения, аналогичного обратной функции lg, поскольку сортировка первых 1000 элементов может занять время, аналогичное сортировке последних 10 (что это конечно обобщение).

Answer 7

Если вы просто сравниваете время сортировки, выведите время до и после сортировки.

Трудно предсказать, сколько времени займет сортировка в дикой природе.Для некоторых видов это зависит от порядка ввода.Я бы использовал i/(double) items.size(), чтобы сгенерировать соотношение выполненной работы, и назвал бы это хорошим днем.Вы можете обновить панель каждые items.size()/100 итераций.Там нет причин хлопать плохой прогресс-бар бесполезными обновлениями.