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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.98
HIMen
 Аватар для HIMen
4103 / 1352 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
29.05.2009, 15:51     Бинарный поиск в текстовом файле #1
Есть текстовый файл с 10000 словами в алфавитном порядке.
Функция проверяет, есть ли введенное слово в этом файле.
Помогите реализовать бинарный поиск по первой букве
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool slovo_true(char *slovo, FILE *stream) 
{
   char read_str[20], *result;
   fseek(stream,0,SEEK_SET);
   while (!feof(stream))  
   {
      result=fgets(read_str,20, stream);
      if (!strcmp(read_str, slovo)) 
      {
         return true;
      }
   }    
   return false;
};
Как менять позицию fseek(stream,0,SEEK_SET) на определенную строчку?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,307
29.05.2009, 15:57     Бинарный поиск в текстовом файле #2
На определенную строчку - никак.
Haster
инженер-системотехник
 Аватар для Haster
109 / 108 / 2
Регистрация: 10.03.2009
Сообщений: 533
29.05.2009, 16:01     Бинарный поиск в текстовом файле #3
Можно предложить, например, такой алгоритм:
считываешь первую букву - если не подходит то читаешь до символа перевод строки..
Затем опять проверяешь и т.д.
(будет работать в случае, если каждое слово на новой строке)
MrAndrey_ka
 Аватар для MrAndrey_ka
77 / 77 / 2
Регистрация: 13.05.2009
Сообщений: 536
Записей в блоге: 1
29.05.2009, 16:02     Бинарный поиск в текстовом файле #4
что имеется ввиду
бинарный поиск по первой букве
, по коду буквы или как?
Gravity
 Аватар для Gravity
556 / 550 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
29.05.2009, 16:03     Бинарный поиск в текстовом файле #5
Если заранее известно кол-во слов в файле, то нужно читать из файла в массив и уже работать с массивом.
HIMen
 Аватар для HIMen
4103 / 1352 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
29.05.2009, 16:08  [ТС]     Бинарный поиск в текстовом файле #6
Цитата Сообщение от MrAndrey_ka Посмотреть сообщение
что имеется ввиду , по коду буквы или как?
да.

Количество слов точно не известно, т.к. файл пополняется словами
Gravity
 Аватар для Gravity
556 / 550 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
29.05.2009, 16:15     Бинарный поиск в текстовом файле #7
Тогда так:
- создаем массив через динамическую память и заводим счетчик считанных слов
- читаем слова из файла в массив
- если счетчик слов превышает размер массива, выделяем еще памяти под массив
И так пока не прочитаешь весь файл, затем делай бинарный поиск по массиву.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
29.05.2009, 16:20     Бинарный поиск в текстовом файле #8
Можно тупо считать из файла все 10 тыщ слов (займут в памяти немного места).

Либо сделать первый проход и запомнить 10 тыщ элементов с позициями начала слова. Потом в массиве из 10 тыщ позиций методом бинарного поиска проверять слово. Идиотизм такого метода почти очевиден

Либо вот так. Делаемм SEEK на середину файла (середину в байтах), далее читаем до энтера - таким образом нашли начало слова, которое приблизительно в середине файла находится. И так даелее, делаем SEEK в терминах абсолютного байтового смещения, ищем начало слова и проверяем. Правда возникнет геморой ближе к концу. Типа если у нас диапазон сузился до 10 байт, при этом в этом диапазоне слово 3 байта и 7 байт. По такому алгоритму мы доначала слова не доберёмся, а потому тут что-то думать надо

Идей, как тут применить бинарный поиск больше нет
HIMen
 Аватар для HIMen
4103 / 1352 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
29.05.2009, 16:22  [ТС]     Бинарный поиск в текстовом файле #9
Цитата Сообщение от Gravity Посмотреть сообщение
Тогда так:
- создаем массив через динамическую память и заводим счетчик считанных слов
- читаем слова из файла в массив
- если счетчик слов превышает размер массива, выделяем еще памяти под массив
И так пока не прочитаешь весь файл, затем делай бинарный поиск по массиву.
На поиск обычным способом уходит 0.2-0.3 секунды.
Это будет быстрее?
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16824 / 5245 / 319
Регистрация: 30.03.2009
Сообщений: 14,121
Записей в блоге: 26
29.05.2009, 16:25     Бинарный поиск в текстовом файле #10
Цитата Сообщение от HIMen Посмотреть сообщение
На поиск обычным способом уходит 0.2-0.3 секунды.
Это будет быстрее?
В твоём варианте на каждое слово читается файл. В предложенном варианте файл читается только один раз идальше вся информация лежит в памяти. Для однократного исполнения разницы по времени скорее всего не будет. Для многократного исполнения твой вариант медленнее
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.04.2010, 17:29     Бинарный поиск в текстовом файле
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
salvafion
10 / 10 / 1
Регистрация: 16.06.2009
Сообщений: 193
01.04.2010, 17:29     Бинарный поиск в текстовом файле #11
держи а начале файла количество слоа в файле а потом как в школе делим колличство пополам и ставим указатели. и смотрим в какую сторону смещаться
Yandex
Объявления
01.04.2010, 17:29     Бинарный поиск в текстовом файле
Ответ Создать тему
Опции темы

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