Введение: сбор и обобщение знаний, связанных с проблемами открытого дизайна!

Открытый дизайн

Поиск пересечения двух файлов с номерами QQ

Задача: в файле A содержится 3 миллиарда номеров QQ, в файле B — 4 миллиарда. Требуется найти пересечение номеров QQ в файлах A и B, при этом объём памяти ограничен 1 ГБ.

Решение 1: прямое сравнение

Самый простой способ — это прямое сравнение: двойной цикл для сравнения. Очевидно, что количество сравнений будет равно: 3 млрд × 4 млрд, а сложность по времени слишком велика.

Решение 2: использование hashmap

Поместите 4 миллиарда номеров QQ из файла B в хеш-таблицу, затем просмотрите 3 миллиарда номеров QQ из файла B и определите, существует ли каждый номер в хеш-таблице.

Очевидно, следует использовать хеш-таблицы для оптимизации скорости поиска, чтобы значительно снизить сложность по времени, достаточно выполнить только один проход. Однако использование памяти всё ещё слишком велико, и 1 ГБ памяти не может вместить 4 миллиарда номеров.

Решение 3: разделение файлов

Поскольку память не может вмещать все данные, необходимо разделить файлы. Например, можно разделить файлы A и B на основе последней цифры номера QQ. Номера QQ с одинаковой последней цифрой могут быть только в файлах Aj и Bj. Необходимо сравнить только файлы Aj и Bj.

Разделив файлы таким образом, можно уменьшить их размер, сделав их более управляемыми. Следует отметить, что если использовать только последнюю цифру для разделения, то каждый маленький файл будет содержать примерно десятую часть данных исходного файла. Поэтому можно рассмотреть использование последних трёх цифр для разделения. В этом случае каждый маленький файл будет содержать около одной тысячной части данных исходного большого файла, или даже можно провести более детальное разделение. Используя определённые правила для разделения данных, можно распределить одинаковые данные из файлов A и B по соответствующим маленьким файлам, решая проблему с памятью.

Решение 4: использование bitmap

Можно оптимизировать хеш-таблицы, используя структуру данных bitmap. Это позволит одновременно решить проблемы со временем и пространством.

Один элемент данных типа unsigned char может обозначать наличие или отсутствие 8 целых чисел от 0 до 7. Аналогично:

• Один элемент данных типа unsigned int может обозначать наличие или отсутствие 32 целых чисел от 0 до 31.
• Два элемента данных типа unsigned int могут обозначать наличие или отсутствие 64 целых чисел от 0 до 63.
• Три элемента данных типа unsigned int могут обозначать наличие или отсутствие 128 целых чисел от 0 до 127.
• Четыре элемента данных типа unsigned int могут обозначать наличие или отсутствие 256 целых чисел от 0 до 255.
• ...
• 28 элементов данных типа unsigned int могут обозначать наличие или отсутствие всех 4 миллиардов целых чисел от 0 до 4 294 967 295.

Теоретический максимум для 10-значного номера QQ составляет 2^32 - 1 ≈ 4 миллиарда бит.

Использование памяти: 4 миллиарда бит ≈ 524 288 КБ ≈ 512 МБ

Таким образом, 512 МБ достаточно для обозначения наличия или отсутствия всех номеров QQ. Теоретический максимум номера QQ равен 2^32 - 1, что составляет примерно 4 миллиарда. Теперь задача становится проще:

Используйте массив размером 512 МБ типа unsigned int для записи наличия или отсутствия номеров QQ в файле B. Создайте bitmap. Затем просмотрите файл A и проверьте, есть ли номер QQ в bitmap. Если да, то этот номер QQ присутствует в обоих файлах.

https://mp.weixin.qq.com/s/Q_EvlN9LvkdA5M5EharBBA

Как удалить дубликаты из 40 миллиардов номеров QQ

В файле содержится 40 миллиардов номеров QQ. Разработайте алгоритм для удаления дубликатов из номеров QQ при ограничении памяти в 1 ГБ.

https://mp.weixin.qq.com/s/YlLYDzncB6tqbffrg__13w

Метод 1: сортировка

Метод 2: хеш-таблица

Метод 3: разделение файла

Метод 4: bitmap

Проектирование функции чтения/непрочтения сообщений в групповом чате

В корпоративных системах обмена мгновенными сообщениями, таких как корпоративные версии WeChat и DingTalk, групповые сообщения имеют функцию чтения/не прочтения. Когда отправитель отправляет сообщение, все участники группы находятся в состоянии непрочтения. По мере того как люди просматривают сообщение, статус меняется на «x человек прочитал, y человек не прочитал». Каждому сообщению соответствует уникальный messageid (uint64_t), а каждому пользователю — уникальный userid (uint64_t). Как сохранить информацию о прочтении/непрочтении сообщений?

Простой и грубый метод

Для каждого messageid сохраните текущие read_ids и unread_ids. Когда участник группы A просматривает сообщение, переместите userid участника A из unread_ids в read_ids. Клиент обновит список деталей сообщения, показывая m человек прочитали и n человек не прочитали.

Согласно текущему дизайну, для каждой детали сообщения требуется 8 байт на каждого члена группы. Для активной группы из 200 человек каждое новое сообщение потребует 1600 байт, а если в среднем отправляется 1 тысяча сообщений в день, то для каждого такого чата потребуется 1,6 МБ дискового пространства в день. Для клиента, особенно мобильного устройства, использование дискового пространства неприемлемо, и нельзя просто удалить рабочие сообщения. С точки зрения сервера, если групп очень много, стоимость хранения данных также будет значительной.

Использование bitmap

...