Вопрос на собеседовании: Оптимизация затрат на чтение с диска

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

Дан непрерывный поток слов, словарь на диске и стоимость чтения с диска, создайте потоковый процессор, который возвращает true, когда слово существует в словаре, при этом минимизируя затраты на чтение с диска. Пример:

Словарь: {Собака, Кошка, Птица, Лев, ...}
Входные данные: [Собака, Кошка, Агхд, ...]
Выходные данные: [True, True, False, ...]

Выходные данные true, true, false, потому что “собака” и “кошка” существуют в словаре слов, а “Агхд” не считается словом.

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

Уровень 1: Мемоизация Мемоизация - один из самых частых ответов, и во многих случаях люди предлагают LRU-кэш как способ реализации мемоизации. Есть несколько вещей, которые могут помочь кандидату выделиться:

  1. вместо реализации LRU-кэша, который прост, но досадно многословен из-за множества краевых случаев при полной реализации, включая связные списки, кандидат может просто предложить использовать стандартные библиотеки, например, в Python есть встроенный LRU-кэш в виде декоратора.
  2. предложить использовать политику вытеснения кэша с случайным выбором или p2c, поскольку они имеют довольно близкую производительность в реальных приложениях. См.: сравнение политик вытеснения кэша

Уровень 2: Потоковая обработка Несмотря на то, что это упоминается в задаче, люди часто игнорируют потоковую обработку. Я спрашивал нескольких кандидатов, как бы они реализовали концепцию потоков и ленивых вычислений на своем языке, и часто кандидаты не могли ответить.

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

Уровень 3: Оптимизация хранения данных Словарь может храниться множеством различных способов, некоторые из которых более удобны для поиска на диске. Варианты, которые может исследовать кандидат, довольно широки:

  1. отсортированный файл;
  2. префиксное дерево (трайе) на диске, оптимизированное для быстрого поиска;
  3. локальная база данных, такая как sqlite3, которая может работать внутри приложения или как сайдкар;
  4. что-то еще, например, построение трайе путем создания миллионов папок и подпапок. Кандидат редко рассматривает что-либо, кроме первого варианта, если вообще рассматривает.

Уровень 4: Дисковый кэш и отображение памяти Существуют структуры данных, иногда из более ранней эпохи компьютеров, оптимизированные для более эффективного использования дискового кэша.

Эти структуры могут требовать определенного профиля распределения запросов, чтобы работать. Но когда это работает, дисковый кэш может полностью заменить manually implemented регулярный кэш.

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

Уровень 5: Оспаривание условий задачи В некоторых случаях вопросы с ответами “да/нет” могут иметь более свободные ограничения. Например, может быть допустимо иметь ложноположительные ответы, но ложноотрицательные могут быть совершенно неприемлемыми. В этом случае можно использовать фильтры Блума.

Например, мы знаем, что скажем 50% запросов дадут False. В этом случае мы можем использовать фильтр Блума, чтобы отсеять эти очевидные отрицательные результаты. А затем использовать LRU-кэш для остального трафика, что сделает кэш в 2 раза эффективнее.

Другой способ использования фильтров Блума для кэширования: https://en.wikipedia.org/wiki/Bloom_filter#Cache_filtering - вся страница крайне интересна для чтения.