Schwartzian sort example in "Text Processing in Python"

Question

I was browsing through "Text Processing in Python" and tried its example about Schwartzian sort.

I used following structure for sample data which also contains empty lines. I sorted this data by fifth column:
383230 -49 -78 1 100034 '06 text' 9562 'text' 720 'text' 867
335067 -152 -18 3 100030 'text' 2400 'text' 2342 'text' 696
136592 21 230 3 100035 '03. text' 10368 'text' 1838 'text' 977

Code used for Schwartzian sorting:

for n in range(len(lines)):       # Create the transform
    lst = string.split(lines[n])
    if len(lst) >= 4:             # Tuple w/ sort info first
        lines[n] = (lst[4], lines[n])
    else:                         # Short lines to end
        lines[n] = (['\377'], lines[n])

lines.sort()    # Native sort

for n in range(len(lines)):       # Restore original lines
    lines[n] = lines[n][1]

open('tmp.schwartzian','w').writelines(lines)

I don't get how the author intended that short or empty lines should go to end of file by using this code. Lines are sorted after the if-else structure, thus raising empty lines to top of file. Short lines of course work as supposed with the custom sort (fourth_word function) as implemented in the example.

This is now bugging me, so any ideas? If I'm correct about this then how would you ensure that short lines actually stay at end of file?

EDIT: I noticed the square brackets around '\377'. This messed up sort() so I removed those brackets and output started working.

else:                         # Short lines to end
    lines[n] = (['\377'], lines[n])
print type(lines[n][0])
>>> (type 'list')

I accepted nosklo's answer for good clarification about the meaning of '\377' and for his improved algorithm. Many thanks for the other answers also!

If curious, I used 2 MB sample file which took 0.95 secs with the custom sort and 0.09 with the Schwartzian sort while creating identical output files. It works!

Answer 1

I don't know what is the question, so I'll try to clarify things in a general way.

This algorithm sorts lines by getting the 4th field and placing it in front of the lines. Then built-in sort() will use this field to sort. Later the original line is restored.

The lines empty or shorter than 5 fields fall into the else part of this structure:

if len(lst) >= 4:             # Tuple w/ sort info first
    lines[n] = (lst[4], lines[n])
else:                         # Short lines to end
    lines[n] = (['\377'], lines[n])

It adds a ['\377'] into the first field of the list to sort. The algorithm does that in hope that '\377' (the last char in ascii table) will be bigger than any string found in the 5th field. So the original line should go to bottom when doing the sort.

I hope that clarifies the question. If not, perhaps you should indicate exaclty what is it that you want to know.

A better, generic version of the same algorithm:

sort_by_field(list_of_str, field_number, separator=' ', defaultvalue='\xFF')
    # decorates each value:
    for i, line in enumerate(list_of_str)):
        fields = line.split(separator)
        try:
             # places original line as second item:
            list_of_str[i] = (fields[field_number], line)
        except IndexError:
            list_of_str[i] = (defaultvalue, line)
    list_of_str.sort() # sorts list, in place
    # undecorates values:
    for i, group in enumerate(list_of_str))
        list_of_str[i] = group[1] # the second item is original line

The algorithm you provided is equivalent to this one.

Answer 2

An empty line won't pass the test

if len(lst) >= 4:

so it will have ['\377'] as its sort key, not the 5th column of your data, which is lst[4] ( lst[0] is the first column).

Answer 3

Well, it will sort short lines almost at the end, but not quite always.

Actually, both the "naive" and the schwartzian version are flawed (in different ways). Nosklo and wbg already explained the algorithm, and you probably learn more if you try to find the error in the schwartzian version yourself, therefore I will give you only a hint for now:

Long lines that contain certain text in the fourth column will sort later than short lines.

Add a comment if you need more help.

Answer 4

Not directly related to the question, but note that in recent versions of python (since 2.3 or 2.4 I think), the transform and untransform can be performed automatically using the key argument to sort() or sorted(). eg:

def key_func(line):
    lst = string.split(line)
    if len(lst) >= 4:             
        return lst[4]
    else:                        
        return '\377'

lines.sort(key=key_func)