Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 66
Кстати, в питоне есть array — docs.python.org/library/array.html Правда, он типизированный для чисел.
Я лично ни разу не использовал, но говорят, что для экономии памяти в некоторых задачах отлично подходит.
Я лично ни разу не использовал, но говорят, что для экономии памяти в некоторых задачах отлично подходит.
Пост целиком не читал. Мне кажется оценивать сложность доступа к элементу хэша как O(1) неверно, т.к. такая оценка не учитывет коллизий, которые разрешаются за линейное время (от количества элементов с таким же хэшем).
Согласен, далее в статье так и написано. Начало — поправлю.
Вы в статье применяете Amort. в двух разных смыслах. Действие работает за амортизированное время O(f(n)), если при выполнении его N раз будет выполнено O(N f(n)) операций. В частности, у Вас написаны правильные оценки для добавления в вектор и для AVL-дерева. Для хэша можно считать, что время операции в среднем O(1). Это означает, что, если входные данные удовлетворяют некоторому распределению, то математическое ожидание количества выполненых операций будет O(1). Для хэша, правда, это свойство ещё надо доказать, но что такое Amort.O(1)/O(N) вообще не понятно, довольно бесполезная оценка.
Если следовать вашей логики, то сложность поиска по массиву не есть O(n), ведь с вероятность 1/n элемент может находится в первой ячейке. А по хешь таблице может быть и O(n), ведь
В том-то и дело, что оценка O(1) — точна и верна, так как она — асимптотическая. В эту оценку входит то, что иногда операции могут выполнятся больше одного раза.
Более строго: в хорошей хэш-таблице оценка количества элементов с совпадающим хэшем пусть и не точно единица, но всё же пренебрежимо мала по сравнению с количеством элемментов, и также мало отличается от единицы. Случаи вырождения хэша в линейный список не рассматриваем :)
Более строго: в хорошей хэш-таблице оценка количества элементов с совпадающим хэшем пусть и не точно единица, но всё же пренебрежимо мала по сравнению с количеством элемментов, и также мало отличается от единицы. Случаи вырождения хэша в линейный список не рассматриваем :)
> В эту оценку входит то, что иногда операции могут выполнятся больше одного раза.
Какая разница сколько раз будут выполняться операции поиска элемента, если число элементов много больше количества возможных хэшей?
> в хорошей хэш-таблице оценка количества элементов с совпадающим хэшем пусть и не точно единица, но всё же пренебрежимо мала по сравнению с количеством элемментов
А в идеальной всё ещё лучше, не поверите. Но мы живём в реальном мире и хранение сверхбольшой хэш-таблицы может привести к непозволительному расходу памяти, потому коллизии — далеко не фантастика.
Какая разница сколько раз будут выполняться операции поиска элемента, если число элементов много больше количества возможных хэшей?
> в хорошей хэш-таблице оценка количества элементов с совпадающим хэшем пусть и не точно единица, но всё же пренебрежимо мала по сравнению с количеством элемментов
А в идеальной всё ещё лучше, не поверите. Но мы живём в реальном мире и хранение сверхбольшой хэш-таблицы может привести к непозволительному расходу памяти, потому коллизии — далеко не фантастика.
Да, ну и раз уж Вы в ладах с теорией, давайте откроем определение О(x). Опишите какую-то реализацию хеша, например просто скажите, что его таблица позволяет хранить ссылки для 1000 разных хешей ключей, потом вычислите ту самую константу C, которой должно хватить для любого количества элементов n, тем самым доказав мою неправоту. Потому что я утверждаю, что для O(1) такой константы не существует.
Объясняю. Предлагаю вам конкретную, достаточно эффективную реализацию.
Как только хэш-таблица заполняется более, чем на 80%, то она расширяется.
Как только заполняется менее, чем на 40% — сжимается.
Среди всех способов разрешения коллизий наиболее эффективный — квадратичное пробирование (метод квадратичных проб, Quadratic collision resolution).
Поэтому используем именно его, это даст лучшие оценки для количества сравнений элементов между собой (точные оценки можно найти здесь).
Еще раз повторюсь.
Во-первых, данное количество сравнений элементов при коллизиях пренебрежимо мало по сравнению с количеством элементов в хэш-таблице (особенно в большой), отсюда и возникает оценка O(1) (на бесконечности).
И два, не надо экономить на памяти, она очень дешёвая. Делайте большие хэш-таблицы, не бойтесь. Сейчас все реализации должны хорошо работать с памятью :)
Как только хэш-таблица заполняется более, чем на 80%, то она расширяется.
Как только заполняется менее, чем на 40% — сжимается.
Среди всех способов разрешения коллизий наиболее эффективный — квадратичное пробирование (метод квадратичных проб, Quadratic collision resolution).
Поэтому используем именно его, это даст лучшие оценки для количества сравнений элементов между собой (точные оценки можно найти здесь).
Еще раз повторюсь.
Во-первых, данное количество сравнений элементов при коллизиях пренебрежимо мало по сравнению с количеством элементов в хэш-таблице (особенно в большой), отсюда и возникает оценка O(1) (на бесконечности).
И два, не надо экономить на памяти, она очень дешёвая. Делайте большие хэш-таблицы, не бойтесь. Сейчас все реализации должны хорошо работать с памятью :)
Пожалуй согласшусь, для такой схемы работы оценка будет верна. Конечно у этой схемы есть свои минусы, и для каких-то очень специфичных задач она не подойдёт, но в целом вполне универсальна.
> Во-первых, данное количество сравнений элементов при коллизиях пренебрежимо мало по сравнению с количеством элементов в хэш-таблице (особенно в большой), отсюда и возникает оценка O(1) (на бесконечности).
Вот тут неточность. Бесконечность малым это количество будет лишь в случае бесконечного значения ключей. Если посмотреть на приведённую Вами таблицу, для метода квадратичных проб и 75% заполненности можно найти два числа — 2.01 и 4.64 (кстати, что такое Successful и Unsuccessful? Лучший и худший случаи?), что подтверждает, что на разрешение коллизии будет тратится время по крайней мере того же порядка.
> Во-первых, данное количество сравнений элементов при коллизиях пренебрежимо мало по сравнению с количеством элементов в хэш-таблице (особенно в большой), отсюда и возникает оценка O(1) (на бесконечности).
Вот тут неточность. Бесконечность малым это количество будет лишь в случае бесконечного значения ключей. Если посмотреть на приведённую Вами таблицу, для метода квадратичных проб и 75% заполненности можно найти два числа — 2.01 и 4.64 (кстати, что такое Successful и Unsuccessful? Лучший и худший случаи?), что подтверждает, что на разрешение коллизии будет тратится время по крайней мере того же порядка.
А на работу то в итоге взяли?
Примеры из Java в принципе допустимы, но не совсем корректны. Где то автор приводит в пример интерфейс (Set, Map), где то реализацию (HashTable, ArrayList), но в принципе ничего криминального в этом нет.
А вот Vector почти тот же самый ArrayList, но потокобесопасный при доступе к элементу. Он считается deprecated в новых версиях и вместо него используется ArrayList+обертка Collections.synchronizedList.
А вот Vector почти тот же самый ArrayList, но потокобесопасный при доступе к элементу. Он считается deprecated в новых версиях и вместо него используется ArrayList+обертка Collections.synchronizedList.
К сожалению, я не java engineer потому делал обзор исходя из своих, довольно скудных знаний. Замечание учту.
Vector не является deprecated, он член Java Collections Framework после реализации интерфейса List с версии Java 1.2, остаётся там наравне с ArrayList, хотя да, рекомендуют использовать последний.
Основа идеологии Java (как я ее себе понимаю), это единый механизм работы сходных классов. В тот момент, когда SUN(ныне oracle) выпустила Java Collections Framework этот механизм организации потокобезопастности стал приоритетным в использовании. Vector действительно еще не помечен как deprecated, но это я подозреваю это связано с тем, что он используется в большом количестве мест и не может быть заменен мгновенно. Так что с точки зрения документации вы правы.
Только не stl::set, stl::map и т.д., а std::set, std::map.
Отличная статья!
Колитесь, что за крупная контора, в которую вы устроились? :)
Колитесь, что за крупная контора, в которую вы устроились? :)
java: java.util.TreeMap<K,V>, так же автора мучает подозрение что java.util.Map<K,V> — из той же оперы
java.util.Map — это интерфейс, в частности для HashMap и TreeMap.
И в java Hashtable — устаревшая реализация ассоциативного массива. HashMap вместо нее
std::list, который в stl, двусвязный.
Если питоновский list является vector, который основан на однотипном array, то как тогда он может содержать разные типы (например [1, 'a', True])?
если не ошибаюсь, list в питоне — гетерогенный. массив указателей на объекты иначе говоря
Это слегка мутировавший вектор. Массив, на котором он базируется — является массивом ссылок на элементы произвольного типа.
Смотрим сорсы в них include/listobject.h
Там видим:
Смотрим сорсы в них include/listobject.h
Там видим:
typedef struct {
PyObject_VAR_HEAD
/* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
PyObject **ob_item;
/* ob_item contains space for 'allocated' elements. The number
* currently in use is ob_size.
* Invariants:
* 0 <= ob_size <= allocated
* len(list) == ob_size
* ob_item == NULL implies ob_size == allocated == 0
* list.sort() temporarily sets allocated to -1 to detect mutations.
*
* Items must normally not be NULL, except during construction when
* the list is not yet visible outside the function that builds it.
*/
Py_ssize_t allocated;
} PyListObject;
В С++ есть hash_map, хотя и не в любой реализации. В майкрософтовской есть, в расширении STL.
unordered_map есть в бусте, в TR1 и в С++0х.
Да, в новом стандарте тоже есть подобие, см. t.co/jgPorAa -> StackOverflow.
насчет множества в питоне ( immutable set в контексте статьи ) — это frozenset, а не кортеж
В PHP есть и Array и Linked List: ru.php.net/manual/en/spl.datastructures.php
Ну автор… Ну нет в C++ пространста имен stl, а есть std! std::vector, std::map. Помарка, а впечатление смазалось.
А вообще, на есть лекции MIT по теории алгоритмов (курс 6.046J), первая лекция к примеру — на youtube. Сам Лезерсон читает и Эрик Демейн (Erik Demaine). Там весь курс.
А вообще, на есть лекции MIT по теории алгоритмов (курс 6.046J), первая лекция к примеру — на youtube. Сам Лезерсон читает и Эрик Демейн (Erik Demaine). Там весь курс.
1. тут неточность:
смешаны в кучу две разные операции:
— вставка в конец (append) — амортизированное O(1)
— вставка куда угодно еще — O(N) без всяких амортизированных оценок.
смысл амортизированной оценки в том, что хотя заранее неизвестна сложность одного append-а (O(1) или O(N)), гарантируется, что суммарная сложность N append-ов — O(N), а не N*O(N) = O(N^2).
про обычную вставку это утверждение не выполняется.
2. про это не написано ни слова, но хэши в разных языках чуть отличаются, например, array в php еще содержит внутри список ключей, благодаря чему можно их обходить в порядке добавления.
(парадоксально, но тут php оказывается удобнее, несмотря на отсталость в поддержке прочих коллекций)
в остальных языках таких гарантий «по умолчанию» нет, в python 2.7+ есть отдельный тип OrderedDict, в java — LinkedHashMap.
многие реализации js тоже сохраняют порядок добавления, но насколько я помню, это не специфицировано.
insert_after: O(N), если вставляется последний элемент, то время может быть O(1) — потому обычно пишут Amort. O(1).
смешаны в кучу две разные операции:
— вставка в конец (append) — амортизированное O(1)
— вставка куда угодно еще — O(N) без всяких амортизированных оценок.
смысл амортизированной оценки в том, что хотя заранее неизвестна сложность одного append-а (O(1) или O(N)), гарантируется, что суммарная сложность N append-ов — O(N), а не N*O(N) = O(N^2).
про обычную вставку это утверждение не выполняется.
2. про это не написано ни слова, но хэши в разных языках чуть отличаются, например, array в php еще содержит внутри список ключей, благодаря чему можно их обходить в порядке добавления.
(парадоксально, но тут php оказывается удобнее, несмотря на отсталость в поддержке прочих коллекций)
в остальных языках таких гарантий «по умолчанию» нет, в python 2.7+ есть отдельный тип OrderedDict, в java — LinkedHashMap.
многие реализации js тоже сохраняют порядок добавления, но насколько я помню, это не специфицировано.
1. Сейчас исправлю.
2. К сожалению подробно не мог рассмотреть все хэши в рамках одной статьи, если рассматривать подробно и все вариации — то на каждую структуру можно по отдельной статье написать (хотя, возможно они этого заслуживают).
2. К сожалению подробно не мог рассмотреть все хэши в рамках одной статьи, если рассматривать подробно и все вариации — то на каждую структуру можно по отдельной статье написать (хотя, возможно они этого заслуживают).
2. как-то странно, что ListIterator отдельно упомянут, хотя там все как раз более очевидно, а с итерацией по хэшам полная тишина.
дальше читаем =)
3. почему оценки для деревьев амортизированы, когда они вполне себе worst-case?
4. почему у вас множества только immutable бывают?
«заморозить» любую коллекцию можно, а множества в виде стандартных типов (java.util.HashSet, set() в python) вполне себе изменяемы.
их можно упомянуть как упрощенный вариант map, где не надо хранить значения.
в том же php множеств нет, но они при желании эмулируются через array('key1' => true, ..);
дальше читаем =)
3. почему оценки для деревьев амортизированы, когда они вполне себе worst-case?
4. почему у вас множества только immutable бывают?
«заморозить» любую коллекцию можно, а множества в виде стандартных типов (java.util.HashSet, set() в python) вполне себе изменяемы.
их можно упомянуть как упрощенный вариант map, где не надо хранить значения.
в том же php множеств нет, но они при желании эмулируются через array('key1' => true, ..);
3. Были упомянуты AVL-деревья, некоторые реализации которых, на сколько я знаю, работают за амортизированное время. Кроме того, бывают и другие деревья. Декартово, например. Там время работы такое в среднем. Правда, я не знаю, применяются ли они как стандарт в каких-нибудь языках.
как я понял, речь о деревьях шла как о способе реализации Map<K,V>, декартовы и прочие деревья это отдельная история для более специализированных задач.
Я думаю, тот факт, что структуру можно использовать для других задач, сам по себе не означает, что её не надо использовать для наших. Map<K,V> можно реализовать как минимум десятком существенно разных способов и красно-чёрные деревья с хэшами выбраны явно не как минимально удовлетворяющие требованиям. Но в целом я придираюсь, конечно.
да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).
а нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
— в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках)
— в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках)
— в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне
и вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
а нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
— в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках)
— в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках)
— в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне
и вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
Из добрых обуждений, а не критики ради (чтоб статья была точнее).
Про вектор (vector): insert_after: O(N), если вставляется последний элемент, то время может быть O(1) — потому обычно пишут Amort. O(1).
Совершенная неправда! Amort. O(N). Амортизированное время добавления в конец — действительно, O(1). Отсылаю к видеолекциям MIT:)
Если на пальцах, то при insert_after вам каждый раз(!) необходимо копировать часть массива до элемента, после которого вставляете. А при добавлении в конец — только когда нет свободного места.
Про вектор (vector): insert_after: O(N), если вставляется последний элемент, то время может быть O(1) — потому обычно пишут Amort. O(1).
Совершенная неправда! Amort. O(N). Амортизированное время добавления в конец — действительно, O(1). Отсылаю к видеолекциям MIT:)
Если на пальцах, то при insert_after вам каждый раз(!) необходимо копировать часть массива до элемента, после которого вставляете. А при добавлении в конец — только когда нет свободного места.
Вообще, неблагодарное это дело на такие темы писать:) Тут мне кажется надо лио об одной из типов коллекций на одной платформе говорить, либо книгу писать.
Кто бы еще оформил подобные сведения в рисунок, который помогал бы быстро выбрать оптимальную структуру исходя из известных требований. Дело в том, что в той же Java этих структур за сотню (с апачевскими и гугловскими либами), и о положительных свойствах большинства из них мало кому известно.
Хотя, конечно, тем кто обладает знаниями обо всех структурах, нет времени диаграммы для чайников рисовать (см. фразу Билла Гейтса об «Искусстве Программирования»)
Хотя, конечно, тем кто обладает знаниями обо всех структурах, нет времени диаграммы для чайников рисовать (см. фразу Билла Гейтса об «Искусстве Программирования»)
В С++ есть нормальные хэши — std::tr1::unordered_set.
Кстати говоря, если автор затронул тему питона, то можно заметить один интересный момент — в питоне хэш-функции для чисел и строк имеют «плохое» распределение, например
Это позволяет быстрее получать индекс элемента, просто беря i бит для таблицы размера 2**i. Правда есть и недостаток — если мы возьмем в качестве ключей последовательность типа [i << 16 for i in range(20000)] то время поиска упадет до O(N). Но, как пишут авторы, «But catering to unusual cases should not slow the usual ones, so we just take the last i bits anyway.» Собственно, если вы будете делать свой класс для ключа в питоне, функцию хэша лучше делать с таким же распределением.
>>> map(hash, (0, 1, 2, 3))
[0, 1, 2, 3]
>>> map(hash, ("namea", "nameb", "namec", "named"))
[-1658398457, -1658398460, -1658398459, -1658398462]
>>>
Это позволяет быстрее получать индекс элемента, просто беря i бит для таблицы размера 2**i. Правда есть и недостаток — если мы возьмем в качестве ключей последовательность типа [i << 16 for i in range(20000)] то время поиска упадет до O(N). Но, как пишут авторы, «But catering to unusual cases should not slow the usual ones, so we just take the last i bits anyway.» Собственно, если вы будете делать свой класс для ключа в питоне, функцию хэша лучше делать с таким же распределением.
В примерах на плюсах несколько досадных ошибок:
1) массив (array) в плюсах объявляется не как
а как
2) с/с++: std::list — как уже написано выше в комментах — двусвязный список а не односвязный
3) таки существуют хеш-таблицы в C++0x: std::unordered_set/std::unordered_map
4) в последнем наборе примеров надо не stl::set, а std::set
1) массив (array) в плюсах объявляется не как
int[10] i_array;а как
int i_array[10];2) с/с++: std::list — как уже написано выше в комментах — двусвязный список а не односвязный
3) таки существуют хеш-таблицы в C++0x: std::unordered_set/std::unordered_map
4) в последнем наборе примеров надо не stl::set, а std::set
Ещё одно: Почему автор считает, что множество это обязательно immutable? Насколько я знаю, это не так.
Множество — это просто реализация абстракции математического множества, т.е. набора уникальных различимых элементов.
Множество — это просто реализация абстракции математического множества, т.е. набора уникальных различимых элементов.
Для Python есть хорошая статья на эту тему: wiki.python.org/moin/TimeComplexity
Неплохо бы еще добавить сравнение контейнеров по расходу памяти. Как я понимаю, HashTable в этом отношении может быть весьма расточительна при длинном хэше
Позволю себе высказаться. Я уже заметил что на Хабре половина читателей до сих пор не в курсе про существование хеш-таблиц, и для поиска всегда предлагают допотопные деревья. Другая половина теперь в курсе, но постоянно от не слышны какие-то жалобы, типа мол коллизий много, распределение плохое, и т.д. Используйте мол, деревья. Прежде чем предлагать использование подобных неудобных, устаревших, громоздких структур из 60-х гг., посчитайте, сколько у вас будет уходить времени только на переворачивание веток при любом добавлении или удалении. И сколько времени будет занимать поиск (сколько надо сделать сравнений) при использовании например строк в качестве ключа.
Хеш-таблица в большинстве случаев выгоднее этого неудобного дерева. Недаром она используется в качестве основы для ассоц. массивов в PHP и других языках.
Ну и списки — тоже на редкость неудобная хрень. Следует всегда использовать индексированные массивы, кроме тех случаев, когда требуется делать вставки в середину.
Хеш-таблица в большинстве случаев выгоднее этого неудобного дерева. Недаром она используется в качестве основы для ассоц. массивов в PHP и других языках.
Ну и списки — тоже на редкость неудобная хрень. Следует всегда использовать индексированные массивы, кроме тех случаев, когда требуется делать вставки в середину.
я про это комментарий выше писал.
да, в самом php деревьев нет, они на тех объемах, с которыми обычно работает php, просто не нужны.
но вы неявно используете деревья всякий раз, когда пишете «order by key» или «where key > const»
использование деревьев вместо хэшей там, где свойства деревьев не нужны — это дурь, как и использование in_array() вместо isset() для поиска во множестве с заранее известными элементами.
последнее повсеместно встречается, особенно доставляют такие проверки в цикле, привет O(N^2) и тормозам уже на паре тысяч элементов.
статья как раз для того написана, чтобы выбирали то, что надо, а не что первое вспомнится.
да, в самом php деревьев нет, они на тех объемах, с которыми обычно работает php, просто не нужны.
но вы неявно используете деревья всякий раз, когда пишете «order by key» или «where key > const»
использование деревьев вместо хэшей там, где свойства деревьев не нужны — это дурь, как и использование in_array() вместо isset() для поиска во множестве с заранее известными элементами.
последнее повсеместно встречается, особенно доставляют такие проверки в цикле, привет O(N^2) и тормозам уже на паре тысяч элементов.
статья как раз для того написана, чтобы выбирали то, что надо, а не что первое вспомнится.
Возник такой вопрос: в самой хеш таблице поиск тоже осуществляется за О(1)? Т. е. значения хешей соответствуют адресам в памяти (со смещением на константу)?
Да. (как много написано выше, время может быть не O(1) а больше, если встретилась коллизия, но суть именно такая)
Спасибо. Просто у меня хеш обычно с md5 ассоциировался, и трудно представить, как его в памяти уместить. Но, как я понял из статьи, нужно брать хеш с меньшей размерностью…
Да, у меня когда я первый раз читал про Хэш Тейбл был такой же вопрос :)
Далее цитата из статьи:
Далее цитата из статьи:
Эти две проблемы связаны: очевидно, что мы не можем вычислять длинные хэши если хотим хранить небольшое количество элементов — это приведет к неоправданым затратам памяти, потому хэш функция обычно выглядти как то так:
index = f(key, arrayLength)
То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда.
Насколько мне известно, в Питоне для вычисления хэша используется магический метод __hash__. Вы пишете, что метод должен принимать ещё и размер массива. Но интерфейс магического метода не подразумевает получение этого параметра. Как тогда в Питоне решается проблема большого массива?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Свой инструмент нужно знать в лицо: обзор наиболее часто используемых структур данных