remove_firts(): Удалить первый элемент.
insert_after(List Iterator, item): Добавить элемент после текущего.
append(item): Добавить элемент в конец списка.
prepend(item): Добавить элемент в начало списка.
List это список элементов произвольного типа переменной длины (то есть мы можем в любой момент добавить элемент в список или удалить его). Список позволяет перебирать элементы, получать элементы по индексу, а так же добавлять и удалять элементы. Реализации у List возможны разные, основные это (Single/Bidirectional) Linked List и Vector. Классический List предоставляет возможность работы с ним напрямую и через итератор, интерфейсы обоих классов рассмотрим ниже.
Python/php/... : как таковой отсутствует
*aj = beginPointer + elementSize*j-1
Почему время доступа к элементу по индексу постоянно? Массив состоит из элементов одного типа, имеет фиксированный размер и располагается в непрерывной области памяти => чтобы получить j-й элемент массива, нам достаточно взять указатель на начало массива и прибавить к нему размер элемента умноженный на его индекс. Результат этого несложного вычисления будет указывать как раз на искомый элемент массива.
Поиск в массиве осуществляется путем перебора элементов по индексам => сложность O(N).
set_element_at(i, value): сложность O(1)
get_element_at(i): сложность O(1)
Array это коллекция фиксированного размера, состоящая из элементов одинакового типа.
1. Array он же индексированный массив.
Пара слов о классификации структур в статье. Если вы изучите источники, которые перечислены в списке использованной информации, то заметите, что классификация в данной статье не соответствует классификации ни в одном из источников (в некоторых источниках ее нет вовсе). Это вызвано тем, что мне показалось более целесообразным рассматривать структуры в контексте их использования. Например ассоциативный массив в PHP/Python/С++ или список в .Net/Python.
Причиной неверного ответа было то, что я не удосужился досконально изучить те структуры, которые лежат в основе работы с коллекциями моего любимого языка. Правда, по результатам опроса нескольких знакомых разработчиков, оказалось что это не только моя проблема, очень многие вообще не задумываются, как работают коллекции в их любимых ЯП. А ведь используем мы их каждый день и не по разу. Так родилась идея этой статьи.
На самом деле никакого бинарного поиска тут нет. И сложность алгоритма не O(lg(N)), а Amort. O(1) так как в основе dict питона лежит структура под названием Hash Table.
Ответ: В dict хранятся хэши от ключей. Каждый раз, когда мы ищем в dict значение по ключу, мы сначала вычисляем его хэш, а потом (внезапно), выполняем бинарный поиск. Таким образом, сложность составляет O(lg(N))!
Вопрос: Почему поиск в dict на больших объемах данных быстрее чем итерация по индексированному массиву?
Некоторое время назад я сходил на собеседование в одну довольно большую и уважаемую компанию. Собеседование прошло хорошо и понравилось как мне, так и, надеюсь, людям его проводившим. Но на следующий день, в процессе разбора полетов, я обнаружил, что в ходе собеседования ответ на как минимум один вопрос был неверен.
Программирование / Свой инструмент нужно знать в лицо: обзор наиболее часто используемых структур данных | Gliffer
Комментариев нет:
Отправить комментарий