Задачка по теории алгоритмов.

[siberian_cat]

Есть некая подсистема, написанная нашими партнёрами. Подсистема пишет файлы на магнитооптику и блюрей. Файловая система - UDF.

Замечено, что с ростом количества файлов в директории - именно в директории, куда пишем, а не на диске - время записи файла увеличивается. На 10000 файлов становится ощутимо, на 15000 - просто невыносимо. Судя по графику, зависимость примерно экспоненциальная (!!!). (Во всяком случае, график выглядит именно так). Вопрос заключается в следующем: где у них вообще мог завестись экспоненциальный алгоритм? Всего-то нужно проверить, есть ли такое имя в директории, завести новую запись, записать, закрыть. Имена файлов они кешируют и хранят в простом списке; не самая эффективная структура в рассуждении поиска, но поиск-то, слава богу, линейный!

Загадка.

Comments

[tor-ont.livejournal.com]

где у них вообще мог завестись экспоненциальный алгоритм?
Это не алгоритм завёлся, а глюк в алгоритме вероятно.

Как в истории про маляра. Которому поручили рисовать продольную разметку на дороге. В первый день он нарисовал сто метров. Начальник вечером его сильно хвалил. Во второй день он нарисовал пятьдесят. Начальник промолчал. А в третий день он нарисовал только десять метров разметки. И на недоумение начальника пояснил: "а как же иначе, ведь чем дальше я ухожу от ведра с краской, тем дальше мне нужно идти макать кисточку".