Оригинал задачи здесь https://github.com/Ecwid/new-job/blob/master/IP-Addr-Counter.md
Основа:
Дан простой текстовый файл с IPv4 адресами. Одна строка – один адрес, примерно так:
145.67.23.4
8.34.5.23
89.54.3.124
89.54.3.124
3.45.71.5
...
Файл в размере не ограничен и может занимать десятки и сотни гигабайт.
Необходимо посчитать количество уникальных адресов в этом файле, затратив как можно меньше памяти и времени.
Насколько нам известно, IPv4 адрес имеет формат {0..255}.{0..255}.{0..255}.{0..255}, то есть имеет
256^4 возможных вариантов адресов, что эквивалентно 4294967296 уникальным адресам.
Наивное решение задачи не сработает, так как размер строки варьируется от 7 до 15 символов, что будет точно больше,
чем 40 байт памяти (содержимое объекта строки + ее полезные символы).
Имея минимум 40 байт для хранения одной строки, нижняя граница составляет
40 байт * 256^4 = 171798691840 байт = 160 гб, что довольно много.
Заметим, что столько же чисел имеет тип Int, 2^32 возможных вариантов, 2^31 из которых положительные
и остальные отрицательные.
Хорошим решением было бы держать информацию о "наличии" такого адреса, а не сам адрес в памяти, и здесь, в первом
приближении решения задачи, мог бы помочь массив типа boolean.
Памяти бы заняло 1 байт * 256^4 = 4294967296 байт = 4 гб, так как 1 элемент массива типа boolean занимает 1 байт.
Выделить массив типа boolean здесь нельзя ввиду того, что JVM не позволяет массивы размера больше,
чем 2^31 - 2.
Попытки выполнить код:
fun main() {
BooleanArray(Int.MAX_VALUE - 1)
}
// Exception in thread "main" java.lang.OutOfMemoryError: Requested array size exceeds VM limit
fun main() {
BooleanArray(Int.MAX_VALUE - 2)
}
// it worksВ таком случае я мог бы иметь 2 массива типа boolean, для положительных и отрицательных чисел, и немного места для
оставшихся нескольких чисел. Однако на 1 бит полезной информации хранить целый байт - расточительство.
Хотелось бы иметь 4294967296 бит, или 512 мб памяти.
После небольшого ресерча я останавливаюсь на BitSet'е. Утилизация памяти здесь компактнее за счет битовых сдвигов
и хранения информации в массиве типа long.
Ну и сравнение, конечно же, уже есть: https://www.baeldung.com/java-boolean-array-bitset-performance. По памяти BitSet лучше всего подходит для решения этой задачи, по времени интервал +- одинаков.
-
Для чтения файла я использую
BufferedReader, по грубым подсчетам он дает мне 1 млрд считанных строк в минуту на моем железе (MacBook Pro 2021 года). -
Каждый считанный IPv4 адрес преобразуется в число типа Int, для этого:
1. Считывается строка, работа происходит с байтами.
2. Каждый октет, представленный байтами, декодируется в одно число типа Int. На выходе 4 числа.
3. Каждый октет, представленный числом типа Int, переводится в двоичное представление, размер которого 8 бит.
4. 8-ми битные октеты последовательно конкатенируются в последовательность из 32 битов.
5. 32-х битовая последовательность переводится в число типа Int.
Все это дело происходит в классе Converter, который является thread-unsafe, в котором:
1. Для работы с переводом в битовое представление используются самописные функции на битовых сдвигах.
2. Для экономии памяти используются переиспользуемые самописные буферы (достаточно простые в реализации).
-
Каждое полученное положительное число кладется в positive BitSet, негативное в negative BitSet.
-
Итогом является сумма кардинальностей двух битсетов. Из 8 млрд прочитанных адресов 1млрд уникальных.
Итоговое решение представлено как CLI тул с помощью библиотеки clikt.
На выходе 2 возможных артефакта:
- Файл jar
- Собранный с помощью GraalVM и native-image бинарь (однако он работает медленнее, чем обычный jar, и исправить это я не могу, так как не имею ЕЕ версии и возможности поиграться с Profile-Guided Optimizations)
Остановился на jar файле.
./build.sh
java -jar uc.jar count -p path-to-file
Для более подробной информации:
java -jar uc.jar --help
java -jar uc.jar count --help