siberian_cat (![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
siberian_cat) wrote2007-12-03 03:51 pm
siberian_cat) wrote2007-12-03 03:51 pm
Задачка по теории алгоритмов.
Есть некая подсистема, написанная нашими партнёрами. Подсистема пишет файлы на магнитооптику и блюрей. Файловая система - UDF.
Замечено, что с ростом количества файлов в директории - именно в директории, куда пишем, а не на диске - время записи файла увеличивается. На 10000 файлов становится ощутимо, на 15000 - просто невыносимо. Судя по графику, зависимость примерно экспоненциальная (!!!). (Во всяком случае, график выглядит именно так). Вопрос заключается в следующем: где у них вообще мог завестись экспоненциальный алгоритм? Всего-то нужно проверить, есть ли такое имя в директории, завести новую запись, записать, закрыть. Имена файлов они кешируют и хранят в простом списке; не самая эффективная структура в рассуждении поиска, но поиск-то, слава богу, линейный!
Загадка.
Замечено, что с ростом количества файлов в директории - именно в директории, куда пишем, а не на диске - время записи файла увеличивается. На 10000 файлов становится ощутимо, на 15000 - просто невыносимо. Судя по графику, зависимость примерно экспоненциальная (!!!). (Во всяком случае, график выглядит именно так). Вопрос заключается в следующем: где у них вообще мог завестись экспоненциальный алгоритм? Всего-то нужно проверить, есть ли такое имя в директории, завести новую запись, записать, закрыть. Имена файлов они кешируют и хранят в простом списке; не самая эффективная структура в рассуждении поиска, но поиск-то, слава богу, линейный!
Загадка.
no subject
Это не алгоритм завёлся, а глюк в алгоритме вероятно.
Как в истории про маляра. Которому поручили рисовать продольную разметку на дороге. В первый день он нарисовал сто метров. Начальник вечером его сильно хвалил. Во второй день он нарисовал пятьдесят. Начальник промолчал. А в третий день он нарисовал только десять метров разметки. И на недоумение начальника пояснил: "а как же иначе, ведь чем дальше я ухожу от ведра с краской, тем дальше мне нужно идти макать кисточку".