Форум программистов, компьютерный форум CyberForum.ru

Быстрый поиск ip адреса в текстовом файле - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
03.07.2012, 20:59     Быстрый поиск ip адреса в текстовом файле #1
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300 000.

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

Посмотрел в сторону этих алгоритмов - http://algolist.manual.ru/search/esearch/

Но не знаю как использовать их в моем случае, т.к. в них используется обращение к "конкретному элементу", а в С++ к произвольной строке обратиться нельзя.

Посоветуйте что-нибудь. Заранее спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2012, 20:59     Быстрый поиск ip адреса в текстовом файле
Посмотрите здесь:

C++ Бинарный поиск в текстовом файле
C++ Поиск в текстовом файле
Поиск слова в текстовом файле C++
C++ поиск в текстовом файле
C++ не работает поиск в текстовом файле
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
03.07.2012, 21:08     Быстрый поиск ip адреса в текстовом файле #2
Цитата Сообщение от post_hack Посмотреть сообщение
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300 000.

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

Посмотрел в сторону этих алгоритмов - http://algolist.manual.ru/search/esearch/

Но не знаю как использовать их в моем случае, т.к. в них используется обращение к "конкретному элементу", а в С++ к произвольной строке обратиться нельзя.

Посоветуйте что-нибудь. Заранее спасибо.
Каким-то образом ip идут? Порядок есть?
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
03.07.2012, 21:12  [ТС]     Быстрый поиск ip адреса в текстовом файле #3
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
Каким-то образом ip идут? Порядок есть?
да, они упорядочены. текстовый файл - это собственно таблица маршрутизации.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
03.07.2012, 21:17     Быстрый поиск ip адреса в текстовом файле #4
Может чем-то вроде бинарного/тернарного поиска?
То есть будем смотреть значения каждой части - они же точками делятся,верно?

Добавлено через 2 минуты
В любом случае, вам нужно будет считывать строку и проверять первые цифры ip-шника, чтобы понимать куда двигаться дальше
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
03.07.2012, 21:18  [ТС]     Быстрый поиск ip адреса в текстовом файле #5
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
Может чем-то вроде бинарного/тернарного поиска?
То есть будем смотреть значения каждой части - они же точками делятся,верно?
да, я хотел попробовать сделать бинарный поиск.
Но:
во-первых, общее количество записей не известно.
во-вторых, как я обращусь к строчке в середине файла?
в-третьих, как обратиться к первым цифрам конкретной строки я тоже не знаю.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
03.07.2012, 21:19     Быстрый поиск ip адреса в текстовом файле #6
Цитата Сообщение от post_hack Посмотреть сообщение
да, они упорядочены. текстовый файл - это собственно таблица маршрутизации.
А памяти много выделяется?

Добавлено через 1 минуту
Цитата Сообщение от post_hack Посмотреть сообщение
да, я хотел попробовать сделать бинарный поиск.
Но:
во-первых, общее количество записей не известно.
во-вторых, как я обращусь к строчке в середине файла?
в-третьих, как обратиться к первым цифрам конкретной строки я тоже не знаю.
Допустимо весь файл прочесать?

Скажите, а сколько времени для этой функции уделяется?
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
03.07.2012, 21:20  [ТС]     Быстрый поиск ip адреса в текстовом файле #7
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
А памяти много выделяется?

Добавлено через 1 минуту


Допустимо весь файл прочесать?
Ограничения по памяти нет. Главная задача - оптимизация времени поиска.

Допустимо весь файл прочесать?
для чего? если для поиска нужного IP - то это не оптимально. Т.к. и IP будет несколько, и каждый раз прочесывать эти 300 000 строк - не оптимально. Если 1 раз для того, чтобы узнать сколько всего строк, то думаю можно. Но как это поможет?

Скажите, а сколько времени для этой функции уделяется?
Для функции поиска? Какой то конкретной цифры нет. Но вариант проходить все каждый раз от начала до конца не подходит.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
03.07.2012, 21:23     Быстрый поиск ip адреса в текстовом файле #8
Цитата Сообщение от post_hack Посмотреть сообщение
Ограничения по памяти нет. Главная задача - оптимизация времени поиска.
Айпишники ведь в самом начале каждой строки?

Добавлено через 47 секунд
Цитата Сообщение от post_hack Посмотреть сообщение
Ограничения по памяти нет. Главная задача - оптимизация времени поиска.



для чего? если для поиска нужного IP - то это не оптимально. Т.к. и IP будет несколько, и каждый раз прочесывать эти 300 000 строк - не оптимально. Если 1 раз для того, чтобы узнать сколько всего строк, то думаю можно. Но как это поможет?
Да-да, конечно, один раз

А вы можете все айпишники же в хеш-таблицу записать?
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
03.07.2012, 21:25  [ТС]     Быстрый поиск ip адреса в текстовом файле #9
Цитата Сообщение от RaiaNKnight Посмотреть сообщение
Айпишники ведь в самом начале каждой строки?
Да. Строчки например такого вида:

192.168.1.0 255.255.255.0 10.20.30.1
192.168.1.3 255.255.255.0 10.20.30.55
185.215.1.0 255.255.255.0 10.20.30.51
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
03.07.2012, 21:29     Быстрый поиск ip адреса в текстовом файле #10
Весь файл в начале все равно нужно пробежать для того, чтобы построить систему для поиска в дальнейшем. Ведь необходимо как-то иметь доступ прямой к ip

Добавлено через 1 минуту
Цитата Сообщение от post_hack Посмотреть сообщение
Да. Строчки например такого вида:
Добавлено через 58 секунд
У меня идея. Скиньте ваш скайп, кажется знаю, какой алгоритм. В личку
Avazart
 Аватар для Avazart
6893 / 5133 / 250
Регистрация: 10.12.2010
Сообщений: 22,560
Записей в блоге: 17
03.07.2012, 22:56     Быстрый поиск ip адреса в текстовом файле #11
а в С++ к произвольной строке обратиться нельзя.
Если файл всего лишь один и весит не много, то почему бы его не грузить в начале работы в память?
А там обращайся к нему как хочиш...
Запихнуть все можно в multimap ну можно конечно еще хеш...
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
07.07.2012, 16:05  [ТС]     Быстрый поиск ip адреса в текстовом файле #12
Такой вопрос возник.. Как мне строку вида "192.168.0.1" преобразовать в u_long число?
Чтобы можно было корректно выполнить операцию &
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
07.07.2012, 16:17     Быстрый поиск ip адреса в текстовом файле #13
Цитата Сообщение от post_hack Посмотреть сообщение
Такой вопрос возник.. Как мне строку вида "192.168.0.1" преобразовать в u_long число?
Чтобы можно было корректно выполнить операцию &
post_hack, насколько знаю это делается по следующей формуле, если адрес имеет такой "a.b.c.d" вод то переводим так
C++
1
((a*256+b)*256+c)*256+d
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2012, 18:05     Быстрый поиск ip адреса в текстовом файле
Еще ссылки по теме:

C++ Поиск и сортировка в текстовом файле
C++ Поиск в текстовом файле
C++ Поиск в текстовом файле со структурой

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
07.07.2012, 18:05  [ТС]     Быстрый поиск ip адреса в текстовом файле #14
теперь возникла другая проблема.. критерий выбора наилучшего маршрута такой:
1) ип_из_2_файла & маска = 1_ип_в_строке_из_1_файла
то есть не обязательно ип_из_2_файла равен 1_ип_в_строке_из_1_файла

например у нас таблица 0.0.0.0 0.0.0.0 х.х.х.х
а ип из второго файла 10.10.0.0
маршрут х.х.х.х нам подойдет, т.к. 0.0.0.0 & 10.10.0.0 == 0.0.0.0

поэтому решение с хэшем и двоичным поиском не подходит. что делать?
Yandex
Объявления
07.07.2012, 18:05     Быстрый поиск ip адреса в текстовом файле
Ответ Создать тему
Опции темы

Текущее время: 09:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru