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

В программировании есть один веселый парадокс. Большинство гениальных принципов, идей и фишек обычно придумывается неформальными задротами в игровой атмосфере. А потом все эти фишки невероятно скучно и нудно впаривают официальные старые дядьки в пиджаках новым неформальным задротам. И если угашенный волосатый хикки с постером хатсуне мику на всю стену вдруг заорет "Да! Придумал! Как же офигенно пилить интересные идеи вместо курсача!", то через лет десять унылый дед будет гундосить "Этот алгоритм был придуман в 2017 году Битардом Сычевским. Сейчас я невероятно скучно опишу его вам, это будет на экзамене двухсотым вопросом"

Подобная хрень случилась со структурами данных. Я их ненавидел, анон. Я на них спал. Но сегодня мы поговорим именно о них, ведь эта тема будет еще не раз и не два всплывать в дальнейших псто. В прошлой части #Лурк_it я анонсировал язык си, но из-за временной смерти моего ноутбука сегодня у нас не совсем форматный спешл. Интересно должно быть всем, так что читайте далее.
Структуры данных были запилены для здоровенных систем с инфой, чтобы быстрее с ней работать. Есть целые отрасли проги, заточенные под работу с огромными базами, и мне довелось косвенно поработать в одной из них. Поверь мне анон, в этом деле даже доли секунды играют роль. Так что это говно юзалось, юзается и будет юзаться еще много лет, если конечно корея не станет сверхдержавой и не расфигарит весь мир.

Для того чтобы понять как это работает, нам понадобится даже не прога с матаном, а абстрактное мышление и фантазия. Итак, представим что есть некий белый листочек. Мы можем записать туда инфу и адрес другого листа. Тысячи таких листов с инфой и адресами друг друга и будут являться структурой данных. Самая понятная обывателю структура данных это очередь. Когда вы приходите в поликлинику, вы спрашиваете "кто последний"? Из другого конца галактики вам ответствует баба Срака. Вы говорите что будете за ней. Все. Вы стали частью структуры данных. Вас не интересует кто первый, кто третий, сколько там всего человек. Вы ориентируетесь на бабу Сраку. И вы зайдете в кабинет после нее. Если осмотреть очередь со стороны замученного жизнью врача, то выяснится что последним в кабинет войдет последний пришедший. Это вроде как справедливо, поэтому очереди и существуют ирл. В проге очередь реализуется кучей элементов, каждый из которых знает кто находится перед ним, и адресом головы очереди(самой первой бабки). При выводе всех элементов на экран, например, печатается и удаляется только голова, остальные элементы просто по очереди в нее превращаются. Совсем грубо говоря, мы перебираем каждый элемент спрашивая его "кто перед тобой?". И так до тех пор, пока элемент не скажет "Да никто, тот кто передо мной уже на экране". И тогда программа говорит о, чудесно, теперь ты голова. Перед тобой никого нет.

А теперь представим параллельную вселенную. В ней в поликлиниках все наоборот, первым в кабинет заходит последний пришедший. То есть вы такие пришли, стали в очередь, перед вами баба Срака, перед бабой Сракой стоит Наруто. Прием еще не начался. Тут приходит тетя Глаша и говорит кто последний? Ты говоришь мол я. Она такая отлично, запомни что я за тобой. Доктор начинает прием. Сначала заходит тетя Глаша, потому что после нее никого нет. Потом человеком после которого никого нет становишься ты. Ты же и идешь следующим, потом идет баба Срака и потом Наруто. Такая структура данных похожа на игрушечную пирамидку с колечками, где чтобы снять первое кольцо нужно снять все остальные. Она называется стек и используется программами для хранения поступивших команд. Почему? Потому что последняя поступившая команда является самой актуальной.

Следующая структура данных это бинарное дерево поиска. Это уже веселее и для объяснения ее работы понадобится совсем уж ебанутая поликлиника. Итак, поначалу все как и раньше, приходит яжемать. Потом приходит баба Срака. Яжемать спрашивает, старше ли бабка чем яжемать. Бабка говорит что да. "Отлично, тогда становись справа от меня. Я тебя запомнила". Потом приходит более молодая тян. Яжемать спрашивает тянку "твой возраст больше чем мой?" завистливо поглядывая на ее плоский животик. Тянка говорит что нет. "Ну ок, тогда становись слева. Я тебя тоже запомнила". Потом приходишь ты, молодой анон. Яжемать спрашивает тебя "твой возраст больше чем мой"? Ты такой ну а ты как думаешь ? Конечно нет. Она тебе говорит окей, но я уже помню два человека, поэтому пройди налево. Ты проходишь налево, там молодая тянка. Она тебя спрашивает про возраст, ты говоришь что младше ее. "Окей, становись слева от меня, я тебя запомнила". Ты краснеешь и становишься слева от тни. Потом приходит киберспортсмен и олдфаг, 11-летний Николай. Он моложе яжемати, и яжемать отсылает его левее, к тянке. Он моложе тянки, и тянка тоже отсылает его левее, к тебе, потому что она может запомнить только одного человека слева и одного человека справа. Ты спрашиваешь у Коли его возраст, он меньше чем твой, и ты запоминаешь что Коля стоит слева от тебя. Потом приходит Ленин, он старше яжемати , она отсылает его вправо, к бабе Сраке. А баба Срака ставит Ленина слева от нее, потому что она настолько древняя что старше даже его. Перебирать подобное дерево можно по разному, доктор может принимать начиная с яжемати, может начиная с тебя, может начиная с Ленина. Суть бинарного дерева в том, что каждый элемент может запомнить еще два элемента, причем элемент с большим значением будет справа, а с меньшим — слева. Деревьев бывает много видов, но в основном они юзаются в здоровых базах данных для большой скорости поиска.

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

Ну и наконец самая ебанутая поликлиника. По описанию кстати похожа на мой военкомат. В этой поликлинике твое имя превращают в цифру по какому-нибудь строгому неслучайному алгоритму. Например перемножают номера букв в алфавите. И если тебя зовут АГБ(совпадение, вовсе не нежелание автора считать другие имена на калькуляторе) то твой номер будет 1*4*2=8. Вуаля, ты восьмой в очереди! Такая структура называется хеш таблицей и юзается вообще везде, потому что она позволяет равномерно заполнить таблицу. Самые проницательные возможно спросят "а что если человека зовут БББ? тогда его номер тоже будет 2*2*2=8"! Это явление называется коллизией. В хороших хеш таблицах она маленькая. Но это не отменяет того факта что у нас тут два человека под номером восемь. И что же делать? Знакомьтесь - структура в структуре. БББ подходит к АГБ и говорит "ты тут восьмой, да?". Ты говоришь ага, и вы(программист) договариваетесь в каком порядке вы войдете если врач вызовет восьмой номер. Это может быть и стек, и очередь, и дерево, и двусвязный список, и небо, и Аллах.

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

Источник: vk.com

Комментарии: