Пример сортировки Шварца в "Обработка текста в Python"

Question

Я просматривал "Обработка текста в Python" и попробовал пример о сортировке Шварца.

Я использовал следующую структуру для выборочных данных, которая также содержит пустые строки. Я отсортировал эти данные по пятому столбцу:
383230 -49 -78 1 100034 '06 текст '9562' текст '720' текст '867
335067 -152 -18 3 100030 'текст' 2400 'текст' 2342 'текст' 696
136592 21 230 3 100035 '03. текст '10368' текст '1838' текст '977

Код, используемый для сортировки по Шварцу:

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)

Я не понимаю, как автор предполагал, что короткие или пустые строки должны идти в конец файла с помощью этого кода. Строки сортируются после структуры if-else, в результате чего пустые строки поднимаются в начало файла. Короткие строки, конечно, работают так, как предполагалось, с помощью пользовательской сортировки (функция четвертое слово), реализованной в примере.

Это меня сейчас беспокоит, так что есть идеи? Если я прав в этом, то как бы вы обеспечили, чтобы короткие строки действительно оставались в конце файла?

РЕДАКТИРОВАТЬ: Я заметил квадратные скобки вокруг \ 377. Это испортило sort (), поэтому я снял эти скобки и вывод начал работать.

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

Я принял ответ Носкло за хорошее разъяснение значения «\ 377» и за его улучшенный алгоритм. Большое спасибо и за другие ответы!

Если любопытно, я использовал образец файла размером 2 МБ, который занимал 0,95 секунды с пользовательской сортировкой и 0,09 с с сортировкой Шварца при создании идентичных выходных файлов. Работает!

Answer 1

Не имеет прямого отношения к вопросу, но обратите внимание, что в последних версиях python (с версии 2.3 или 2.4, я думаю) преобразование и отсутствие преобразования могут выполняться автоматически с использованием аргумента key для sort() или sorted(). например:

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

lines.sort(key=key_func)

Answer 2

Я не знаю, в чем вопрос, поэтому я постараюсь прояснить ситуацию в общих чертах.

Этот алгоритм сортирует строки, получая 4-е поле и размещая его перед строками. Тогда встроенный sort() будет использовать это поле для сортировки. Позже оригинальная линия восстановлена.

Строки, пустые или короче 5 полей, попадают в else часть этой структуры:

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])

Добавляет ['\377'] в первое поле списка для сортировки. Алгоритм делает это в надежде, что '\ 377' (последний символ в таблице ascii) будет больше , чем любая строка, найденная в 5-м поле. Поэтому при выполнении сортировки исходная строка должна идти вниз.

Надеюсь, это проясняет вопрос. Если нет, возможно, вам следует указать, что именно вы хотите знать.

Лучшая, общая версия того же алгоритма:

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

Алгоритм, который вы указали, эквивалентен этому.

Answer 3

Хотя используемое преобразование Шварца для Python довольно устарело, стоит отметить, что вы могли бы написать код таким образом, чтобы исключить возможность сортировки строки со строкой [4], начинающейся с \377, в неправильную место

for n in range(len(lines)):
    lst = lines[n].split()
    if len(lst)>4:
        lines[n] = ((0, lst[4]), lines[n])
    else:
        lines[n] = ((1,), lines[n])

Поскольку кортежи сравниваются поэлементно, кортежи, начинающиеся с 1, будут always отсортированы по основанию.

Также обратите внимание, что тест должен быть len(list)>4 вместо >=

Та же логика применяется при использовании современной эквивалентной AKA функции key=

def key_func(line):
        lst = line.split()
        if len(lst)>4:
            return 0, lst[4]
        else:
            return 1,

lines.sort(key=key_func)

Answer 4

Ну, в конце будут отсортированы короткие строки почти , но не всегда.

На самом деле, и «наивная», и шварцевская версия ошибочны (по-разному). Nosklo и wbg уже объяснили алгоритм, и вы, вероятно, узнаете больше, если попытаетесь найти ошибку в версии Шварца, поэтому я покажу только подсказку:

длинные строки, содержащие определенный текст в четвертом столбце рассортирую позже чем короткие строки.

Добавьте комментарий, если вам нужна дополнительная помощь.

Answer 5

Пустая строка не пройдет тест

if len(lst) >= 4:

поэтому он будет иметь ['\ 377'] в качестве ключа сортировки, а не 5-й столбец ваших данных, который равен lst[4] (lst[0] - первый столбец).