Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
И снова здравствуйте!
На днях угораздило меня писать про алгоритмы. И писал я про них всяко и всякое. И то, что вертел я их на местах причинных, и то, что без них жизни своей программистской не представляю в случаях критических, моментах важных, выборах трудных. Ну и раз взял на себя оный труд, то ничто так не мотивирует на его продолжение, как положительные отзывы.
По этому решил я эту тему продолжать. Хотя, правды ради и прохождения полиграфа для, я бы всё равно не выдержал и написал бы что-нибудь про это ещё.
Сего дня я решил, что напишу про алгоритмы структур данных. Про те, которые смогу вспомнить. И, как говорит наш дорогой шеф: «Погнали!»
Мы так часто видим вместе слова «Алгоритмы» и «Структуры данных», что давно привыкли их «одноитожести» (изобретаю слова). И вот кажется нам, что одно без другого ну вот прям никак. Но мне кажется, что и по данному поводу надо бы высказать своё мнение, облечь тезисы в словеса, ибо мнение моё может быть тут «разойдётся с политикой партии».
Итак, откуда же такое отождествление одного с другим? Прям как партия и Ленин, ибо когда говорят об алгоритмах, то сразу же подразумевают структуры данных, а когда говорят о структурах данных, то тут же возникают алгоритмы.
И кажется мне, что эти понятия запутались между собой, как квантовые состояния (или что там путается вечно?). Но я предлагаю разобраться и вспомнить добрым словом и то, и другое (и без хлеба).
Нет, когда нас спрашивают отдельно о структурах данных, то мы, полагаю, можем как-то воспринимать их отделёнными от алгоритмов. Вот у нас массив, структура, список, словарь, таблица, хеш-таблица, дерево, что-то там ещё. И мы отделяем их от алгоритмов. Но в общем-то алгоритмы без структур данных сами по себе редко что дают. Но сами структуры данных часто под своим капотом имеют те самые алгоритмы, о которых я читал в книжке «Паскаль в иллюстрациях», упомянутой в предыдущей публикации. Так давайте же отделим алгоритмы вообще от алгоритмов внутри структур данных и пробежимся по этим структурам с точки зрения этих алгоритмов.
Структуры данных
Программисты навыдумывали за свою недолгую эру столько разнообразных структур, что наверное про все я тут не расскажу. Но постараюсь пройти по самым полезным. Предыдущая статья говорила о том, что сами по себе алгоритмы — это такое, не особо кому нужное. Да, хорошо, если кто разбирается или думать ещё не разучился, но и без этого наивным способом перебора элементов можно решить большинство задач за некое O(N). Но содержимое каких структур программа должна перебирать — программист знать ну хоть мало-мальски, но должен. Надеюсь, что против такого тезиса никто не возразит. Ну а если возразит — на то он и Хабр, чтобы возражать.
Ну а начнём давайте с эффективности алгоритмов вообще, чтобы потом указать эту эффективность для каждой из рассмотренных структур. Ну чтобы на одном языке говорит.
Я тут выше уже привёл некое O(N). Так вот «O» здесь — это «эффективность», а N — это количество итераций для вычисления результата. Эффективность распространяется так же и на количество используемой памяти, поэтому алгоритм может быть очень хорош в плане итераций, но очень плох в плане памяти — все это мы тоже рассмотрим.
МАССИВЫ
Итак, начнём с массивов. Примем за массив последовательный список элементов. В общем и целом массив — это последовательная область памяти, содержащая в себе или однородные значения, или их адреса. Доступ к элементу массива осуществляется по индексу, и эффективность этого доступа равна O(1). Т.е. программа в ходе обращения к элементу массива просто вычисляет его положение относительно адреса начала, умножая размер элемента (или его адреса) на индекс. В массив, если память за ним свободна, можно легко добавить элемент — это тоже занимает одну итерацию O(1). А вот вставка элемента в середину вынуждает сдвигать все остальные элементы вверх, поэтому эффективность такой вставки от условного O(2) — предпоследний элемент, до O(N) — если мы вдруг захотели вставить в самое начало. Время поиска значения среди значений массива уже стремится к O(N), особенно если такого значения там нет. В массиве легко менять элементы местами, поэтому его несложно отсортировать огромным количеством разнообразных алгоритмов — от детского собирания пирамидки и до всех этих «сортировок слиянием», которые, предположу, реализованы в разнообразных библиотеках для разнообразных языков. В 1с, например, нет метода сортировки массива, поэтому бравые 1С-неги загружают массив в список значений, который можно упорядочить, а потом выгружают назад. Никому в голову не приходят все эти мысли о том, чтобы написать свою сортировку. И ведь правильно же, да?
В общем, массив — это просто, как дважды два. Поэтому я его применяю весьма нечасто. А как у вас обстоит с этим дела? Расскажите в комментах.
СТРУКТУРЫ
После массива у меня в порядке увеличения сложности идёт структура. Они есть во многих языках. По сути, структура — это совокупность именованных элементов. Структуру можно представить, как строку базы данных, в каждой колонке которой содержатся свои типы (строки, числа, даты, ну и все прочее). Структура — это в общем-то «закрытая» штука, но в той же 1С в неё можно повставлять ключи со значениями и даже без них. Здесь структура превращается в этакое хранилище «Ключ»:«Значение». И если в низкоуровневых языках обращение к полям структуры скомпилировано с эффективность O(1), то в высокоуровневых языках, предполагающих изменение набора данных, все не так однозначно. В итоге структура там реализуется скорее всего как связанный список, о котором мы и поговорим.
СПИСКИ
Список — это, в моем понимании, некий связанный набор данных, где каждый элемент указывает на то, где находится следующий. И если в массиве к элементу можно обратиться по индексу, то в структуре нельзя — можно обратиться только к следующему элементу, который будет содержать адрес ещё более следующего, ну и так далее. Часто элементы списка имеют не только ссылку на следующий элемент, но и на предыдущий. Помимо прочего, списки могут всегда находиться в упорядоченном состоянии — это достигается за счёт того, что вставка между любыми двумя его элементами весьма эффективна. Фактически создаётся новый элемент списка, в нем указываются адреса следующего и предыдущего элемента, а у самих этих элементов меняется адрес следующего или предыдущего элемента. При том вставка в обычный список в принципе имеет эффективность O(1), т. к. этот элемент привязывается к последнему (ну или первому — разницы нет). А вставка в упорядоченный список имеет эффективность O(Log2N). Подобная эффективность объясняется тем самым алгоритмом двоичного поиска места вставки, о котором я вещал в прошлой статье.
Кстати, сишная std::map — это такой вот связанный список. Можете сами прикинуть эффективность доступа к N-ному элементу или эффективность поиска значения в такой структуре данных.
ХЕШ-ТАБЛИЦЫ
Хеш-таблицы — тоже очень интересная структура данных, рассказ о которой может быть поможет вам взглянуть на эту штуку по новому. В Си для такой структуры данных есть std::unordered_map, в 1С такой структурой несомненно является Соответствие. Есть подобное и в питоне — словарь. Про другие языки особо не интересовался, но в годы моей юности ни в паскале, ни в бейсике, ни тем более в ассемблере ничего подобного не было.
Итак, давайте попробуем разобраться, как работают подобные ассоциативные массивы и в чем преимущество их использования.
Состоит такая таблица из записей, которые расположены в памяти практически так, как и массивы — последовательно. А вот индекс массива получается с помощью вычисления хеш-функции от ключа. И чем больше бит возвращает хеш-функция, тем больше памяти кушает хеш-таблица. Чувствуете погружение в детали? Так вот, если мы захотим использовать в качестве хеш-функции какой-нибудь MD5, то нам нужно будет где-то разместить 2^128 адресов даже для одного элемента, зато доступ к этому элементу будет иметь эффективность условно O(1). И понятно, что языки программирования режут хеш-функцию до приемлемого размера, создавая 2^8/12/16/24 элементов, меняя разрядность в ходе роста количества коллизий. Кстати, давайте о них (коллизиях) тоже поговорим.
КОЛЛИЗИИ В ХЕШ-ТАБЛИЦАХ
Коллизии — это когда хеш-функция для двух разных значений вернула один и тот же индекс. Знаете, как оценить предельный размер коллизий? Там все просто. Если у нас есть хеш-функция, результат которой занимает N бит, то количество коллизий для ключей, длина которых M бит, равна 2^(M-N). Для того, чтобы оживить пример, возьмём MD5, которая возвращает 128-битный результат. 128 бит — это 16 байт. Допустим, у нас есть много файлов длиной в 20 байт. И если взять все на свете варианты этих 20-ти байт, то на каждую хеш-сумму найдётся 2^(160-128=32) коллизий. Т.е. 4 миллиарда. Предположу, что вам не нужны все варианты 20-байтных файлов — у нас и своих файлов хватает разной длины. Но имейте ввиду, что среди файлов на вашем компьютере вполне могут обнаружится такие, у которых MD5 одинаковый.
Итак, когда у нас хеш-функция порождает коллизию, т. е. оказывается, что в ячейке с таким хешем уже что-то лежит, то по адресу лежащего данные могут быть преобразованы в массив, список и в чего угодно ещё. При третьей коллизии в этот массив или список просто будет добавлена ещё одна запись. Ну и понятно, что ключи тоже где-то должны храниться, чтобы при поиске нужного ключа было с чем сравнить.
Ну а после того, как хеш-функция будет признана вырожденной (после преодоления какого-нибудь порога коллизий), должно произойти перестроение хеш-таблицы с новой хеш-функцией большей разрядности. Поэтому вставка в такую таблицу далеко не всегда происходит с эффективностью O(1), а при стремящейся к вырождению хеш-функции и эффективность чтения из этой структуры данных уходит от O(1). Но если хеш-функция подобрана хорошо, обеспечивая при обрабатываемом наборе данных минимальное количество коллизий, эффективность работы данной структуры великолепна.
ЗАКЛЮЧЕНИЕ
Да, я опять не привёл никакого кода ни на каких ассемблерах, сях, питонах и даже 1С-ах. Но что поделать — я существо ленивое, как и все живое. Может быть ещё накопятся ягоды в ягодицах, и я разрожусь более технической статьёй. Но надеюсь, что и словесно-цифровое описание структур данных прольёт чуть-чуть света на то, как ими пользоваться, немного понимая в алгоритмах, которые внутри них вертятся. Надеюсь, что это все я писал не зря.
Подписывайтесь на мой канал, ставьте лайк (с)
