Forum Webscript.Ru
Программирование => Perl => Тема начата: KiLLjoY aka SerZH от 29 Июля 2004, 02:48:22
-
Товарищи нужна помощь!
Помогите найти оптимальный вариант!
--- у нас есть текстовый файл, примерно:
123 \\t dfdsf \\t fdgsdfg \\t dfsgfdg \\t dfgs\\n (строка около 20кб)
.....................
.........
-- около 100000 записей, 123 уникальный ID, не обязательно последовательный ведь могут взять и удалить например 456 и останется 455 и 457 :o)
-- суть такова нужно искать в этом файле строку, по определённому ID! не по номеру строки, а именно по ID(в самой строке)!
-- условия, использование памяти не более 15мб(процесс)+13мб сам Перл = 28мб! На выполнение всей программы не более 10с!
-
KiLLjoY aka SerZH
IMHO самый оптимальный вариант: использовать SQL БД, например MySQL.
Иначе: открываешь файл, считываешь построчно, проверяешь полученную строку. Памяти съест немного, но со временем можно не уложиться.
-
Как часто изменяется файл? Если достаточно редко, то проще всего сделать дополнительный индекс на ID в отдельном файле. Поиск будет практически мгновенным.
-
Нужен другой выход!
-
KiLLjoY aka SerZH
Нужен другой выход!
На такие высказывания, у меня вопрос возникает по поводу того кому нужен этот выход.
Форум - не зал ожидания манны небесной.
Мотивируй свой отказ использования моих предложений...
-
Это не выполнимо вроде :)
100k*20k=2000kk = тоесть 2 гига читаться с винта они будут более 10с :)
а если держать это в оперативе ты по памяти не уложишся в 28 мб :)
но если строка фиксированого размера, то все не такуж и плохо
индекс
id
смещение относительно начала файла
читаем индекс из отдельного файла (таблици), и дальше seek по файлу с данными.
Может и уложишся в 10с
-
Если все ID более менее упорядочены (то есть они даются последовательно и значит при 100к записей вряд ли превысят 1000000), то проблем вообще нет. Для каждого ID в отдельном файле записываем смещение этой записи в файле с данными (по четыре байта на ID). При чтении нужно будет сделать всего лишь два seek\'а. Никаких ограничений на размер записи нет. Работает практически мгновенно.
Если ID могут быть очень большими, тогда нужно немного усложнить схему. Но все равно за полчаса можно сделать.
-
Нужно использование Процессов + открытие файла не сразу целиком, а часиями! Если файл будет 130 метров, сервер просто свалится! И вырубит мой процесс(программу) нафиг!
-
Да, файл не сортирован, изменяется часто! Таку что вариант с индексом отпадает!
-
KiLLjoY aka SerZH колись давай
1. строка около 20 кб, плюс/минус сколько?
2. файл не сортирован, но ID таки идут последовательно, хотя и с "дырками" (455,456,458)?
3. файл часто изменяется. Как? Чем? А не лежит ли где то рядом файлик с соответствиями индкс-позиция?
[OFF]Ну и риторические вопросы
У тебя то самого есть какие мысли?
А о чем раньше думали, когда не было 100000 по 20к[/OFF]
-
1) 20 кб... хм... |+бесконечность | -20кб |
2) Последовательность любая.
3)Я же сказал индекс отпадает!
P.S.: Я же уже написал что нужно каким-то неизвестным образом использовать!
P.S.S.: В коде должен быть собственный контроль времени! Во как!
Не забываем также про 10сек и 18 мегабайт на выполнение!
-
KiLLjoY aka SerZH ты предлагаешь за тебя написать?
-
Нет я жду совета... как бы мне это использовать!
-
Хотя бы рабочий алгоритм!
-
KiLLjoY aka SerZH:
Нужно использование Процессов
perldoc threads
KiLLjoY aka SerZH:
открытие файла не сразу целиком, а часиями!
perldoc -f seek
-
--- Вопрос в том, как выбирать размер блока, который будет открываться каждый раз?
--- И если открыть файл на произвольном байте, то можно искомый адрес, допустим, разбить на две части, тогда как искать?
--- И как эти потоки запустить одновременно?
-
KiLLjoY aka SerZH:
Вопрос в том, как выбирать размер блока, который будет открываться каждый раз?
зная общую длинну можно разбить его хоть на сто частей.
KiLLjoY aka SerZH:
И если открыть файл на произвольном байте, то можно искомый адрес, допустим, разбить на две части, тогда как искать?
может, даже будет. писать обработчик такой ситуации.
KiLLjoY aka SerZH:
И как эти потоки запустить одновременно?
доки читать:
http://search.cpan.org/~nwclark/perl-5.8.4/ext/threads/threads.pm
-
> Я же сказал индекс отпадает!
А без индекса никак. 2 гига по любому будут читаться более 10 секунд. Почему тот скрипт, который обновляет файл не может перстраивать индекс?
Как именно обновляется файл - новые записи просто дописываются в конец? Тогда индекс перестраивать не нужно, нужно просто добавить в конец индекса новую позицию. А если какие-то записи удаляются из середины файла, то данная операция сама по себе занимает столько времени, что и полная перестройка индекса тут ничем не помешает.
-
KiLLjoY aka SerZH, а эта задачка вообще то практический смысл будет иметь? Или это все из разряда чистой теории?
-
Читаем последний пост NeoNox\'a он оказался прав...
Практическое значение.. хм... огромнейшее, особенно с интернет, т.к. как к файлу одновременно может обратиться 2-100 и.т.д. человек!
--- Короче - потоки это сила!
-
Тратить 10 секунд на простейшую операцию доступа к данным по уникальному ключу (на которую и 0.1 сек. много) - что-то мне подсказывает, что это тупиковое решение и через полгода все равно придется переписывать.
-
КшЫуфксрук согласен.
KiLLjoY aka SerZH у тебя сервер упадет при порождении 10000 процессов.
-
А кто сказал, что я буду столько потоков открывать....?
Так же сервер упадёт при загрузке памяти и также если процесс будет занимать больше 10с, так что здесь нужна золотая середина!
Её поиском я и занимаюсь!
-
>Её поиском я и занимаюсь!
Херней ты занимаешься, извини уж.
Упорядочи данные и будь счастлив.
-
хех... да не будет там упорядочивания данных...
Да и представь процечч сортровки...ыгыг... я бы посмотрел сколько бы этот процесс занял!
-
KiLLjoY aka SerZH:
я бы посмотрел сколько бы этот процесс занял!
Я думаю, что не более того времени которое ты затратишь на поиски той самой золотой середины.
И все таки, чем же его редактируют, этот файл?
-
Да не нужно сортировать данные. Индекс должен быть отсортирован и хранить позиции записей для каждого ID.
И действительно, ты до сих пор не сообщил, кто и как редактирует этот файл и сколько времени занимает перезапись 2-гигабайтного файла.
-
КшЫуфксрук вероятно ничего не занимает.
open FH, ">>", \'./file\'; операция практически мгновенная на любом размере файла.
-
NeoNox так ведь я ранее писал, что если файл только дописывается в конец, то индекс перестраивать не нужно, а также нужно в конец индекса добавить новые указатели на новые данные - операция не менее мгновенная. А если же данные удаляются из середины файла, то перезапись файла займет столько времени, что перестройка индекса на фоне этой операции займет не так уж много времени.
В общем, пока не прозвучало ни одного аргумента, почему же ни в коем случае невозможно использовать хоть какое-нибудь примитивное подобие индекса.