Page 53 - Bkhargava_-_Grokaem_algoritmy

52 Глава 2. Сортировка выбором

Какую структуру данных вы бы использовали для реализации этой
очереди: массив или связанный список? (Подсказка: связанные списки
хорошо подходят для вставки/удаления, а массивы - для произволь­
ного доступа к элементам. Что из этого понадобится в данном случае?)

2.3 Проведем мысленный эксперимент. Допустим, Facebook хранит
список имен пользователей. Когда кто-то пытается зайти на сайт
Facebook, система пытается найти имя пользователя. Если имя входит
в список имен зарегистрированных пользователей, то вход разреша­
ется. Пользователи приходят на Facebook достаточно часто, поэтому
поиск по списку имен пользователей будет выполняться часто. Будем
считать, что Facebook использует бинарный поиск для поиска в спи­
ске. Бинарному поиску необходим произвольный доступ - алгоритм
должен мгновенно обратиться к среднему элементу текущей части
списка. Зная это обстоятельство, как бы вы реализовали список поль­
зователей: в виде массива или в виде связанного списка?
2.4 Пользователи также довольно часто создают новые учетные записи на
Facebook. Предположим, вы решили использовать массив для хране­
ния списка пользователей. Какими недостатками обладает массив для
выполнения вставки? Допустим, вы используете бинарный поиск для
нахождения учетных данных. Что произойдет при добавлении новых
пользователей в массив?
2.5 В действительности Facebook не использует ни массив, ни связанный
список для хранения информации о пользователях. Рассмотрим ги­
бридную структуру данных: массив связанных списков. Имеется мас­
сив из 26 элементов. Каждый элемент содержит ссылку на связанный
список. Например, первый элемент массива указывает на связанный
список всех имен пользователей, начинающихся на букву «А». Второй
элемент указывает на связанный список всех имен пользователей, на­
чинающихся на букву «В», и т. д.

} _ '\. С6язанн111ii сrшсок со 6семц цменамц
_ __..\ _:з-r_ "" ~ мл1>зо6аw.tлей на бук8у «А»

~
МАСС.И&
www.trk.kg