Ранее мы поговорили поговорили о такой структуре данных как массив. Настало время поговорить про остальные базовые структуры данных
Хэш
Хэш таблица (еще она называется Hash map в других ЯП) - структура данных, хранящая в себе сразу 2 элмента - ключ и значение. Ключ - уникальный, значение - нет.
# создание пустой хэш таблицыhash =Hash.new# Упрощенная записьhash = {}# Способ создания хэш таблицы с заранее созданным содержаниемhash =Hash['key_1'=>'value_1','key_2'=>'value_2','key_1'=>'value_3']# Упрощенная запись через кавычкиhash = {'key_1'=>'value_1','key_2'=>'value_2','key_1'=>'value_3'}# Начиная с ruby 1.9 появилась возможность записывать ключ - значение через двоеточие. # Данный вариант записи стоит считать наиболее предпочтительный, вместо Hash[...] или использования => # так как при записи key: value, key приводится к символу, о котором мы поговорим в следующем урокеhash = {'key_1':'value_1','key_2':'value_2','key_1':'value_3'}# Обрати внимание, что key_1 содержится только один раз, не смотря на то, что мы его объявляли дважды# И значение содержится от последней объявляенной пары с таким же ключомputs hash # = {'key_1' => 'value_3', 'key_2' => 'value_2'}
Легче всего представлть хэш таблицу как словарь. Если открыть любой словарь, то мы увидим в нем слово и его перевод/ы. При этом один и тот же перевод, может относиться к различным словам. Давайте попробуем реализовать такой словарь с помощью Hash:
# создание пустой хэш таблицыdictionary =Hash.new# Упрощенная записьdictionary = {'be':'быть','have':'иметь','mandarin':'мандарин','tangerine':'манадрин'}# как можем заметить словарь включает в себя несколько одинаковых значенийputs dictionary# Получение значения по его ключу# Принцип схож с массивом, только если там мы оперируем индексом, то здесь у нас произвольный ключputs dictionary['be'] # = быть# Так как такого ключа нет в нашем хэше, то значение будет nilputs dictionary['you'] # = nil
Теперь стоит обсудить как изменять хэш таблицу:
muttable_hash = {'key_1':'value_1'}puts muttable_hash.length # = 1# принцип похож на изменение значения массива по индексу# только если там у нас массив изменял размер до последнего индекса# то тут поведение уже нормальное и ожидаемое muttable_hash['key_2'] ='value_2'puts muttable_hash.length # = 2# изменение значения по ключу ничем не отличается от добавления# так как ключи уникальны, то значение просто перезапишется muttable_hash['key_1'] ='value_2'puts muttable_hash.length # = 2# метод удаления достаточно предсказуемиmuttable_hash.delete('key_2')
Давайте посмотрим на особенность итерации хэша в цикле:
example = { '1':1,'2':1,'3':1}#попробуем написать в обычном для нас форматеfor x in example# только вместо puts будем использовать p для более подробной информацииp x # = [:"1", 1], потом [:"2", 1], потом [:"3", 1] # если все еще не поняли, то давайте сразу посмотрим на тип у x puts x.class # = Array. Да, при обходе в цикле хэша, на каждую иетрацию мы получаем доступ к ключу и значению, которые представлены в виде массива
# где 1 элемент - ключputs"key: #{x[0]}"# а второй элемент это наше значениеputs"value: #{x[1]}"end# данный цикл делает тоже самое, что и цикл выше# только мы заменили одну переменную, которая была массивом# на 2 переменные, первая - ключ, вторая - значение for key, value in exampleputs"key: #{key}"puts"value: #{value}"end
Сет
Настало поговорить про Set. Set - это нечто среднее между массивом и хэш таблицей. Сет - это тот же самый Hash, но без значений, только ключи.
# set является частью языка ruby, но недоступен в глобальной области видимости в отличии от Hash или Array, поэтому его необходимо 'требовать' перед тем как использовать
require'set'str_set =Set.new# метод .add(element) добавляет элемент в setstr_set.add('Hello')str_set.add('World')str_set.add('Hello')# Хоть мы добавили 3 элемента, но так как один из них повторяется, то в сете у нас 2 элементаputs str_set.length # = 2
Сравнение Set vs Array
Хоть базовые алгоритмы мы изучим в дальнейшем, но сейчас важно понимать в чем приемущество Set по сравнению с Array
Рассмотрим такой метод как .include? который присутствует и у Array и у Set
# Метод добавления элементов позволяет нам избавиться от дублирования кодаdefadd_elements(structure)for x in1..10_000_000# хоть метод добавления у Array и Set отличаются# но обе структуры имеют метод <<, который является alias для метода push и add# Подробнее про такую конструкцию мы поговорим в разделе с полиморфизмом structure << xendendset =Set.newarr = []# сначала добавляем элементы в сет# подробнее про time мы поговорим в следующих уроках# пока не обращаем внимание, здесь он играет утилитарную роль для замера скоростиstart =Time.nowadd_elements(set)finish =Time.now# показывает время, затраченное на добавление элементов в секундах для сетаputs"Time taken to add items to Set (in seconds) - #{finish - start}"# теперь добавим такие же элементы в массивstart =Time.nowadd_elements(arr)finish =Time.now# показывает время, затраченное на добавление элементов в секундах для массиваputs"Time taken to add items to Array (in seconds) - #{finish - start}"start =Time.now# метод .include? возращает true если элемент с атким значением присутствует в структуреset.include?(9153452)finish =Time.now# показывает время, затраченное на проверку на наличие в секундах для сетаputs"Time taken to check for an item in Set (in seconds) - #{finish - start}"start =Time.now# точно такой же смысл работы как и у сетаarr.include?(9153452)finish =Time.now# показывает время, затраченное на проверку на наличие в секундах для массиваputs"Time taken to check for an item in Array (in seconds) - #{finish - start}"
Попробуйте запустить код у себя локально и сравнить время работы одних и тех же методов у разных структур.
Проверили ? Да, разница впечатляющая. Все дело в особенности работы этих структур. Метод .unclude? у Array обходит все свои элементы и проверяет на соотвествие (==). Сначала 1 элемент, потом 2, потом 3 и тд. Чем больше элементов, тем дольше может работать unclude?.
Семейство хэш структур одновременно знают все о своих ключах. Даже если увеличить размер структуры в десять раз или в сотню, скорость от этого не меняется. Это называется константное время, когда скорость доступа к элементу не меняется при изменении размера самой структуры. Так как Set это тот же самый Hash, но без значений, то правило и применимо для него.
Возможно у вас появилась мысль а зачем тогда испоьзовать массив если есть сет ? Всему свое место. Set - отлично, когда нам целенаправлено нужно использовать уникальность знчений. Если посмотреть на разницу во времени на добавление элементов, то заметим внушительный перевес по скорости у массива.
В дальнейших главах мы подробно изучим за счет чего такие структуры знают где искать свои ключи, почему для сета нужно гораздо больше времени н добавление, чем массиву, но пока нужно запомнить и держать в уме:
У массива доступ к элементу по значению прямо зависит от размера самого массива
У хэш таблицы и сета доступ по ключу не зависит от размера структуры, за счет чего действие происходит мгновенно
Задание key_vs_value
У Hash также имеются методы value?, который проверяет на наличие значения, и key?, который проверяет на наличие ключ.
Перепишите пример со сравнением скорости массива и сета на сравнение скорости метода value? и key?, переписав также метод добавления элементов, где ключ и значение это одно и тоже значение для хэш таблицы
Расскажите о выводах которые вы можете сделать касаемо этих методов, после изучения полученных результатов
Задание email_checker
Задание на умение работать сетом.
Напишите программу, в которой будет храниться перечень адресов электронной почты. Адреса можно добавлять через консоль командой ADD и печатать весь список командой LIST.
Программа должна проверять корректность вводимых email’ов (вспоминаем прошлый урок) и печатать сообщение об ошибке при необходимости.
Принцип работы команд
LIST — выводит список электронных адресов.
ADD — проверяет и, если формат адреса верный, добавляет в множество.
Примеры команд
LIST
ADD ruby_course@rambler.ru
Команды вводятся одной строкой пользователем в консоль.
Задание phone_book
Задание на умение работать с хэш таблицей.
Напишите программу, которая будет работать как телефонная книга:
Если пишем новое имя, программа просит ввести номер телефона и запоминает его. Если новый номер телефона — просит ввести имя и также запоминает.
Если вводим существующее имя или номер телефона, программа выводит всю информацию о контакте.
При вводе команды LIST программа печатает в консоль список всех абонентов в алфавитном порядке с номерами.
Определяйте имя и телефон с помощью регулярных выражений.
Подумайте, что выбрать в качестве ключа и значения для хэш таблицы, выберите лучший вариант по вашему мнению. Опишите, какие минусы и плюсы видите в вашем выборе.