Skip to content

Latest commit

 

History

History

practice_1.5

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
test_external_sort.py
test_external_sort.py
 
 

README.md

Практическая работа №5 "Алгоритмы внешней сортировки"

Реализовать консольную утилиту сортировки текстовых данных.

Предусмотреть:

  1. Интерфейс командной строки (CLI)
  2. Сортировку данных в форматах csv, txt.
  3. Для форматa csv необходимо указывать ключ сортировки, например, номер/наименование столбца в csv.
  4. Сортировку по невозрастанию/неубыванию
  5. Сохранение результата в новый файл (без изменения исходных)
  6. Сортировку нескольких файлов одного формата
  7. Многопоточную сортировку (указывать количество потоков)
  8. Ограничение на размер блока (по памяти) при разбиении исходных данных

При реализации запрещается считывать файлы целиком.

Алгоритмы:

  1. Естественное слияние
  2. Двухпутевое сбалансированное слияние
  3. N-путевое слияние
  4. Многофазная сортировка (Фибоначчиевая)
  5. Каскадное слияние

Требования к реализации

Реализуйте модуль external_sort.py, где должна быть функция my_sort (название должно соответствовать используемому алгоритму) с примерной сигнатурой:

PathType = Union[str, pathlib.Path]

my_sort(src: PathType, output: Optional[PathType]=None, reverse: bool=False,
		key: Optional[Callable]=None, nflows: int=1,
        bsize: Optional[int]=None) -> None

Описание аргументов:

  • src : исходный файл
  • output : выходной файл, если не указан файл src сортируется на месте
  • reverse: флаг определяющий вариант сортировки:
    False - по неубыванию
    True - по невозрастанию
  • key : функция, вычисляющая значение, на основе которого будет производится сортировка. Должна принимать один аргумент и возвращать значение.
  • nflows : количество потоков
  • bsize : размер блока, хранимого в памяти

Входные и выходные данные

Функция сортировки должна принимать абсолютный или относительный путь до исходного файла в формате csv или txt.

Результатом работы функции сортировки должен стать либо новый файл, либо тот же файл с отсортированными записями.

Для работы с путями рекомендуется использовать pathlib.

Методика оценивания

Оценка выставляется в соответствии со следующими требованиями:

  1. Общие требования:
    • код работы проходит проверку утилитой pylint с конфигурационным файлом .pylintrc.
    • код работы успешно проходит тесты, если таковые имеются.
    • наличие документации к функциям, методам, классам и модулям.
  2. На оценку 3 балла реализовать:
    • все вышеперечисленное;
    • пункты 1, 2 и 3.
  3. На оценку 4 балла дополнительно реализовать:
    • все вышеперечисленное;
    • пункты 4 и 5;
  4. На оценку 5 балла:
    • реализовать все требования, указанные в описании к работе, кроме 7 и 8.
  5. Плюс в карму:
    • все вышеперечисленное;
    • пункты 7, 8;

Полезные материалы