Комментарии 40
*на первой картине изображена баба с коромыслом автор — Воснецов…
-17
Дежавю?
+1
Обычно buckets в русскоязычной литературе называют «корзинами», а не «вёдрами».
+2
Увеличивается в два раза при заполнении для амортизации операции выделения памяти, а не потому что в нет массивов с нефиксированным размером.
Если нужна матчасть, гуглите амортизационный анализ.
Если нужна матчасть, гуглите амортизационный анализ.
-1
в C нет массивов*
0
В реализации по большей части для того, чтобы уменьшить число коллизий и соответственно уменьшить число итераций по сколлайденным бакетам при поиске.
0
Может расскажете нам про амортизацию выделения памяти под массив для бакетов хэштаблицы? Гугл особо делиться информацией не хочет.
Или Вы имели ввиду, что амортизацией является именно удвоение массива, а не, скажем, инкрементальное увелечение? В таком случае да, я даже не знал что у этого действия есть свое название и как-то глупо было бы увеличивать массив инкрементально, поэтому я не стал вдаваться в детали очевидного решения.
Или Вы имели ввиду, что амортизацией является именно удвоение массива, а не, скажем, инкрементальное увелечение? В таком случае да, я даже не знал что у этого действия есть свое название и как-то глупо было бы увеличивать массив инкрементально, поэтому я не стал вдаваться в детали очевидного решения.
+3
И вообще хотя бы про хэштаблицы — это же совсем базовые вещи. При чём тут вообще PHP?
-4
Гм… Что значит причем тут пхп? Загляните в заголовок, там сюрприз =)
+4
Это базовая структура данных сделанная в пхп так же как в во всех других языках, правда немного через задницу, как это обычно в пхп.
-3
Что-то вы про классический hash table слишком подробно расписали, а чем PHP-шная реализация отличается от классической не отметили.
Я, например, не понял чем обеспечивается упорядоченность массива после сортировки… pListNext может ссылаться на элемент из другой корзины? Получается, что эффективная итерация в обратном порядке невозможна?
Я, например, не понял чем обеспечивается упорядоченность массива после сортировки… pListNext может ссылаться на элемент из другой корзины? Получается, что эффективная итерация в обратном порядке невозможна?
+2
А, блин. Понял. Тут в одной структуре скрестили практически независимые друг от друга хеш-таблицу (h, pData) и двусвязный список (pListNext, pListLast)…
И почему назвали pListLast а не pListPrev…
Чувствую оверхед на это должен быть приличный (по 3 указателя на каждый элемент против 1 на классическую hash table и 0 для массива). Ну и поиск по числовому индексу в такой структуре происходит через хеш-таблицу тоже, что не очень круто.
Кстати, кто-то объяснит зачем им понадобился именно двусвязный список? Или это исключительно для удаления элементов?
И почему назвали pListLast а не pListPrev…
Чувствую оверхед на это должен быть приличный (по 3 указателя на каждый элемент против 1 на классическую hash table и 0 для массива). Ну и поиск по числовому индексу в такой структуре происходит через хеш-таблицу тоже, что не очень круто.
Кстати, кто-то объяснит зачем им понадобился именно двусвязный список? Или это исключительно для удаления элементов?
0
pListLast меня тоже сначала смутил… И не понятно зачем нужен pLast (могли бы и односвязным списком для сколлайденых обойтись)
А в чем проблема поиска по числовому индексу через хештаблицу? Он не может быть реализован иначе т.к. массив в пхп это еще и мэп и вы можете использовать не только последовательные ключи.
Двусвязный так же и сортировку упрощает. На самом деле в бакете в пхп, так на память, где-то шесть членов и примерно десять в хештаблице (в структурах), это об экономии памяти.
А в чем проблема поиска по числовому индексу через хештаблицу? Он не может быть реализован иначе т.к. массив в пхп это еще и мэп и вы можете использовать не только последовательные ключи.
Двусвязный так же и сортировку упрощает. На самом деле в бакете в пхп, так на память, где-то шесть членов и примерно десять в хештаблице (в структурах), это об экономии памяти.
0
Проблема поиска по числовому индексу в том, что это намного медленнее, чем в массивах в более типизированных языках. Я всё думал, может в пхп всё же массивы реализованы в комбинации обычный массив (для целых индексов) + хэш… Но в такой реализации непонятно как реализовать: $m[0] = $m[10000000] = «ok». Всё же надеялся, что светлые умы что-нибудь да придумали)
0
Для повышения кругозора можете сравнить, как реализуются словари в Python — blip.tv/pycon-us-videos-2009-2010-2011/pycon-2010-the-mighty-dictionary-55-3352147
0
О, это же Open adressed hash tables en.wikipedia.org/wiki/Open_addressing
Даже не подозревал что они используются. Это и про python 2.7 и про 3.x?
Даже не подозревал что они используются. Это и про python 2.7 и про 3.x?
0
Я решил не возвращаться к нашему кейсу с ключами 54 и 90… А вообще спасибо, мне нравятся ваши статьи, довольно интересно заглядывать внутрь.
0
Не очень понял график с памятью. Типа при 4096 элементах памяти требуется дофига, а при 4097 уже с гулькин нос? И вообще научитесь подписывать оси на графике. Это ж технический пост, а не какой-то дешёвый маркетинг.
+1
4096-8191 элементов потребляется одинаковое количество памяти. Графики можете в виде лестницы представить.
0
А вот вы неправы. Я вчитался в детали и запустил тест. График в статье показывает разницу до и после вставки определённого элемента и падает он не до нуля, а до 132-136. А график кумулятивного потребления памяти выглядел бы так:
(по вертикали общий объём памяти в байтах)
Заметьте, совсем другая картина: нет никаких ужасающих скачков. Сами корзины едят гораздо больше памяти, чем собственно хэш-таблица.
(по вертикали общий объём памяти в байтах)
Заметьте, совсем другая картина: нет никаких ужасающих скачков. Сами корзины едят гораздо больше памяти, чем собственно хэш-таблица.
+1
Интересно ещё представить график в другом виде, как я это делал в своей недавней статье:
По вертикали отношение используемой памяти в байтах к числу элементов в массиве, то есть количество байт на элемент. Тестировалось на PHP 5.3.2-1ubuntu4.14 (i686).
Видно, что в пределе расширение хэш-таблицы вызывает прыжки на 4 байта, со 140 до 144, вызывая трёхпроцентные колебания вокруг общего среднего. Кстати, интересен вопрос, почему у маленьких таблиц затраты на запись от 132, а дальше нижний порог доходит до 140.
По вертикали отношение используемой памяти в байтах к числу элементов в массиве, то есть количество байт на элемент. Тестировалось на PHP 5.3.2-1ubuntu4.14 (i686).
Видно, что в пределе расширение хэш-таблицы вызывает прыжки на 4 байта, со 140 до 144, вызывая трёхпроцентные колебания вокруг общего среднего. Кстати, интересен вопрос, почему у маленьких таблиц затраты на запись от 132, а дальше нижний порог доходит до 140.
0
Да, простите за хреновые графики. Просто так долго искал тулзу, которая способна построить график по, хотя бы, 1000 точек (тобишь не юзает гугловские чарты, которые вываливаются в 400 из-за длинных урлов), что терпения уже еле хватало на детали.
Кстати если кто-нибудь подскажет действительно хорошую тулзу для чартов, буду признателен.
Кстати если кто-нибудь подскажет действительно хорошую тулзу для чартов, буду признателен.
0
Я использую неправославный Excel, но вообще люди любят gnuplot.
+1
Асимптотика O(1) при работе с массивами радует.
+1
Когда читаю книги о том же PHP, всегда, когда сталкивался вновь с теми же массивами (циклы, функции и тп.), хотелось видеть не только описание на примере, но также пару строк о том, где эти массивы применяются при разработке приложений. Ведь, легче разобраться в том, что понятно, как и где это можно будет применить на практике.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как устроены массивы в PHP