Ползунок полосы прокрутки поля списка изменяет размер, когда содержание является переменной высотой

Возможно, это немного поздно для вас в игре, так как ваш вопрос, но давайте закончим.

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

Во-первых, приоритетные очереди не обязательно O (n log n).

Если у вас целочисленные данные, существуют очереди с приоритетом, которые работают за O (1) времени. Публикация Beucher и Meyer 1992 года «Морфологический подход к сегментации: трансформация водораздела» описывает иерархические очереди, которые работают довольно быстро для целочисленных значений с ограниченным диапазоном. В публикации Брауна 1988 года «Календарные очереди: реализация быстрой очереди с 0 (1) приоритетами для задачи с набором событий моделирования» предлагается другое решение, которое хорошо работает с большими диапазонами целых чисел - два десятилетия работы после публикации Брауна дали некоторые хорошие результаты для целочисленных операций. очереди с приоритетами быстро . Но механизм этих очередей может стать сложным: сортировки ведра и сортировки по основанию могут все еще обеспечивать работу O (1). В некоторых случаях вы можете даже иметь возможность квантовать данные с плавающей запятой, чтобы использовать преимущества очереди приоритетов O (1).

Даже в общем случае данных с плавающей запятой, что O (n log n) немного вводит в заблуждение. Книга Эделькампа «Эвристический поиск: теория и приложения» содержит следующую удобную таблицу, показывающую сложность времени для различных алгоритмов очереди приоритетов (помните, что очереди приоритетов эквивалентны сортировке и управлению кучей):

Как видите, многие приоритетные очереди имеют O (log n) затрат не только на вставку, но и на извлечение и даже управление очередями! Хотя коэффициент, как правило, отбрасывается для измерения временной сложности алгоритма, эти затраты все же стоит знать.

1118 Но все эти очереди все еще имеют временные сложности, которые сопоставимы. Какой лучше? В документе Cris L. Luengo Hendriks 2010 года, озаглавленном «Пересмотр очередей приоритетов для анализа изображений», рассматривается этот вопрос.

В тесте удержания Хендрикса в очередь приоритета были добавлены случайные числа N в диапазоне [0,50] , Затем самый верхний элемент очереди был исключен из очереди, увеличен на случайное значение в диапазоне [0,2] , а затем поставлен в очередь. Эта операция была повторена 10 ^ 7 раз. Затраты на генерацию случайных чисел были вычтены из измеренных времен. Лестничные очереди и иерархические кучи показали хорошие результаты в этом тесте.

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

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

Давайте вернемся к вашим вопросам:

Что быстрее: вставка в очередь с приоритетами или ретроспективная сортировка?

Как показано выше, очереди с приоритетами можно создавать эффективный, но все еще существуют затраты на вставку, удаление и управление. Вставка в вектор происходит быстро. Это амортизированное время O (1), и нет никаких затрат на управление, плюс вектор для считывания O (n).

Сортировка вектора обойдется вам в O (n log n) при условии, что у вас есть данные с плавающей точкой, но на этот раз сложность не скрывает такие вещи, как очереди с приоритетами. (Однако вы должны быть немного осторожнее. Быстрая сортировка очень хорошо работает с некоторыми данными, но имеет сложность времени в наихудшем случае O (n ^ 2). Для некоторых реализаций это серьезный риск для безопасности.)

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

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

Мы, вероятно, рассмотрели это выше .

Есть еще один вопрос, который вы не задавали. И, возможно, вы уже знаете ответ. Это вопрос стабильности. C ++ STL говорит, что приоритетная очередь должна поддерживать «строго слабый» порядок. Это означает, что элементы одинакового приоритета несопоставимы и могут быть расположены в любом порядке, в отличие от «общего порядка», где каждый элемент сопоставим. (Здесь хорошее описание порядка здесь .) В сортировке «строгий слабый» аналогичен нестабильной сортировке, а «полный порядок» аналогичен стабильной сортировке.

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

1133 Надеюсь, это поможет. Дайте мне знать, если вы хотите получить копию какой-либо из упомянутых статей или хотите получить разъяснения. : -) [тысяча сто тридцать три]