Как лучше всего организовать файлы в папках, чтобы найти их было удобно?

Какой алгоритм можно использовать для распределения N файлов по папкам таким образом, чтобы суммарный размер файлов в каждой папке не превышал 2 мегабайта, и при этом количество папок было минимальным?
  • 26 января 2024 г. 9:51
Ответы на вопрос 4
Организация файлов в папках должна соответствовать логике работы пользователя или системы, которая будет их использовать. В общем случае, разделение может быть выполнено по таким критериям, как тип файлов, дата создания, проект, в рамках которого они использовались, или иное деление, которое логически упорядочивает данные и облегчает доступ к ним. Образцы схем для организации файлов:

1. По типу: Изображения, Документы, Видео, Музыка, Архивы.
2. По проекту/задаче: ПроектА, ПроектБ, Личное, Работа.
3. По дате: 2023/Январь, 2023/Февраль, и т.д.
4. По автору или отделу: ОтделМаркетинга, ОтделРазработки.

Теперь определим алгоритм распределения N файлов по папкам так, чтобы суммарный размер файлов в каждой папке не превышал 2 МБ, и количество папок было минимальным.

Пример классического алгоритма, подходящего для этой задачи — это алгоритм упаковки в контейнеры (Bin Packing Problem). Известный упрощённый жадный алгоритм, решающий этот тип задачи — алгоритм First Fit или Best Fit.

Для First Fit алгоритма шаги могут быть следующими:
1. Отсортируйте файлы по убыванию размера (это необязательный шаг, но он может помочь сократить количество папок).
2. Создайте первую папку для файлов.
3. Перебирайте файлы по одному и размещайте каждый файл в первую папку, в которую он помещается, гарантируя, что суммарный размер не превысит 2 МБ.
4. Если файл не помещается в существующие папки, создайте новую папку и поместите в неё файл.
5. Продолжайте пункты 3 и 4, пока все файлы не будут распределены.

Алгоритм Best Fit работает похоже на First Fit, но вместо того чтобы размещать файл в первую папку, в которую он помещается, он ищет папку, в которую файл помещается наилучшим образом (с минимальным остатком места после добавления файла).

Обратите внимание, что эти алгоритмы не гарантируют нахождение оптимального решения для всех случаев, но являются хорошим компромиссом между качеством решения и временем выполнения. Вероятно, оптимальное решение потребовало бы применения более сложных алгоритмов или полного перебора возможных комбинаций, что может быть неосуществимо для большого количества файлов из-за экспоненциального роста вычислительной сложности.
Это задача об упаковке . Она сложная. И ближе даже не к задаче о рюкзаке, а к задаче о мульти-рюкзаке. Для больших размеров файлов и N решения, кроме переборного, нет. 

Если N маленькое, то есть быстрые алгоритмы вроде Динамического Программирования. Но там и перебор будет не то, чтобы сильно медленнее.

Если вам не важно получить абсолютно минимально возможное количество папок, то подойдет какое-нибудь жадное решение. Оно даст хорошее приближение. Скажем, вместо 30 идеальных папок вы часто получите 40.

Например, кладите файлы в текущую папку, пока они туда помещаются. Потом создавайте следующую папку. Заполняйте ее, пока размер папки + размер следующего файла <= 2Mb.

Можно всякие эвристики сюда навешивать: например, отсортиовали файлы по размеру. Жадно пихаем самые большие файлы, пока помещается. Потом жадно пихаем самые маленькие. Потом начинаем новую папку.
1. Сортируешь все файлы по размеру 
2. Берешь самый большой файл и помещаешь в первую папку
3. Дальше каждый файл по убыванию размера:
1. Находишь папку с наименьшим оставшимся размером, который позволяет добавить туда файл
2. Если таких нет - создаешь новую папку и кладешь туда
вам сюда 

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