File-level, optionally external sorting

[PlatonB]

BPO	41678
Nosy	@rhettinger, @pablogsal, @sweeneyde, @PlatonB
Files	disksort.py: External sort for iterables proof of concept

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2020-09-04.17:45:27.307>
created_at = <Date 2020-08-31.16:01:22.707>
labels = ['type-feature', '3.10']
title = 'File-level, optionally external sorting'
updated_at = <Date 2020-09-04.17:45:27.306>
user = 'https://github.com/PlatonB'

bugs.python.org fields:

activity = <Date 2020-09-04.17:45:27.306>
actor = 'rhettinger'
assignee = 'none'
closed = True
closed_date = <Date 2020-09-04.17:45:27.307>
closer = 'rhettinger'
components = []
creation = <Date 2020-08-31.16:01:22.707>
creator = 'platon.work'
dependencies = []
files = ['49436']
hgrepos = []
issue_num = 41678
keywords = []
message_count = 9.0
messages = ['376157', '376168', '376174', '376178', '376179', '376332', '376333', '376334', '376391']
nosy_count = 4.0
nosy_names = ['rhettinger', 'pablogsal', 'Dennis Sweeney', 'platon.work']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue41678'
versions = ['Python 3.10']

[PlatonB]

Feature request: a convenient sorter of whole files with the possibility of disk usage. Here's the syntax in my mind:

shutil.sort(src, dst, headers=0, key=None, reverse=False, allow_disk_use=False)

[pablogsal]

What do you refer when you say "sorting a file"?

What does "key" act upon? Strings representing the lines in the file?

For allow_disk_use=False, what's the difference between opening the file, reading the lines, using sort() and writing the contents?

[PlatonB]

I mean Python's analog of sort [-k x.y] table.txt from GNU Coreutils.

> What do you refer when you say "sorting a file"?

Sorting a file with multi-line plain text. Optionally, text consisting of
several columns separated by a specific character.

> What does "key" act upon? Strings representing the lines in the file?

This is a sort rule argument similar to that of the existing in-memory
sort()/sorted() method.

> For allow_disk_use=False, what's the difference between opening the
file, reading the lines, using sort() and writing the contents?

If False, there is no difference.

вт, 1 сент. 2020 г. в 00:18, Pablo Galindo Salgado <report@bugs.python.org>:

Pablo Galindo Salgado <pablogsal@gmail.com> added the comment:

What do you refer when you say "sorting a file"?

What does "key" act upon? Strings representing the lines in the file?

For allow_disk_use=False, what's the difference between opening the file,
reading the lines, using sort() and writing the contents?

----------
nosy: +pablogsal

---

Python tracker <report@bugs.python.org>
<https://bugs.python.org/issue41678\>

---

[sweeneyde]

If we were to do this, I think a better API might be to accept an arbitrary iterable, then produce a sorted iterable:

def sorted_on_disk(iterable, key=None, reverse=False) -> Iterable:
    ...

It would sort chunks of the input and store them in files as sequences of pickles, merging them as they got bigger, and then return an iterator over the resulting single sorted file.

This would be more composable with other standard Python functions and would be a good way of separating concerns. sorted(...) and heapq.merge(...) already have the correct APIs to do it this way.

Potential implementation detail: For some small fixed n, always doing a 2^n-way heapq.merge instead of a bunch of 2-way merges would do fewer passes over the data and would allow the keys to be computed 1/n as many times, assuming we wouldn't decorate-sort-undecorate.

[sweeneyde]

Attached is a proof of concept.

[rhettinger]

This doesn't seem like something that should be in the standard library. It is more of an application than a building block for writing code. It is a good candidate for an external package on PyPI rather than the standard library.

[pablogsal]

I am of the same opinion as Raymond

[PlatonB]

Why is shutil.make_archive suitable for a standard library but the file sorter not?

[rhettinger]

Thanks for the suggestion, but Pablo and I agree that this isn't within scope for the standard library. Marking as closed.

If you want to discuss further, please post to the Python ideas list.