Коротко — сначала варианты реализации, затем конкретная тестовая стратегия и набор тестов/метрик.
1) Возможные реализации (для выбора и тестирования)
- Точный подсчёт:
- Разбиение по хэшу (external hashing/partitioning): файл разбивается на $k$ бакетов по $h(line)\mathrm{mod}k$; каждый бакет помещается в память и в нём считается множество, затем суммируются уникальные.
- Внешняя сортировка: отсортировать строки внешним алгоритмом (sort + merge), пройти и посчитать границы групп.
- Приближённый подсчёт (меньше памяти, допускает ошибку):
- HyperLogLog (HLL) — даёт оценку числа уникальных с относительной ошибкой ~$\frac{1.04}{\sqrt{m}}$ при $m$ регистрах.
- Bloom/quotient-filter для дедупликации + внешнее хранение (если нужен булев «видел/не видел»).
2) Ключевые критерии тестирования
- Корректность (точность/ошибка).
- Устойчивость к ограничениям памяти и диска (максимальная пиковая память, диск).
- Проходимость для очень больших файлов (время, I/O).
- Поведение при краевых данных (пустые строки, очень длинные строки, разные кодировки, бинарный контент).
- Устойчивость к неблагоприятному распределению хэша (skew).
- Параллелизм/синхронизация и отказоустойчивость (обрыв, переполнение диска).
3) Формула для выбора числа бакетов при partitioning
Если всего строк $N$, средняя длина строки $s$ (байт), доступная оперативная память $M$ (байт), то нужно выбрать $k$ такое, что ожидаемый размер одного бакета $\approx \frac{N\cdot s}{k}\le M$, т.е.
$$k\ge \frac{N\cdot s}{M}.$$
4) Набор тестов (ранжировать от простых к нагрузочным)
A — функциональные / корректность
- Пустой файл — ожидаемый результат $0$.
- Один символ/одна строка — ожидаемый $1$.
- Все строки одинаковы (файл длины $L$, все одинаковые) — ожидаемый $1$.
- Все строки уникальны (файл из $n$ уникальных строк, например $n=10^3$ или $10^6$) — ожидаемый $n$.
- Смешанные дубли: заранее сгенерировать файл с известной долей уникальных, например $N=10^6$, уникальных $U=10^5$. Сравнить с эталоном (см. ниже).
- Краевые строки: пустые строки, пробелы, табы, разные окончания строк ($\backslash n$, $\backslash r\backslash n$), строки с нулевыми байтами и не-UTF8.
B — стабильность/границы
- Очень длинная строка длиной $>M$ (например $\text{len}=10\text{MB}$) — убедиться, что стриминг/буферизация работает.
- Количество уникальных > $2^{31}$ (испытание типа переполнения счётчика); проверка использования 64‑битного счётчика — проверять на значениях близких к $2^{63}-1$ при моделировании.
C — нагрузочные / производительность
- Файлы больших размеров: $1\text{GB},10\text{GB},100\text{GB}$ (или «несколько гигабайт» — например $5\text{GB}$). Проверять:
- Время исполнения.
- Пиковая память (использовать профайлер / OS tools).
- Дисковое использование (для partitioning / spill files).
- Тесты с ограниченной памятью: запускать с ограничением памяти $M$ (например $M=100\text{MB}$, $M=500\text{MB}$) и проверять, что алгоритм корректно «спиллит» на диск и не выходит за лимит.
D — устойчивость к неблагоприятному хеш‑распределению
- Сгенерировать данные так, чтобы хэш большинства строк попадал в один бакет (адверсариальный набор) и проверить, что алгоритм обнаружит переполнение/склон к деградации и обработает (уведомление/увеличение $k$ / fallback на внешнюю сортировку).
E — тесты для приближённых алгоритмов (HyperLogLog)
- Проверять среднюю относительную ошибку на наборе входов: запустить $t$ раз (с разными seed'ами), посчитать среднюю относительную ошибку $\frac{|estimate-true|}{true}$ и сравнить с теоретическим пределом $\approx \frac{1.04}{\sqrt{m}}$.
- Тест на малые $U$ (где HLL может иметь большую погрешность) и на большие $U$.
F — отказоустойчивость / негативные сценарии
- Прерывание выполнения (SIGTERM) — есть ли корректная очистка/частичный результат/чекпоинт.
- Заполнение диска при записи бакетов → корректные ошибки и откат.
- Повреждённые входные блоки / неполные строки.
5) Как валидировать корректность для больших файлов (эталон)
- Для малых/средних файлов: использовать in-memory эталон (set) или системный sort + uniq, сравнивать точные числа.
- Для больших файлов, где эталон тяжёл: проверить на подвыборках (стримовый сэмплинг с известной статистикой) либо сравнить результат двух независимых алгоритмов (например partitioning vs external sort) на тех же данных; для приближённых методов оценивать доверительный интервал и относительную ошибку.
6) Тестовые данные — как генерировать
- Генератор с параметрами: $N$ (число строк), распределение длин (константное, экспоненциальное), дублирование (dup ratio), алфавит (ASCII, UTF‑8, бинар).
- Семена для воспроизводимости.
- Наборы: «малые» $N=10^3$, «средние» $N=10^6$, «большие» $N\sim 10^8$ (в зависимости от среды).
7) Метрики и пороги
- Пиковая RAM $\le M_{allowed}$.
- Время обработки на файл $F$ — установить SLA (например $T(F)$ не более допустимого).
- Точность для приближённых: средняя относительная ошибка $\le$ заданного порога (например $\le 1\%$ при выбранных $m$).
- Диск временных файлов — логирование и лимиты.
8) Автоматизация тестов
- Пайплайн: unit → интеграционные → нагрузочные.
- Использовать контейнеры с лимитами памяти для воспроизведения ограничений.
- Автоматизированные проверки пикового потребления памяти и I/O (perf, /usr/bin/time, cgroups, valgrind massif, Linux perf).
Короткие контрольные примеры (для ручной проверки):
- пусто → $0$ - одна строка → $1$ - файл из $10^6$ строк, уникальных ровно $10^5$ (генератор) → проверка совпадения.
Итог: тестовая стратегия должна покрывать функциональность (корректность), поведение при ограниченной памяти (partitioning/fallback), производительность и статистику ошибок (для HLL). Для каждой реализации подготовить набор воспроизводимых генераторов данных, метрик (RAM/IO/время) и сценариев отказа.