Хэши, хэштеги, поросята в загоне: номенклатура вокруг # сильно злоупотреблялась — или, возможно, просто была переопределена — в эпоху твитов. Скромный octothorpe, возможно, превратился в знак фунта из-за грязного почерка; либра — да, известная астрология — была единицей веса из древности, описанной на английском языке как римский фунт и сокращенно lb., что было часто пишется как ℔. (полоса, соединяющая буквы, должна была прояснить их статус как единого целого). Неаккуратный курсив в том, что это такое, ℔. превратился в #, а поскольку единицы веса почти всегда встречаются вместе с цифрами, он также стал известен как знак числа¹.
Конечно, все это справедливо только в том случае, если вы находитесь в Северной Америке. Британцам и в голову не придет называть # либо знаком фунта — эта честь зарезервирована за £, — либо цифровым знаком — это карандаш № 2, большое спасибо. Эти парни из po(u)nd² предпочитают обращаться к # как к решетке (вероятно, искажение слова штриховка из-за появления символа из штриховок, например, сделанных в куске дерева ). В дикие, суматошные дни Твиттера не было удобного способа для простых пользователей платформы организовать твиты на основе их темы, пока какой-то парень по имени Крис Мессина, позаимствовав из лексикона интернет-релейного чата (IRC), рекомендуется ставить перед ключевыми словами символ #, чтобы упростить их поиск. Первоначально Twitter не хотел принимать его, но вскоре после того, как #sandiegofire загорелся на их платформе, превратившись в полезный инструмент для сбора информации из микроблогов, относящейся к внезапной вспышке лесных пожаров в восьмом по величине городе США, было добавлено несколько строк кода. и то, что стало так называемым хэштегом, было включено в основную технологию технологического гиганта — и с тех пор мир никогда не был прежним. Никогда еще так много постов не было помечено таким количеством хэшей.
Конечно, это все прекрасно и модно — знак фунта/знак цифры/решетка/октоторп, как мы все знаем, теперь часто (и неправильно, хотя и в просторечии) называют «хэштегом», синекдохой, которой он является (n' t) заменяется на имя индекса, которым он является (частью). Что бы ни. Так оно и есть: пусть спящие собаки врут (об их номенклатуре), и пойдем дальше. Этот автор придерживался такого менталитета в течение многих лет, пока одна судьбоносная лекция по разработке программного обеспечения о базах данных — на примере концепции твита в Twitter — не последовала за изучением структуры данных Ruby, известной как хеш.
В объектно-ориентированном примере, предложенном в лекции, твиты могут быть созданы как объекты из родительского класса Tweet, которые, в свою очередь, будут помещены в массив в указанном родительском классе; таким образом родитель мог не только генерировать дочерние элементы, но и отслеживать всех своих дочерних элементов. Если кто-то заинтересован в поиске определенного твита или набора твитов по одному или нескольким его атрибутам, например. один из его хэштегов, нужно просто перебрать массив твитов родительского класса Tweet (то есть его коллекцию дочерних элементов) и вернуть все твиты, содержащие интересующий хэштег.
Кажется достаточно простым — пока вы не сделаете несколько шагов назад и не вспомните, что мы говорим о Twitter, платформе с сотнями миллионов пользователей и сотнями миллиардов твитов в год. Перебор каждого твита, когда-либо созданного, только для того, чтобы найти те, которые помечены #coffee (забудьте на данный момент об исправлении злоупотреблений священным синтаксисом), занял бы целую вечность, а всего лишь горстки инквизиторов хэштегов было бы достаточно, чтобы обрушить серверы Twitter. Там должен быть лучший способ.
Количество времени, необходимое для слепого перебора набора неорганизованных данных в поисках конкретных интересующих данных, как это сделано в примере из лекции, упомянутой выше, масштабируется линейно с размером набора данных: если набор имеет n фрагментов данных, функции f(n) = time_of_comparison * n требуется некоторое время для завершения поиска. Эта временная шкала определяется в зависимости от «порядка n» или O(n), используя концепцию, известную в компьютерных науках как «большая нотация O»³.
Мы можем сделать несколько лучше, организовав данные в массиве твитов, например. расположить твиты в алфавитном порядке по их хэштегу. Чтобы найти интересующий нас твит, мы можем разделять и властвовать: сначала посмотрите на хэштег, который встречается в середине массива, и посмотрите, идет ли он до или после интересующего хэштега в алфавите. Если он идет после интересующего нас хэштега, мы можем отфильтровать всю вторую половину массива твитов из нашего поиска; если он приходит раньше, мы можем отфильтровать всю первую половину нашего массива твитов. Теперь, когда нам больше не нужно перебирать половину наших твитов, мы можем сосредоточиться на поиске нашего твита в оставшейся половине массива твитов — и, более того, мы можем снова и снова выполнять тот же набор шагов в этом подмножестве массива твитов. исходный массив (это то, что называется рекурсивным алгоритмом), начиная с хэштега твита в середине подмассива. С помощью этого процесса (известного как двоичный поиск) полоскания и повторения мы можем легко отделить зерна от плевел и намного быстрее сосредоточиться на нашем твите — получается, что O(log n) раз. (Не нужно много математических вычислений, чтобы понять, что, например, log 1000 = 3 ‹‹ 1000, т. е. для произвольного набора данных из 1000 точек данных двоичный поиск займет примерно 0,3% времени простого поиска. итерация).
Теперь я знаю, о чем вы думаете: благодаря гениальности мы резко сократили время поиска! Давайте похлопаем себя по спине и на этом закончим. Заманчиво, но что, если бы этот автор сказал вам, что есть способ найти интересующий вас твит по его хэштегу за время O(1)? Да, вы правильно поняли: есть способ избавиться от всей этой чепухи и почти сразу же найти нужный твит, независимо от того, насколько велик массив твитов. Как это вообще возможно, спросите вы? Заимствуя из широкого мира компьютерных наук, этот автор представляет вам: хеш-карту.
Простите меня за свободную ассоциацию, но вышеупомянутый тип хеш-данных в Ruby использует терминологию, аналогичную хэштегам, и (несколько неточная) интуиция привела автора к тому, чтобы связать их через концепцию хеш-карт. Хотя Twitter не обязательно использует хеш-карты как таковые, он, вероятно, использует что-то или что-то, связанное с концепцией указанной структуры данных, в своих алгоритмах для индексации входящих твитов по хэштегу (и, вероятно, другим атрибутам). ) для быстрого поиска⁴. Запуская функцию над поисковым термином, который последовательно указывает на связанное с ним значение в памяти каждый раз, когда он запускается для того же самого поискового запроса, мы сокращаем время поиска до бесконечно малой длины по сравнению с теми, которые задействованы в итерации.
Хорошо, круто, но как работает такая функция хеширования? Как можно воспроизводимо и надежно преобразовать ключ в координаты в памяти связанного с ним значения? Это не должно быть сложно. Простой глупый алгоритм, который принимает ключ в формате строки строчных букв латинского алфавита, мог бы просто присвоить числовое значение каждой букве алфавита, суммировать значения букв в строке и разделить результат на целое число пробелов, доступных в памяти, с использованием остатка от этого деления в качестве адреса хранения значения. Например, предположим, что мы просто считаем, начиная с 1, так что a = 1, b = 2, c =3…y = 25 и z = 26. Скажем, у нас есть 64 блока памяти, в которых можно хранить данные, связанные с любым заданным ключом. Скажем, в данном случае нашим ключом является слово «собака» (вы можете представить, что оно происходит, например, от #собака). Запустив его с помощью нашего простого алгоритма, d = 4, o = 15 и g = 7, чтобы мы сохранили связанные значения собаки ( это может быть, например, твит с сообщением⁵ «это лицо мопса, хотя #собака») в (4 + 15 + 7) % 64 = 26-м блоке памяти. Здорово. Если бы нам дали другое значение с ключом «трубкозуб», мы бы сохранили связанные с ним значения (например, твит с сообщением⁶ «подождите, это тапир разновидность #трубкозуб, потому что я даже не знаю») в ( 1 + 1 + 18 + 4 + 22 + 1 + 18 + 11) % 64 = 12-й блок памяти. Вы поняли идею. Мы могли бы продолжать в том же духе⁷, пока не заполним все 64 блока памяти значениями, которые мы отобразили туда из нашего впечатляющего набора ключей. Прекрасный.
Просто чтобы по-настоящему продемонстрировать жестокую эффективность хеш-карт, давайте попробуем найти наш драгоценный, например. Твит #aardvark в нашем массиве твитов с помощью простой итерации. Хорошо, круто, давайте:
- Проверьте твит по номеру блока памяти. 1 (или это был №1?). Нет.
- Проверьте твит по номеру блока памяти. 2. Нет.
- Проверьте твит по номеру блока памяти. 3. Где ты ааааа?!
- Проверьте твит по номеру блока памяти. 4. Серьезно? Здесь тоже нет.
- Проверьте твит по номеру блока памяти. 5. Нам действительно нужно продолжать поиски?
Ладно, ладно, я не заставлю тебя продолжать, пока ты не достигнешь 12-го блока памяти. (Я также не заставлю вас искать #dog таким образом: это было бы просто жестоко.) Я даже буду так мил, что позволю вам использовать нашу функцию хеширования, чтобы вернуться и найти наш твит #aardvark:
- Запустите хэш-функцию на «муравьед» =› 12. Бум, нашел.
Так как это было так просто, давайте попробуем это в нашем твите #dog, пока мы это делаем:
- Запустите хеш-функцию для «собаки» =› 26. Ого, снова прелесть в первый раз!
Как насчет того твита #cat, о котором я даже не рассказывал вам до сих пор?
- Запустите хэш-функцию для «кошки» =› 24.Этот алгоритм — кошачье мяу!
Итак, у вас есть это: мы разобрали хеширование, хэши и хэштеги — все они технически разные, но слабо связанные. Прежде чем делать поспешные выводы, не предполагайте никаких ассоциаций, которых не вызвал бы этот автор; используйте хеш-карты надлежащим образом, и ваша жизнь как программиста будет #благословлена.
Информатика вышла.
¹знак цифры обычно используется перед рассматриваемыми цифрами: например, карандаш №2; тогда как знак фунта обычно используется после соответствующих цифр.
«Да, этот автор — американец — еще хуже, житель Нью-Йорка — со склонностью к чрезмерной и/или вызывающей стон игре слов.
³Заглавная буква O часто небрежно используется для обозначения алгоритмической эффективности, но, точнее, она относится к верхней границе времени выполнения (алгоритма). (лениво) взаимозаменяемо с Θ, который одновременно относится к верхней и нижней границам времени выполнения. Для дальнейшего обсуждения см. эту тему на многолетнем друге программистов, Stack Overflow.
⁴Учитывая, что поисковый гигант Google занимается индексированием всего, что может, во всей сети, помещая большую часть человеческих знаний в несколько нажатий клавиш, мы (и корпоративная Америка) в долгу перед скромной хеш-картой (идеей, стоящей за ней). . (На самом деле Google, скорее всего, хочет иметь возможность решать, где хранить все веб-страницы мира на основе хэшируемых условий поиска; вместо этого ему приходится постоянно сканировать сеть. , анализировать веб-страницы, разбросанные волей-неволей, и связывать их с условиями поиска для последующего поиска пользователем в вышеупомянутом процессе, известном как индексирование.)
⁵ Ключ не обязательно должен быть включен в связанное с ним значение; из-за характера сообщений в твиттере это просто случайность в этом гипотетическом примере. (Автор клянется, что не пытается вас запутать.)
⁶Нет — даже близко. Несмотря на то, что оба являются странными животными с забавными носами, свободные ассоциации отвратительны и могут привести к ложным ассоциациям.
⁷ Скорее всего, это не будет абсолютно гладко — наш алгоритм может дать сбой, когда наша хеш-функция неизбежно попытается сохранить значения из разных ключей, которые сопоставляются с одной и той же точкой памяти в этой точке памяти. Это называется коллизией, но не волнуйтесь, есть способы решить эту проблему (возможно, за пределами темы этого поста, но никогда не выходит за рамки, да, переполнения стека). FWIW, как правило, хорошая хэш-функция должна приводить к случайному распределению сопоставленных точек и должна возвращать очень разные сопоставления даже для очень похожих ключей (например, значения для собака и собаки не должны быть рядом друг с другом. ). Наш примитивный пример хеш-функции, с другой стороны, отображает одно и то же место для анаграмм (например, собака и бог). Упс.
