Сортировка файлов по расширению python
Обновлено: 06.07.2024
В этой статье мы вкратце расскажем, какие есть основные алгоритмы сортировки и каковы их главные характеристики. Также по каждому алгоритму покажем реализацию на Python.
Искусство наведения порядка
Расположение элементов в определенном порядке улучшает поиск элемента. Следовательно, сортировка широко используется в информатике.
В данной статье мы рассмотрим обычные алгоритмы сортировки и их реализации на Python. Для сравнения их производительности мы будем рассматривать задачу с сайта Leetcode о сортировке массива. Размеры данных этой задачи ограничены следующим образом:
Мы решили эту задачу при помощи всех известных алгоритмов сортировки. Вот какие у нас получились результаты:
Сортировка методом пузырька
Это самый простой алгоритм сортировки. В процессе его выполнения мы перебираем наш список и на каждой итерации сравниваем элементы попарно. При необходимости элементы меняются местами, чтобы больший элемент отправлялся в конец списка.
- нерекурсивный;
- устойчивый;
- преобразует входные данные без использования вспомогательной структуры данных (in place);
- имеет сложность O(n 2 );
Сортировка выбором
В этом алгоритме мы создаем два сегмента нашего списка: один отсортированный, а другой несортированный.
В процессе выполнения алгоритма мы каждый раз удаляем самый маленький элемент из несортированного сегмента списка и добавляем его в отсортированный сегмент. Мы не меняем местами промежуточные элементы. Следовательно, этот алгоритм сортирует массив с минимальным количеством перестановок.
- нерекурсивный;
- может быть как устойчивым, так и неустойчивым;
- преобразует входные данные без использования вспомогательной структуры данных (in place);
- имеет сложность O(n 2 );
Сортировка вставками
Подобно алгоритму сортировки выбором, мы делим наш список на две части. Далее мы перебираем неотсортированную часть и вставляем каждый элемент из данного сегмента на его правильное место в отсортированной части списка.
- нерекурсивный;
- устойчивый;
- преобразует входные данные без использования вспомогательной структуры данных (in place);
- имеет сложность O(n 2 );
Марк Лутц «Изучаем Python»
Скачивайте книгу у нас в телеграм
Сортировка Шелла
Сортировка Шелла является оптимизированным вариантом сортировки вставками.
Оптимизация достигается путем сравнения не только соседних элементов, но и элементов на определенном расстоянии, которое в течении работы алгоритма уменьшается. На последней итерации это расстояние равно 1. После этого алгоритм становится обычным алгоритмом сортировки вставками, что гарантирует правильный результат сортировки.
Но следует отметить один момент: к тому времени, когда это произойдет, наш массив будет почти отсортирован, поэтому итерации будут выполнятся очень быстро.
- нерекурсивный;
- устойчивый;
- преобразует входные данные без использования вспомогательной структуры данных (in place);
- имеет сложность O(n 2 ), но это также зависит от выбора длины интервала;
Как и в двух предыдущих алгоритмах, мы создаем два сегмента списка: отсортированный и несортированный.
Метод heapify в примере кода использует рекурсию для получения элемента с максимальным значением на вершине.
- нерекурсивный;
- неустойчивый;
- преобразует входные данные без использования вспомогательной структуры данных (in place);
- имеет сложность O(nlog(n));
Сортировка слиянием
Здесь мы делим список ровно пополам и продолжаем это делать, пока в нем не останется только один элемент. Затем мы объединяем уже упорядоченные части нашего списка. Мы продолжаем это делать, пока не получим отсортированный список со всеми элементами несортированного входного списка.
- рекурсивный;
- устойчивый;
- требует дополнительной памяти;
- имеет сложность O(nlog(n));
Быстрая сортировка
В этом алгоритме мы разбиваем список при помощи опорного элемента, сортируя значения вокруг него.
В нашей реализации мы выбрали опорным элементом последний элемент массива. Наилучшая производительность достигается тогда, когда опорный элемент делит список примерно пополам.
- рекурсивный;
- неустойчивый;
- преобразует входные данные без использования вспомогательной структуры данных (in place);
- имеет сложность O(nlog(n));
Сортировка подсчетом
Этот алгоритм не производит сравнение элементов. Для сортировки используются математические свойства целых чисел. Мы подсчитываем вхождения числа в массиве и сохраняем результат во вспомогательном массиве, где индексу соответствует значение ключа.
- нерекурсивный;
- устойчивый;
- преобразует входные данные без использования вспомогательной структуры данных (in place), но все же требует дополнительной памяти;
- имеет сложность O(n);
Следует также упомянуть поразрядную сортировку, которая использует сортировку подсчетом либо блочную (корзинную) сортировку в качестве подпрограммы. Этот метод сортировки заслуживает отдельной статьи для разбора.
Для удобства соберем весь наш код вместе:
Испытав все эти алгоритмы, мы ради любопытства запустили встроенную в Python функцию sorted() . Она показала весьма быстрое время в 152 мс. В данной функции используется алгоритм Timsort, который сочетает в себе сортировку слиянием и сортировку вставками. Реализация данного алгоритма также может быть рассмотрена в отдельной статье.
Мы нашли потрясающий плейлист, в котором алгоритмы сортировки демонстрируются при помощи народного танца. Посмотрите это видео, оно того стоит!
Штош. Скорее всего, у многих в папке загрузок собиралась куча разных инсталляторов, архивов и прочих файлов. Намного проще найти нужное, когда папки отсортированы в едином стиле. Вот я и подумал, почему бы не написать скрипт сортировщика по расширениям файлов на Python?
Пишем код
Для начала импортируем стандартный модуль os для работы с операционной системой. С помощью этого модуля мы будем создавать папки и перемещать файлы.
Чтобы создать папку, используем метод os.mkdir()
Создаем много папок
Напишем функцию для создания папок из списка названий. Для каждого названия проверяем существование папки с помощью метода os.path.exists().
Теперь давайте создадим словарь extensions. Ключи - названия папок. Значения - расширения файлов для каждой отдельной папки.
Передаем в функцию create_folders_from_list() новоиспеченный словарь. Папки создадутся из названий ключей.
Получаем пути подпапок и файлов
Пишем функцию для получения путей подпапок. Для каждого объекта в методе os.scandir() проверяем, является ли он каталогом.
Можно создать функцию получения имен подпапок, которая нам не пригодится дальше. Почему бы и нет? На самом деле, как сниппет для дальнейших проектов она может быть полезна.
Нам нужно взять пути подпапок, разделить по бэкслэшам строку и взять последний элемент.
Теперь получим пути всех файлов в папке, скопируем функцию get_subfolder_paths() и добавим в условие генератора not.
Для полного счастья не хватает только функции получения имен файлов.
Сортируем файлы
Приступаем к функции сортировки. Получаем пути файлов в переменную file_paths. Создаем переменную ext_list со списком метода словаря extensions.items(). Обращение к списку по индексу возвращает нам пару ключ-значение в виде списка, первый элемент которого - это ключ или название папки в нашем проекте, а второй элемент - это значение, то есть расширения файлов для этой папки.
Теперь создадим цикл для каждого пути файла в списке. Вытащим отдельно расширение и имя файла.
Создадим еще один цикл внутри. Для каждого ключа в словаре мы проверяем, есть ли расширение файла в списке расширений. Если есть, то перемещаем файл.
Сделать это можно при помощи изменения пути файла методом os.rename("Путь файла сейчас", "Будущий путь файла")
Готовая функция сортировки файлов:
Удаляем пустые папки
Остался последний штрих - удаление пустых папок. Все просто. Создаем функцию. Получаем пути подпапок. Проверяем, какой список возвращает метод os.listdir("folder_path") для каждой подпапки. Если возвращается пустой список, значит удаляем папку с помощью os.rmdir("folder_path")
Полный код программы
Настройка программы под свои нужды
Как вы уже могли понять, программа довольно гибкая, и вы можете настроить ее под себя. Для этого нужно всего-лишь изменить словарь extensions.
Приведу пример. Для каждого видео на свой YouTube канал я создаю каталог, в котором есть папки для футажей, картинок, звука, mkv файлов для последующего конвертирования в mp4 (premiere не любит mkv) и самого проекта.
Вот такой словарь.
С помощью такого подхода я могу накидать любые файлы для монтажа в одну папку, затем запустить скрипт и легко импортировать все это дело в premiere pro.
Заключение
Штош. Код лежит на GitHub. Берите, изменяйте под себя, пользуйтесь на здоровье. Буду рад любому фидбеку.
UPD. Доработал программу, учитывая (не все) замечания в комментариях. Статью не переписывал, мне лень.
Вместо os.path.* и прочих лучше использовать pathlib, а вместо range(len(list)) — enumerate(list) .
main_path стоит сделать параметром скрипта.
А чем pathlib лучше?
В связи с потенциально большим количеством файлов в папке, лучше использовать генераторы
Примерно о таких:
То, что вы назвали генератором — таковым не является. Вы даже в аннотации к функции указали результатом тип list и именно его и возвращаете.
Если бы это действительно было генератором, выглядело бы оно примерно так.
Работать с путями куда проще и правильней при помощи стандартного os.path.join и os.path.split.
Насчет os.path.join и split согласен.
Меньше памяти. Вместо огромного списка из 100500 строк получаешь небольшой итератор.
Как заставить себя придумывать годные имена для переменных? Чтобы не однобуквенные, но немногословные, друг на друга непохожие, осмысленные, и в одном стиле? ;)
нужно найти какой-то файл. Вот я и подумал, почему бы не написать скрипт сортировщика по расширениям файлов на Python?
Соррян. Так нужно файл найти или отсортировать? Вроде хотели одно, а делаем другое.
У старика Кнута это прям разные главы были. Из того, что я помню, это более эффективный поиск по отсортированной последовательности, но у вас явно не про это.
ЗЫ Вроде в виндоусе есть даже встроенный поиск. Даже я помню вечно тормозящая служба индексера была, да да! Что-то вы странное делаете.
Плохо написал первый абзац, заметил это, но не стал исправлять, так как не нашел более подходящих слов. Я думаю, по заголовку статьи и содержанию можно все-таки понять, что задача именно в сортировке файлов по папкам.
Решил организовать в едином стиле папки с большим количеством файлов + чуть-чуть покодить В качестве задачи со звёздочкой можно реализовать в исключительных случаях определение типа файла не по названию расширения, а по каким-нибудь мета-данным. Допустим .ts используется и для исходных файлов языка typescript, и для видеофайлов. Интересное предложение, реализовывать я его, конечно же, не буду :)
P.S. Вы действительно имели дело с видеофайлами .ts? Я впервые от вас узнал, что такое существует.
Когда я пропускаю какие-то интересные мне спортивные трансляции по телевизору, то скачиваю записи через торрент. Иногда их выкладывают в формате .ts. Я был и сам удивлён в первый раз, когда только что скачанный файл мне предложили открыть vscodo'м.
Штош. Скорее всего, у многих в папке загрузок собиралась куча разных инсталляторов, архивов и прочих файлов.
Посмотрел бы я как вы запустите инсталлятор, после вашей сортировки, исключение только если инсталлятор идет одним файлом.
По тексту статьи она совсем об другой сортировке, сильно специфичной.
Да, если инсталлятор идет не одним файлом, будет грустно. Можно закомментировать в словаре папку exe, как вариант решения проблемы.Во первых, если в папке Downloads завелись файлы setup.exe, setup(1).exe. то самый разумный способ автоматической сортировки - Ctrl+A Del. Никто никогда не вспомнит, что это за инсталляторы. Нет смысла их куда то перекладывать.
Во вторых, если было при скачивании лень нажать save as - значит, скачивалось что то одноразовое. Могу предложить отсортировать файлы по дате и удалить все что старше 1 месяца.
Не забывайте про os.path.join()
а если так? не проще…
Для конечного потребителя не проще. В скрипте нужно лишь поменять переменную пути каталога и настроить словарь extensions под свой метод сортировки.
В cmd тоже можно использовать переменные ;) А строк получается значительно меньше. Получается, так проще.
Еще раз, для конечного потребителя (обычного юзера, не для энтузиастов с хабра, знающих про ROBOCOPY в cmd) это не проще. Куда легче набрать в текстовом редакторе путь каталога, названия папок и расширения (а можно использовать типовые), чем вот это вот все.Ваше решение более чем интересное, но, наверное, стоит начать с того. что обычные пользователи пользуются исключительно мышкой и не ходят на Хабр =)
а папка %HOMEPATH%\Downloads обычно является просто свалкой, наравне с %TEMP% и %TMP%
К вашему решению для обычного пользователя осталось добавить gui для настройки и инсталлятор с вэб установщиком интерпретатора.
Это слишком длинный путь ;)
Простой способ решения проблемы файлопомойки - сортировка средствами файл менеджера, перенос нужного, удаление ненужного. Написание кода тут совершенно лишнее. :Ь
Хорошо, вы правы.Извините, что потратил ваше время на чтение этой статьи и написание 4 комментариев
Да я понимаю, что решать разные задачи на питоне это прикольно ;) Но не всегда код на питоне это лучшее решение. И ваша задача - отличная иллюстрация для этого утверждения ;)
Вы никак не угомонитесь, все вас поняли, спасибо. Я зря писал программу. Решил в лоб, знал про os.listdir и os.scandir. Нужны были пути папок и файлов отдельно. Сделал.С os.walk не приходилось встречаться, хотя если так подумать, с ним очень просто реализовать многоуровневую сортировку.
Привет. Буквально вчера перебирал file_cache на сервере, папка для временных файлов, которые необходимы пользователям. У нас уже было создано нечто подобное сортировке из статьи. За 6 лет функция обросла многими доработками. Потому расскажу, какие сложности встречались в этой, казалось бы, банальной задаче:
Предпосылки — 100 гигабайт хранилище, 350 000 файлов, расширения png, gif, ico, jpeg, svg, webp, tiff, pdf, tmp, html, xml, xls, xslx, doc, docx, js, css. Видео ни разу не встречал, хоть и можно. И бесконечное количество файлов с .tmp, .temp или без расширений. Адобовские еще файлы какие то AI, PSD… и т.п.
Сложности:
1. Как уже в комментариях сказали — расширение файла не говорит ничего. Хуже того, если отсортировать картинки по расширению, не проверив, для последующей пакетной обработки, например, в PhotoShop или программно в том же PIL — все упадет. Хорошо так упадет.
Для проверки переимовываем xxxxx.jpg в yyyy.jpg и открываем в photoshop.
В итоге мы стали использовать Fleep автор Mykyta Paliienko. Эта утилита сообщает о типе файла по содержимому. Кстати пришлось доработать «fleeper» до рабочего состояния, в issue автору тоже сообщили.
2. Файлы с именами, написанными через точку, и без расширений. Отдельная задача, поскольку формально расширение есть.
Решилось так же флиппером.
В коде git статьи extension получается через fp.split('.')[-1], это аналог os.path.splitext(fp) и оба не помогут в решении пункта 2, но os.path.splitext более «кошерный» в случае работы с файловой системой.
3. Также в комментариях сказали про однострочные генераторы. Как в статье так и GIT с примером кода, используются листы или функции генераторов, даже там, где достаточно однострочного генератора, который может делать еще и полезную работу:
Если кого расстраивают длинные строки, например линтер black прям беснуется, то можно так же сделать генераторный pipline:
4. Создание папок, и, потом, удаление пустых папок — выглядит вычурно. Если есть словарь хранящий < расширение: путь >, тогда проще получать путь из словаря и создавать путь, если словарь вернул пустое значение.
Решение — использовать стандартный логгер Python c выводом в консоль/файл управляя выводом через атрибуты запуска.
Многим из нас знакома ситуация, когда компьютер оказывался завален тоннами беспорядочных файлов. Только что вы открывали большой zip-архив, спустя мгновение – файлы повсюду в этой директории, вперемешку с важными документами. Наверняка приходилось мучительно скучно сортировать эту свалку вручную? Чтобы облегчить подобные задачи, мы сейчас погрузимся в «умную» работу с файлами при помощи Python.
Итак, приступим, вооружившись Python версии 3.4 или выше. Сначала пройдемся по модулю OS, а по ходу дела познакомимся еще с несколькими. Всё, что мы будем использовать, доступно в Python «с коробки», так что ничего дополнительно устанавливать не потребуется.
Генератор случайных файлов
Чтобы поиграться с файлами, мы сгенерируем их случайным образом в директории RandomFiles . Создайте файл create_random_files.py в папке ManageFiles . Вот что должно получиться:
Готово? Теперь поместите в файл следующий код, и перейдем к его рассмотрению:
Начиная с Python 3.4 мы получили pathlib, нашу маленькую волшебную палочку. Также мы импортируем функцию random для генерации случайных чисел, но ее мы посмотрим в действии чуть ниже.
Сперва создадим список файловых расширений для формирования названий файлов. Не стесняйтесь добавить туда свои варианты.
Далее мы переходим в папку RandomFiles и запускаем цикл. В нем мы просто говорим: возьми каждый элемент list_of_extensions и сделай с ним кое-что во внутреннем цикле 20 раз.
Теперь пришло время для импортированной функции random . Используем ее для производства случайных чисел от 1 до 50. Это просто не очень творческий способ побыстрее дать названия нашим тестовым файлам: к сгенерированному числу добавим расширение файла и получим что-то вроде 23.txt или 14.txt . И так 20 раз для каждого расширения. В итоге образуется беспорядок, достаточный для того, чтобы его было лень сортировать вручную.
Итак, запустим наш генератор хаоса через терминал.
Поздравляю, теперь у нас полная папка неразберихи. Будем распутывать.
В той же директории, где create_random_files.py , создадим файл clean_up.py и поместим туда следующий код.
Способ 1
Для этого импортируем еще две библиотеки: shutil и glob. Первая поможет перемещать файлы, а вторая – находить и систематизировать. Но обо всем по порядку.
Для начала получим список всех файлов в директории.
Здесь мы предполагаем, что у нас нет ни малейшего понятия о том, какие именно файлы лежат в этой папке. Вместо того, чтобы вписывать все расширения вручную и использовать лестницу инструкций if или switch, мы желаем, чтобы программа сама просмотрела каталог и определила, на какие типы можно разделить его содержание. Что, если бы там были файлы с десятками расширений или логи? Вы бы стали описывать их вручную?
Получив список всех файлов, мы заходим в еще один цикл, чтобы извлечь расширения названий.
Сейчас наша переменная our_file выглядит как-нибудь так: 5.docx . Когда разделим ее, получим следующее:
Мы возьмем отсюда второй элемент по индексу [1], то есть .docx . Ведь по индексу [0] у нас располагается 5 .
Таким образом, у нас имеется список всех файловых расширений в папке, в том числе повторяющихся. Чтобы оставить только уникальные элементы, преобразуем его во множество. К примеру, если бы этот список состоял исключительно из .docx , повторяющегося снова и снова, то в set остался бы всего один элемент.
Заметим, что в списке типов файлов каждое расширение содержит . в начале. Если мы назовем так папки на UNIX-системе, то они будут скрытыми, что не входит в наши намерения.
Поэтому, итерируя по нашему множеству, мы заменяем точку на пустую строку. И создаем папку с полученным названием.
Но чтобы переместить файлы, нам все еще нужно расширение .docx .
Этим попросту отбираем все файлы, оканчивающиеся расширением .docx . Заметьте, что в f'*.') нет пробелов.
Символ подстановки * обозначает, что подходит любое имя, если оно заканчивается на .docx . Поскольку мы уже включили точку в поиск, мы используем [1:], что значит «все после первого символа». В нашем примере это docx .
Что дальше? Перемещаем любые файлы с данным расширением в директорию с тем же названием.
Таким образом, как только в цикле создана папка для первого попавшегося файла с данным расширением, все последующие файлы будут отправлены в нее же. Все будет сгруппировано без повторения каталогов.
Способ 2
В качестве хитрого способа создать список в одну строку можно использовать генераторы.
Оба варианта сработают, и все ваши файлы будут отсортированы по расширению.
Вот и все. Если вам когда-либо понадобится отсортировать файлы таким образом, вы сэкономите немало времени 😊. Код упражнения доступен здесь.
Читайте также: