Что делает поиск таблиц таким дешевым?

Question

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

Например, циклически просматривая каждый элемент в массиве, чтобы что-то с ним делать

foreach(item in array)
    doSomethingWith(item)

- это алгоритм O(n), поскольку число циклов, которые выполняет программа, прямо пропорционально размеру массива.

Что меня поразило, так это то, что поиск по таблице O(1).То есть поиск ключа в хэш-таблице или словаре

value = hashTable[key]

занимает одно и то же число циклов независимо от того, имеет ли таблица один ключ, десять ключей, сто ключей или гигабриджиллион ключей.

Это действительно круто, и я очень рад, что это правда, но это не интуитивно для меня, и я не понимаю почему это правда.

Я могу понятьпервый алгоритм O(n), потому что я могу сравнить его с реальным примером: если у меня есть листы бумаги, которые я хочу проштамповать, я могу просматривать каждую бумагу по одному и штамповать каждый.Для меня имеет большой смысл, что если у меня есть 2000 листов бумаги, штамповка с использованием этого метода займет вдвое больше времени, чем если бы у меня было 1000 листов бумаги.

Но я не могупонять, почему поиск по таблице O(1).Я думаю, что если у меня есть словарь, и я хочу найти определение полиморфизм , мне понадобится O(logn) время, чтобы найти его: я открою страницу в словаре и посмотрюесли это в алфавитном порядке до или после полиморфизм .Если, скажем, это было после раздела P , я могу удалить все содержимое словаря после страницы, которую я открыл, и повторять процесс с оставшейся частью словаря, пока не найду полиморфизм слова ..

Это не процесс O(1): мне обычно требуется больше времени, чтобы найти слова в словаре из тысячи страниц, чем в словаре из двух страниц.Мне трудно представить процесс, который занимает одинаковое количество времени, независимо от размера словаря.

tl; dr : Можете ли вы объяснить мне, как можно выполнить поиск таблицы со O(1) сложностью?

(Если вы покажете мне, как реплицироватьУдивительный O(1) алгоритм поиска, я определенно получу большой толстый словарь, чтобы я мог показать всем своим друзьям свои навыки поиска ниндзя-словаря)

РЕДАКТИРОВАТЬ: Большинство ответов, по-видимому, зависят от этого предположения:

У вас есть возможность доступа к любой странице словаря по номеру страницы в постоянном времени

Если это правда, мне легко увидеть.Но я не знаю, почему это основополагающее предположение верно: я бы использовал тот же процесс для поиска страницы по номеру, как и по слову.

То же самое с адресами памяти, для чего используется алгоритмзагрузить адрес памяти?Что делает так дешево найти часть памяти по адресу?Другими словами, почему доступ к памяти O(1)?

Answer 1

Вы должны прочитать статью Википедии .

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

Итак, в упрощенном псевдокоде:

ValueType array[ARRAY_SIZE];

void insert(KeyType k, ValueType v)
{
    int index = hash(k);
    array[index] = v;
}

ValueType lookup(KeyType k)
{
    int index = hash(k);
    return array[index];
}

Очевидно, что это не обрабатывает столкновения, но вы можете прочитать статью, чтобы узнать, как это обрабатывается.

Обновление

Чтобы ответить на отредактированный вопрос, индексирование в массив: O (1) , потому что под капотом процессор делает это:

    ADD index, array_base_address -> pointer
    LOAD pointer -> some_cpu_register

где LOAD загружает данные, хранящиеся в памяти по указанному адресу.

Обновление 2

И причина загрузки из памяти O(1) на самом деле просто потому, что эту аксиому мы обычно указываем, когда говорим о сложности вычислений (см. http://en.wikipedia.org/wiki/RAM_model). Если мы игнорируем иерархию кеша и шаблоны доступа к данным, тогда это разумное предположение. Поскольку мы масштабируем размер машины, это может быть не так (машина с объемом памяти 100 ТБ может не занять столько же времени, сколько машина с объемом памяти 100 КБ). Но обычно мы предполагаем, что Емкость нашей машины постоянна и намного больше, чем размер любой проблемы, на которую мы, вероятно, обращаем внимание. Так что, по сути, это операция с постоянным временем.

Answer 2

Я рассмотрю этот вопрос с разных точек зрения.Надеемся, что это даст понять, почему доступ к x[45] и доступ к x[5454563] занимает одинаковое количество времени.

RAM размещена в сетке (то есть в строках и столбцах) конденсаторов.ОЗУ может адресовать конкретную ячейку памяти, активируя конкретный столбец и строку в сетке, поэтому, скажем, если у вас есть 16-байтовая память ОЗУ, размещенная в сетке 4x4 (безумно мала для современного компьютера, но достаточна для иллюстрациицель), и вы пытаетесь получить доступ к адресу памяти 13 (1101), сначала вы разбиваете адрес на строки и столбцы, то есть row 3 (11) column 1 (01).

Предположим, 0 означает, что вы берете левое пересечение, а 1 - что вы попали в правое пересечение.Поэтому, когда вы хотите активировать строку 3, вы отправляете армию электронов в стартовые ворота строки, электроны армии рядов направляются направо, прямо к воротам активации строки 3;затем вы отправляете еще одну армию электронов на стартовые ворота колонны, электроны армии колонн шли налево, затем направо, чтобы добраться до 1-го вентиля активации колонны.Ячейка памяти может быть прочитана / записана только в том случае, если строка и столбец активированы, так что это позволит читать / записывать помеченную ячейку.

Эффект всего этого абсурда состоит в том, что время доступа адреса памяти зависит от длины адреса , а не от конкретного адреса памяти;если в архитектуре используется 32-разрядное адресное пространство (то есть 32 пересечения), то для адресации памяти 45 и адреса памяти 5454563 все равно придется проходить через все 32 пересечения (фактически 16 пересечений для электронов строк и 16 пересечений для столбцовэлектроны).

Обратите внимание, что в действительности адресация памяти занимает очень мало времени по сравнению с зарядкой и разрядкой конденсаторов, поэтому даже если мы начинаем иметь адресное пространство длиной 512 бит (достаточно для ~ 1,4 * 10 ^130 йодбайт оперативной памяти, то есть достаточно, чтобы держать все под солнцем в вашей оперативной памяти), что означает, что электроны должны были бы пройти 512 пересечений, это на самом деле не добавило бы столько времени к фактическому времени доступа к памяти.

Обратите внимание, что это грубое упрощение современной оперативной памяти.В современной DRAM, если вы хотите получить доступ к последующим адресам памяти, вы изменяете только столбцы и не тратите время на изменение строк, поэтому доступ к последующей памяти гораздо быстрее, чем к совершенно случайным адресам.Кроме того, в этом описании совершенно не учитывается влияние кэш-памяти ЦП (хотя кэш-память ЦП также использует аналогичную схему адресации сетки, однако, поскольку в кэш-памяти ЦП используется гораздо более быстрый транзисторный конденсатор, отрицательный эффект наличия большого адресного пространства кеша становится очень важным).Тем не менее, точка зрения остается неизменной: если вы перепрыгиваете через память, доступ к любому из них займет столько же времени.

Answer 3

Вы правы, удивительно трудно найти реальный пример этого. Идея, конечно, в том, что вы ищете что-то по адресу, а не по стоимости.

Пример словаря дает сбой, потому что вы не сразу знаете местоположение страницы, например, 278. Вам все равно придется искать это так же, как слово, потому что местоположения страниц не в вашей памяти.

Но, скажем, я пометил число на каждом из ваших пальцев, а затем сказал вам шевелить тем, на котором написано 15. Вам придется посмотреть на каждого из них (при условии, что он не отсортирован), и если это не 15, вы проверите следующий. О (п).

Если бы я сказал тебе покачивать правую мизинец. Вам не нужно ничего искать. Вы знаете, где это, потому что я только что сказал вам, где это. Значение, которое я только что передал вам, является его адресом в вашей «памяти».

Это похоже на базы данных, но в гораздо большем масштабе, чем 10 пальцев.

Answer 4

Хорошо, в двух словах хеш-таблицы:

Вы берете обычный массив (доступ O (1)), и вместо обычных значений Int для доступа к нему вы используете MATH.

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

Итак, в этом случае вы просто делаете 4-5 вычислений (O (1)), чтобы получить объект из этого массива, используя ключ, который не является целым.

Теперь труднее всего избежать столкновений и найти правильную математическую формулу для хорошего распределения.Вот что довольно хорошо объясняется в википедии: en.wikipedia.org / wiki / Hash_table

Answer 5

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

Предполагая, что у вас не так много памяти, затем выделите примерно на 30% больше массивов, чем количество записей, которые вы намерены хранить, а затем напишите хеш-функцию, чтобы найти ее.

Очень простой (и, вероятно, плохой) хеш-функцией будет социальный% numElementsInArray.

Проблема в столкновениях - вы не можете гарантировать, что в каждом месте есть только один элемент. Но это нормально, вместо того, чтобы хранить запись в массиве, вы можете сохранить связанный список записей. Затем вы сканируете линейно для элемента, который вы хотите, как только вы хэш, чтобы получить правильное расположение массива.

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

Answer 6

Представьте, что у вас есть словарь, в котором все, начиная с буквы А, было на странице 1, буквы В на странице 2 ... и т. Д. Так что, если бы вы хотели посмотреть «воздушный шар», вы бы точно знали, на какую страницу перейти. Это концепция O (1) поиска.

Произвольный ввод данных => отображается на определенный адрес памяти

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

Answer 7

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

Answer 8

Теоретически, хеш-таблица - это набор сегментов (адресов в памяти) и функция, которая отображает объекты из домена в эти сегменты.

Скажем, ваш домен состоит из 3 букв, вы заблокируете 26 ^ 3 = 17 576 адресов для всех возможных 3 буквенных слов и создадите функцию, которая отображает все 3 буквенные слова на эти адреса, например, aaa = 0, aab = 1 и т. Д. Теперь, когда у вас есть слово, которое вы хотите найти, скажем, «и», вы сразу узнаете из своей функции O (1), что это адрес с номером 367.

Answer 9

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