Строки и файлы!

← →
Samael6 (2003-09-30 09:41) [0]

Господа программисты!
Такая проблема:
У меня есть текстовый файл, в котором в колонку записаны некоторые числа по три числа в строку:
"123","345","4"
Длина строки меняется так как числа могут быть разные. В конце строки стоит только символ #10(без #13!).
Первые 2 числа в строке характеризуют некий диапазон и каждая строка свой. Имея некоторое число мне нужно подобрать диапазон, в который входит это число и проанализировать 3 число в строке диапазона(уф...). Надеюсь понятно.
Проблема вот в чем: файл диапазонов весит примерно 50Мб! Поиск я делаю посимвольно читая строки(так как признак конца не стандартный), их разбивая и так далее... Но этот метод очень медленно работает(один нужный диапазон находится примерно от 30сек - 1 минуты), а если мне нужно найти 20-40 диапазонов :-(

Помогите разобраться, как сделать быстрый поиск?

Заранее благодарен!

← →
pasha_golub (2003-09-30 10:16) [1]

TFileStream or TMemoryStream
Идея в том, что сначала загружем все это, а потом все остальное

← →
Verg (2003-09-30 10:21) [2]

Я бы использовал проецирование файла в память.
При данных условиях, быстрее по-моему уже не сделаешь.

← →
Izyum (2003-09-30 10:26) [3]

Тут возникают сразу несколько вопросов:
1. Могут ли диапазоны перекрываться?
2. Как организован файл? Новые диапазоны дописываются в конец файла или вставляются в каком-то осмысленном порядке? Проще говоря, сортировка есть?
3. Почему нельзя привести все строки к одной длине? ("123","345","004")?

Если на вопрос 1 ответ "нет", на вопрос 2 ответ "сортировка есть", н вопрос 3 "можно сделать" - то тогда можно попробовать реализовать поиск по методу половинного деления или еще какой алгоритм использовать.

← →
Samael6 (2003-09-30 10:29) [4]

> Izyum

Отвечаю:
1: нет
2: нет
3: нет
Вот так!

← →
Anatoly Podgoretsky (2003-09-30 10:33) [5]

А преобразовать файл в нормальный можно?

← →
Izyum (2003-09-30 10:37) [6]

Собственно, самое главное - диапазоны не перекрываются.
Пункты 2,3 ИМХО можно реализовать и это ни как не скажется на основной функциональности. При встаке нового диапазона лучше потратить 20с на анализ файла и поиск места встаки, а при обработке 3-го числа убрать лишние нули (может даже проще будет пробелы). А може использовать в качестве разделителя стандартные #10#13? Это даст возможность проще анализировать строки. В любом случае это ИМХО лучше, чем затягивать 50М в память:)

А вобще-то очень трудно рассуждать не зная конечной цели:) Для таких целей может проще всего использовать какую-нибудь СУБД?

← →
Samael6 (2003-09-30 10:40) [7]

> Anatoly Podgoretsky

Файл базы диапазонов не мой, его нужно только обработать, но думаю что можно(в конце концов если конвертнуть его в db и не кому об этом не говорить...)

Вопрос только в том, как это все сделать програмно?

← →
Verg (2003-09-30 10:44) [8]

> Izyum © (30.09.03 10:26) [3]

> 1. Могут ли диапазоны перекрываться?

> Samael6 © (30.09.03 10:29) [4]

> Отвечаю:
> 1: нет

Это уже лучше.
Организовать индекс (сортированный "массив" начал диапазонов с указанием соотв. смещение этого диапазона в файле).
Пытаться искать используя индекс, а если в нем пока недостаточно информации продолжать прямой перебор всех диапазонов с одновременным дополнением индекса.
Каждый поиск будет косвенно приводить к убыстрению следующего.

← →
Izyum (2003-09-30 10:44) [9]

>Samael6
Тогда тебе нужно будет конвертить его после каждой модификации основного файла. Или файл с диапазнами статичен?

← →
Izyum (2003-09-30 10:49) [10]

Verg © (30.09.03 10:44) [8]
Мне кажется, что строить в данной ситуации еще и индекс нецелесообразно, т.к. индексный файл будет еще больше основного. Ведь индексировать придется по двум полям (это же диапазоны).

Если файл все таки статичен, проще его раз отсортировать и потом, как вариант, методом половинного деления искать нужный диапазон.

← →
Verg (2003-09-30 10:53) [11]

> . Ведь индексировать придется по двум полям (это же диапазоны).
>

Нет, достаточно по началу, если конечно всегда начало меньше конца.

Просто проверять надо будет всегда два соседних по индексу диапазона

x>=Idx[i] and x<=Idx[i+1] - > либо x принадлежит диапазону i, либо вообще не принадлежит ни одному.

← →
Samael6 (2003-09-30 10:54) [12]

> Izyum

Файл не статичен, но обновляться судя по всему будет не часто(хотя не факт)

А с индексированием можно по подробнее?

← →
Anatoly Podgoretsky (2003-09-30 10:55) [13]

Samael6 © (30.09.03 10:40) [7]
А зачем в БД можно и в текстовый, а потом много кратно использовать.

← →
Verg (2003-09-30 10:58) [14]

> x>=Idx[i] and x<Idx[i+1]

Конечно же...

Индекс может быть представлен в двоичном виде, а не в текстовом.

← →
Samael6 (2003-09-30 11:11) [15]

> Verg

Ты не мог бы пояснить на примере свой метод поиска?

← →
Verg (2003-09-30 11:15) [16]

> А с индексированием можно по подробнее?

Ну, как объяснить-то....
Упорядоченный список ссылок на позиции в файле:
<значение начала диапазона><позиция этого диапазона в файле>

По этому списку можно двоичным поиском (методом половинного деления) найти подходящий диапазон, либо убедиться в том, что индекс не содержит подходящей записи. Если не содержит, то продолжить сканированного FileMap-а с запомненного с предыдущего раза адреса, одновременно достраивая индекс, но если оказалось, что уже просканирован весь Map, то значит x не принадлежит ни одному из диапазонов.
При смене файла, ясно что индекс придется строить весь заново.
Может и мутно, но для данных условий задачия ничего лучшего не вижу в плане ускорения работы.

← →
Izyum (2003-09-30 11:31) [17]

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

Ну а насчет построения индексного файла, то...
Создаем еще один файл, в котором формируем возрастающий список диапазон/смещение в основном файле.
Примерно так:
"10", 256
"25", 13
"135", 1236
"432", 111
"439", 53

Теперь при поиске нужного диапазона мы сначала ищем (методом половинного деления) его в индексном файле, определяем смещение в основном и получаем искомые данные.

Если пойти еще дальше, то в индексный файл можно вынести еще и длину каждой записи, типа "439", 53, 12. Тогда в операции получения интересующей информации можно не анализировать основной файл, а сразу выбирать всю запись о интересующем диапазоне.

← →
Samael6 (2003-09-30 11:39) [18]

> Izyum

Да, ты прав, лучше наверно ничего не получится. Так и сделаю, спасибо!

← →
Izyum (2003-09-30 11:44) [19]

Не за что! Рад, что помог - тешу себя такой надеждой;-)

← →
Verg (2003-09-30 11:52) [20]

> Все таки, я думаю, в данном случае индексы не очень подходят,
> ведь с уччетом того, что диапазоны не перекрываются отсортированный
> файл будет повторять структуру самого индексного файла.
>

Хм. Не логично. Диапазоны-то не перекрываются, но они же не отсортированы в файле по увеличению начал диапазонов.

Как тут можно
метод половинного деления можно будет применять на самом файле
??

Файл - текстовой - каждая запись содержить три значения, но в общем она переменной длины.
Индекс - двоичный массив с фиксированной длиной записи.

Где тут "повторения структур"?

← →
Izyum (2003-09-30 12:00) [21]

Verg © (30.09.03 11:52) [20]
Ну, во первых, я писал " отсортированный файл будет повторять структуру самого индексного файла"
А во вторых, выше я предлагал привести файл к "правильному" виду: с фиксированной длиной записи, и с #10#13 в качестве разделителя.

И сейчас считаю, что это лучше чем строить индекс. Почему? Да потому что при модификации основного файла придется все равно перестраивать индексный. А если перестраивать индексный, то почему нельзя вместо этого пересторить сам файл? А с одним файлом заморачиваться проще, чем с двумя ИМХО:)

← →
Izyum (2003-09-30 12:04) [22]

А вообще-то, для более осмысленной дискуссии не хватает вводных данных: мы не знаем как этот файл формируется, чем формируется, как используется, чем используется (другими словами, скоко прог его юзают), есть ли исходники (и можно ли их модифицировать) этой (этих) прог и т.д. По этому, трудно сказать с уверенностью что лучше: индексы строить или структуру самого файла менять.

← →
Verg (2003-09-30 12:18) [23]

> А если перестраивать индексный, то почему нельзя вместо
> этого пересторить сам файл? А с одним файлом заморачиваться
> проще, чем с двумя ИМХО

Ну то есть разом построить индекс на весь файл? Отсортировать, привести к фиксированной длине записи, потратить вагон времени. А потом окажется, что надо было из всего файла-то первых 5 записей...
Ты не понял основной идеи - индекс индексом - это хорошо, но может индекс строить не весь сразу. Компромис между прямым перебором и построением индекса, чтобы не перебирать уже "перебраное"... но и не "перелопачивать" весь файл целиком.

← →
Izyum (2003-09-30 12:28) [24]

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

Если я правильно понял твою мысль, то при первом запуске проги, мы осуществляем прямой перебор пока не найдем искомые данные. Заносим их в индекс. При втором запуске сначала просматриваем индексный файл, и если не нашли - прямой перебор с добавлением в индекс. Так получается?

← →
Izyum (2003-09-30 12:37) [25]

Пока постился - дошло:)
Меня все время сбивало с толку понятие инрдексации применительно к БД, в которой новая запись может вставляться не только в конец, но и в начало. Да и в старых записях индексируемое поле могло бы изменяться, или вся запись могла бы удалиться. И тгда нужно весь индекс перещитывать! Но ведь сдесь такой картины нет! - новые записи всегда добавляются в хвост файла. Тогда твоя идея имеет рациональное зерно. Просто при втором запросе, если в индексном файле искомый диапазон не найден, мы будем продолжать прямой перебор не с начала файла, а стого места, на котором остановились в прошлый раз. Это ты предлагал? Если да - то это хорошая идея!:)

Правда, тогда нужно спросить у автора топика: имеющиеся диапазоны всегда статичны? Другими словами, может ли имеющийся диапазон удаляться, изменяться? Если ответ "да", тогда это не сработает и нужно будет все равно пересчитывать весь индексный файл. А если "что написано - то свято", тогда я присоединяюсь к твоей идее!

← →
Verg (2003-09-30 12:52) [26]

> Если не содержит, то продолжить сканированного FileMap-а
> с запомненного с предыдущего раза адреса, одновременно достраивая
> индекс, но если оказалось, что уже просканирован весь Map,
> то значит x не принадлежит ни одному из диапазонов.

Это из моего 16-ого поста

> А если "что написано - то свято",

Я бы по-другому немного сказал -
Попытаться решить задачу в чистом виде - как есть, а уже потом пытаться "землю под комбаины"....

← →
Samael6 (2003-09-30 13:39) [27]

> Правда, тогда нужно спросить у автора топика: имеющиеся
> диапазоны всегда статичны?

Если я сам все правильно понял, то добавление будет происходить только в конец файла.

← →
Izyum (2003-09-30 13:46) [28]

> Если я сам все правильно понял, то добавление будет происходить
> только в конец файла.

Это хорошо, но для того чтобы метод, предложенный Vеrg-ом работал стабильно, нужно еще чтоб имеющиеся уже не модифицировались и не удалялись!

А в остальном - нет предела совершенству! По моему, информации к размышлению методом мозгового штурма тебе накидали вагон и маленькую тележку. Пробуй реализовывать!
Успехов.

← →
Samael6 (2003-09-30 13:56) [29]

Большое спасибо, но один вопрос:
Когда мы находим подходящий диапазон в исходном файле и делаем запись в индексном, мы сохраняем его физ. положение в исходном файле и в случае если не найдем следующего диапазона в индексном файле, то продолжим поиск с сохраненного положения(Так, я ничего не перепутал?). Но ведь в исходном файле все в "разнобой" и поиск с сохраненного места не гарантирует, что очередная запись будет находится в исходном файле после сохраненного положения!

Я извиняюсь, если чего-то не допонял...

← →
Samael6 (2003-09-30 14:00) [30]

Или имелось ввиду, что построение списка индексов происходит непрерывно во время сканирования исходного файла? ТОгда я все понял!

← →
Verg (2003-09-30 14:04) [31]

> Но ведь в исходном файле все в "разнобой" и поиск с сохраненного
> места не гарантирует, что очередная запись будет находится
> в исходном файле после сохраненного положения!

А если еще подумать?

Ты же уже считывал строки ДО сохраненного положения, а значит к этому времени индексный масси уже содержит инфу про ВСЕ эти строки и если они не менялись в исходном файле, то и сканировать их заново нет никакого смысла. Если в уже построенном индексе поиск ни к чему не привел, то надо сканировать исходный файл дальше, перебирая все записи по очереди и достраивая индекс до тех пор, пока не будет найден подходящий диапазон либо не кончится файл.

← →
Izyum (2003-09-30 14:06) [32]

> построение списка индексов происходит непрерывно во время
> сканирования исходного файла?

Конечно. Раз уж ты делаешь прямой перебор - грех уже обработанные записи не занести в индексный файл:) Тогда, если ты ищешь диапазон, который физически находится в файле выше границы, до которой ты дошел в прошлый раз - он обязательно будет проиндексирован и прямой перебор не нужен. А вот если в индексном файле его нет - значит до него ты еще не дошел и продолжаем поиск, или его физически не существует - может быть и такой вариант.

Только индексный файл нужно формировать строго по возрастанию и при поиске в нем использовать половинное деление - в противном случае результат будет отрицательным.

← →
Izyum (2003-09-30 14:08) [33]

> Verg © (30.09.03 14:04) [31]
Трудно работать в форуме когда сразу несколько ответчиков сидят в онлайне. Может нужно ввести понятие транзакции?:-)

← →
Samael6 (2003-09-30 14:10) [34]

А что это за такое половинное деление? Если не трудно, расскажите.

← →
Verg (2003-09-30 14:13) [35]

> Трудно работать в форуме когда сразу несколько ответчиков
> сидят в онлайне. Может нужно ввести понятие транзакции

:)))
Трудно вообще работать, сидя на форуме в онлайне.
:)))

← →
Samael6 (2003-09-30 14:15) [36]

Ребята как думаете: если при запуске проги проверять корректность индексного файла(поверяя размер исходного, его дату и т.п с где-то ранее сохраненными) и в случае его изменения просто создавать его один раз и весь сразу? Будет польза?

← →
Izyum (2003-09-30 14:15) [37]

Ну ты, дружище, даешь:) Это даже не институтский курс математики - это школьный!

У тебя есть список:
1
2
3
4
5
6
Всего 6 элементов. Мы ищем 4. Что мы делаем: берем 6/2=3-й элемент. Смотрим меньше он или больше тог, что мы ищем. Если меньше - все элементы от начала до 3 отбрасываем. Оставшиеся элементы опять делим пополам и смотрим - какую часть из оставшихся нужно отбросить, а какую оставить.

В общем, используя такой подход последовательный список из 1024 элементов ты сможешь обработать не более чем за 10 итераций, вместо прямых 1024-х:)

← →
Samael6 (2003-09-30 14:17) [38]

> Izyum

Спасибо, торможу =:)

← →
Izyum (2003-09-30 14:23) [39]

> Ребята как думаете: если при запуске проги проверять корректность
> индексного файла(поверяя размер исходного, его дату и т.п
> с где-то ранее сохраненными) и в случае его изменения просто
> создавать его один раз и весь сразу? Будет польза?

все зависит от специфики работы. Если изменения в основной файл вносятся не часто - я бы именно так и сделал, а переиндексацию проводил бы только после изменения основного файла.

P.S.: Интересно, кто щас раньше ответить успеет - я или Verg?:)

← →
Samael6 (2003-09-30 14:26) [40]

Ну вроде разобрался, спасибо большое! Больше не пристаю!

Строки и файлы! Найти похожие ветки