WikiProject Computing | (Номинальный стартовый класс) |
---|---|
WikiProject Информатика | (Номинальный начальный класс, средняя важность) |
---|---|
Я думаю, что некоторые пояснения нуждаются в уточнении
- Разве определение не должно быть таким: пустая куча | корень + список непустых парных куч?
- Отсутствие указания, что под-куча в списке детей не может быть пустой, вводит в заблуждение.
- кажется, что слияние - это симметричная операция, но не ассоциативная. поэтому, если мы объединим список суб-куч в группы по 3 (или более), а затем объединим полученный список - будет иметь значение, в каком направлении мы делаем каждую часть. но слияние пар является симметричным, так что какое значение имеет в merge-pair (), идем ли мы слева направо или иначе на каждом уровне?
- Итаж Шерман ( разговорное ) 01:49, 11 октября 2013 г. (UTC)
Открытый вопрос уже решен
В статье говорится, что:
«Более того, это открытый вопрос, можно ли одновременно достичь ao (log n) амортизированной временной границы для клавиши уменьшения и O (1) амортизированной временной границы для вставки [8]».
Этот вопрос вроде бы решен. Например, Амр Элмасри в своей статье TALG'17 «На пути к оптимальным самонастраивающимся кучам» дает структуру данных с O (1) вставкой и ключом уменьшения O (log log n).
- 2001: 62A: 4: 413: 5D51: AF10: 173B: A57C ( разговор ) 12:41, 15 ноября 2018 г. (UTC)
- Спасибо; статья обновлена . 167.88.12.231 ( разговорное ) 05:09, 2 июля 2019 (UTC)
Утверждение «Часто быстрее, чем кучи на основе массивов»
В тексте в настоящее время утверждается, что «кучи спаривания часто на практике быстрее, чем двоичные кучи на основе массивов и d-арные кучи». Когда я прочитал это вчера, я обнаружил, что это довольно сильное и удивительное утверждение, поэтому я проверил 3 процитированных источника. Я пришел к выводу, что претензия кажется необоснованной, и я ее удалил. К сожалению, это изменение было отменено.
Здесь я хочу еще раз более подробно описать, почему я считаю, что текущая претензия не обоснована.
Позвольте мне сначала сосредоточиться на самой последней статье Ларкина, Сена и Тарьяна (2014), потому что она кажется отличного качества, актуальна и наиболее актуальна.
Если вы прочитаете эту статью, вы увидите, что объединенная куча выигрывает только в 9 из 41 выполненных тестов, в то время как неявные d-арные кучи выигрывают в 17 из 41. В конце статьи они просто приходят к выводу, что разные структуры данных благоприятны в разные ситуации. Наше решительное заявление, безусловно, не может быть оправдано на этом основании.
Ревертер моего изменения предложил в качестве компромисса формулировку «иногда» вместо «часто». Однако я вижу еще одну причину, по которой мы должны полностью удалить утверждение: что именно означает «на основе массива» и является ли реализация неявных куч в источниках этой формы?
В последней статье я думаю не потому, что в ней фактически используются указатели на индивидуально управляемые узлы памяти. Это делается для того, чтобы отслеживать узлы в структуре данных и поддерживать на них операцию «уменьшение ключа» на более позднем этапе. Однако это, очевидно, сводит на нет некоторые преимущества, связанные с кешем, и я утверждаю, что это больше не является истинно «основанным на массивах». Мы не определяем, что это означает, в статье Википедии, но я почти уверен, что большинство людей представляют себе полностью неявную структуру данных без вспомогательных данных и указателей. Связанный источник также тестирует «истинно» неявные d-арные кучи на основе массивов (которые они назвали «implicit_simple_n»), но они могут участвовать только в некоторых тестах, в которых стабильность указателя не требуется. Однако во ВСЕХ 9 тестах этот вариант также был самым быстрым и, в частности, быстрее, чем кучи спаривания. Иногда значительно так, как в тесте сортировки кучи.
Я также проверил два других связанных источника. Во втором, написанном Моретом и Шапиро, действительно утверждается, что для них кучи спаривания были быстрее, чем двоичные кучи. Однако это было 30 лет назад, когда компьютерный ландшафт был совершенно другим, и мы не знаем, в какой степени их реализация была «основанной на массивах». В отличие от более новой статьи, они не публиковали исходные коды или тайминги.
Поэтому я предлагаю полностью удалить выражение «кучи сопряжения на практике часто быстрее, чем двоичные кучи на основе массивов и d-арные кучи».
2A02: 810D: 4BC0: 33B8: 64EA: C348: 8F07: DFBB ( разговор ) 22:53, 2 сентября 2020 г. (UTC)
- Я не согласен полностью удалить это утверждение. Статья Море и Шапиро несколько устарела, но не противоречит более поздним работам, о которых я знаю. Ларкин нашел смешанные результаты, и мы должны сказать это; они также обнаружили, что наилучшие результаты были получены при отказе от функции отслеживания узлов, необходимой для таких вещей, как уменьшение ключа, и мы определенно должны сказать это, потому что отказ от этой функции несовместим со многими `` обычными '' вещами, которые можно было бы использовать в куче для, как алгоритм Дейкстры. Понятно, что если вы выполняете кучу вставок и удалений, «неявная простая» двоичная куча превзойдет всех соперников. Но в обстоятельствах, когда вам нужно уменьшить или удалить узлы, в последних двух документах сообщается, что спаривание кучи часто побеждает. Снефтел ( разговорное ) 11:47, 3 сентября 2020 (UTC)
- О, кстати, я не нашел ничего стоящего в статье Стаско и Виттера, и, похоже, вы пришли к такому же выводу. Независимо от всего остального, я предлагаю удалить ссылку на него. Снефтел ( разговор ) 12:06, 3 сентября 2020 (UTC)
- Также, чтобы еще больше замутить пруд, обратите внимание на https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.9380&rep=rep1&type=pdf . Они весьма негативно относились к двоичным кучам, особенно к маленьким (но в 1987 году это означало, что они даже больше не связаны с современными процессорами, чем Moret & Shapiro). Тем не менее их вывод - «Это зависит от того, нужна ли вам клавиша уменьшения» - сформулирован более четко. Снефтел ( разговор ) 12:33, 3 сентября 2020 (UTC)
- Я согласен с тем, что отказ от функции отслеживания узлов / уменьшения ключа является ключевым моментом во всем обсуждении производительности, и мы должны это заявить. Формулировка "на основе массива" - это моя самая большая проблема в текущем заявлении. Я согласен с более поздним заявлением в Википедии о том, что кучи объединения «почти всегда» быстрее, чем кучи на основе указателя. «Почти всегда» - опять же довольно сильная формулировка, но по сравнению с кучей пар, бумага действительно показывает, что они довольно конкурентоспособны.
- Я не являюсь экспертом в использовании кучи, но сомневаюсь, в какой степени требуется уменьшение ключа для выполнения «обычных» операций с кучей. Реализации кучи, которые я лично использовал в C ++, не поддерживают это, и, в частности, STL "std :: priority_queue" не поддерживает. Что касается алгоритма Дейкстры, вы можете тривиально переформулировать его так, чтобы он работал без отслеживания узлов и / или функции уменьшения ключа. Это можно сделать, всегда добавляя новые узлы вместо корректировки старых и просто игнорируя более поздние события при появлении. К сожалению, это не используется в статье Ларкина, Сена и Тарьяна, и, насколько я могу судить, это явно не описано в статье Википедии об алгоритме Дейкстры. Есть только небольшое неопределенное примечание: «На практике можно использовать другие структуры данных для достижения еще более быстрых вычислений». со ссылкой на статью, в которой авторы обнаружили, что алгоритм Дейкстры был самым быстрым с бинарными деревьями и без ключа уменьшения. Я цитирую: «В целом, наши результаты показывают, что использование стандартной очереди приоритета без операции уменьшения ключа в большинстве случаев приводит к лучшей производительности, чем использование очереди с операцией уменьшения ключа».
- В этой статье также говорится о двоичной куче без ключа стабильности / уменьшения указателя: «Это куча, полностью основанная на массивах». Это означает, что, по их мнению, реализация «implicit_n» Ларкина, Сена и Тарьяна на самом деле не основана на массивах.
- Я согласен с тем, что статья Стасько и Виттера не имеет большого отношения к заявлению. Вероятно, нам следует сослаться на вашу статью и вместо нее https://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf .
- 2A02: 810D: 4BC0: 33B8: 5408: DD09: 5FC0: F54F ( разговор ) 19:27, 3 сентября 2020 г. (UTC)
- Я решил добавить краткое описание безключевого подхода к статье об алгоритме Дейкстры, где раньше очень расплывчато упоминались «другие структуры данных». 2A02: 810D: 4BC0: 33B8: 5408: DD09: 5FC0: F54F ( разговор ) 20:18, 3 сентября 2020 г. (UTC)
- В случае Дейкстры, по общему признанию, рассмотрение неполной асимптотики времени из-за отсутствия поддержки ключа уменьшения является в значительной степени теоретическим; «нормальные» графики не приводят к большому количеству клавиш уменьшения. Существуют и другие алгоритмы, такие как Bentley-Ottmann, где клавиша уменьшения используется чаще, и именно здесь я лично видел, что кучи на основе указателей показывают явное преимущество перед двоичными кучами.
- Я думаю, что сейчас мы практически на одной странице ... Я собрал правку, как вы думаете? Снефтел ( разговор ) 09:34, 4 сентября 2020 (UTC)
- Я решил добавить краткое описание безключевого подхода к статье об алгоритме Дейкстры, где раньше очень расплывчато упоминались «другие структуры данных». 2A02: 810D: 4BC0: 33B8: 5408: DD09: 5FC0: F54F ( разговор ) 20:18, 3 сентября 2020 г. (UTC)
- Мне эти изменения нравятся. Спасибо за работу. Я бы, может быть, прямо упомянул бы общие чертовы кучи и в первом предложении, но это не принципиально важно по существу. 2A02: 810D: 4BC0: 33B8: B8E0: D0DD: 67A8: DFB4 ( разговор ) 15:14, 4 сентября 2020 г. (UTC)
Реализация на основе указателя
Выражение «представление дочерних узлов узла односвязным списком: указатель на первого дочернего узла, один на его следующего брата и один на его предыдущего брата (или, для крайнего левого брата, на его родителя)» является противоречивый. Узлы в односвязных списках не имеют указателей на своего предыдущего члена. Либо мы меняем формулировку на «двусвязный список», либо меняем описание на описание альтернативы с флагом конца списка. Мы также могли бы добавить ссылку на двоичное дерево левого потомка и правого брата, поскольку это более подробно раскрывает идею. Альбрехт Дж. ( Разговорное ) 08:22, 5 ноября 2020 (UTC)
- Я искал, кто мог бы добавить такую откровенно противоречивую информацию, и, как известно, это был я . Я бы поддержал вашу первую идею - переключиться на «двусвязный список» в этом предложении, а затем описать альтернативу, как это делается в статье. Обратите внимание, что двоичного дерева левого потомка и правого брата недостаточно: где-то должен быть родительский указатель, чтобы реализовать клавишу уменьшения. Снефтел ( разговор ) 11:07, 5 ноября 2020 (UTC)