Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 31
Жаль, что не оставили в переводе оригинальное название “It’s turtles all the way down.” – A guide to the Basics of Data Structures
На самом деле это намёк на смешной случай с Бертраном Расселом.
А в целом отличный подход к знакомству со структурами данных для младшего поколения.
Или для старшего, которое ещё не наигралось.
На самом деле это намёк на смешной случай с Бертраном Расселом.
А в целом отличный подход к знакомству со структурами данных для младшего поколения.
Или для старшего, которое ещё не наигралось.
А что за случай? Не слышал.
Этот случай, например, приведён в книге Хокинга «Кратчайшая история времени».
===
Несколько десятилетий назад известный ученый (некоторые говорят, что это был Бертран Рассел) выступал с публичной лекцией по астрономии.
Он рассказал, что Земля обращается вокруг Солнца, а оно, в свою очередь, — вокруг центра обширной звездной системы, называемой нашей Галактикой.
В конце лекции маленькая пожилая леди, сидевшая в задних рядах, встала и заявила:
— Вы рассказывали нам здесь полную ерунду. В действительности мир — это плоская плита, покоящаяся на спине гигантской черепахи.
Улыбнувшись с чувством превосходства, ученый спросил:
— А на чем стоит черепаха?
— Вы очень умный молодой человек, очень, — ответила старая леди. — Она стоит на другой черепахе, и так дальше, до бесконечности!
===
===
Несколько десятилетий назад известный ученый (некоторые говорят, что это был Бертран Рассел) выступал с публичной лекцией по астрономии.
Он рассказал, что Земля обращается вокруг Солнца, а оно, в свою очередь, — вокруг центра обширной звездной системы, называемой нашей Галактикой.
В конце лекции маленькая пожилая леди, сидевшая в задних рядах, встала и заявила:
— Вы рассказывали нам здесь полную ерунду. В действительности мир — это плоская плита, покоящаяся на спине гигантской черепахи.
Улыбнувшись с чувством превосходства, ученый спросил:
— А на чем стоит черепаха?
— Вы очень умный молодой человек, очень, — ответила старая леди. — Она стоит на другой черепахе, и так дальше, до бесконечности!
===
В более полной версии этой истории Рассел не просто рассказал о современной космологии, но перед этим обсмеял древнюю космологию с плоской землёй, китами-слонами и черепахой: мол, древние не задали себе вопрос, на чём же стоит та черепаха. А задали бы, так и отказались бы от неё.
Тут-то старушка взяла и поправила очень умного, но слишком молодого выскочку.
Тут-то старушка взяла и поправила очень умного, но слишком молодого выскочку.
Спасибо за статью.
Во-первых, опечатка в слове
Во-вторых, ссылка вроде должна вести на код, оформленный в виде класса, но ведет на все тот же список функций.
Чтобы обобщить все вышесказанное, я написала несколько строчек кода, содержащего функции для работы с кучей, а для фанатов ООП оформила все в виде класа
Во-первых, опечатка в слове
класа
Во-вторых, ссылка вроде должна вести на код, оформленный в виде класса, но ведет на все тот же список функций.
Наконец-то узнал что такое куча. Всё остальное приходилось сталкиваться и использовать. Но кучи… применимость несколько ограничена.
Кстати не сказано еще что хеш-таблицы хоть и имеют малое время на поиск данных, но в компенсацию этой характеристики плохо работают на вставку/добавление новых записей посему имеют ограниченное применение.
Кстати не сказано еще что хеш-таблицы хоть и имеют малое время на поиск данных, но в компенсацию этой характеристики плохо работают на вставку/добавление новых записей посему имеют ограниченное применение.
Куча — достаточно специфическая структура данных: у неё теоретически весьма неплохая сложность, но обращение к памяти весьма нерегулярное и потому она эффективна только на небольших размерах (когда она влазит в L1 кеш).
А насчёт «имеющих ограниченное применение» хеш-таблиц… вы это всерьёз или просто издеваетесь? В современном мире стоить только попытаться плюнуть — попадёшь в хеш-таблицу. Ещё до того, как плюнешь.
Когда вы пишите, скажем,
С хеш-таблицами есть другая беда: если использовать некриптостойкий хеш, то можно на коллизии нарваться, а считать криптостойкие хеши долго. Слава богу тут нам пришёл на помощь Intel: на процессорах с поддержкой AES можно посчитать aeshash за то же время, что и какой-нибудь менее «замороченный» хеш, а DoS-атаку уже не провести.
Так что с хеш-таблицами всё хорошо: с вероятностью 99% вы их используете по 100 раз на дню, только не знаете об этом.
А насчёт «имеющих ограниченное применение» хеш-таблиц… вы это всерьёз или просто издеваетесь? В современном мире стоить только попытаться плюнуть — попадёшь в хеш-таблицу. Ещё до того, как плюнешь.
Когда вы пишите, скажем,
var a = 1;a? Ответ: в хеш-таблицу соответствующей JavaScript-функции. А когда вы пишите a.x = b.x;a и b, ещё два — живут внутри объектов a и b). То же самое — в большинстве других сколько-нибудь распространённых скриптовых языках (неважно: это python, ruby или какой-нибудь lisp). Даже такие языки как C++ и Java, в некотором смысле подвержены этой участи: у них тоже для каждой функции есть хеш-таблица с переменными… в компиляторе. Когда всё «замораживается» и получается скомпилированный код эти хеш-таблицы исчезают, но если вы используете какой-нибудь guice, то часть таблиц этого рода остаются и в рантайме.С хеш-таблицами есть другая беда: если использовать некриптостойкий хеш, то можно на коллизии нарваться, а считать криптостойкие хеши долго. Слава богу тут нам пришёл на помощь Intel: на процессорах с поддержкой AES можно посчитать aeshash за то же время, что и какой-нибудь менее «замороченный» хеш, а DoS-атаку уже не провести.
Так что с хеш-таблицами всё хорошо: с вероятностью 99% вы их используете по 100 раз на дню, только не знаете об этом.
хеш-таблицы хороши когда соотношение чтение/запись сильно отличается, и когда нужно за один раз выбирать одно значение из таблицы. Большинство реальных запросов из баз данных и структур далеки от этих особенностей поскольку очень редко используют полный ключ для сопоставления записей, а для хеш-таблицы требуется исключительно полный ключ для позиционирования на конкретной записи, частичный ключ не имеет никакого смысла.
Единственное преимущество — это поиск конкретных записей по полному ключу в реально огромных базах данных, когда даже двоичный поиск в сортированном массиве не проходит по временным рамкам.
Единственное преимущество — это поиск конкретных записей по полному ключу в реально огромных базах данных, когда даже двоичный поиск в сортированном массиве не проходит по временным рамкам.
Мы, в общем-то, говорим об одном и том же, только смотрим на проблему с разных сторон. Вы рассматриваете разные структуры с позиций «а чего, собственно, с ними можно сделать» и приходите к выводу, что хеш-таблицы ведь почти ничего делать-то и не умеют: «поиск конкретных записей по полному ключу» и только. Я же замечаю, что эта одна-единственная операция, собственно, и нужна чуть ли не в сто раз чаще, чем все остальные, вместе взятые и в результате вы, почти наверняка, используете кучу хеш-таблиц даже не замечая этого.
Единственное преимущество — это поиск конкретных записей по полному ключу в реально огромных базах данных, когда даже двоичный поиск в сортированном массиве не проходит по временным рамкам.Ну да. Только я не знал что десяток элементов — это теперь называется «реально огромная база данных». Начиная примерно с этой точки хеш-таблицы начинают обгонять бинарный поиск — при условии, что хеш-функция распределяет данные по бакетам равномерно.
Вы всерьез не заметили, что человек сказал о куче, а не х. таблицах:
?
Всё остальное приходилось сталкиваться и использовать. Но кучи… применимость несколько ограничена.
?
Неа. Я всерьёз заметил про что именно человек говорит:
Кстати не сказано еще что хеш-таблицы хоть и имеют малое время на поиск данных, но в компенсацию этой характеристики плохо работают на вставку/добавление новых записей посему имеют ограниченное применение.
… и в ответе стали говорить о том, что таблицы применяются повсеместно, а не характеристиках вставки и удаления и связанных с этим ограничениями по применению, что было «ядром» высказывания. То, что хеш-таблицы применяются повсеместно (во многих областях) не вляется опровержением того, что у них есть ограничения (применение ограничено в силу характеристик). «Ограниченное применение» вовсе не означает, что структура мало где применяется.
Мне стоило написать не «Вы всерьез не заметили, что человек сказал о куче, а не х. таблицах», а "… не заметили, что человек сказал об ограниченности применения без уточнений именно о куче, а не хеш-таблицах..."
В первом сообщении сказано об ограниченном применении обоих структур, но «ограниченность» хеш-таблицы аргументирована, в отличие от кучи. Причем получается по сути трюизм — у каждой структуры есть особенности, которые ограничивают ее применение. Т.е. оспаривать фразу в целом бессмысленно — она верна в таком изложении (это трюизм), оспорить можно значимость характеристик вставки и пр., но не ссылкой на массовость применения. Указание же на ограниченность применения кучи — «голая», здесь нет аргументов, оправдывающих «ограниченность», и оспорить эту часть отсылкой к широте применения — разумный первый шаг.
Мне стоило написать не «Вы всерьез не заметили, что человек сказал о куче, а не х. таблицах», а "… не заметили, что человек сказал об ограниченности применения без уточнений именно о куче, а не хеш-таблицах..."
В первом сообщении сказано об ограниченном применении обоих структур, но «ограниченность» хеш-таблицы аргументирована, в отличие от кучи. Причем получается по сути трюизм — у каждой структуры есть особенности, которые ограничивают ее применение. Т.е. оспаривать фразу в целом бессмысленно — она верна в таком изложении (это трюизм), оспорить можно значимость характеристик вставки и пр., но не ссылкой на массовость применения. Указание же на ограниченность применения кучи — «голая», здесь нет аргументов, оправдывающих «ограниченность», и оспорить эту часть отсылкой к широте применения — разумный первый шаг.
Вы тут развели какую-то философию вокруг пары фраз. Причём дурацкую. Я же отвечал по существу: куча — действительно довольно редко применяемая структура данных. Хотя обоснованием этого факта Alexeyslav действительно не озабачивался (да и непонятно как он мог озаботится если он о том как устроена эта структура узнал из этой статьи «для начинающих») — я это сделал за него.
Вторая же фраза является трюизмом только если у вас переклинило в голове и вы забыли о том, что в русском языке слова могут иметь несколько значений. Слово ограниченный — из их числа. Оно может обозначать как окруженный, отделенный, огороженный со всех сторон, так и небольшой, умеренный, имеющий достаточно узкие пределы. В первом варианте вся фраза становится трюизмом, который обсуждать бессмысленно, тут вы правы — но это, собственно, означает, что вы её неправильно поняли. Я и все остальные люди отметившиеся в теме обсуждали именно второй вариант прочтения этой фразы, вторую часть которой я и опроверг.
Обсуждать же «ядро» высказывания после этого уже не нужно: я опроверг следствие, а значит и посылка тоже неверна (вспоминаем уроки логики: из лжи может следовать как ложь, так и истина, но из истины ложь следовать никак не может).
P.S. Уж если хотите быть занудой — то хотя бы вчитывайтесь в то, что вы пишите. И не считайте всех кругом идиотами.
Вторая же фраза является трюизмом только если у вас переклинило в голове и вы забыли о том, что в русском языке слова могут иметь несколько значений. Слово ограниченный — из их числа. Оно может обозначать как окруженный, отделенный, огороженный со всех сторон, так и небольшой, умеренный, имеющий достаточно узкие пределы. В первом варианте вся фраза становится трюизмом, который обсуждать бессмысленно, тут вы правы — но это, собственно, означает, что вы её неправильно поняли. Я и все остальные люди отметившиеся в теме обсуждали именно второй вариант прочтения этой фразы, вторую часть которой я и опроверг.
Обсуждать же «ядро» высказывания после этого уже не нужно: я опроверг следствие, а значит и посылка тоже неверна (вспоминаем уроки логики: из лжи может следовать как ложь, так и истина, но из истины ложь следовать никак не может).
P.S. Уж если хотите быть занудой — то хотя бы вчитывайтесь в то, что вы пишите. И не считайте всех кругом идиотами.
Вторая же фраза является трюизмом только если у вас переклинило в голове и вы забыли о том, что в русском языке слова могут иметь несколько значений
Именно об этом я вам и написал — о ином смысле слова «ограниченный», применимом в этом контексте.
Обсуждать же «ядро» высказывания после этого уже не нужно: я опроверг следствие
Только в случае, если воспринимать «ограниченность применения», как это сделали вы — как «редкий», «мало где применяющийся». Что, конечно, неверно. Опровержение следствия вида «хеш-таблицы используются повсюду, вы даже не замечаете этого» не опровергает посылки — посылка не была «мало где используется».
C «Я же замечаю, что эта одна-единственная операция, собственно, и нужна чуть ли не в сто раз чаще, чем все остальные, вместе взятые» не спорю.
P.S. Уж если хотите быть занудой — то хотя бы вчитывайтесь в то, что вы пишите. И не считайте всех кругом идиотами.
Что вы, это просто ремарка «проходя мимо» по поводу вашего разговора, не более. Никаких личных оценок; не воспринимайте это как выпад против вас. Вы правы по сути, и я с вами согласен в выводах. Просто претензия вида «хеш-таблицы, в силу своих особенностей (а и б) имеют ограниченное применение» разбивается простым «любая структура имеет ограничения в силу своих особенностей. Но операция поиска — наиболее частая и нагруженная, поэтому эти ограничения несущественны»(1). И это покрывает все смыслы «ограниченное применение». В отличие от «применяется повсюду»(2). (2) лишнее при наличии (1), я только об этом — по сути с вами согласен во всем.
Про сортировку кучей стоит добавить, что она не требует дополнительной памяти и применима только к структурам данных с прямым доступом. И вообще, выбор метода сортировки должен производиться индивидуально под конкретную задачу. При малых размерах эффективнее могут оказаться qsort или сортировка Шелла.
И еще про применение кучи. Помимо сортировки, можно выполнять эффективный поиск элементов по определенному условию. Например, кроме банального максимума (который является корнем в max-heap), легко найти 2-й или 3-й по величине элемент — это будут непосредственные потомки корня, ну и так далее. Также куча применяется в алгоритмах на графах.
И еще про применение кучи. Помимо сортировки, можно выполнять эффективный поиск элементов по определенному условию. Например, кроме банального максимума (который является корнем в max-heap), легко найти 2-й или 3-й по величине элемент — это будут непосредственные потомки корня, ну и так далее. Также куча применяется в алгоритмах на графах.
Вы забыли про самое распространённое применение кучи: priority queue. Когда вам нужно выбрать N самых больших (или самых маленьких) элементов из множества, то куча — это самая подходящая структура. Обыно нужное N невелико, так что главный бич кучи (нелокальные обращения к памяти) не успевает проявиться, а зато тот факт, что не нужна дополнительная память (и, главное, что не нужно эту дополнительную память выделать и освобождать) оказывается весьма полезным.
ребят… я тут формочки на php клепаю, можно я рядом посижу?)
Частичная сортировка по мотивам квиксорта тоже inplace делается.
en.cppreference.com/w/cpp/algorithm/nth_element
en.cppreference.com/w/cpp/algorithm/partial_sort
Причём, если нужно просто разбить N-элементный набор по K-ной порядковой статистике, то это выполняется за O(N). А если ещё и упорядочить первые K — то O(N*logK).
Хипсорт же — гарантировано выжрет O(N*logN) на построение кучи, а затем O(K*logN) на извлечение.
en.cppreference.com/w/cpp/algorithm/nth_element
en.cppreference.com/w/cpp/algorithm/partial_sort
Причём, если нужно просто разбить N-элементный набор по K-ной порядковой статистике, то это выполняется за O(N). А если ещё и упорядочить первые K — то O(N*logK).
Хипсорт же — гарантировано выжрет O(N*logN) на построение кучи, а затем O(K*logN) на извлечение.
Ну зачем же полный хипсорт-то делать? Достаточно маленькой кучки размера K. Легко и просто. Так у вас и памяти будет O(K) и времени потребуется O(N*logK). Первое — часто важнее, так как позволяет вам не портить обрабатываемые данные (если они в памяти) и обрабатывать данные, которые в память не влазят (в том числе распределённо на многих машинах). Что же касается K-ой порядковой статистики за время O(N), то сложность алгоритма (и, соответственно константа) там такие, что на небольших K (скажем до сотни) priority queue будет быстрее.
Ничего подобного. www.cplusplus.com/reference/algorithm/nth_element
P.S. Сори (коменты не читай — сразу отвечай)
P.S. Сори (коменты не читай — сразу отвечай)
> Например, кроме банального максимума (который является корнем в max-heap), легко найти 2-й или 3-й по величине элемент — это будут непосредственные потомки корня, ну и так далее. Также куча применяется в алгоритмах на графах.
Дабы читатели не остались в заблуждении, поправлю. 2й по величине элемент действительно находится в одном из двух потомков корня. А вот третий по величине элемент — это либо оставшийся потомок корня, либо один из двух потомков 2-го по величине элемента. Согласно определению кучи.
К слову, даже в той же википедии на иллюстрации-примере кучи 3-й по величине элемент находится не на первом, а на втором уровне глубины от корня.
Дабы читатели не остались в заблуждении, поправлю. 2й по величине элемент действительно находится в одном из двух потомков корня. А вот третий по величине элемент — это либо оставшийся потомок корня, либо один из двух потомков 2-го по величине элемента. Согласно определению кучи.
К слову, даже в той же википедии на иллюстрации-примере кучи 3-й по величине элемент находится не на первом, а на втором уровне глубины от корня.
1. «Не говоря уже о том, что структуры данных постоянно используются в спортивном программировании.» — самый последний повод изучать структуры данных, на мой взгляд.
2. Черепашками по воротам? Куда смотрят защитники природы и комитет против пыток животных??
3. К тем же воротам — обычная очередь в магазине была бы гораздо более наглядной аналогией. Собственно, от человеческой очереди и пошло название этой структуры.
2. Черепашками по воротам? Куда смотрят защитники природы и комитет против пыток животных??
3. К тем же воротам — обычная очередь в магазине была бы гораздо более наглядной аналогией. Собственно, от человеческой очереди и пошло название этой структуры.
Хабрахабр — не для клонов.Лучше бы от своего имени писали, а не создавали виртуала. С НЛО шутки плохи.
А за статью спасибо.
На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского.
На самом деле тут есть небольшая неточность, дочерние элементы в куче ещё могут быть равны родительскому элементу, иначе было бы неинтересно, а алгоритм пирамидальной сортировки требовал бы уникальности элементов массива.
Также куча всегда имеет высоту logn, где n — количество элементов
IMHO, в переводе на русский более привычно использовать
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Структуры данных. Неформальный гайд