Ответ 1

Ну, похоже, что очень много данных, возможно, слишком дорогостоящих для хранения всех частот. Когда количество данных настолько велико, что мы не можем надеяться сохранить его все, мы вводим домен алгоритмов потока данных.

Полезная книга в этой области: Muthukrishnan - "Потоки данных: алгоритмы и приложения"

Близко связанная ссылка на проблему, которую я выбрал из вышеперечисленного: Манку, Мотвани - "Приблизительная частота отсчетов по потокам данных" [pdf]

Кстати, Мотвани, из Стэнфорда, (автор) был автором очень важной "Рандомизированные алгоритмы" . В 11-й главе этой книги рассматривается эта проблема. Изменить: Извините, плохая ссылка, эта глава посвящена другой проблеме. После проверки я вместо этого рекомендую раздел 5.1.2 книги Мутукришнана, доступный в Интернете.

Привет, хороший собеседование.

Ответ 2

Обзор оценки частоты

Существуют некоторые хорошо известные алгоритмы, которые могут предоставлять частотные оценки для такого потока с использованием фиксированного объема памяти. Один из них часто встречается Мисрой и Грисом (1982). Из списка n элементов он находит все элементы, которые встречаются больше, чем n/k раз, используя k - 1 счетчиков. Это обобщение алгоритма Байера и Мура (Fischer-Salzberg, 1982), где k равно 2. Алгоритмы Manku и Motwani LossyCounting (2002) и Metwally SpaceSaving (2005) имеют одинаковые требования к пространству, но могут предоставлять более точные оценки при определенных условия.

Важно помнить, что эти алгоритмы могут обеспечивать только частотные оценки. В частности, оценка Misra-Gries может подсчитать фактическую частоту по элементам (n/k).

Предположим, что у вас был алгоритм, который мог бы позитивно идентифицировать элемент, только если он встречается более чем в 50% случаев. Подайте этот алгоритм потоком из N отдельных элементов, а затем добавьте еще N - 1 копии одного элемента, x, в общей сложности 2N - 1 элементов. Если алгоритм говорит вам, что x превышает 50% от общего числа, он должен был быть в первом потоке; если это не так, x не был в исходном потоке. Чтобы алгоритм выполнил это определение, он должен сохранить исходный поток (или некоторое суммарное пропорциональное его длине)! Итак, мы можем доказать себе, что пространство, требуемое таким "точным" алгоритмом, будет & Omega; (N).

Вместо этого эти частотные алгоритмы, описанные здесь, дают оценку, идентифицирующую любой элемент, который превышает пороговое значение, наряду с некоторыми элементами, которые падают ниже его на определенный запас. Например, алгоритм большинства, используя один счетчик, всегда даст результат; если какой-либо элемент превышает 50% потока, он будет найден. Но он также может дать вам элемент, который встречается только один раз. Вы не узнаете, не сделав второй проход над данными (используя, опять же, один счетчик, но глядя только на этот элемент).

Частый алгоритм

Здесь простое описание частого алгоритма Мисры-Гриса. Demaine (2002) и другие оптимизировали алгоритм, но это дает вам суть.

Укажите пороговую долю, 1/k; любой элемент, который встречается более n/k раз, будет найден. Создайте пустую карту (например, красно-черное дерево); ключи будут поисковыми терминами, а значения будут счетчиком для этого термина.

• Посмотрите на каждый элемент в потоке.
• Если этот термин существует на карте, увеличьте соответствующий счетчик.
• В противном случае, если отображение меньше, чем k - 1, добавьте этот термин к карте с помощью счетчика.
• Однако если в карте есть k - 1 записи, уменьшите счетчик в каждой записи. Если какой-либо счетчик достигнет нуля во время этого процесса, удалите его с карты.

Обратите внимание, что вы можете обрабатывать бесконечное количество данных с фиксированным объемом памяти (только для карты фиксированного размера). Требуемый объем хранения зависит только от порога интереса, и размер потока не имеет значения.

Подсчет поиска

В этом контексте, возможно, вы буферизируете один час поиска и выполняете этот процесс по данным часа. Если вы можете пройти второй проход в этом часовом журнале поиска, вы можете получить точное количество вхождений лучших "кандидатов", идентифицированных в первый проход. Или, может быть, все в порядке, чтобы сделать один проход, и сообщить всем кандидатам, зная, что какой-либо предмет, который должен быть там включен, и любые дополнения - это просто шум, который исчезнет в следующий час.

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

Ответ 3

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

Вход

Вход представляет собой бесконечный поток английских слов или фраз (мы называем их tokens).

Выход

• Выведите верхние N токенов, которые мы видели далеко (из всех токенов у нас есть видел!)
• Выведите верхние N токенов в историческое окно, скажем, в последний день или на прошлой неделе.

Применение этого исследования - найти горячую тему или тенденции темы в Twitter или Facebook. У нас есть искатель, который сканирует на веб-сайте, который генерирует поток слов, который будет загружаться в систему. Затем система выводит слова или фразы с верхней частотой либо в общем, либо в историческом плане. Представьте себе, что за последние пару недель фраза "Кубок мира" появится много раз в Twitter. Так и "Павел осьминог".:)

Строка в целые числа

Система имеет целочисленный идентификатор для каждого слова. Хотя в Интернете есть почти бесконечные возможные слова, но после накопления большого набора слов возможность поиска новых слов становится все ниже и ниже. Мы уже нашли 4 миллиона разных слов и присвоили уникальный идентификатор для каждого. Весь этот набор данных может быть загружен в память как хэш-таблица, потребляющая примерно 300 МБ памяти. (Мы внедрили нашу собственную хеш-таблицу. Реализация Java требует огромных издержек памяти)

Каждая фраза может быть идентифицирована как массив целых чисел.

Это важно, потому что сортировка и сравнение целых чисел намного быстрее, чем на строках.

Архивные данные

Система хранит архивные данные для каждого токена. В основном это пары (Token, Frequency). Однако таблица, в которой хранятся данные, будет настолько огромной, что мы должны физически разбить таблицу. Как только схема разделов основана на ngrams токена. Если токен - это одно слово, оно равно 1грамме. Если токен представляет собой двусловную фразу, это 2грамма. И это продолжается. Примерно в 4грамме у нас есть 1 миллиард записей, таблица размером около 60 ГБ.

Обработка входящих потоков

Система будет поглощать входящие предложения до тех пор, пока память не будет полностью использована (Ya, нам нужен MemoryManager). После принятия N предложений и сохранения в памяти система приостанавливается и начинает подписывать каждое предложение на слова и фразы. Каждый токен (слово или фраза) подсчитывается.

Для очень частого токена они всегда хранятся в памяти. Для менее частых токенов они сортируются на основе идентификаторов (помните, что мы переводим String в массив целых чисел) и сериализуем в файл на диске.

(Тем не менее, для вашей проблемы, поскольку вы считаете только слова, тогда вы можете поместить всю картографическую карту только в память. Тщательно продуманная структура данных будет потреблять только 300 МБ памяти для 4 миллионов разных слов. ASCII char для представления строк), и это очень приемлемо.

Между тем, будет еще один процесс, который активируется, когда он найдет любой файл на диске, сгенерированный системой, а затем начнет его слияние. Так как файл диска сортируется, слияние будет происходить аналогичным процессом, таким как сортировка слияния. Некоторую конструкцию нужно позаботиться и здесь, так как мы хотим избежать слишком большого количества случайных попыток на диске. Идея состоит в том, чтобы одновременно избежать чтения (процесс слияния)/записи (выход системы) и позволить процессу слияния читать один диск при записи на другой диск. Это похоже на реализацию блокировки.

Конец дня

В конце дня система будет иметь много частых токенов с частотой, хранящейся в памяти, и многие другие менее частые токены, хранящиеся в нескольких дисковых файлах (и каждый файл сортируется).

Система очищает карту памяти в файл диска (сортирует ее). Теперь проблема заключается в объединении набора отсортированного файла диска. Используя аналогичный процесс, мы получим один отсортированный файл диска в конце.

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

   for each record in sorted disk file
        update archive database by increasing frequency
        if rowcount == 0 then put the record into a list
   end for

   for each record in the list of having rowcount == 0
        insert into archive database
   end for

Интуиция заключается в том, что после некоторого времени количество вставок станет меньше и меньше. Все больше и больше операций будет только на обновление. И это обновление не будет наказываться индексом.

Надеюсь, что это объяснение поможет.:)

Ответ 4

Вы можете использовать хеш-таблицу в сочетании с двоичный поиск дерево. Внесите словарь <search term, count>, в котором указывается, сколько раз искали каждый поисковый запрос.

Очевидно, что каждый час хеш-таблицы каждый раз, чтобы получить верхнюю 10, очень плох. Но это google, о котором мы говорим, поэтому вы можете предположить, что десятка будет получать, скажем, более 10 000 просмотров (это, вероятно, гораздо большее число). Поэтому каждый раз, когда количество поисковых запросов превышает 10 000, вставьте его в BST. Затем каждый час вам нужно только получить первые 10 из BST, которые должны содержать относительно немного записей.

Это решает проблему топ-10 за все время.

Действительно сложная часть связана с тем, что один термин занимает еще одно место в ежемесячном отчете (например, "переполнение стека" может иметь 50 000 обращений за последние два месяца, но только 10 000 в прошлом месяце, а "амазонка" - может иметь 40 000 в течение последних двух месяцев, но за последний месяц - 30 000. Вы хотите, чтобы "амазонка" приходила до "переполнения стека" в вашем ежемесячном отчете). Чтобы сделать это, я бы сохранил для всех основных (более 10 000 поисковых запросов в течение всего времени) 30-дневный список, который расскажет вам, сколько раз этот термин был найден в каждый день. Список будет работать как очередь FIFO: вы удаляете первый день и вставляете новый каждый день (или каждый час, но тогда вам может потребоваться хранить больше информации, что означает больше памяти/пространства. Если память не проблема, это, в противном случае, для этого "приближения", о котором они говорят).

Это похоже на хорошее начало. Затем вы можете беспокоиться об обрезке терминов, которые имеют > 10 000 обращений, но не так много за долгое время и тому подобное.

Ответ 5

case i)

Сохраняйте хэш-таблицу для всех поисковых запросов, а также отсортированный список из десяти, отделенный от хэш-таблицы. Всякий раз, когда выполняется поиск, увеличивайте соответствующий элемент в хеш-таблице и проверяйте, должен ли этот элемент теперь переключаться с 10-м элементом в списке из десяти.

O (1) поиск списка топ-десяти и max O (log (n)) вставки в хеш-таблицу (предполагая, что столкновение управляется самобалансирующимся двоичным деревом).

case ii) Вместо сохранения огромной хэш-таблицы и небольшого списка мы сохраняем хэш-таблицу и отсортированный список всех элементов. Всякий раз, когда выполняется поиск, этот термин увеличивается в хеш-таблице, а в отсортированном списке этот термин может быть проверен, чтобы проверить, следует ли ему переключаться с термином после него. Самобалансирующееся двоичное дерево могло бы хорошо работать для этого, так как нам также нужно будет быстро его запросить (подробнее об этом позже).

Кроме того, мы также сохраняем список "часов" в виде списка FIFO (очередь). Каждый элемент "hour" будет содержать список всех поисков, выполненных за этот конкретный час. Например, наш список часов может выглядеть так:

Time: 0 hours
      -Search Terms:
          -free stuff: 56
          -funny pics: 321
          -stackoverflow: 1234
Time: 1 hour
      -Search Terms:
          -ebay: 12
          -funny pics: 1
          -stackoverflow: 522
          -BP sucks: 92

Затем, каждый час: если в списке есть не менее 720 часов (количество часов в 30 дней), посмотрите на первый элемент в списке и для каждого условия поиска уменьшите этот элемент в хеш-таблице на соответствующую сумму. Затем удалите этот элемент из первого часа из списка.

Итак, скажем, мы на час 721, и мы готовы посмотреть первый час в нашем списке (выше). Мы уменьшили бы свободные вещи на 56 в хэш-таблице, смешные картинки на 321 и т.д., А затем удалили бы час 0 из списка, так как нам больше не понадобится смотреть на него снова.

Причина, по которой мы поддерживаем отсортированный список всех терминов, который позволяет выполнять быстрые запросы, заключается в том, что каждый час после того, как мы проходим поисковые запросы с 720 часов назад, нам необходимо обеспечить, чтобы список из десяти оставался отсортированным. Так как мы уменьшаем "бесплатный материал" на 56 в хэш-таблице, например, мы проверили бы, где он теперь принадлежит в списке. Поскольку это самобалансирующееся двоичное дерево, все это может быть выполнено хорошо в O (log (n)) времени.

Изменить: точность приземления...

Возможно, было бы полезно также реализовать большой список в первом, как и во втором. Затем мы могли применить следующую оптимизацию пространства в обоих случаях: Запустите задание cron, чтобы удалить все, кроме верхних элементов x в списке. Это снизит требования к пространству (и в результате ускорит выполнение запросов в списке). Конечно, это приведет к приблизительному результату, но это разрешено. x может быть рассчитан до развертывания приложения на основе доступной памяти и динамически изменен, если будет доступно больше памяти.

Ответ 6

Грубое мышление...

В первую десятку все время

• Использование хеш-коллекции, в которой хранится счет для каждого термина (дезинфекция терминов и т.д.).
• Сортированный массив, содержащий текущую вершину 10, член/счет в добавлении к этому массиву всякий раз, когда счетчик термина становится равным или больше наименьшего числа в массиве

Для ежемесячных топ-10 обновляется ежечасно:

• Использование массива, проиндексированного по количеству часов, прошедших с момента запуска по модулю 744 (количество часов в течение месяца), записи массива состоят из хэш-коллекции, в которой хранится счет для каждого термина, встречающегося в течение этого часового слота. Запись reset всякий раз, когда изменяется счетчик часовых интервалов.
• статистика в массиве, проиндексированном по часовому интервалу, должна собираться всякий раз, когда текущий счетчик часовых интервалов изменяется (максимум один час максимум), путем копирования и выравнивания содержимого этого массива, индексированного по часовым интервалам

Эрр... смысл? Я не думал об этом, как в реальной жизни

Ах да, забыл упомянуть, часовое "копирование/сглаживание", требуемое для ежемесячной статистики, может фактически повторно использовать тот же код, который используется для первых 10 всех времен, хороший побочный эффект.

Ответ 7

Точное решение

Во-первых, решение, которое гарантирует правильные результаты, но требует большой памяти (большая карта).

Вариант "Все время"

Поддерживать хэш-карту с запросами как ключами и их значениями в качестве значений. Кроме того, сохраните список f 10 наиболее часто встречающихся запросов и подсчет 10-го наиболее частого счета (порогового значения).

Постоянно обновлять карту по мере чтения потока запросов. Каждый раз, когда счетчик превышает текущий порог, сделайте следующее: удалите 10-й запрос из списка "Топ-10", замените его запросом, который вы только что обновили, и также обновите порог.

Вариант "Предыдущий месяц"

Сохраните тот же список "Top 10" и обновите его так же, как описано выше. Кроме того, сохраните аналогичную карту, но на этот раз векторы хранения 30 * 24 = 720 count (по одному на каждый час) в качестве значений. Каждый час для каждого ключа нужно сделать следующее: удалите самый старый счетчик из вектора, добавьте новый (инициализированный в 0) в конце. Удалите ключ из карты, если вектор равен нулю. Кроме того, каждый час вам нужно рассчитать список "Топ-10" с нуля.

Примечание. На этот раз мы сохраняем 720 целых чисел вместо одного, но есть гораздо меньше ключей (у варианта с полным временем есть очень длинный хвост).

Аппроксимация

Эти аппроксимации не гарантируют правильное решение, но менее трудоемки.

• Обработать каждый N-й запрос, пропуская остальные.
• (Только для всех временного варианта) Держите на карте не более пары ключей-ключей M (M должен быть таким большим, как вы можете себе позволить). Это своего рода кеш LRU: каждый раз, когда вы читаете запрос, который отсутствует на карте, удалите последний использованный запрос с счетчиком 1 и замените его обработанным в настоящее время запросом.

Ответ 8

Топ-10 поисковых запросов за последний месяц

Использование эффективной индексации данных/структуры данных, например плотно упакованные попытки (из записей в wikipedia try) приблизительно определяет некоторую связь между требованиями к памяти и n - количеством терминов.

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

Здесь также есть предположение, которое интерпретирует "последний месяц" как фиксированное окно. Но даже если месячное окно скользит, описанная выше процедура показывает принцип (скользящий может быть аппроксимирован фиксированными окнами заданного размера).

Это напоминает мне round-robin database, за исключением того, что некоторые статистические данные вычисляются на "все время" (в некотором смысле, что нет все данные сохраняются, rrd объединяет периоды времени без учета деталей путем усреднения, суммирования или выбора значений max/min, в заданной задаче теряемая деталь - это информация о низкочастотных элементах, которая может вводить ошибки).

Предположение 1

Если мы не сможем провести идеальную статистику за весь месяц, тогда мы сможем найти определенный период P, для которого мы должны иметь возможность держать отличную статистику. Например, предположим, что у нас есть отличная статистика за некоторый период времени P, который идет в месяц n раз. Отличная статистика определяет функцию f(search_term) -> search_term_occurance.

Если мы можем сохранить все n идеальные таблицы статистики в памяти, тогда скользящие месячные статистики можно рассчитать следующим образом:

• добавить статистику за последний период.
• удалить статистику за самый старый период (поэтому мы должны поддерживать n идеальные таблицы статистики)

Однако, если мы удерживаем только 10 лучших на агрегированном уровне (ежемесячно), мы сможем отбросить много данных из полной статистики фиксированного периода. Это дает уже рабочую процедуру, которая фиксировала (предполагая верхнюю границу по идеальной таблице статистики для периодов P).

Проблема с вышеописанной процедурой заключается в том, что если мы сохраняем информацию только по 10-ти терминам для скользящего окна (аналогично за все время), то статистика будет корректной для поисковых терминов, которые пика за период, но могут не видеть статистику по поисковым запросам, которые постоянно стекаются с течением времени.

Это может быть компенсировано сохранением информации на более чем 10 первых терминах, например, 100 лучших терминов, в надежде, что топ-10 будет правильным.

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

(При определении того, какие записи должны стать частью статистики, можно также отслеживать и отслеживать тенденции, например, если линейная экстраполяция появления в каждом периоде P для каждого термина говорит вам, что этот термин станет значительным в течение месяца или два, вы уже можете начать отслеживать его. Аналогичный принцип применяется для удаления поискового термина из отслеживаемого пула.)

Наихудший случай для вышеизложенного заключается в том, что у вас много почти одинаково частых терминов, и они все время меняются (например, если отслеживать только 100 терминов, то если более 150 терминов встречаются одинаково часто, но более 50 чаще в первый месяц, и чтобы не часто спустя некоторое время статистика не была сохранена правильно).

Также может быть и другой подход, который не фиксируется в размере памяти (строго говоря, ни один из них не указан), что бы определить минимальное значение с точки зрения событий/периода (день, месяц, год, все время), для которых чтобы сохранить статистику. Это может гарантировать максимальную ошибку в каждой статистике во время агрегации (см. Круглый робин).

Ответ 9

А как насчет адаптации "алгоритма замены часов" (также известный как "второй шанс" )? Я могу представить, что он работает очень хорошо, если запросы на поиск распределяются равномерно (это означает, что большинство искомых выражений появляются регулярно, а не 5 миллионов раз подряд, а затем никогда больше).

Здесь визуальное представление алгоритма:

Ответ 10

Сохраняйте количество поисковых запросов в гигантской хэш-таблице, где каждый новый поиск заставляет отдельный элемент увеличиваться на единицу. Следите за 20 или около того поисковых запросов; когда элемент в 11-м месте увеличивается, проверьте, нужно ли менять позиции с помощью # 10 * (вам не нужно сортировать 10 лучших, все, о чем вы заботитесь, составляет различие между 10-м и 11-м).

* _{Необходимо выполнить аналогичные проверки, чтобы увидеть, находится ли новый поисковый запрос на 11-м месте, поэтому этот алгоритм также сбрасывается на другие поисковые запросы - поэтому я немного упрощаю.}

Ответ 11

иногда лучший ответ - "Я не знаю".

Плохо сделай глубже. Моим первым инстинктом было бы подавать результаты в Q. Процесс будет постоянно обрабатывать элементы, входящие в Q. Процесс будет поддерживать карту

term → count

каждый раз, когда обрабатывается элемент Q, вы просто просматриваете поисковый запрос и увеличиваете счет.

В то же время я бы сохранил список ссылок на 10 лучших записей на карте.

Для записи, которая в настоящее время реализована, посмотрите, больше ли ее счетчик, чем счетчик самой маленькой записи в верхней части 10 (если не в списке уже). Если это так, замените наименьшее значение на запись.

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

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

Ответ 12

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

Алгоритм прост, но недостатком будет большее потребление памяти и времени.

Ответ 13

Как насчет использования Splay Tree с 10 узлами? Каждый раз, когда вы пытаетесь получить доступ к значению (поисковому термину), который не содержится в дереве, выкиньте любой лист, вставьте вместо него значение и получите доступ к нему.

Идея этого в том же, что и в моем другом ответе . В предположении, что поисковые термины доступны равномерно/регулярно, это решение должно работать очень хорошо.

изменить

Можно также сохранить еще несколько поисковых терминов в дереве (то же самое касается решения, которое я предлагаю в другом ответе), чтобы не удалять node, к которому можно получить доступ в ближайшее время. Чем больше значений хранится в нем, тем лучше результаты.

Ответ 14

Не знаю, понимаю ли я это правильно или нет. Мое решение использует кучу. Из-за 10 лучших элементов поиска я создаю кучу размером 10. Затем обновите эту кучу новым поиском. Если новая частота поиска больше вершины кучи (Max Heap), обновите ее. Отбросьте ту, с наименьшей частотой.

Но, как рассчитать частоту конкретного поиска будет засчитываться что-то еще. Может быть, как утверждают все, алгоритм потока данных....

Ответ 15

Используйте cm-эскиз для хранения количества всех поисков с начала, сохраните мини-кучу размера 10 с ним для 10 лучших. Для ежемесячного результата держите 30 см-эскиз/хеш-таблицу и мини-кучу с ней, каждый начинает отсчет и обновление с последних 30, 29.., 1 день. В качестве дневного прохода очистите последнее и используйте его как день 1. То же самое для почасового результата, держите 60 хеш-столов и мини-кучу и начинайте считать за последние 60, 59,... 1 минуту. В качестве минутного прохода очистите последнее и используйте его как минуту 1.

Результат Montly является точным в диапазоне 1 день, почасовой результат является точным в диапазоне 1 мин.

Ответ 16

Проблема не универсально разрешима, если у вас фиксированный объем памяти и "бесконечный" (думаю, очень большой) поток токенов.

Грубое объяснение...

Чтобы понять, почему, рассмотрите токен-поток, который имеет конкретный токен (т.е. слово) T, каждый N токенов во входном потоке.

Кроме того, предположим, что память может содержать ссылки (идентификатор слова и количество) до не более M токенов.

В этих условиях можно построить входной поток, где токен T никогда не будет обнаружен, если N достаточно большой, чтобы поток содержал разные M токены между T.

Это не зависит от деталей алгоритма top-N. Это зависит только от предела М.

Чтобы понять, почему это так, рассмотрим входящий поток, состоящий из двух одинаковых токенов:

T a1 a2 a3 ... a-M T b1 b2 b3 ... b-M ...

где a и b - все допустимые токены, не равные T.

Обратите внимание, что в этом потоке T появляется дважды для каждого a-i и b-i. Тем не менее, он редко бывает достаточно, чтобы очищаться от системы.

Начиная с пустой памяти, первый токен (T) займет слот в памяти (ограниченный M). Тогда a1 будет потреблять слот, вплоть до a- (M-1), когда M исчерпан.

Когда a-M приходит, алгоритм должен отбросить один символ, поэтому пусть это будет T. Следующий символ будет b-1, который приведет к покраске a-1 и т.д.

Итак, T не будет оставаться резидентной памятью достаточно долго, чтобы создать реальный счет. Короче говоря, любой алгоритм будет пропускать токен с достаточно низкой локальной частотой, но с высокой глобальной частотой (по длине потока).