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

Question

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

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

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

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

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

Answer 1

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

Дать объявление самостоятельно Merge sort было бы возможно; алгоритм прост и количество шагов хорошо определено.

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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

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

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

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

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

Answer 5

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

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

Мои предложения являются:

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

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

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

Answer 6

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

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 

(в случае, если вы не хотите, чтобы реализовать свой собственный зЬй :: сортировки() и так как я не хватает полных требований)

Answer 7

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

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

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

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

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

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