зачем нужно структурировать данные
Урок 3. Структурирование информации
При запоминании большого количества информации нам необходимо ее структурировать. Структурирование информации заключается, во-первых, в делении информации на группы и подгруппы по определенному критерию. Во-вторых, в умении строить логические связи между выделенными группами информации, чтобы структура надежно хранилась в нашей памяти. Структурирование – это создание прочного каркаса, на основе которого будет строиться запоминание всей необходимой информации.
В этом уроке вы узнаете принципы, критерии и методы структурирования информации для ее наилучшего запоминания.
Оглавление:
Что такое структурирование?
К примеру, возьмем номер телефона, написанный сплошным текстом 89115439080. Чтобы ее запомнить в таком виде нужно будет сильно постараться. Но если номер переписать в другом виде, например, в таком: 8 (911) 543-90-80, то запомнить его не составит большого труда. Поэтому, начиная от простого номера телефона и заканчивая большими учебниками, любая запоминаемая информация нуждается в структурировании.
Принципы структурирования
Главная цель структурирования – упрощение понимания основных элементов, из которых состоит весь массив информации, а также логики взаимосвязанности этих элементов. В результате такого упрощения нам становится удобнее запоминать информацию, строить ассоциативные ряды, применять различные мнемотехники. В соответствии с этой целью можно выделить два ключевых принципа структурирования изучаемой информации:
Первый принцип: информация должна быть поделена на группы и подгруппы в соответствии с определенным значимым для нас критерием.
Второй принцип: выделенные группы должны быть логично связаны, выстроены в необходимом порядке (по важности, по времени, по интенсивности и т.п.).
Также к этим принципам можно добавить еще несколько полезных правил, связанных с построением структурированной информации.
Правило Миллера (7 ± 2)
Эта закономерность «семь плюс-минус два» была обнаружена американским учёным-психологом Джорджем Миллером в результате ряда экспериментов. Она показывает, что кратковременная память человека способна запоминать в среднем: девять двоичных чисел, восемь десятичных чисел, семь букв алфавита или пять односложных слов. Что примерно составляет группу в количестве семи плюс-минус двух элементов.
Это правило уже использовалось в уроке по тренировке внимания, но оно также справедливо и для создания информационной структуры, которая должна храниться в нашей оперативной памяти. Поэтому не рекомендуется создавать количество групп или подгрупп, превышающее 7 элементов.
Эффект края
Эффект края (или краевой эффект) заключается в том, что мы обычно лучше запоминаем информацию в начале и в конце структурного ряда. Этот принцип известен в нашей стране благодаря фильму «17 мгновений весны», где главный герой-разведчик использовал его для того, чтобы переключить внимание собеседника. Однако открыт этот принцип был достаточно давно, а его исследованием занимался немецкий ученый Герман Эббингауз еще в XIX веке. Этот ученый также открыл «кривую забывания», информацию о которой вы найдете в следующем уроке.
Эффект Ресторфф
Эффект Ресторфф — называемый иначе эффект изоляции, эффект человеческой памяти, когда объект, выделяющийся из ряда сходных однородных объектов, запоминается лучше других. Иными словами, запоминается то, что сильно выделяется. Этим эффектом часто пользуются рекламщики для того, чтобы завоевать в вашем сознании хорошую позицию для своего товара. В нашем курсе знание этого эффекта необходимо для того, чтобы при структурировании информации выделялись группы непохожие одна на другую. В случае, когда каждый элемент структуры запоминаемого материала будет ярким и неоднозначным, наша память сможет лучше усвоить весь материал.
Методы структурирования
В процессе изучения человеческой памяти исследователи вывели несколько способов и методик структурирования информации, помогающих сделать процесс запоминания удобнее. Среди таких наиболее известных способов можно выделить методы Цицерона («римская комната») и Тони Бьюзена («карты памяти»).
Метод римской комнаты
Метод ментальных карт (карт памяти) Бьюзена
Метод ментальных карт, или как его еще называют майндмэппинг (а также диаграмма связей, интеллект карта, карта мыслей или ассоциативная карта) – это способ изображения структуры информации при помощи блок-схемы. Такие ментальные карты часто рекомендуют рисовать психологи или ведущие тренингов для правильной постановки целей или ведения проектов, но в нашем случае ментальные карты полезны именно для структурирования запоминаемой информации.
Для того чтобы построить ментальную карту, необходимо выполнить ряд следующих действий:
В результате вместо просмотра списков слов или предложений сверху вниз и слева направо (как это бывает в обычных конспектах), вы видите главную идею в центре листа, а затем двигаетесь по ветвям к краям листа в таком порядке, который вам нужен.
Итак, третье правило запоминания:
Создавайте удобную и логичную структуру запоминаемой информации.
Напоминаем, что для полноценной работы сайта вам необходимо включить cookies, javascript и iframe. Если вы ввидите это сообщение в течение долгого времени, значит настройки вашего браузера не позволяют нашему порталу полноценно работать.
Проверьте свои знания
Если вы хотите проверить свои знания по теме данного урока, можете пройти небольшой тест, состоящий из нескольких вопросов. В каждом вопросе правильным может быть только 1 вариант. После выбора вами одного из вариантов, система автоматически переходит к следующему вопросу. На получаемые вами баллы влияет правильность ваших ответов и затраченное на прохождение время. Обратите внимание, что вопросы каждый раз разные, а варианты перемешиваются.
Напоминаем, что для полноценной работы сайта вам необходимо включить cookies, javascript и iframe. Если вы ввидите это сообщение в течение долгого времени, значит настройки вашего браузера не позволяют нашему порталу полноценно работать.
Как внедрить микроразметку Schema.org на сайт, полное руководство
Schema.org приводит в порядок все структурированные данные вашего сайта. Если вы используете ее для разметки ваших продуктов, статей, рецептов, поисковые системы могут самостоятельно вытаскивать эти данные и расширенным образом представлять их в выдаче. Если вы хотите красивые сниппеты, голосовой поиск с мобильного устройства, список в графе рецептов, разделите контент на странице по типу. Это полное руководство о внедрении микроразметки на сайт.
Постепенно мы будем дополнять руководство. Пока доступна базовая информация о том, что такое микроразметка.
Что такое структурированная информация
Это данные, которые вы добавляете на свой сайт, размеченные особым способом. Он помогает пс понимать, что именно находится на вашем портале. Вам понадобится так называемый словарь, который использует большинство систем — Schema.org. В нем находятся описание для разного типа материалов: продукты, обзоры, списки местных компаний… Системы Google. Bing, Яндекс и Yahoo вместе разработали этот словарь, чтобы лучше читать веб-сайты.
Если разметка правильно внедрена на сайт, системы смогут использовать структурированные данные. Результатом станет лучшее ранжирование ресурса, и получение дополнительного места в выдаче: расширенные сниппеты или карточки товаров. Гарантировать, однако, это нельзя — все зависит от самого поисковика.
Зачем нужно структурировать данные
Маркировка продуктов, статей, мероприятий в соответствии с правилами Schema.org мгновенно сделает сайт понятным поисковым системам. Это значит, что ПС могут точно определить, какая информация относится к данным о компании, к товарам. Роботам не потребуется дополнительное время на решение, что чем является на вашем сайта.
Влияет ли структура данных на SEO
Быстрый ответ: да, влияет. Shema.org для структурирования нужна для оптимизации сайта. Правильное внедрение может вам и не дать прибавки к рейтингу в выдаче, но косвенно она сделает ваш сайт лучшим в ней результатом.
Ваш сайт будет представлен расширенным образом. А значит, привлечет больше внимания пользователей. И если текстовое сопровождение несет пользу, а страница в целом соответствует тому, что нужно человеку, то ваш сайт станет лучшим результатом. Это улучшит поведенческий фактор. 
Число отказов уменьшится. Google сочтет ваш сайт хорошим результатом для конкретного запроса, где пользователь находит точный ответ на волнующий его вопрос.
Кроме того, многие сайты еще не внедрили микроразметку. Для вас это шанс стать лучше конкурентов. Просто вдумайтесь. Вы разметите 300 положительных отзывов, которые оставлены на сайте вашей парикмахерской. Конкурент, который не будет также использовать комментарии о своем заведении, останется не у дел. Google соберет отзывы, покажет их в результате поиска. Какую парикмахерскую вы выберете — у которой 300 положительных отзывов или у которой нет ни одного?
Структурированные данные — больше места в выдаче
Адаптируя свой сайт под требования поисковиков, вы позволяете им делать интересные вещи с вашими материалами. Shema.org постоянно развивается и обновляется. Структурированные данные — основа для новых разработок в сфере SEO, например, голосового поиска. В будущем появится еще больше новых функций. Ниже — выборка результатов расширенного поиска, которые доступны сейчас.Здесь приведены самые важные и актуальные.
Расширенные результаты
Согласно заявлению Google, термин «расширенный сниппет» больше не используется. Однако суть не изменилась. Это дополнительная информация на странице выдачи, интерактивные функции. К обычному тексту из дескрипшна подтягиваются данные с информацией о продукте: цена, отзывы, рейтинг, быстрые ссылки для навигации, хлебные крошки.
Расширенные результаты на мобильных устройствах
Вот так они выглядят сейчас.
Результаты поиска для определенных запросов — местных заведений, рецептов, фильмов, обучающих курсов — могут получить специальное размещение. Его называют каруселью. Она удобна для сенсорных экранов.
Google крайне заинтересован в том, чтобы в выдаче предоставить вам столько информации, сколько вы можете обработать. Так, вы можете забронировать авиабилеты, заказать столик в ресторане, купить билеты в кино, отправить рецепт вкусного чизкейка маме, чтобы к вашему возвращению домой вкусняха уже была готова. Все из перечисленного работает на основе структурированных данных. И это только начало.
Сеть знаний
Это большой блок информации справа от основных результатов поиска. Он рассказывает конкретный результат поиска, детализирует его. Вся информация проверяется системой, после чего формируется такой граф. Чтобы его получить, например, для своего бренда, нужно обладать авторитетностью в сфере, верифицировать свою компанию.
Расширенный сниппет
По правде сказать, данные для такого типа данных берутся не из структурированной информации. Текст отвечает на поисковый запрос пользователя прямо в выдаче. Он формируется из текстового контента страницы.
Как структурирование информации работает на мобильных устройствах
Результаты структурирования показываются на всех устройствах. Для мобильных Shema.org только начинает портироваться. Хотя Google давно заявляет о важности этих платформ и уже ввел специальное индексирование.
Если страница соответствует критериям системы, то вы можете забронировать стол или купить билет в кино прямо с экрана смартфона на странице выдачи. Если внедрение микроразметки проведено правильно, для ваших страниц в мобильной выдаче будет введено несколько интерактивных элементов. Кроме того, с использованием технологии AMP число таких элементов увеличится.
Разные типы структурированных данных
Посмотрите на сайт микроразметки Schema.org. Есть много разных типов данных, которые вы можете использовать для своего портала. Но не все из них будут уместны. Чтобы внедрить микроразметку, ответьте на следующие вопросы:
Изучите требования поисковых систем к микроразметке. Так вы избежите ошибок, которые ухудшат ранжирование и могут даже загнать сайт под фильтр.
Не гонитесь за микроразметкой всех данных. Начните с тех форматов, которые проще всего внедрить. Некоторые есть на миллионе сайтов. А некоторые только на тысяче. Для удобства доступные форматы разделены на две группы.
Creative works
Это творческие работы, которые были созданы авторами. Ниже расскажем о самых популярных. Однако в действительности типов в этой группе намного больше. Многие из них не столь информативны, когда попадаются на глаза пользователю в выдаче. Поэтому ценятся меньше.
Статьи
Это новостной пост, отчет об исследовании, запись из личного блога. Вы можете даже указать сферу публикации: новость, технический текст, личное.
Книги
Может быть в бумажном или электронным формате. Можно отдельно указать автора, даже его награды и премии.
Курсы
Образовательные мероприятия. Сейчас этот вариант тестируется. Скоро каждый спикер может применить микроразметку для своих курсов и улучшить внешний вид в выдаче.
Множества
Google анализирует ваши наборы данных и может уже в выдаче о них рассказать. Как это работает для разных примеров, можете прочитать на сайте для разработчиков.
Руководства
Скоро вы можете разметить практические гайды на своем сайте. Пользователь будет следовать пошаговому чек-листу и выполнит свою задачу. Пока для этого типа информации нет расширенного результата.
Музыка
СКРИНШОТ
Аудио тоже может попасть в расширенную выдачу. Есть несколько типов для такой информации:
Указывая поисковику, что текст на сайте — рецепт, вы можете вывести их на главную страницу выдачи. А ранжирование для мобильных устройств позволяет сделать представление красочным — добавить на сниппет изображения блюда. Но и это не все. Голосовой бот Google может вслух зачитать этот рецепт для вас.
Фильмы и ТВ-передачи
Они также получают свои представления. Поиск фильма даст расширенный результат с постерами, трейлером, отзывами. Пользователь сможет заказать билет в кинотеатр.
Вы можете сделать собственную подборку с фильмами или телепередачами, разметить ее и таким образом загнать в выдачу. Дайте пользователю сразу то, что ему нужно — используйте ViewAction и Watch Action. Человек сможет сразу в выдаче перейти к просмотру материала.
Видеоролики
С видео можно делать интересные вещи. Прямо сейчас Google работает над новыми способами отображения в выдаче, например, над использованием AMP в каруселях роликов или списках Top Stories.
Подкасты
Записываете свои подскасты? Разметьте! Google подтянет на страницу выдачи описание к каждому выпуску, даже добавит кнопку воспроизведения.
Commerce
Вторая основная группа — это коммерческие расширения.
Мероприятия
Разметка событий в соответствии с правилами позволит им попасть на страницу выдачи. Это нужно в первую очередь владельцем площадок для организации мероприятий — ночным клубам, выставочным залам, конференц-холлам.
Организации
Вы можете монетизировать свой сайт и начать собственное дело. При помощи микроразметки вы можете сделать красивое оформление для вашей фирмы в выдаче. Если правильно все сделаете, можете получить в придачу граф знаний или другой тип расширенного сниппета. Вы даже можете разметить контактную информацию, чтобы клиенты звонили вам, находясь прямо в поисковой выдаче.
Товары
Schema.org нужна не только для выделения важной информации о вашей компании. Вы можете разметить товары, которыми торгуете. Обратите внимание на все результаты расширенного поиска, с которыми сталкивались в выдаче.
Помните о качественных изображениях ваших продуктов! Если пользователь увидит размытую картинку в выдаче, он пойдет на тот ресурс, где сможет ясно увидеть товар.
Отзывы
Отзывы и рейтинги играют важную роль в процессе выбора человеком товара. Компании используют их для привлечения большего числа клиентов. Отзывами фирмы вызывают доверие у своей аудитории.
Получение рейтинга в 5 звезд может стать одной из главных задач маркетинга.
Новый расширенный результат: действия
Голосовые помощники стремительно набирают популярность — у Яндекса появилась «Алиса», а Google начал вплотную заниматься голосовым поиском. Вы можете отправить рецепт блюда со страницы выдачи в Google Home. Голосовой помощник вслух зачитывает рецепт, пока вы будете готовить еду. Этот расширенный результат называется «действия».
Добавьте на свой сайт эту структуру данных. Дополнительную информацию найдете здесь. На странице Google’s Assistant почитайте о том, что еще можно воплотить в жизнь таким способом.
Технические аспекты
Для внедрения микроразметки данных, разберитесь, как работает Schema.org. Посмотрите на все спецификации — увидите строгую иерархию в словаре данных. Все связано между собой. Ознакомьтесь со всем списком, запишите те данные, которые вам потребуются.
Посмотрим на иерархию. Внедрение микроформатов начинается с сущности Thing — общего типа всех элементов. Элемент — более конкретная сущность: авторская работа, событие, компания, личность, место, товар.
Например, фильм — это thing и авторская работа. Он относится к категории «Кино». К нему можно добавить много свойств-атрибутов:
Таких атрибутов очень много. Уточните как можно больше информации о сущности. Но не перегружайте выдачу. Не все свойства поисковики подтягивают в расширенную выдачу. Список участвующих атрибутов уточняйте в документации Google.
Простой пример иерархии для Schema.org
Если мы расположим всю информацию о сущности в иерархическом порядке, получим следующее:
Если мы работаем с описанием компании, получим что-то такое:
Для местных организаций укажите конкретный вид бизнеса. Поисковые системы сразу поймут, чем вы занимаетесь. Иногда вы можете заниматься тем, для чего нет конкретной сущности в Schema.org. Используйте Product Types Ontology, чтобы дифференцировать вашу тематику.
Есть ряд обязательных данных, которые нужно указать. Среди них — адрес и телефон компании. Есть рекомендуемые данные:
Заполните столько информации, сколько можете. Только так вы получите богатый результат в выдаче. Составьте список характеристик, которые вы считаете важными для своего дела. А затем начинайте внедрять микроразметку для каждой.
Есть интересный плагин от Yoast. Инструмент платный, но он поможет вытянуть все необходимые сущности, которые вам следует разметить.
Какие данные нужно размечать
На первый взгляд, внедрение микроразметки на сайт — дело непростое. Начните с азов. Вы же уже выбрали характеристики, которые непременно нужны в расширенной выдаче о вашей компании? С них и начните. Обратите внимание на нюансы: товары и отзывы. Они просты в разметке, а преимущества от их присутствия на сниппете неоспоримые.
Как внедрить микроразметку Schema.org на сайт
Несмотря на то, что это техническая работа, все упрощает JSON-LD. Этот формат данных основан на JavaScript. Он упрощает добавление микроформатов. Вам не нужно ничего вписывать в HTML-код страниц. Внесение данных и их обновление стали простыми. А сам инструмент отлично подходит для людей — он простой и понятный, и для поисковиков — они с легкостью распознают микроформаты.
Используем JSON-LD для микроформатов
JSON-LD сегодня — предпочтительный вариант внедрения микроразметки на ресурс. Он долго не поддерживался поисковиком Bing. Но сегодня все популярные системы распознают этот формат. Ниже — листинг для микроразметки информации для SEO-плагина от Yoast.
Для простоты используется небольшой объем информации:
В конце кода есть раздел с призывом к действию купить плагин, который стоит 86 долларов.
Другие способы: RFDa и Microdata
Традиционный метод внедрения — это включение микроразметки в код страницы. Делать это было долго, сложно и муторно. Поэтому Schema.org не сразу стала популярной.
Написание микроформата и поддержка через RDFa или Microdata — боль. Старайтесь как можно чаще использовать JSON-LD.
Тем более, Microdata нуждается в функции itempops. Любой микроформат придется прописывать в HTML-коде. Читать и редактировать это крайне неудобно.
Структурированные данные и AMP
Суть технологии AMP — ускорить загрузку страниц на мобильных устройствах. Google продвигает AMP, в том числе и для структурированных данных. Хотите внедрить AMP? Добавьте структурированные данные. Система использует несколько элементов Schema.org, чтобы сохранить интерактивность в выдаче.
Инструменты для работы со структурированными данными
Со Schema.org работать несложно. Но вручную писать код не эффективно. Попробуйте инструменты из списка ниже. Попросите разработчика вам помочь. Для них это — работа на пару минут.
Генераторы
Валидаторы
Плагины для WordPress
Полезные ссылки
Большинство поисковиков имеют собственные консоли для управления сайтами. В руководствах вы найдете конкретные советы для каждой поисковой системы.
Всегда проверяйте код в разных валидаторах микроразметок. Поддерживайте работоспособное состояние.
Структуры данных для самых маленьких
James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.
Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.
Сегодня мы узнаем всё о структурах данных.
«Оооооой как интересно. », да?
Да уж, не самая сочная тема на сей день, однако крайне важная. Не для того, чтобы сдавать курсы наподобие CS101, а чтобы лучше разбираться в программировании.
Второй пункт тоже важен. Когда учитываются производительность или память программы, правильный выбор структуры данных значительно сказывается на работе.
Чтобы познакомиться со структурами данных, мы реализуем некоторые из них. Не беспокойтесь, код будет лаконичен. На самом деле, тут больше комментариев, а кода между ними — раз, два и обчёлся.
Что такое структуры данных?
По сути, это способы хранить и организовывать данные, чтобы эффективней решать различные задачи. Данные можно представить по-разному. В зависимости от того, что это за данные и что вы собираетесь с ними делать, одно представление подойдёт лучше других.
Чтобы понять, почему так происходит, сперва поговорим об алгоритмах.
Алгоритмы
Алгоритм — такое хитроумное название для последовательности совершаемых действий.
Структуры данных реализованы с помощью алгоритмов, алгоритмы — с помощью структур данных. Всё состоит из структур данных и алгоритмов, вплоть до уровня, на котором бегают микроскопические человечки с перфокартами и заставляют компьютер работать. (Ну да, у Интела в услужении микроскопические люди. Поднимайся, народ!)
Любая данная задача реализуется бесконечным количеством способов. Как следствие, для решения распространённых задач изобрели множество различных алгоритмов.
Например, для сортировки неупорядоченного множества элементов существует до смешного большое количество алгоритмов:
Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка.
Некоторые из них значительно быстрее остальных. Другие занимают меньше памяти. Третьи легко реализовать. Четвёртые построены на допущениях относительно наборов данных.
Каждая из сортировок подходит лучше других для определённой задачи. Поэтому вам надо будет сперва решить, какие у вас потребности и критерии, чтобы понять, как сравнивать алгоритмы между собой.
Для сравнения производительности алгоритмов используется грубое измерение средней производительности и производительности в худшем случае, для обозначения которых используется термин «О» большое.
О большое
«О» большое — обозначение способа приблизительной оценки производительности алгоритмов для относительного сравнения.
О большое — заимствованное информатикой математические обозначение, определяющее, как алгоритмы соотносятся с передаваемым им некоторым количеством N данных.
О большое характеризует две основные величины:
Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.
Оценка объёма — общее количество памяти, требующееся алгоритму для обработки данного множества данных.
Оценки делаются независимо друг от друга: одни алгоритмы могут производить меньше операций, чем другие, занимая при этом больше памяти. Определив свои требования, вы сможете выбрать соответствующий алгоритм.
Вот некоторые распространённые значения О большого:
Чтобы дать представление, о каких порядках чисел мы говорим, давайте взглянем, что это будут за значения в зависимости от N.
Как видите, даже при относительно небольших числах можно сделать *дофига* дополнительной работы.
Структуры данных позволяют производить 4 основных типа действий: доступ, поиск, вставку и удаление.
Замечу, что структуры данных могут быть хороши в одном из действий, но плохи в другом.
Кроме того, некоторые действия имеют разную «среднюю» производительность и производительность в «самом худшем случае».
Идеальной структуры данных не существует. Вы выбираете самую подходящую, основываясь на данных и на том, как они будут обрабатываться. Чтобы сделать правильный выбор, важно знать различные распространённые структуры данных.
Память
Компьютерная память — довольно скучная штука. Это группа упорядоченных слотов, в которых хранится информация. Чтобы получить к ней доступ, вы должны знать её адрес в памяти.
Фрагмент памяти можно представить так:
Если вы задумывались, почему в языках программирования отсчёт начинается с 0 — потому, что так работает память. Чтобы прочитать первый фрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адреса этих фрагментов соответственно равны 0 и 1.
Конечно же, в компьютере больше памяти, чем показано в примере, однако её устройство продолжает принцип рассмотренного шаблона.
Просторы памяти — как Дикий Запад. Каждая работающая на компьютере программа хранится внутри одной и той же *физической* структуры данных. Использование памяти — сложная задача, и для удобной работы с ней существуют дополнительные уровни абстракции.
Абстракции имеют два дополнительных назначения:
— Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать.
— Сохраняют данные в памяти так, чтобы их было проще использовать.
Списки
Для начала реализуем список, чтобы показать сложности взаимодействия между памятью и структурой данных.
Список — представление пронумерованной последовательности значений, где одно и то же значение может присутствовать сколько угодно раз.
Начнём с пустого блока памяти, представленного обычным JavaScript-массивом. Также нам понадобится хранить значение длины списка.
Заметьте, что мы хотим хранить длину отдельно, поскольку в реальности у «памяти» нет значения length, которое можно было бы взять и прочитать.
Первым делом нужно получать данные из списка. Обычный список позволяет очень быстро получить доступ к памяти, поскольку вы уже знаете нужный адрес.
Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!»
У списков есть порядковые номера, поэтому можно вставлять значения в начало, середину и конец.
Это настолько же легко, как добавить значение в адрес, следующий за нашим списком. Поскольку мы храним длину, вычислить адрес — проще простого. Добавим значение и увеличим длину.
Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»
Комментарии хабра: poxu не согласен с автором и объясняет, что существует операция расширения памяти, увеличивающая сложность добавления элементов в список.
Далее, реализуем метод «pop», убирающий элемент из конца нашего списка. Аналогично push, всё, что нужно сделать — убрать значение из последнего адреса. Ну, и уменьшить длину.
Удаление элемента из конца списка — константа O(1) — «ОХРЕНЕННО!!»
«Push» и «pop» работают с концом списка, и в общем-то являются простыми операциями, поскольку не затрагивают весь остальной список.
Давайте посмотрим, что происходит, когда мы работаем с началом списка, с операциями «unshift» и «shift».
Чтобы добавить новый элемент в начало списка, нужно освободить пространство для этого значения, сдвинув на один все последующие значения.
Чтобы сделать такой сдвиг, нужно пройтись по каждому из элементов и поставить на его место предыдущий.
Поскольку мы вынуждены пройтись по каждому из элементов списка:
Добавление элемента в начало списка — линейно O(N) — «НОРМАС.»
Осталось написать функцию сдвига списка в противоположном направлении — shift.
Мы удаляем первое значение и затем сдвигаем каждый элемент списка на предшествующий адрес.
Удаление элемента из начала списка — линейно O(N) — «НОРМАС.»
Списки отлично справляются с быстрым доступом к элементам в своём конце и работой с ними. Однако, как мы увидели, для элементов из начала или середины они не слишком хороши, так как приходится вручную обрабатывать адреса памяти.
Давайте посмотрим на иную структуру данных и её методы по добавлению, доступу и удалению значений без необходимости знать адреса элементов.
Хеш-таблицы
Хеш-таблица — неупорядоченная структура данных. Вместо индексов мы работаем с «ключами» и «значениями», вычисляя адрес памяти по ключу.
Смысл в том, что ключи «хешируются» и позволяют эффективно работать с памятью — добавлять, получать, изменять и удалять значения.
Вновь используем обычный JavaScript-массив, представляющий память.
Чтобы сохранять пары ключ-значение из хеш-таблицы в память, нужно превращать ключи в адреса. Этим занимается операция «хеширования».
Она принимает на вход ключ и преобразовывает его в уникальное число, соответствующее этому ключу.
Такая операция требует осторожности. Если ключ слишком большой, он будет сопоставляться несуществующему адресу в памяти.
Следовательно, хеш-функция должна ограничивать размер ключей, т.е. ограничивать число доступных адресов памяти для неограниченного количества значений.
Любая реализация хеш-таблиц сталкивается с этой проблемой.
Однако, поскольку мы собираемся рассмотреть лишь устройство их работы, предположим, что коллизий не случится.
Давайте определим функцию «hashKey».
Не вдавайтесь во внутреннюю логику, просто поверьте, что она принимает на вход строку и возвращает (практически всегда) уникальный адрес, который мы будем использовать в остальных функциях.
Теперь определим функцию «get», получающую значение по ключу.
Сложность чтения значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»
Перед тем, как получать данные, неплохо бы их сперва добавить. В этом нам поможет функция «set».
Сложность установки значения в хеш-таблицу — константа O(1) — «ОХРЕНЕННО!!»
Наконец, нужен способ удалять значения из хеш-таблицы. Сложность удаления значения из хеш-таблицы — константа O(1) — «ОХРЕНЕННО!!»
Теперь мы прекратим работать с памятью напрямую: все последующие структуры данных будут реализовываться через другие структуры данных.
Стеки
Стеки похожи на списки. Они также упорядочены, но ограничены в действиях: можно лишь добавлять и убирать значения из конца списка. Как мы увидели ранее, это происходит очень быстро, если обращаться к памяти напрямую.
Однако стеки могут быть реализованы через другие структуры данных, чтобы получить дополнительную функциональность.
Наиболее общий пример использования стеков — у вас есть один процесс, добавляющий элементы в стек и второй, удаляющий их из конца — приоритизируя недавно добавленные элементы.
Нам вновь понадобится JavaScript-массив, но на этот раз он символизирует не память, а список, вроде реализованного выше.
Нам понадобится реализовать два метода, функционально идентичных методам списка — «push» и «pop».
Push добавляет элементы на верхушку стека.
Pop удаляет элементы из верхушки.
Кроме того, добавим функцию peek, показывающую элемент на верхушке стека без его удаления. Прим. переводчика: peek – взглянуть.
Очереди
Теперь создадим очередь — структуру, комплементарную стеку. Разница в том, что элементы очереди удаляются из начала, а не из конца, т.е. сначала старые элементы, потом новые.
Как уже оговаривалось, поскольку функциональность ограничена, существуют разные реализации очереди. Хорошим способом будет использование связного списка, о котором мы поговорим чуть позже.
И вновь мы призываем на помощь JavaScript-массив! В случае с очередью мы опять рассматриваем его как список, а не как память.
Аналогично стекам мы определяем две функции для добавления и удаления элементов из очереди.
Первым будет «enqueue» — добавление элемента в конец списка.
Далее — «dequeue». Элемент удаляется не из конца списка, а из начала.
Аналогично стекам объявим функцию «peek», позволяющую получить значение в начале очереди без его удаления.
Важно заметить, что, поскольку для реализации очереди использовался список, она наследует линейную производительность метода shift (т.е. O(N) — «НОРМАС.»).
Как мы увидим позже, связные списки позволяют реализовать более быструю очередь.
С этого места и далее мы будем работать со структурами данных, где значения ссылаются друг на друга.
Элементы структуры данных становятся сами по себе министруктурами, содержащими значение и дополнительную информацию — ссылки на другие элементы родительской структуры.
Сейчас вы поймёте, что я имею ввиду.
Графы
На самом деле граф — совсем не то, о чём вы подумали, увидев ascii-график.
Граф — структура наподобие этой:
Эти вершины можно представить вот так:
А весь граф будет выглядеть вот так:
Представим список вершин JavaScript-массивом. Массив используется не с целью специально упорядочить вершины, а как место для хранения вершин.
Начнём добавлять значения в граф, создавая вершины без каких-либо линий.
Теперь нужен способ искать вершины в графе. Обычно для ускорения поиска делается ещё одна структура данных поверх графа.
Но в нашем случае мы просто переберём все вершины, чтобы найти соответствующую значению. Способ медленный, но работающий.
Теперь мы можем связать две вершины, проведя «линию» от одной до другой (прим. переводчика: дугу графа).
Полученный граф можно использовать вот так:
Кажется, что для такой мелкой задачи сделано слишком много работы, однако это мощный паттерн.
Он часто применяется для поддержания прозрачности в сложных программах. Это достигается оптимизацией взаимосвязей между данными, а не операций над самими данными. Если вы выберете одну вершину в графе, невероятно просто найти связанные с ней элементы.
Графами можно представлять уйму вещей: пользователей и их друзей, 800 зависимостей в папке node_modules, даже сам интернет, являющийся графом связанных друг с другом ссылками веб-страниц.
Связные списки
Давайте теперь посмотрим, как графоподобная структура может оптимизировать упорядоченный список данных.
Связные списки — распространённая структура данных, зачастую используемая для реализации других структур. Преимущество связного списка — эффективность добавления элементов в начало, середину и конец.
Связный список по своей сути похож на граф: вы работаете с вершинами, указывающими на другие вершины. Они расположены таким образом:
Если представить эту структуру в виде JSON, получится нечто такое:
В отличие от графа, связный список имеет единственную вершину, из которой начинается внутренняя цепочка. Её называют «головой», головным элементом или первым элементом связного списка.
Также мы собираемся отслеживать длину списка.
Первым делом нужен способ получать значение по данной позиции.
В отличие от обычных списков мы не можем перепрыгнуть на нужную позицию. Вместо этого мы должны перейти к ней через отдельные вершины.
Теперь необходим способ добавлять вершины в выбранную позицию.
Создадим метод add, принимающий значение и позицию.
Последний метод, который нам понадобится — remove. Найдём вершину по позиции и выкинем её из цепочки.
Две оставшиеся структуры данных относятся к семейству «деревьев».
Как и в жизни, существует множество различных древовидных структур данных.
Прим. переводчика: ну не-е-е-е, я пас…
Binary Trees:
AA Tree, AVL Tree, Binary Search Tree, Binary Tree, Cartesian Tree, left child/right sibling tree, order statistic tree, Pagoda,…
B Trees:
B Tree, B+ Tree, B* Tree, B Sharp Tree, Dancing Tree, 2-3 Tree,…
Heaps:
Heap, Binary Heap, Weak Heap, Binomial Heap, Fibonacci Heap, Leonardo Heap, 2-3 Heap, Soft Heap, Pairing Heap, Leftist Heap, Treap,…
Trees:
Trie, Radix Tree, Suffix Tree, Suffix Array, FM-index, B-trie,…
Multi-way Trees:
Ternary Tree, K-ary tree, And-or tree, (a,b)-tree, Link/Cut Tree,…
Space Partitioning Trees:
Segment Tree, Interval Tree, Range Tree, Bin, Kd Tree, Quadtree, Octree, Z-Order, UB-Tree, R-Tree, X-Tree, Metric Tree, Cover Tree,…
Application-Specific Trees:
Abstract Syntax Tree, Parse Tree, Decision Tree, Minimax Tree,…
Чего уж вы не ожидали, так это что будете изучать сегодня дендрологию… И это ещё не все деревья. Пусть они вас не смущают, большинство из них вообще не имеет смысла. Надо же было людям как-то защищать кандидатские степени и что-то для этого доказывать.
Деревья похожи на графы или связные списки, с той разницей, что они «однонаправленые». Это значит, что в них не может существовать циклических ссылок.
Если вы можете пройти круг по вершинам дерева… что ж, поздравляю, но это не дерево.
Деревья применяются во множестве задач. Они используются для оптимизации поиска или сортировки. Они могут лучше организовывать программу. Они могут создать представление, с которым проще работать.
Деревья
Начнём с простой древовидной структуры. В ней нет особых правил, и выглядит она примерно так:
Дерево должно начинаться с единственного родителя, «корня» дерева.
Нам нужен способ обходить наше дерево и вызывать определённую функцию в каждой его вершине.
Теперь нужен способ добавлять вершины в дерево.
Это простое дерево, возможно, полезное лишь в случае, когда отображаемые данные на него похожи.
Однако при наличии дополнительных правил деревья могут выполнять кучу различных задач.
Двоичные деревья поиска
Двоичные деревья поиска — распространённая форма деревьев. Они умеют эффективно читать, искать, вставлять и удалять значения, сохраняя при этом отсортированный порядок.
Представьте, что у вас есть последовательность чисел:
Развернём её в дерево, начинающееся из центра.
Это делает обход дерева при поиске значения очень эффективным. Например, попробуем найти число 5 в нашем дереве.
Заметьте, чтобы добраться до 5, потребовалось сделать лишь 3 проверки. А если бы дерево состояло из 1000 элементов, путь был бы таким:
Всего 10 проверок на 1000 элементов!
Ещё одной важной особенностью двоичных деревьев поиска является их схожесть со связными списками — при добавлении или удалении значения вам нужно обновлять лишь непосредственно окружающие элементы.
Как и в прошлой секции, сперва нужно установить “корень” двоичного дерева поиска.
Чтобы проверить, находится ли значение в дереве, нужно провести поиск по дереву.
Чтобы добавить элемент в дерево, нужно произвести такой же обход, как и раньше, перепрыгивая по левым и правым вершинам в зависимости от того, больше или меньше ли они по сравнению с добавляемым значением.
Однако теперь, когда мы доберёмся до левой или правой вершины, равной null,
мы добавим вершину в эту позицию.
Конец
Надеюсь, вы получили хорошую дозу знаний. Если вам понравилось,
ставьте звездочки в репозитории и подписывайтесь на меня в твиттере.
Также можете прочитать другую мою статью, «The Super Tiny Compiler» github.com/thejameskyle/the-super-tiny-compiler
Также эту статью можно прочитать на гитхабе.
Перевод: aalexeev, редактура: iamo0, Чайка Чурсина.