Опишу ситуацию
У меня есть файл, такого формата

Это начальное и конечное значение диапозона ip адресов стран... сама страна указана в третьем столбце.
Величина файла в строках: 85000
Я хочу использовать этот файл для определения страны, к которой принадлежит тот или иной сервер. Частота обращений к файлу заранее неизвестна

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

1) Хранение распарсеной информации в памяти
Подразумевается один раз открыть файл, распарсить и сложить куда - нибидь в список. Под списком подразумеваю либо std::vector или Qlist из библиотеки Qt или же самописный односвязный список. При необходимости можно пройтись по списку, тупо прямо и определить к какой стране относится адрес
Но: Если я распарсю всю инфу и сохраню в памяти, то это будет: (4 байта(начало диапазона) + 4 Байта(конец диапазона) + 2 байта) * 80000(строк) = много
Отсюда первый вопрос: хранить такое количество байтов в памяти для быстрого доступа обосновано?
И второй вопрос: справятся ли для этой цели стандартные контейнеры (list или vector)?

2) Можно постоянно считывать данные с файла на диске. Тупо открыть его в начале работы программы, а при необходимости обновления того или иного сервера, запускать просмотр строк файла
Вопрос 3: не будет ли это слишком долго? для приложения

3) Третий способ это отображения файла в адресное пространство процесса (mmap), в этом случае я выиграю с задержками, связанными с обращению к файловой системе. То есть висит в памяти файл, размером 2 мегабайта и происходит парсинг его с начала... хотя это не очень здорово наверное

В одном случае я выигрываю на парсинге, в другом в структурах в памяти
И так, это то, что мне пришло на ум, но может вы мне подскажите, что лучше, или предложите какую - нибудь свою идею?
Заранее благодарен за помощь

блин, запарился, пока отвечал

короче 800000 байт - это немного

Это сообщение отредактировал(а) Alek86 - 8.10.2009, 15:51

Почему 800000?
85000 диапазонов IP.
IP - это 4-хбайтовое число
Итого 680000 байт, примерно 550 кб
Сразу загнать в массив

Это сообщение отредактировал(а) Anikmar - 8.10.2009, 16:19

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

Я бы залил все в базу, но если базы нет - текстовый файл тоже база, в данном случае (csv) comma separated values, через ADO  

ну как, два числа на диапазон + два символа, которые позволяет сформировать файлик с флагом...
и того 4 + 4 + 2 = 10 байт (без упаковок) на одну структуру + 4 байта на один указатель = 16 * 85000 = 1 360 000 байт в памяти
здесь же речь о нижней и верхней границе

Добавлено через 2 минуты и 7 секунд
Void, а смысл упорядочивания? я же не знаю, как мне адрес попадется и среднее время поиска никак от сортировки не изменится

Смысл упорядочивания как уже написали - бинарный поиск.

эээ
я исходил из

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

«Дырки» могут быть, не весь адреса IPv4 (пока ещё) присвоены.

Хранить IP-диапазоны в таком виде — в некотором роде изврат, ибо CIDR. Проверять принадлежность проще по сети и маске подсети.

файл взят отсюда
http://ip-to-country.webhosting.info/downl...country.csv.zip

и обработан в шеле


Уж не знаю, подтвердится ли утверждение о неразрывности

Добавлено через 2 минуты и 45 секунд
вообще дырка в конце файла, на счет середины сложно так сказать

Даже если и по 10 байт на диапазон - загнать все в один массив отсортировать по началу диапазона и не парится.


Может я чего-то недопонимаю, но маски и подмаски - это уже внутрипротокольное дело. IP4 - это обычный стандартный long, маска там нужна для маршрутизации, но ни как для определения вхождения адреса в диапазон. Или существуют 2 одинаковых адреса IP но с разными масками, идинтифицирующие разные хосты?

Все диапазоны из вышеуказанного списка имеют форму xxx(N нулей) — xxx(N единиц). Nuff said.

Void, по подробнее можно, как ты предлагаешь искать принадлежность диапазону?

Добавлено через 1 минуту и 18 секунд
как ты предлагаешь отличить, например, вот эти два диапазона

очевидно по маске