Время поиска против последовательного чтения

Предположим, что на жестком диске у меня есть какой-то очень большой файл данных с последовательностью символов:

АБРДЗ....

Мой вопрос заключается в следующем, если голова позиционируется в начале файла, и мне нужно 5 символов через каждые 1000 позиций, будет ли лучше сделать поиск (так как я знаю, где искать) или просто иметь большой буфер который просто читает последовательно, а затем выполняет работу в памяти.

Наивно я бы ответил, что чтение «A», а затем поиск «V» быстрее, чем >> чтение всего файла до, скажем, позиции 200 (позиция «V»). Хорошо, это всего лишь пример, так как наименьший ввод-вывод составляет 512 байт.

Редактировать: мой предыдущий самонаивный ответ частично оправдан следующим случаем: учитывая файл размером 100 ГБ, мне нужны первый и последний символы; Здесь я, очевидно, сделал бы поиск .... правильно?

Может быть, есть компромисс между тем, как «долго» искать и сколько данных нужно получить?

Может ли кто-нибудь прояснить это для меня?


person DED    schedule 11.06.2012    source источник
comment
Огромное предположение, что файл есть и останется непрерывным!   -  person Tony Hopkinson    schedule 11.06.2012
comment
Верно, но должны же быть способы убедиться в этом, не так ли? Более того, дефрагментация причинит больше вреда последовательному чтению, чем поиску.   -  person DED    schedule 11.06.2012
comment
Обеспечение смежности не является бесплатным. Моделирование файлов с фреймами менее просто. Я бы подумал, что это почти так же повлияло на последовательное чтение и поиск. Ужасно так с интервалом в квартал или больше.   -  person Tony Hopkinson    schedule 12.06.2012
comment
У меня такой же вопрос. Мне нужно хранить часто используемые данные в очень большом файле. Мне удобнее хранить его в конце файла. Я хотел рассмотреть влияние на производительность: сильно ли повлияет ли поиск ближе к концу файла на производительность? Учитывая, что в фрагментированном файле блоков размером 4 КБ файловая система должна каким-то образом читать и перемещаться по связанному списку блоков, чтобы добраться до искомого местоположения! Будет ли время поиска эквивалентно времени чтения? Хранится ли список выделенных блоков где-то еще в непрерывном разделе, что улучшит время заполнения?   -  person Philibert Perusse    schedule 15.01.2013
comment
@PhilibertPerusse Я бы сказал: поместите часто используемые данные в начало файла, загрузите их в память и сохраните там.   -  person DED    schedule 29.01.2013


Ответы (1)


[ОБНОВЛЕНИЕ] Как правило, из ваших исходных чисел 5 из каждых 1000 (я предполагаю, что 5 байтов являются частью 1000, таким образом, количество ваших шагов составляет 1000), если ваше количество шагов меньше 2x ваш размер блока, чем мой первоначальный ответ, является довольно хорошим объяснением. Это становится немного сложнее, когда вы превысите 2-кратный размер блока HD, потому что в этот момент вы легко потратите время чтения, когда вы можете ускориться, ища прошлые неиспользованные (или в этом отношении ненужные ) HD-блоки.

[ORIGINAL] Что ж, это чрезвычайно интересный вопрос, и я считаю, что ответ на него не менее интересен (хотя и несколько сложен). Я думаю, что на самом деле это сводится к паре других вопросов, например, насколько велик размер блока, который вы реализовали на своем диске (или на диске, на котором будет работать ваше программное обеспечение). Если размер вашего блока составляет 4 КБ, то (истинный) минимум, который ваш жесткий диск может получить за один раз, составляет 4096 байт. В вашем случае, если вам действительно нужно 5 символов каждые 1000, то, если бы вы сделали это со ВСЕМ дисковым вводом-выводом, вы бы, по сути, перечитывали один и тот же блок 4 раза и выполняли 3 поиска между ними (ДЕЙСТВИТЕЛЬНО НЕ ЭФФЕКТИВНО).

Мое личное убеждение состоит в том, что вы могли бы (если хотите быть эффективными) в своем коде попытаться понять, каков размер блока используемого вами диска, а затем использовать это число размера, чтобы узнать, сколько байтов за раз вы используете. следует вывести в ОЗУ. Таким образом, вам не нужно было бы иметь ОГРОМНЫЙ буфер ОЗУ, но в то же время вам не нужно было бы искать, вы бы не тратили (или не выполняли) какие-либо дополнительные чтения.

ЭТО САМОЕ ЭФФЕКТИВНОЕ. Я не думаю, что он самый эффективный, но он может быть достаточно хорош для нужной вам производительности, кто знает. Я действительно думаю, что даже если головка чтения находится там, где вы хотите, если вы выполняете алгоритмическую работу в середине каждого прочитанного блока, а не читаете весь файл сразу, вы потеряете время в ожидании следующее вращение приводных дисков. Принимая во внимание, что если вы должны были прочитать все сразу, диск должен иметь возможность выполнять последовательное чтение всех частей файла одновременно. Опять же, не так просто, как если бы ваш файл действительно состоял из более чем 1 блока на вращающемся диске, вы можете пострадать, ЕСЛИ ваш диск не был дефрагментирован, поскольку ему, возможно, придется выполнять случайный поиск только для того, чтобы перейти к следующему блоку.

Извините за длинный ответ, но, как обычно, в вашем случае нет простого ответа.

Я действительно думаю, что общая производительность ВОЗМОЖНО будет лучше, если вы просто прочитаете весь файл сразу. Нет никакого способа убедиться в этом, так как каждая система будет иметь разные параметры настройки своего привода и т. д.

person trumpetlicks    schedule 11.06.2012
comment
Ага! Спасибо, вы правильно затронули мою проблему, если количество ваших шагов меньше 2-кратного размера вашего блока. Это выглядит как критерий того, когда поиск лучше. У вас есть ссылка на это? - person DED; 11.06.2012
comment
К сожалению, у меня нет ссылки на это, это из моего собственного опыта :-) Извините.... - person trumpetlicks; 11.06.2012