Навеяно вот этим сообщением
http://rsdn.ru/forum/alg/5003217.1Автор: watch-maker
Дата: 18.12.12
Господа, а не кажется ли вам, что их больше нет вообще ?
Поясню свою мысль.
Классические структуры прямого доступа — файл и массив.
Файл в раннедосовские времена (когда еще кэша не было) — безусловно структура прямого доступа. Да, для доступа к кластеру нужно просмотреть элементы FAT, но поскольку этих элементов на порядки меньше, чем число байтов в файле, то этим можно пренебречь, равно как и тем, что головка должна совершать различные перемещения — в среднем будет примерно одинаково. В остальном же время доступа к любому кластеру (а значит, и байту) не зависит от его номера в файле.
Но даже в те раннедосовские времена это было верно, пока не использовали stdio с ее буферизацией. С буферизацией — уже неверно, последовательное чтение намного быстрее произвольного. Ну а в наши времена, когда между моим запросом и файлом на диске сидит несколько кешей, это вообще неверно.
Массив. Опять же в раннедосовсеие времена скорость доступа не зависит от того, в каком порядке выбираем элементы. RAM, одним словом. Но и RAM у нас тоже больше нет, по крайней мере напрямую мы к ней не обращаемся. Есть несколько уровней кеша, да еще и подкачка, чего доброго, а они все хорошо работают при последовательном доступе и гораздо хуже при прямом.
Резюме : когда мы используем алгоритмы, требующие прямого доступа, надо отдавать себе отчет, что мы имеем дело фактически с компьютером, намного более медленным, чем мы считаем. Иными словами, если мы думаем, что со времен ДОС скорость работы машины увеличилась в N раз (я не обсуждаю многоядерность и многопоточность), то реально она увеличилась лишь в N/K раз.
А если это так, то не означает ли это , что надо озаботиться преобразованием алгоритмов, использующих прямой доступ, к некоторому иному виду, его не использующему ? Даже если поначалу кажется (из общих соображений), что это приведет к падению быстродействия ?
