абракадабра

Это сообщение отредактировал(а) sprinterv - 27.1.2009, 13:33

Раз строки имеют переменную длину, то без предварительного индексирования не обойтись. Нужно просканировать файл один раз и собрать, как минимум, позиции начала записей. Но требуемый объем памяти уже будет зависеть от размера файла. Нет, конечно можно лезть в любое место файла наугад и искать ближайший конец записи (0A), но криво это жутко...

Почему же криво? Во-первых, иначе нужна будет память дополнительная память для хранения начал, что не удовлетворяет условию.
А так - ну вот есть у нас два указателя в файле (l;r), указывающие на начала записей, находящихся в текущем рассмотрении. Берём середину m=(l+r)/2 и идём от неё влево, пока не встретим начало блока. Если мы пришли в позицию l, и окажется, что всё-таки l надо включать в отрезок поиска, то надо подвигать l вправо до начала следующего блока (с асимптотикой всё будет ок, у нас же один этот l-ый блок такую длину имеет, что она больше (l+r)/2). А иначе, если текущий случай - не этот особый, то вообще стандартный бинпоиск.

Это не так. Делим файл на логические блоки. Размер каждого блока не менее двухх максимальных длин записи. Это гарантирует, что вне зависимости от того, откуда мы возьмём такой блок, в нём будет минимум одна полная запись. После чего собсно бинарным поиском ищем БЛОК, в которых находится требуемая запись. На каждом шаге сужается тот кусок файла, в котором ищется нужная запись (отбрасывается чуть менее половины куска с предыдущего шага).

Т.е. для файла в 10 Г и записей по 4к читаем сперва 8к, начиная со смещения 5Г, находим в этом блоке начало первой полной записи (сразу после первого разделителя), экстрагируем ключ и сравниваем. Если больше, то на следующем шаге надо искать в диапазоне смещений 0 - 5Г+4к, если меньше - в диапазоне смещений 5Г - 10Г... можно посчитать, что потребное количество чтений 8-килобайтных блоков не превышает 21, и то при условии что на очередном шаге нам случайно не подвернётся нужный ключ (вероятность чего, кстати, не такая уж и маленькая)... и если на это потребуется 5 секунд, то просто комп надо менять, хотя бы на второй пенёк.

Abrakadabra

Это сообщение отредактировал(а) sprinterv - 30.1.2009, 14:21

sprinterv, а файл Ваш был 10 Гбт? как тогда быть с индексами?  

Это сообщение отредактировал(а) gcc - 22.1.2009, 17:09

задание которое автор удалил тут   (по непонятным причинам)
http://unixforum.org.ua/index.php?topic=18004

Добавлено через 2 минуты и 21 секунду
собсьвенно и ответ там же почти будет скоро       

Это сообщение отредактировал(а) gcc - 27.1.2009, 17:48

вполне понятные 
это тестовое задание на вакансию в рекламапорт
http://rabota.ua/company490967/vacancy4318883

Кое кто решил сэкономить свое время  Только вот работать кто за него будет непонятно


Это сообщение отредактировал(а) djars - 30.1.2009, 12:47

  

мне мужики задали это, это скорее всего не задание а "быдло-задание" с первого раза не понятно, я не на пи-ах-пи делал