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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
#1

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

03.07.2012, 20:59. Просмотров 1560. Ответов 13
Метки нет (Все метки)

Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько раз). На каждой строчке по 1 ip-адресу. Всего строк ~300 000.

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

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

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

Посоветуйте что-нибудь. Заранее спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 459
Записей в блоге: 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
Сообщений: 459
Записей в блоге: 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
Сообщений: 459
Записей в блоге: 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
Сообщений: 459
Записей в блоге: 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
Сообщений: 459
Записей в блоге: 1
03.07.2012, 21:29     Быстрый поиск ip адреса в текстовом файле #10
Весь файл в начале все равно нужно пробежать для того, чтобы построить систему для поиска в дальнейшем. Ведь необходимо как-то иметь доступ прямой к ip

Добавлено через 1 минуту
Цитата Сообщение от post_hack Посмотреть сообщение
Да. Строчки например такого вида:
Добавлено через 58 секунд
У меня идея. Скиньте ваш скайп, кажется знаю, какой алгоритм. В личку
Avazart
 Аватар для Avazart
7037 / 5214 / 259
Регистрация: 10.12.2010
Сообщений: 22,903
Записей в блоге: 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++
C++ Поиск символа в текстовом файле
Каков самый быстрый способ узнать количество строк в оргомном текстовом файле в Windows? 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 адреса в текстовом файле
Ответ Создать тему
Опции темы

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