Поиск записей (строк,значений) в файловой базе.

← →
Arsenija © (2006-11-29 11:19) [0]

Ребята нужен совет по работе с файлами.
Задача:
Имеется "исходный" текстовый файл вида:
произвольный заголовок
12345 1234567890 123 1234 12345678
...
...
54321 0234567891 321 4321 99999999
(около 10тыс записей)

имеется некая база из таких файлов. Нужно в этой базе найти повторы (к примеру значения второго столбца).
Реализация:
Моя прога берет исходный файл, формирует массив значений, которые ищем. Далее ищет в выбранном каталоге файлы с нужным расширением открывает их (Assignfile(), Reset(), Readln(,), Closefile()) И начинает построчно обрабатывать. При этом используется либо функция POS(подстрока из массива, считанная из файла строка)-вариант1, либо ищется вторая запись отделенная пробелами и проверяется длина записи-вариант2.
Вывод:
Не устраивает время работы-долго.При реализации варианта2 - 300файлов(200мегов) обрабатывает около 13 минут. Вариант 1 - вообще тупит по черному. Аналогичная функция поиска в TotalComander работает на порядок быстрее.
Внимание вопрос:
Какие есть варианты ускорения поиска?

← →
Сергей М. © (2006-11-29 11:36) [1]

> Аналогичная функция поиска в TotalComander работает на порядок
> быстрее

Нет там аналогичной функции - ТС рассматривает файл не как табличный объект БД, а просто как некие бин.данные, при этом ни о каком "построчном" чтении файла речи не идет. Отсюда и высокая скорость сканирования.

> либо ищется вторая запись отделенная пробелами

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

Отбросив первую строку, получаем данные регулярной структуры, обращение к которым с легкостью осуществляется прямым позиционированием в файле (Seek по расчетному смещению) и чтением с установленной позиции блока байт заранее известного размера (для 2-го поля в приведенном примере - 10 байт)

← →
clickmaker © (2006-11-29 11:37) [2]

> Аналогичная функция поиска в TotalComander работает на порядок
> быстрее

там, скорей всего, используется что-то типа CompareMem()

← →
Anatoly Podgoretsky © (2006-11-29 11:40) [3]

И что там есть поиск дубликатов во втором столбце?

← →
Сергей М. © (2006-11-29 11:45) [4]

> обрабатывает около 13 минут

А куда спешить ? Что, эти 300файлов(200мегов) куда-то испарятся, если ты не успеешь их обработать менее чем за 13 минут ?

Поясни вот этот момент...

← →
Arsenija © (2006-11-29 12:37) [5]

1- Смещение второго поля не фиксированное (поэтому ищутся разделители(пробелы)
2- Кол-во строк заголовка - не фиксированное
3- TotalComander имеет функцию поиска (find) в содержании файла заданного(ручками) фрагмента. Т.е. получается мы можем искать в файловой базе только одну запись. Хотелось бы проверять на дублирование сразу все(10тыс)
4- 300файлов(200мегов) это примерно десятая часть всей базы, и ее выцепил для тестирования, при обработке всей базы система впадает в печаль.
5- 13 мин - это много, 13 умножаем на 10 - получаем чуть более 2ч. Нереально много. В течении дня таких процедур может быть достаточно много (до 20-40).
6 - создавать собственную базу этих номеров (записей) и постоянно ее обновлять - это изменение технологии обработки данных - неприемлимо ( еще несколько причин). Поэтому нужно опираться на существующую файловую базу.
7 - актуально только название файла, в котором происходит совпадение (если будут выводиться и совпадающие номера - то это будет предел мечтаний), поэтому при первом совпадении обработка файла прекращается и его название выводится в поле Memo.
8 - Фантазирую: считать весь файл (не построчно) и как в обычном текстовом редакторе пробежаться поиском на предмет дублирования массива искомых значений. Но даст ли это выигрыш по времени или нет, и реализацию процесса я не представляю.

← →
Сергей М. © (2006-11-29 12:50) [6]

Каков максимальный размер подобного файла в составе "базы" ?

← →
Jeer © (2006-11-29 12:52) [7]

TFileStream

Длина записи около 36 байт + 10 тыс записей = 0.360 Mбайт
Приемлимо.

← →
Arsenija © (2006-11-29 13:12) [8]

Сергей М.
средний размер около 500кб (максимальный на текущий день такой же)

Jeer
на начальный пример опираться не надо
реальный пример вот:
111111111111111 2222222222222222222 333333333333
или так
111111111111111 2222222222222222222 3333 44444444 5555 66666666 77777777777777777777777777777777 8888 99999999
или так
1111111111111 2222222222222222222 3333 44444444 5555 66666666 77777777777777777777777777777777 8888 99999999

TFileStream упоминул в связи с чем ? Попробовал применить TMemoryStream, но заткнулся на процедуре вычленения нужных даных для сравнения да и сама процедура поиска не вытанцовывается.

← →
Arsenija © (2006-11-29 13:15) [9]

Jeer
кстати если уж на то пошло, то формально можно ограничить длину строки 255 байтами - размером string

← →
Jeer © (2006-11-29 13:22) [10]

Алгоритм такой:
Файл любым способом всасывается в память целиком.
Критерий раздела записей - два символа CRLF
Критерий второй колонки - поиск первого пробела и до второго.
Получаем текущее поле.

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

> размером string

Тебе виднее, но бывают и длинные строки.

← →
Сергей М. © (2006-11-29 13:27) [11]

> средний размер около 500кб

Понятно.
Мелочь, одним словом)

> массива искомых значений

Еще раз подробней про это :
Что за массив такой ? Откуда он взялся в связи с "в этой базе найти повторы" (цитата) ?

← →
Anatoly Podgoretsky © (2006-11-29 14:11) [12]

> Arsenija (29.11.2006 13:15:09) [9]

Размер string около 2 гб

← →
Arsenija © (2006-11-29 14:27) [13]

Ребята,
1 - привязка к 255 байт - длиннее наверняка не будет (string на фиг, просто у меня строка заложена как стринг(короткий))
2 - массив искомых значений :
есть исходный файл (описание вверху)
Моя прога берет исходный файл, формирует массив значений, которые ищем. Получаем массив искомых значений, каждое значение которого и прорабатываем на предмет дублирования.

З.Ы.
Anatoly Podgoretsky
Размер string около 2 гб - это если есть нулевой символ в конце. Иначе 255 байт. Но это все лирика.

← →
Сергей М. © (2006-11-29 14:33) [14]

> Размер string около 2 гб - это если есть нулевой символ
> в конце. Иначе 255 байт

В огороде бузина, а в Киеве дядька.

> длиннее наверняка не будет

Гадание на кофейной гуще.

> у меня строка заложена как стринг(короткий)

Что значет "заложена" ? В ломбард что ли ?)
Или таки "декларация переменной" ?)

> прорабатываем на предмет дублирования

Подозреваю, что у тебя и здесь "узкое" место с т.з. эффективности/производительности алгоритма той самой "проработки"

← →
Arsenija © (2006-11-29 14:35) [15]

> Алгоритм такой:
> Файл любым способом всасывается в память целиком.
> Критерий раздела записей - два символа CRLF
> Критерий второй колонки - поиск первого пробела и до второго.
> > Получаем текущее поле.
> > Поля записываются в хэш-таблицу или массив уникальных.
> Перед занесением предварительно ищется вхождение, если найдено
> - повтор.
> >
Что-то похожее я и реализовал, затык на скорости обработки. Если проводить чтение и анализ каждой строки файла из базы - скажем так построчный метод, то получется неприемлимо долго. Поэтому прошу посоветовать дельное что-нить. Возможно на предмет (8)- Фантазии из [5]

← →
Anatoly Podgoretsky © (2006-11-29 14:38) [16]

> Arsenija (29.11.2006 14:27:13) [13]

Анализ логов показывает наличие строк свыше 8 кб

> Но это все лирика.

Это не лирика, это называется гораздо хуже.

← →
Arsenija © (2006-11-29 14:45) [17]

> В огороде бузина, а в Киеве дядька.
> Гадание на кофейной гуще.
> Что значет "заложена" ? В ломбард что ли ?)
> Или таки "декларация переменной" ?)

Лирику в сторону

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

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

← →
Arsenija © (2006-11-29 14:50) [18]

> Анализ логов показывает наличие строк свыше 8 кб

Не понял, это как?

← →
Anatoly Podgoretsky © (2006-11-29 15:10) [19]

> Arsenija (29.11.2006 14:50:18) [18]

Это значит, что есть строки и более 8 кб по размеру, что тут не понятно русским языком.
А ты утверждаешь, что строки свыше 255 байт не бывают.

← →
Сергей М. © (2006-11-29 15:18) [20]

> Лирику в сторону

"Пацанщину" в программинге - туда же.

Не обижайся, увидев себя в "Прочее".

← →
Arsenija © (2006-11-29 15:29) [21]

> Это значит, что есть строки и более 8 кб по размеру, что
> тут не понятно русским языком.
> А ты утверждаешь, что строки свыше 255 байт не бывают.

Может и быват, может и до 2гб бывают. Суть в том, что зашел разговор про размер (в каком то посте). Ок. Добавляем условие длина строки не больше 255 символов (255 байт). Решение-то какое?

← →
Arsenija © (2006-11-29 15:30) [22]

> "Пацанщину" в программинге - туда же.
> Не обижайся, увидев себя в "Прочее".

Если нет ничего конструктивного, то лирику в сторону - без обид.

← →
Jeer © (2006-11-29 15:40) [23]

> Arsenija © (29.11.06 15:29) [21]
>
>

255*10000 = 2.55 Мбайт
Копейки.

Зачем считывать построчно.

← →
Arsenija © (2006-11-29 15:44) [24]

> Зачем считывать построчно.

Если целиком, то как внутри поиск проводить?
Так средниц размер и есть 500к

← →
Anatoly Podgoretsky © (2006-11-29 15:59) [25]

> Arsenija (29.11.2006 15:29:21) [21]

> Решение-то какое?

Размер строки к поиску отношения не имеет.

← →
Arsenija © (2006-12-01 09:04) [26]

Нет никаких вариантов?

← →
Сергей М. © (2006-12-01 10:12) [27]

Грузи файл целиком в StringList и работай с уже готовым списком строк

Пример в сабже очень мне напомнил информацию об акционерах (списки акционеров) в конце года, по которому надо делать рассылку.

> прога берет исходный файл, формирует массив значений, которые ищем. Далее ищет в выбранном каталоге файлы с нужным расширением открывает их (Assignfile(), Reset(), Readln(,), Closefile()) И начинает построчно обрабатывать.

Прочитал 3 раза. Так и не понял ЧТО же надо сделать, что это за таинственный "массив значений", каким обьразом выбирается каталог и что в нем, и что такое "нужные расширения".
Однако сдается мне, что все это надо завернуть в БД

> MsGuns © (01.12.06 10:26) [28]

Я тоже не въехал, с какой луны тут свалился массив.

Мой кривой телепатор подсказывает, что за всем этим словоблудием скрыта след.задача : имея некий список файлов отобрать из них только те, у которых в упомянутой 2-й колонке имеются повторяющиеся ц/ч значения, т.е. значения в интересующей колонке не уникальны

И если телепатор таки не ошибся, то пара-тройка стринг-листов идеально подойдут для решения этой задачи

> Прочитал 3 раза. Так и не понял ЧТО же надо сделать, что
> это за таинственный "массив значений", каким обьразом выбирается
> каталог и что в нем, и что такое "нужные расширения".

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

> Однако сдается мне, что все это надо завернуть в БД

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

> Сергей М. © (01.12.06 10:12) [27]
> Грузи файл целиком в StringList и работай с уже готовым
> списком строк

Спасибо, попробую, о результатах отпишусь.

> Надо проверить второй столбец на предмет повтора в уже существующем
> списке файлов

Это что же получается ? Всякий раз при проверке нового файла ты будешь лезть в старые (уже проверенные ранее) файлы ?!

> Arsenija (04.12.2006 11:52:31) [31]

> Надо проверить второй столбец на предмет повтора в уже существующем списке файлов.

Что такое второй столбец, дай четкое определение.
Данный вопрос тебе уже задавался.

Anatoly Podgoretsky © (04.12.06 12:10) [33]

он ответил.

Arsenija © (29.11.06 12:37) [5]
1- Смещение второго поля не фиксированное (поэтому ищутся разделители(пробелы)

Получается так. Есть вероятность, что дадут формат существующей базы даных (упоминал в [31] ). Пока, как говорится: чем богаты, тому и рады.

Скажу более: на текущий момент при дублировании (повторе) значения, существующая система выдает значение (одно, первое повторяющееся). Оно (значение, которое уже повторялось) ручками-поиском (проводник или TotalComander)ищется в папке c файлами. Получаем имя файла дата и далее уже разборки на другом уровне.
Как правило, повторы затрагивают один-три файла базы. Но теоретически возможен случай, когда каждая запись (элемент массива - как удобнее) входного файла (примерно 10тыс) имела повторы в разных файлах. Получается что ручками надо искать 10 тыс раз (и найдем 10 тыс файлов).

> Сергей М. © (01.12.06 10:12) [27]
> Грузи файл целиком в StringList и работай с уже готовым
> списком строк

Попробовал.
Ввел один StringList куда поочереди целиком записывал файлы из базы c помощью TempList.LoadFromFile(name) (вместо построчного считывания командой readln).
Результат по сравнению с [5] немного улучшился с 13 мин до 11 мин. Наверное, это предел.

А почему не воспользоваться консольными командами find или grep?

> novill © (05.12.06 14:51) [37]
> А почему не воспользоваться консольными командами find или
> grep?

Поясни пожалуйста свою мысль.
З.Ы. Что за команда такая grep ?

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

если интересно обработать самому:
1. Закачиваешь весь файл в буфер. например, через file stream (с StringList не связываешься, он много лишнего делает)
2. Простым POS ищешь вхождение.
3. Если подстроку нашел, смотришь где она относительно ближайших пробелов и #13#10 находится.

Поиск записей (строк,значений) в файловой базе. Найти похожие ветки