Comments 14
Я не знаю, как вы искали, но в C++ из коробки есть std::priority_queue.
ЗЫ: ну а linked list... Никто не использует его в качестве контейнера, это медленно. Максимум – "прошнуровывают" данные, хранящиеся где-то ещё.
ЗЫ: ну а linked list... Никто не использует его в качестве контейнера, это медленно. Максимум – "прошнуровывают" данные, хранящиеся где-то ещё.
вы можете сказать чем мой вариант медленней чем решение с массивами? Мне просто такое тестовое задание хотели дать на собеседовании, но не дали.
Я так и не понял, что именно вы нашли. Наивное решение с "раздвиганием" массива, что ли? Самое смешное – оно, как и ваше, работает за O(n), и не поручусь даже, что в среднем медленнее (данные лежат компактно – это преимущество)
Упомянутая тут же двоичная куча гарантирует вставку за O(log n). У неё, правда, есть недостаток – если придёт несколько элементов с одним приоритетом, то не факт, что они выйдут в том же порядке (типа unstable sort). Но для многих задач это неважно, а при необходимости можно решить так же, как для сортировки – заменив приоритет на пару (приоритет, номер по порядку), сортируемую лексикографически.
Для конкретных же задач есть свои решения. Например, если уровней приоритета мало – выгодно сделать несколько простых очередей по уровням.
А вообще прочитайте Кнута, на многие вопросы появятся базовые ответы, сможете с ходу подбирать если не оптимальное, то приемлемое решение.
Я улучшил алгоритм, посмотрите, если интересно. Теперь он работает быстрее. я сделал что приоритет можно устанавливать от -20 до 20. если у нас уже есть такой приоритет, то мы добавляемся в хвост последнему, если нет, то просто по массиву пробегаемся и потом к root устанавливаемся. Я пока думаю над этим решением, но оно теперь почти не ходит по указателям как в linked list, но в тоже время им считается. Можете показать алгоритм с двоичной кучей, который вы приводите за log n? я бы сравнил эту реализацию с моей.
Бинарная на массиве из rust std
Если без шуток то: бинарная, биномиальная
Для очереди с приоритетом используют двоичные кучи, по-сравнению с linked list здесь следующие преимущества:
Добавление элемента в сортированный linked list дает линейную сложность, тогда как двоичная куча - логарифмическую. То есть, имея очередь из миллиона элементов, чтоб добавить элемент в конец для linked list понадобится миллион итераций, а для кучи - всего 20.
Кучу очень удобно хранить в массиве что приводит к существенно меньшему количеству ре-аллокаций памяти, по сравнению с linked list. Ну и в целом данные будут компактнее, т.к. нет нужны для каждого элемента хранить адрес следующего элемента.
Я думаю то, что вы видели пример с массивом, на самом деле был пример с кучей. И в случае с массивом нет нужны при каждом новом элементе увеличивать его всего на один элемент. Обычно увеличивают в 2 раза, просто используется не все место сразу.
На хабре есть хорошие статьи про кучи, например эта: https://habr.com/ru/post/112222/ очень понятно рассказывает на пальцах как она работает, с примерами кода и где чаще всего применяется.
Если говорить про типичную реализацию связанного списка как стуктуры данных, а не как АТД (т.е. память под каждый элемент выделяется отдельно и связаны они через указатели), то как раз для списка реалокаций памяти не будет совсем (будут только аллокации для элементов списка). Для массива же придется иногда делать реалокации и это его недостаток (если не выделять память с запасом). Компенсируется это тем, помимо прочего, что данные лежат плотно, а это хорошо для кеш-памяти процессора - он может легко предсказать адрес следующей порции данных и загрузить её в кеш до того как она фактически понадобится в вычислениях.
ну вот смотрите, в массиве в некоторых случаях как я понял, нужно копировать из одного массива в другой все элементы, это разве правильно? в моем случае ничего копировать не надо. ну конечно это я поменял немного алгоритм, посмотрите как стало и да, можете привести пример алгоритма вашего, чтобы я сравнил?
Да, при исчерпании capacity придется копировать весь массив. Но за счет одной маленькой хитрости можно добиться, что это копирование произойдет O(1) для каждого элемента. Практически бесплатно, если учесть огромное увеличение скорости работы с массивом засчет локальности данных.
Хитрость называется "удвоение" — вы каждый раз, когда вам надо копировать массив, выделяете памяти в 2 раза больше текущего. Тогда следующий раз копировать массив придется совсем не скоро. При добавлении n элементов в массив за время работы программы будет максимум log(n) копирований массива. А если учесть размеры копируюмых массивов, то получится суммарно O(n) копирований элементов.
На практике используют не 2, а какой-то меньший множитель. Скажем, 1.7, но это принципиально ничего не меняет.
очереди с приоритетом используют min heap (https://en.wikipedia.org/wiki/Binary_heap), и насколько я знаю, это общепризнанно самый быстрый метод.
Списки точно медленные, потому что шмотки памяти, которые вам выглядят как элементы списка, на самом деле, внутри вот это: https://sourceware.org/glibc/wiki/MallocInternals и там мнооого всего.
Точно min heap, кстати? Я тут погуглил на предмет аналогов кучи с устойчивой сортировкой (элементы с одним приоритетом – в FIFO), так наткнулся на интересную конструкцию: The Bently-Saxe method, https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap
Не гарантирует худшее время (но амортизированное Ok), зато stable sort и вроде даже проще кучи.
Ключевое слово `register` - устаревшее. Сейчас он не оказывает никого эффекта на компилятор. Он знает лучше.
Очень много повторяющегося кода с незначительными измененями в правой части присваиваний - кандидат на отдельную фунцию. Её можно полностью протестировать. Без неё - есть верояность ошибки при копировании.
Пипец, чувак нашёл общий паттерн и обернул его во что-то осмысленное, набежали деды и заминусили, хабр как он есть
Алгоритм. Очередь с приоритетом