Как гигантские сайты, такие как Twitter, всего за несколько секунд проверяют, доступно или занято имя пользователя? — Пища для размышлений

В базе данных Twitter 328 миллионов активных пользователей в месяц. Это означает более 328 миллионов записей пользователей, каждая из которых имеет уникальное имя пользователя. Ну, как Twitter так быстро проверяет, существует ли имя пользователя в их базе данных?

Ответ? Бинарный поиск.

Прежде всего, Twitter хранит все имена пользователей в отсортированном алфавитном списке, например a, aab, aamu, baaa, baobab, cali, candy, …. ххх, ю, зш. Похоже на слова в словаре.

Теперь, что происходит, когда вы вводите новое имя пользователя?

Twitter присвоит ему переменную, скажем, просто username , затем сверит ее с именем пользователя в строке middle списка и, если это то же имя, отклонит его. . Но вероятность того, что это так, меньше 0,1 - в зависимости от количества записей. Таким образом, вероятность совпадения в этом первом сравнении меньше. Но если это произойдет, вы получите сообщение "имя ​​пользователя уже занято" .

Чтобы продолжить, если имена пользователей не совпадают, система Twitter проверит, находится ли ваше новое имя пользователя в алфавитном порядке до или после среднего имени пользователя.

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

Мне нужно было убедиться, что я понял это, чтобы завершить сегодняшнюю лабораторию бинарного поиска в Анделе. Проблема была особенно сложной в том, что вы пишете класс BinarySearch, который наследуется от списка. Но при вызове класса тесты вместо этого передают два целых числа, а не список: a, который представляет собой длину списка, и b, который определяет шаг или разницу между одним значением списка и другим — то есть, если список равен [1,2,3,4], тогда bбудет 1 . Таким образом, мы должны манипулировать переданными значениями и заполнять класс сгенерированными данными.

Что-то типа:

for i in range(1, a+1):            
    self.append(i * b)   # b is the step value

Внимательно посмотрите на self.append() , он передает нашему классу (своему родителю) данные из списков. На самом деле, чтобы справиться с этой задачей, вам просто нужно хорошее понимание self .

Если вы хотите узнать больше, вот мой репозиторий Github.

Это был сложный день, и завтра последний день первой недели. Я искренне молюсь о том, чтобы дожить до следующей недели, проектной недели. Андельцы в учебном лагере все умные, так что вам остается только скрестить пальцы и надеяться на лучшее.

Желаю всем товарищам по команде удачи.