Свой инструмент нужно знать в лицо: обзор наиболее часто используемых структур данных

    image
    Некоторое время назад я сходил на собеседование в одну довольно большую и уважаемую компанию. Собеседование прошло хорошо и понравилось как мне, так и, надеюсь, людям его проводившим. Но на следующий день, в процессе разбора полетов, я обнаружил, что в ходе собеседования ответ на как минимум один вопрос был неверен.

    Вопрос: Почему поиск в python dict на больших объемах данных быстрее чем итерация по индексированному массиву?

    Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!

    На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) — так как в основе dict питона лежит структура под названием Hash Table.

    Причиной неверного ответа было то, что я не удосужился досконально изучить те структуры, которые лежат в основе работы с коллекциями моего любимого языка. Правда, по результатам опроса нескольких знакомых разработчиков, оказалось что это не только моя проблема, очень многие вообще не задумываются, как работают коллекции в их любимых ЯП. А ведь используем мы их каждый день и не по разу. Так родилась идея этой статьи.


    Пара слов о классификации структур в статье. Если вы изучите источники, которые перечислены в списке использованной информации, то заметите, что классификация в данной статье не соответствует классификации ни в одном из источников (в некоторых источниках ее нет вовсе). Это вызвано тем, что мне показалось более целесообразным рассматривать структуры в контексте их использования. Например ассоциативный массив в PHP/Python/С++ или список в .Net/Python.

    Итак, поехали.

    1. Array — он же индексированный массив.


    Array — это коллекция фиксированного размера, состоящая из элементов одинакового типа.

    Интерфейс:
    • get_element_at(i): сложность O(1)
    • set_element_at(i, value): сложность O(1)

    Поиск в массиве осуществляется путем перебора элементов по индексам => сложность O(N).

    Почему время доступа к элементу по индексу постоянно? Массив состоит из элементов одного типа, имеет фиксированный размер и располагается в непрерывной области памяти => чтобы получить j-й элемент массива, нам достаточно взять указатель на начало массива и прибавить к нему размер элемента умноженный на его индекс. Результат этого несложного вычисления будет указывать как раз на искомый элемент массива.
    *aj = beginPointer + elementSize*j-1


    Примеры:
    с/с++: int i_array[10];
    java/C#: int[10] i_array;
    Python: array.array
    php: SplFixedArray


    2. List (список).


    List — это список элементов произвольного типа переменной длины (то есть мы можем в любой момент добавить элемент в список или удалить его). Список позволяет перебирать элементы, получать элементы по индексу, а так же добавлять и удалять элементы. Реализации у List возможны разные, основные — это (Single/Bidirectional) Linked List и Vector. Классический List предоставляет возможность работы с ним напрямую и через итератор, интерфейсы обоих классов рассмотрим ниже.

    Интерфейс List :
    • prepend(item): Добавить элемент в начало списка.
    • append(item): Добавить элемент в конец списка.
    • insert_after(List Iterator, item): Добавить элемент после текущего.
    • remove_firts(): Удалить первый элемент.
    • remove_after(List Iterator): Удалить элемент после текущего.
    • is_empty(): Пуст ли List.
    • get_size(): Возвращает размер списка.
    • get_nth(n): Вернуть n-й элемент.
    • set_nth(n, value): Задать значение n-му элементу.

    Интерфейс List Iterator:
    • get_value(): получить значение текущего элемента.
    • set_value(): задать значение текущему элементу.
    • move_next(): переместиться к следующему элементу.
    • equal(List Iterator): проверяет — ссылается ли другой итератор на тот же элемент списка.

    Надо отметить, что в некоторых (в основном интерпретируемых), языках программирования эти два интерфейса «склеены» и «обрезаны». Например в python объект типа list можно итерировать, но у него же можно и получить значение обратившись непосредственно по индексу.

    Перейдем к реализациям списка.

    2.1 Single Linked List

    image
    Однонаправленный связный список (односвязный список) представляет из себя цепочку контейнеров. Каждый контейнер содержит внутри себя ссылку на элемент и ссылку на следующий контейнер, таким образом, мы всегда можем переместиться по односвязному списку вперед и всегда можем получить значение текущего элемента. Контейнеры могут располагаться в памяти как им угодно => добавление в односвязный список нового элемента тривиально.

    Стоимость операций:
    • prepend: O(1)
    • insert_after: O(1)
    • remove_first/remove_after: O(1)
    • get_nth/set_nth: O(N)

    Примеры:
    с/с++: std::list //Bidirectional Linked List
    Java: java.util.LinkedList
    c#: System.Collection.Generic.LinkedList //Bidirectional Linked List
    php: SplDoublyLinkedList // Bidirectional Linked List


    Bidirectional Linked List мы подробно рассматривать не будем, вся разница между ним и Single Linked List заключается в том, что в контейнерах есть ссылка не только на следующий, но и на предыдущий контейнер, что позволяет перемещаться по списку не только вперед, но и назад.

    2.2 Vector

    Vector — это реализация List через расширение индексированного массива.

    Стоимость операций:
    • prepend: O(N)
    • append: Amort.O(1)
    • insert_after: O(N)
    • remove_first/remove_after: O(1)
    • get_nth/set_nth: O(1)


    Очевидно, что главное преимущество Vector'а — быстрый доступ к элементам по индексу, унаследовано им от обычного индексированного массива. Итерировать Vector так же достаточно просто, достаточно увеличивать некий счетчик на единицу и осуществлять доступ по индексу. Но за скорость доступа к элементам приходиться платить временем их добавления. Для того чтобы вставить элемент в середину Vector'a (insert-after) необходимо скопировать все элементы между текущим положением итератора и концом массива, как следствие время доступа в среднем O(N). То же и с удалением элемента в середине массива, и с добавлением элемента в начало массива. Добавление элемента в конец массива при этом может быть выполнено за O(1), но может и не быть — если опять таки потребуется копирование массива в новый, потому говорится, что добавление элемента в конец Vector'а происходит за Amort. O(1).

    Примеры:
    с/с++: std::vector
    Java: java.util.ArrayList
    C#: System.Collections.ArrayList, System.Collections.List
    Python: list


    3. Ассоциативный массив(Словарь/Map)


    Коллекция пар ключ=>значение. Элементы (значения) могут быть любого типа, ключи обычно только строки/целые числа, но в некоторых реализация диапазон объектов, которые могут быть использованы в качестве ключа, может быть шире. Размер ассоциативного массива можно изменять путем добавления/удаления элементов.

    Интерфейс:
    • add(key, value) — добавить элемент
    • reassign(key, value) — заменить элемент
    • delete(key) — удалить элемент
    • lookup(key) — найти элемент

    Существует две основные реализации Ассоциативного массива: HashMap и Binary Tree.

    3.1 Hash Table

    image
    Как можно догадаться из названия, тут используются хэши. Механика работы Hash Table следующая: в основе лежит все тот же индексированный массив, в котором индексом работает значение хэша от ключа, а значением — ссылка на объект, содержащий ключ и хранимый элемент (bucket). При добавлении элемента — хэш функция вычисляет хэш от ключа и сохраняет ссылку на добавляемый элемент в ячейку массива с соответствующим индексом. Для получения доступа к элементу мы опять таки берем хэш от ключа и, работая так же как с обычным массивом получаем ссылку на элемент.

    Пытливый читатель может заметить некоторые проблемы, характерные для реализации этой СД.
    • Если хэш от ключа равен например 1928132371827612 — это ведь будет означать, что нам надо иметь массив соответствующего размера? А если у нас в нем всего 2 элемента?
    • А если у нас хэши от двух разных ключей совпадут?

    Эти две проблемы связаны: очевидно, что мы не можем вычислять длинные хэши, если хотим хранить небольшое количество элементов — это приведет к неоправданым затратам памяти, потому хэш функция обычно выглядти как то так:
    index = f(key, arrayLength)


    То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда. Обратная сторона такого поведения хэш функции — возможность коллизий. Коллизии на самом деле характерны для Hash Table, и существует два метода их разрешения:

    Chaining:
    image
    Каждая ячейка массива H является указателем на связный список (цепочку) пар ключ-значение, соответствующих одному и тому же хеш-значению ключа. Коллизии просто приводят к тому, что появляются цепочки длиной более одного элемента.

    Open addressing:

    В массиве H хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива H в некотором порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую и будет записан новый элемент. Этот порядок вычисляется на лету, что позволяет сэкономить на памяти для указателей, требующихся в хеш-таблицах с цепочками.
    image

    Стоимость операций:
    • add: Amort.O(1)/O(N)
    • reasign: Amort.O(1)/O(N)
    • delete: Amort.O(1)/O(N)
    • lookup: Amort.O(1)/O(N)

    Здесь первое значение — средняя сложность, второе — сложность выполнения операции в худшем случае. Такая разница обусловлена следующим: при добавлении элемента, в случае если массив заполнен, может понадобиться перестроить Hash Table целиком. При поиске элемента может оказаться так, что мы наткнемся на длинную цепочку коллизий, и опять же будем вынуждены перебрать все элементы.

    Примеры:
    c++: за исключением QHash автору не известныboost::unordered_map/boost::unordered_set (by NickLion)
    java: java.util.HashMap<K,V>
    c#: System.Collections.Hashtable, System.Collections.Dictionary<K, V>
    python: dict
    php: array()


    3.2 Binary Tree

    image
    На самом деле не просто Binary Tree, а Self-balancing Binary Tree. Причем следует отметить, что существует несколько различных деревьев, которые могут быть использованы для реализации Ассоциативного массива: red-black tree, AVL-tree и т.д. Мы не будем рассматривать каждое из этих деревьев в деталях, так как это возможно тема еще одной, отдельной статьи, а может и нескольких (если изучать деревья особо тщательно). Опишем только общие принципы.

    Определение: двоичное дерево — древовидная структура данных в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. В случае, если у узла нет наследников — он называется листовым узлом.

    Для примера возьмем поисковое бинарное дерево (binary search tree): каждый узел представляет из себя контейнер, содержащий три элемента: data — собственно привязанные данные (data содержит как собственно элемент, так и значение ключа), left — ссылка на левый нижележащий узел и right — ссылка на правый нижележащий узел. При этом выполняется такое правило: key[left[X]] < key[X] ≤ key[right[X]] — т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого. При поиске элемента мы обходим дерево, каждый раз сравнивая значение нашего ключа с ключом текущего узла, и, по результатам сравнения определяя в которую сторону нам идти. Несложно подсчитать, что сложность такого поиска — стабильно O(lgN). При добавлении нового узла мы выполняем в целом похожую процедуру пока не найдем, куда воткнуть новый элемент. Правда следует отметить то, что такие деревья еще требуется балансировать — но это мы уже опустим. Пытливый читатель сам найдет необходимую информацию, изучив список источников.

    Стоимость операций:
    • add: Amort.O(lgN)
    • reasign: Amort.O(lgN)
    • delete: Amort.O(lgN)
    • lookup: Amort.O(lgN)

    Примеры:
    c++: std::map, std::set
    java: java.util.TreeMap<K,V>, так же автора мучает подозрение что java.util.Map<K,V> - из той же оперы
    c#: автор теряется в догадках :( SortedDictionary(by NickLion)
    python: -
    php: -


    4. Множество (Set).


    Immutable набор элементов. Множество определяется один раз — при создании, и в дальнейшем предоставляет доступ к элементам только на чтение. Множество нельзя расширить, равно как нельзя и удалить из него элементы или изменить элемент множества. В качестве базы для реализации данной коллекции обычно используется Hash Table — описание которого см. Выше.

    Множество — это просто реализация абстракции математического множества, т.е. набора уникальных различимых элементов. (спс. danilI)
    Примеры:
    c++: std::set
    java: java.util.Set
    C#: System.Collections.HashSet
    python: set/frozenset


    Сравнительные характеристики структур данных:
    image

    Структуры данных в различных языках программирования:
    image

    Ссылки:


    Data Structures (en)
    Структуры Данных (рус)
    Binary search tree (en)
    Двоичное дерево поиска (рус)

    Так же автор заглянул в исходники PHP и почитал доку по STL.

    Upd. Да, в питоне есть обычный индексированный массив (array.array). Спасибо enchantner. С поправкой, тип не обязательно числовой, тип можно указывать.

    Upd. Сделано много исправлений по тексту. idemura, zibada, tzlom, SiGMan, freeOne, Slaffko, korvindest, Laplace, enchantner спасибо за правки!

    Upd.
    Из комментариев zibada:
    Да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).

    Нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
    — в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках);
    — в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках);
    — в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне.

    А вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
    Что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
    Метки:
    Поделиться публикацией
    Комментарии 66
    • +4
      Кстати, в питоне есть array — docs.python.org/library/array.html Правда, он типизированный для чисел.
      Я лично ни разу не использовал, но говорят, что для экономии памяти в некоторых задачах отлично подходит.
      • +1
        Спасибо, не знал. Пойду почитаю.
      • 0
        Пост целиком не читал. Мне кажется оценивать сложность доступа к элементу хэша как O(1) неверно, т.к. такая оценка не учитывет коллизий, которые разрешаются за линейное время (от количества элементов с таким же хэшем).
        • +1
          Согласен, далее в статье так и написано. Начало — поправлю.
          • +3
            Вы в статье применяете Amort. в двух разных смыслах. Действие работает за амортизированное время O(f(n)), если при выполнении его N раз будет выполнено O(N f(n)) операций. В частности, у Вас написаны правильные оценки для добавления в вектор и для AVL-дерева. Для хэша можно считать, что время операции в среднем O(1). Это означает, что, если входные данные удовлетворяют некоторому распределению, то математическое ожидание количества выполненых операций будет O(1). Для хэша, правда, это свойство ещё надо доказать, но что такое Amort.O(1)/O(N) вообще не понятно, довольно бесполезная оценка.
          • 0
            Если следовать вашей логики, то сложность поиска по массиву не есть O(n), ведь с вероятность 1/n элемент может находится в первой ячейке. А по хешь таблице может быть и O(n), ведь
            • 0
              в крайнем случае колизий может быть и по количеству элементов.

              На самом деле за единичную операцию при оценке работы с хешь таблицами берется операция в которой может возникнуть коллизия
              • 0
                Я честно пытался прочитать оба комментария, но сломал глаза. Извините за это, наверняка Вы правы.
            • 0
              В том-то и дело, что оценка O(1) — точна и верна, так как она — асимптотическая. В эту оценку входит то, что иногда операции могут выполнятся больше одного раза.

              Более строго: в хорошей хэш-таблице оценка количества элементов с совпадающим хэшем пусть и не точно единица, но всё же пренебрежимо мала по сравнению с количеством элемментов, и также мало отличается от единицы. Случаи вырождения хэша в линейный список не рассматриваем :)
              • 0
                > В эту оценку входит то, что иногда операции могут выполнятся больше одного раза.

                Какая разница сколько раз будут выполняться операции поиска элемента, если число элементов много больше количества возможных хэшей?

                > в хорошей хэш-таблице оценка количества элементов с совпадающим хэшем пусть и не точно единица, но всё же пренебрежимо мала по сравнению с количеством элемментов

                А в идеальной всё ещё лучше, не поверите. Но мы живём в реальном мире и хранение сверхбольшой хэш-таблицы может привести к непозволительному расходу памяти, потому коллизии — далеко не фантастика.
                • 0
                  Да, ну и раз уж Вы в ладах с теорией, давайте откроем определение О(x). Опишите какую-то реализацию хеша, например просто скажите, что его таблица позволяет хранить ссылки для 1000 разных хешей ключей, потом вычислите ту самую константу C, которой должно хватить для любого количества элементов n, тем самым доказав мою неправоту. Потому что я утверждаю, что для O(1) такой константы не существует.
                  • +2
                    Объясняю. Предлагаю вам конкретную, достаточно эффективную реализацию.

                    Как только хэш-таблица заполняется более, чем на 80%, то она расширяется.
                    Как только заполняется менее, чем на 40% — сжимается.
                    Среди всех способов разрешения коллизий наиболее эффективный — квадратичное пробирование (метод квадратичных проб, Quadratic collision resolution).
                    Поэтому используем именно его, это даст лучшие оценки для количества сравнений элементов между собой (точные оценки можно найти здесь).

                    Еще раз повторюсь.
                    Во-первых, данное количество сравнений элементов при коллизиях пренебрежимо мало по сравнению с количеством элементов в хэш-таблице (особенно в большой), отсюда и возникает оценка O(1) (на бесконечности).
                    И два, не надо экономить на памяти, она очень дешёвая. Делайте большие хэш-таблицы, не бойтесь. Сейчас все реализации должны хорошо работать с памятью :)
                    • 0
                      Пожалуй согласшусь, для такой схемы работы оценка будет верна. Конечно у этой схемы есть свои минусы, и для каких-то очень специфичных задач она не подойдёт, но в целом вполне универсальна.

                      > Во-первых, данное количество сравнений элементов при коллизиях пренебрежимо мало по сравнению с количеством элементов в хэш-таблице (особенно в большой), отсюда и возникает оценка O(1) (на бесконечности).

                      Вот тут неточность. Бесконечность малым это количество будет лишь в случае бесконечного значения ключей. Если посмотреть на приведённую Вами таблицу, для метода квадратичных проб и 75% заполненности можно найти два числа — 2.01 и 4.64 (кстати, что такое Successful и Unsuccessful? Лучший и худший случаи?), что подтверждает, что на разрешение коллизии будет тратится время по крайней мере того же порядка.
              • +5
                А на работу то в итоге взяли?
              • +8
                Примеры из Java в принципе допустимы, но не совсем корректны. Где то автор приводит в пример интерфейс (Set, Map), где то реализацию (HashTable, ArrayList), но в принципе ничего криминального в этом нет.
                А вот Vector почти тот же самый ArrayList, но потокобесопасный при доступе к элементу. Он считается deprecated в новых версиях и вместо него используется ArrayList+обертка Collections.synchronizedList.
                • +4
                  К сожалению, я не java engineer потому делал обзор исходя из своих, довольно скудных знаний. Замечание учту.
                  • 0
                    Я ни разу не хотел вас обидеть и прошу прощения, если это все таки произошло. Просто, интерфейсы сами по себе хоть и подразумевают определенный механизм работы, но не гарантируют, что реализация будет выполнена именно тем алгоритмом, который вы описываете.
                  • 0
                    Vector не является deprecated, он член Java Collections Framework после реализации интерфейса List с версии Java 1.2, остаётся там наравне с ArrayList, хотя да, рекомендуют использовать последний.
                    • 0
                      Основа идеологии Java (как я ее себе понимаю), это единый механизм работы сходных классов. В тот момент, когда SUN(ныне oracle) выпустила Java Collections Framework этот механизм организации потокобезопастности стал приоритетным в использовании. Vector действительно еще не помечен как deprecated, но это я подозреваю это связано с тем, что он используется в большом количестве мест и не может быть заменен мгновенно. Так что с точки зрения документации вы правы.
                  • +7
                    Только не stl::set, stl::map и т.д., а std::set, std::map.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +3
                        Отличная статья!

                        Колитесь, что за крупная контора, в которую вы устроились? :)
                        • +4
                          java: java.util.TreeMap<K,V>, так же автора мучает подозрение что java.util.Map<K,V> — из той же оперы

                          java.util.Map — это интерфейс, в частности для HashMap и TreeMap.

                          И в java Hashtable — устаревшая реализация ассоциативного массива. HashMap вместо нее
                          • 0
                            Готов переработать примеры по Java. :)
                            • 0
                              Класс Hashtable не является устаревшим. Он не аннотирован как @Deprecated.
                            • +1
                              std::list, который в stl, двусвязный.
                              • +2
                                Если питоновский list является vector, который основан на однотипном array, то как тогда он может содержать разные типы (например [1, 'a', True])?
                                • +4
                                  если не ошибаюсь, list в питоне — гетерогенный. массив указателей на объекты иначе говоря
                                  • +4
                                    Это слегка мутировавший вектор. Массив, на котором он базируется — является массивом ссылок на элементы произвольного типа.
                                    Смотрим сорсы в них 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;
                                    
                                  • +1
                                    В С++ есть hash_map, хотя и не в любой реализации. В майкрософтовской есть, в расширении STL.
                                    • +2
                                      unordered_map есть в бусте, в TR1 и в С++0х.
                                      • –1
                                        Да, в новом стандарте тоже есть подобие, см. t.co/jgPorAa -> StackOverflow.
                                      • +4
                                        насчет множества в питоне ( immutable set в контексте статьи ) — это frozenset, а не кортеж
                                      • +1
                                        В PHP есть и Array и Linked List: ru.php.net/manual/en/spl.datastructures.php
                                      • +3
                                        Ну автор… Ну нет в C++ пространста имен stl, а есть std! std::vector, std::map. Помарка, а впечатление смазалось.
                                        А вообще, на есть лекции MIT по теории алгоритмов (курс 6.046J), первая лекция к примеру — на youtube. Сам Лезерсон читает и Эрик Демейн (Erik Demaine). Там весь курс.
                                        • 0
                                          Автор поправил :) Картинки перерисует.
                                          • –1
                                            Спасибо за ссылку!
                                          • +4
                                            1. тут неточность:
                                            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 тоже сохраняют порядок добавления, но насколько я помню, это не специфицировано.
                                            • 0
                                              1. Сейчас исправлю.
                                              2. К сожалению подробно не мог рассмотреть все хэши в рамках одной статьи, если рассматривать подробно и все вариации — то на каждую структуру можно по отдельной статье написать (хотя, возможно они этого заслуживают).
                                              • 0
                                                2. как-то странно, что ListIterator отдельно упомянут, хотя там все как раз более очевидно, а с итерацией по хэшам полная тишина.

                                                дальше читаем =)

                                                3. почему оценки для деревьев амортизированы, когда они вполне себе worst-case?

                                                4. почему у вас множества только immutable бывают?
                                                «заморозить» любую коллекцию можно, а множества в виде стандартных типов (java.util.HashSet, set() в python) вполне себе изменяемы.
                                                их можно упомянуть как упрощенный вариант map, где не надо хранить значения.
                                                в том же php множеств нет, но они при желании эмулируются через array('key1' => true, ..);
                                                • 0
                                                  3. Были упомянуты AVL-деревья, некоторые реализации которых, на сколько я знаю, работают за амортизированное время. Кроме того, бывают и другие деревья. Декартово, например. Там время работы такое в среднем. Правда, я не знаю, применяются ли они как стандарт в каких-нибудь языках.
                                                  • 0
                                                    как я понял, речь о деревьях шла как о способе реализации Map<K,V>, декартовы и прочие деревья это отдельная история для более специализированных задач.
                                                    • 0
                                                      Я думаю, тот факт, что структуру можно использовать для других задач, сам по себе не означает, что её не надо использовать для наших. Map<K,V> можно реализовать как минимум десятком существенно разных способов и красно-чёрные деревья с хэшами выбраны явно не как минимально удовлетворяющие требованиям. Но в целом я придираюсь, конечно.
                                                • +1
                                                  да, вот как раз из-за отсутствия описания итерации по Map из статьи вообще непонятно, зачем, казалось бы, нужны деревья, когда есть хэши. (O(logN) против O(1)).

                                                  а нужны они затем, что перечислять элементы Map (или Set) можно хотеть:
                                                  — в любом, негарантированном порядке (HashMap, встроенные хэши в некоторых скриптовых языках)
                                                  — в порядке добавления (LinkedHashMap, встроенные хэши в некоторых других скриптовых языках)
                                                  — в порядке возрастания ключей + возможность перебрать только ключи в заданном диапазоне

                                                  и вот для последнего случая альтернатива деревьям — только полная сортировка всей коллекции после каждого изменения или перед запросом.
                                                  что долго и печально для больших коллекций, но вполне работает для небольших — поэтому в скриптовые языки деревья особо и не встраивают.
                                              • 0
                                                Из добрых обуждений, а не критики ради (чтоб статья была точнее).

                                                Про вектор (vector): insert_after: O(N), если вставляется последний элемент, то время может быть O(1) — потому обычно пишут Amort. O(1).
                                                Совершенная неправда! Amort. O(N). Амортизированное время добавления в конец — действительно, O(1). Отсылаю к видеолекциям MIT:)

                                                Если на пальцах, то при insert_after вам каждый раз(!) необходимо копировать часть массива до элемента, после которого вставляете. А при добавлении в конец — только когда нет свободного места.
                                                • +2
                                                  Вообще, неблагодарное это дело на такие темы писать:) Тут мне кажется надо лио об одной из типов коллекций на одной платформе говорить, либо книгу писать.
                                                  • 0
                                                    Ух, сколько их уже написано-переписано! :)
                                                  • 0
                                                    Кто бы еще оформил подобные сведения в рисунок, который помогал бы быстро выбрать оптимальную структуру исходя из известных требований. Дело в том, что в той же Java этих структур за сотню (с апачевскими и гугловскими либами), и о положительных свойствах большинства из них мало кому известно.
                                                    Хотя, конечно, тем кто обладает знаниями обо всех структурах, нет времени диаграммы для чайников рисовать (см. фразу Билла Гейтса об «Искусстве Программирования»)
                                                    • 0
                                                      В С++ есть нормальные хэши — std::tr1::unordered_set.
                                                      • +3
                                                        Кстати говоря, если автор затронул тему питона, то можно заметить один интересный момент — в питоне хэш-функции для чисел и строк имеют «плохое» распределение, например

                                                        >>> 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
                                                          В примерах на плюсах несколько досадных ошибок:
                                                          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
                                                          • +3
                                                            Ещё одно: Почему автор считает, что множество это обязательно immutable? Насколько я знаю, это не так.
                                                            Множество — это просто реализация абстракции математического множества, т.е. набора уникальных различимых элементов.
                                                            • +1
                                                              Для Python есть хорошая статья на эту тему: wiki.python.org/moin/TimeComplexity
                                                              • +1
                                                                Неплохо бы еще добавить сравнение контейнеров по расходу памяти. Как я понимаю, HashTable в этом отношении может быть весьма расточительна при длинном хэше
                                                                • +2
                                                                  Позволю себе высказаться. Я уже заметил что на Хабре половина читателей до сих пор не в курсе про существование хеш-таблиц, и для поиска всегда предлагают допотопные деревья. Другая половина теперь в курсе, но постоянно от не слышны какие-то жалобы, типа мол коллизий много, распределение плохое, и т.д. Используйте мол, деревья. Прежде чем предлагать использование подобных неудобных, устаревших, громоздких структур из 60-х гг., посчитайте, сколько у вас будет уходить времени только на переворачивание веток при любом добавлении или удалении. И сколько времени будет занимать поиск (сколько надо сделать сравнений) при использовании например строк в качестве ключа.

                                                                  Хеш-таблица в большинстве случаев выгоднее этого неудобного дерева. Недаром она используется в качестве основы для ассоц. массивов в PHP и других языках.

                                                                  Ну и списки — тоже на редкость неудобная хрень. Следует всегда использовать индексированные массивы, кроме тех случаев, когда требуется делать вставки в середину.
                                                                  • 0
                                                                    я про это комментарий выше писал.
                                                                    да, в самом php деревьев нет, они на тех объемах, с которыми обычно работает php, просто не нужны.
                                                                    но вы неявно используете деревья всякий раз, когда пишете «order by key» или «where key > const»

                                                                    использование деревьев вместо хэшей там, где свойства деревьев не нужны — это дурь, как и использование in_array() вместо isset() для поиска во множестве с заранее известными элементами.
                                                                    последнее повсеместно встречается, особенно доставляют такие проверки в цикле, привет O(N^2) и тормозам уже на паре тысяч элементов.
                                                                    статья как раз для того написана, чтобы выбирали то, что надо, а не что первое вспомнится.
                                                                  • 0
                                                                    Возник такой вопрос: в самой хеш таблице поиск тоже осуществляется за О(1)? Т. е. значения хешей соответствуют адресам в памяти (со смещением на константу)?
                                                                    • 0
                                                                      Да. (как много написано выше, время может быть не O(1) а больше, если встретилась коллизия, но суть именно такая)
                                                                      • 0
                                                                        Спасибо. Просто у меня хеш обычно с md5 ассоциировался, и трудно представить, как его в памяти уместить. Но, как я понял из статьи, нужно брать хеш с меньшей размерностью…
                                                                        • 0
                                                                          Да, у меня когда я первый раз читал про Хэш Тейбл был такой же вопрос :)

                                                                          Далее цитата из статьи:
                                                                          Эти две проблемы связаны: очевидно, что мы не можем вычислять длинные хэши если хотим хранить небольшое количество элементов — это приведет к неоправданым затратам памяти, потому хэш функция обычно выглядти как то так:
                                                                          index = f(key, arrayLength)

                                                                          То есть, кроме значения ключа, она так же получает текущий размер массива, это необходимо для определения длины хэша: если мы храним всего 3 элемента — нет смысла делать хэш длиной в 32 разряда.
                                                                    • 0
                                                                      Насколько мне известно, в Питоне для вычисления хэша используется магический метод __hash__. Вы пишете, что метод должен принимать ещё и размер массива. Но интерфейс магического метода не подразумевает получение этого параметра. Как тогда в Питоне решается проблема большого массива?

                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.