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

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

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

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

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

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

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

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

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

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

Каков самый быстрый способ узнать количество строк в оргомном текстовом файле в Windows? - C++
Есть текстовый файл с кучей строк (размер файла ~ 1Гб). Как можно максимально быстро узнать кол-во строк в этом файле? Если делать тупо...

Поиск в текстовом файле всех слов, заданных в другом текстом файле - C++
Вообщем такое задание: Поиск в текстовом файле всех слов, заданных в другом текстом файле; Не могу понять почему не работает: ...

Поиск в текстовом файле - C++
Добрый вечер еще разок. Никак не могу сообразить, как реализовать следующий алгоритм (представляю его так): есть база (назовем ее...

Поиск в текстовом файле - C++
Всем привет! Нужно на С++ написать программу,в поиске похожего не нашёл. Вот сама задача - Имеются два текстовых файла. Определить в каком...

Поиск в текстовом файле - C++
Есть тестовый файл такого типа: Имя: Плотник Трудоемкость: 32 Время: 22 Квалификация: бывалый Необходимо создать поиск по...

Поиск в текстовом файле - C++
Здравствуйте, нужно осуществить поиск нужной строки в файле .txt. Как быть?

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

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

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

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

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

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

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

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

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


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

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

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

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



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

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

Добавлено через 1 минуту
Цитата Сообщение от post_hack Посмотреть сообщение
Да. Строчки например такого вида:
Добавлено через 58 секунд
У меня идея. Скиньте ваш скайп, кажется знаю, какой алгоритм. В личку
1
Avazart
Эксперт С++
7213 / 5385 / 286
Регистрация: 10.12.2010
Сообщений: 23,796
Записей в блоге: 17
03.07.2012, 22:56 #11
а в С++ к произвольной строке обратиться нельзя.
Если файл всего лишь один и весит не много, то почему бы его не грузить в начале работы в память?
А там обращайся к нему как хочиш...
Запихнуть все можно в multimap ну можно конечно еще хеш...
0
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
07.07.2012, 16:05  [ТС] #12
Такой вопрос возник.. Как мне строку вида "192.168.0.1" преобразовать в u_long число?
Чтобы можно было корректно выполнить операцию &
0
dr.curse
388 / 344 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
07.07.2012, 16:17 #13
Цитата Сообщение от post_hack Посмотреть сообщение
Такой вопрос возник.. Как мне строку вида "192.168.0.1" преобразовать в u_long число?
Чтобы можно было корректно выполнить операцию &
post_hack, насколько знаю это делается по следующей формуле, если адрес имеет такой "a.b.c.d" вод то переводим так
C++
1
((a*256+b)*256+c)*256+d
1
post_hack
0 / 0 / 0
Регистрация: 03.07.2012
Сообщений: 7
07.07.2012, 18:05  [ТС] #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

поэтому решение с хэшем и двоичным поиском не подходит. что делать?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2012, 18:05
Привет! Вот еще темы с ответами:

Поиск данных в текстовом файле - C++
Подскажите как можно через массив вывести информацию находящуюся в текстовом файле. ну например у меня есть в файле Имя Фамилия и т.д. и...

Не работает поиск в текстовом файле - C++
Я хочу чтобы данные которые я ввожу , записывались в файл с пробелами и считывались на экран(так же с пробелами). Все получилось , но не...

Поиск в текстовом файле со структурой - C++
Здравствуйте! подскажите пожалуйста как грамотно реализовать поиск по структуре из текстового файла. вот что пока написано: ...

Бинарный поиск в текстовом файле - C++
Есть текстовый файл с 10000 словами в алфавитном порядке. Функция проверяет, есть ли введенное слово в этом файле. Помогите реализовать...


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

Или воспользуйтесь поиском по форуму:
14
Yandex
Объявления
07.07.2012, 18:05
Ответ Создать тему
Опции темы

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