Как отслеживать / показывать прогресс во время сортировки C ++

Question

Я планирую написать интерактивный плагин для обработки геометрии C ++, который будет часто сортировать большие объемы данных. Хотя предварительные признаки состоят в том, что сортировка займет всего секунду или две, я бы предпочел показывать прогресс за это время - т.е. я хотел бы обновлять индикатор прогресса несколько раз в секунду. Это было бы предпочтительнее, чем включать курсор ожидания и оставлять пользователя с программой, который зависает на неопределенный период времени (даже если это всего несколько секунд).

Если бы я использовал что-то вроде std :: sort, я мог бы использовать функцию сравнения, чтобы время от времени обновлять индикатор прогресса, но у меня не было бы понятия «процент выполнения». Я также мог бы разбить сортировку на подсортировки, обновляя прогресс между подсортировками, а затем объединяя. Моя лучшая ставка может состоять в том, чтобы написать собственный метод сортировки, хотя я не знаю, сколько усилий потребуется, чтобы получить производительность, такую ​​же, как std :: sort (и обеспечить правильность). В любом случае, этот метод сортировки иногда отправляет «процент выполнения» в метод обратного вызова.

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

Обновление: Спасибо за отличные ответы. Было несколько очень хороших предложений, и я не буду выбирать приемлемый ответ, пока у меня не будет возможности проверить идеи в моем предстоящем проекте.

Обновление 2: Я завершил свой проект, и это оказалось не проблема (по крайней мере, для клиента. Поскольку они будут продавать программное обеспечение, они все еще могут получать отзывы от своих клиентов что изменит свое мнение по этому поводу). Выбор приемлемого ответа был трудным, потому что было много хороших ответов, но в итоге тот, который я выбрал, указывал на вики-статью о сортировке слиянием, которая имела очень вызывающую анимацию. Так что это первая стратегия, которую я бы придерживался, если бы мне нужно было продолжать это).

Answer 1

Я думаю, даже если бы вы написали свой собственный вид, вам бы пришлось провести много тщательных измерений, если вы хотите, чтобы индикатор прогресса был точным.Если вам нужен только приблизительный индикатор прогресса, вы можете использовать в качестве метрики некоторую метрику, например «среднее расстояние между сравниваемыми элементами» или «количество сравнений по сравнению со средним ожидаемым числом для быстрой сортировки», и реализовать идею сравнения, о которой вы уже упоминали.

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

В качестве примера вы, как правило, ожидаете около n log2 n операций для быстрой сортировки.Анализ количества сравнений является более подробным и может быть более точным, чем этот общий показатель, но для целей этого примера, давайте просто предположим.Таким образом, вы можете посчитать сравнения и сообщить number_of_comparisons / (n log2 n) как оценку прогресса.

Поскольку это всего лишь средний показатель, я бы провел несколько экспериментов и посмотрел бы, насколько далеко ваша оценка, и добавлю некоторые коэффициенты помадки, чтобыпривести его в соответствие со средним ожидаемым случаем.Вы также могли бы иметь индикатор выполнения, который указывал на неопределенность, имея вид «Это то, где я думаю, что я сделаю».индикатор и некоторое пространство после индикатора.

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

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

Если вы хотите использовать собственную сортировку, а ваша цель - предсказуемость, выберите heapsort .Это все еще O(n log2 n) сортировка, и она близка к минимальной сортировке сравнения (или я так помню из чтения Кнута).Кроме того, требуется очень предсказуемое количество времени для выполнения независимо от набора данных, который он подал.Это один из медленных сортов O(n log2 n), но все же.

Как уже упоминал один из ваших комментаторов, вы, возможно, решаете проблему, которой на самом деле не существует.Сначала запустите несколько экспериментов.Проблема - забавная интеллектуальная проблема независимо от ее полезности все же.: -)

Answer 2

Поскольку std :: sort основан на шаблонах, источник должен быть доступен в заголовке.Вы можете сделать его копию и вставить свой обратный вызов.Большой проблемой будет предсказать, насколько вы близки к завершению - большинство функций сортировки будут основаны на быстрой сортировке, которая не всегда выполняет одинаковое число сравнений.* будет возможность;алгоритм прост, а количество шагов четко определено.

Answer 3

Я бы порекомендовал ваш второй вариант: используйте std::sort или другую стандартную функцию сортировки, например qsort, и попросите компаратор сообщить о его ходе. Но не обновляйте при каждом сравнении - это будет невыносимо медленно - вместо этого обновляйте каждые (скажем) 100 мс.

Answer 4

использовать перебор:)

int elem_num = raw_data.size();
int percentage_delta = 100/(elem_num/20);
int percentage = 0;
int i = 0;
std::multiset<Elem*> sorted_data(&compareElemFunc);
foreach(Elem& elem, raw_data)
{
    sorted_data.insert(&elem);
    if(i%20)
    {
        updateProgressBar(percentage);
        percentage += percentage_delta;
    }
    i++;
}
//now, your data is perfectly sorted, iterate through sorted_data

(если вы не хотите реализовывать свой собственный std :: sort () и у меня нет полных требований)

Answer 5

Я вижу вашу проблему в следующем:

1. Вы хотите, чтобы дискретные события запускались во время одного непрерывного процесса.
2. Это подразделение просто для того, чтобы рассказать пользователю вещи

Мои предложения:

1. Используйте значок загрузки из чего-то вроде http://ajaxload.info/, или, если это не графический интерфейссреда, просто разобрать загрузку.Поскольку событие менее 2 секунд, это не будет проблемой.Ожидается зависание, если время ожидания превышает 10 секунд.

2. При написании собственного метода сортировки возникает много проблем с безопасностью потоков, что может вызвать проблемы, если ваш код использует мульти-предупреждение или обязательство сделать это в будущем.

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

Answer 6

Я не рекомендую пытаться взломать std :: sort.Это обычно реализуется с помощью introsort и является чрезвычайно быстрой операцией NLogN.Построение контейнера, который вы собираетесь сортировать, обычно обходится дороже, чем сортировка данных.

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

Вы можете обобщить этот ненавязчивый подход для любого вида трудоемкой операции, не прибегая к разбросу вызовов типа update_progress_bar () по всему коду, не вдаваясь в реализации std :: sort или не пытаясь заново изобрести колеса.Поскольку основной поток будет в состоянии ожидания / обновления индикатора выполнения и, следовательно, в некотором смысле блокируется, пока ваш рабочий поток не будет завершен, у вас нет проблем, связанных с многопоточностью (необходима синхронизация потоков для доступа к общим ресурсам по всему вашемуприложение за исключением счетчика хода выполнения, условий гонки, мертвых блокировок и т. д.).Это также будет самый плавный счетчик хода выполнения, который вы сможете внедрить, поскольку он будет обновляться одновременно.

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

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

Также, если ваш интросорт занимает так много времени, я должен задаться вопросом:В контейнере хранятся эти треугольные объекты или указатели на них?Если первое, вы можете рассмотреть второе, поскольку оно должно значительно ускорить процесс.

Answer 7

Используйте шаблон наблюдателя , чтобы сообщить родителю о завершении каждой части.Используя это и общее количество элементов, требующих сортировки, вы можете обновлять свой индикатор в реальном времени.