Как гигантские сайты, такие как 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.
Это был сложный день, и завтра последний день первой недели. Я искренне молюсь о том, чтобы дожить до следующей недели, проектной недели. Андельцы в учебном лагере все умные, так что вам остается только скрестить пальцы и надеяться на лучшее.
Желаю всем товарищам по команде удачи.