Строки разной длины: MSD-сортировка и трёхпутевая поразрядная быстрая

Если ты знаешь, почему сравнения на строках с общим префиксом медленные, как устроены MSD и трёхпутевая поразрядная быстрая и чем MSD платит за маленькие корзины, листай до «Теперь сам».

Как думаешь, сколько стоит одно сравнение двух строк

Мы привыкли считать сравнение за единицу. Для чисел так и есть. А сравнение двух строк - это цикл: идём по символам, пока они совпадают, и решаем по первому несовпавшему.

Прежде чем читать дальше, ответь себе: сколько символов прочитает сравнение двух адресов https://shop.example/catalog/item/48213 и https://shop.example/catalog/item/48220? И сколько таких сравнений сделает сортировка двадцати тысяч похожих адресов?

На что это похоже

Расстановка книг по алфавиту на полке. Сравнивать каждую пару книг целиком, буква за буквой, никто не станет. Библиотекарь сначала раскладывает книги в стопки по первой букве автора, потом каждую стопку - по второй, и так далее. Каждую букву каждой фамилии он читает один раз, а не каждый раз, когда книга сталкивается с соседкой.

Правда, если на букву «Щ» всего две книги, заводить для них ещё тридцать три стопки по второй букве - смешно: проще поменять их местами руками. Это и есть главная слабость MSD-сортировки.

Механизм: две строковые сортировки

MSD (most significant digit - «от старшего символа»)
msd(a, d):                     строки a совпадают в первых d символах
    если в a ≤ 1 строки - готово
    разложить a подсчётом по символу d (кончившиеся строки - первыми)
    для каждой корзины: msd(корзина, d + 1)

Отличие от поразрядной сортировки из прошлой главы: там шли от МЛАДШЕЙ цифры и требовали равную длину ключей. MSD идёт от старшего символа, поэтому работает со строками любой длины и заглядывает только в распознающий префикс: строка, оказавшаяся в корзине одна, дальше не читается.

ТРЁХПУТЕВАЯ ПОРАЗРЯДНАЯ БЫСТРАЯ
q3(a, d):
    v = d-й символ первой строки            (опорный символ)
    разбить a на три части по d-му символу:
        меньше v | равно v | больше v
    q3(меньше, d)
    q3(равно, d + 1)        ← только тут переходим к следующему символу
    q3(больше, d)

Трёхпутевое разбиение - проход с тремя указателями: всё, что меньше опорного, сдвигается в начало, всё, что больше, - в конец, равные остаются посередине. Это та же быстрая сортировка из главы «Слиянием и быстрая», только опорным служит один символ, а не строка целиком, и средняя часть не выбрасывается, а уходит на следующий символ.

Правило

Сортировка сравнениями на строках стоит n·log n сравнений, и каждое перечитывает общий префикс - на строках с длинным общим началом это главная цена. Строковые сортировки читают символы распознающего префикса по одному-два раза. MSD раскладывает подсчётом по старшему символу и рекурсивно уходит в корзины; на маленьких корзинах её съедает массив счётчиков размером с алфавит, поэтому корзины меньше нескольких десятков строк досортировывают вставками. Трёхпутевая поразрядная быстрая делит по символу на «меньше, равно, больше» и к следующему символу отправляет только равных: счётчиков нет, длинные общие префиксы проходятся один раз.

Разбор: шесть строк трёхпутевой быстрой

вход: кот, кит, ток, как, кто, том        d = 0, опорный символ «к»

меньше «к»:  -
равно «к»:   кот, кит, кто, как           → на d = 1
больше «к»:  том, ток                     → снова d = 0

группа «к», d = 1, опорный «о» (из «кот»):
    меньше:  кит, как    → d = 1, опорный «и»: меньше «как», равно «кит»
    равно:   кот         → одна строка, готово
    больше:  кто
группа «т», d = 0, опорный «т»: обе равны → d = 1, опорный «о»: обе
    равны → d = 2, опорный «м» (из «том»): меньше «ток», равно «том»

итог: как, кит, кот, кто, ток, том

Обрати внимание: символ «к» в начале четырёх слов прочитан по разу на слово - один проход разбиения. Сравнения прочитали бы его при каждом столкновении этих слов, то есть много раз.

Разбор: три сортировки на словах и адресах

Программа сортирует по 20 тысяч строк тремя способами и считает прочитанные символы. Первый набор - случайные слова из восьми букв, второй - адреса страниц с общим префиксом в 34 символа. Сравнения считаем честно: каждое идёт по символам до первого различия.

import random

R = 128                                      # ASCII
stat = {}


def ch(s, d):
    stat["симв"] += 1
    return ord(s[d]) if d < len(s) else -1  # -1: строка кончилась


def msd(a, lo, hi, d):
    if hi - lo <= 1:
        return
    stat["счётч"] += R + 1
    count = [0] * (R + 2)
    for i in range(lo, hi):
        count[ch(a[i], d) + 2] += 1
    for r in range(R + 1):
        count[r + 1] += count[r]
    aux = [None] * (hi - lo)
    for i in range(lo, hi):
        c = ch(a[i], d) + 1
        aux[count[c]] = a[i]
        count[c] += 1
    a[lo:hi] = aux
    for r in range(R):                       # «кончилась» уже готова
        msd(a, lo + count[r], lo + count[r + 1], d + 1)


def q3(a, lo, hi, d):
    if hi - lo <= 1:
        return
    lt, gt, i = lo, hi - 1, lo + 1
    v = ch(a[lo], d)
    while i <= gt:
        t = ch(a[i], d)
        if t < v:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif t > v:
            a[gt], a[i] = a[i], a[gt]
            gt -= 1
        else:
            i += 1
    q3(a, lo, lt, d)
    if v >= 0:                               # равные идут на d + 1
        q3(a, lt, gt + 1, d + 1)
    q3(a, gt + 1, hi, d)


class Klyuch:                                # сравнение по символам
    def __init__(self, s):
        self.s = s

    def __lt__(self, other):
        d = 0
        while True:
            x, y = ch(self.s, d), ch(other.s, d)
            if x != y or x < 0:
                return x < y
            d += 1


def sravn(a, lo, hi, d):
    a[lo:hi] = [k.s for k in sorted(map(Klyuch, a[lo:hi]))]


rng = random.Random(7)
n = 20000
slova = ["".join(rng.choice("abcdefghij") for _ in range(8))
         for _ in range(n)]
prefiks = "https://shop.example/catalog/item/"
adresa = [prefiks + str(rng.randrange(10**6)) for _ in range(n)]
for imya, data in (("слова", slova), ("адреса", adresa)):
    for f in (sravn, msd, q3):
        a = data[:]
        rng.shuffle(a)
        stat["симв"] = stat["счётч"] = 0
        f(a, 0, len(a), 0)
        assert a == sorted(data)
        print(f"{imya:7} {f.__name__:6} символов {stat['симв']:9}"
              f"  ячеек счётчиков {stat['счётч']:8}")

слова   sravn  символов   1345406  ячеек счётчиков        0
слова   msd    символов    202802  ячеек счётчиков  1168740
слова   q3     символов    280726  ячеек счётчиков        0
адреса  sravn  символов  19015318  ячеек счётчиков        0
адреса  msd    символов   1563932  ячеек счётчиков  1148229
адреса  q3     символов    971672  ячеек счётчиков        0

Три вывода. Первый: на адресах сравнения прочитали в 20 раз больше символов, чем трёхпутевая быстрая, - каждое из n·log n ≈ 290 тысяч сравнений перечитывает 34 общих символа. Второй: MSD читает символы экономно (по два раза каждый: подсчёт и раскладка), но заводит больше миллиона ячеек счётчиков - на словах в пять с лишним раз больше, чем прочитала символов. Почти все её вызовы приходятся на корзины из двух-трёх строк, и каждый платит за 129 счётчиков. Третий: трёхпутевая быстрая без всяких счётчиков держится рядом с минимумом на обоих наборах. Поэтому в библиотеках строковых сортировок MSD всегда идёт с отсечкой «маленькую корзину - вставками», а трёхпутевую быструю берут как универсальный вариант.

Что ломается без этого

Сортировка миллионов путей файлов, URL или ключей с общим префиксом (user:12345:…, 2024-10-28T…) обычной сортировкой сравнениями тормозит пропорционально длине префикса, и профиль показывает время не в сортировке, а в сравнении строк. Вторая ошибка - MSD без отсечки и с большим алфавитом: для Юникода алфавит в сотни тысяч символов, и каждый рекурсивный вызов заводит такой массив - память и время уходят на нули. Третья - забыть про кончившиеся строки: «кот» должен стоять раньше «котёнок», и у MSD для этого нужна отдельная корзина «строка кончилась» перед всеми символами.

Зачем это в работе

Строковые сортировки сидят внутри индексов полнотекстового поиска и словарей сжатия: там сортируют миллионы окончаний одного текста, у которых общие префиксы бывают длинными. Базы данных при сортировке строковых ключей используют те же приёмы: сравнивают сначала короткий «нормализованный префикс» из нескольких байт целиком, а полное сравнение запускают только при совпадении. Когда сортировка строк в твоём коде оказывается узким местом, первая мысль - не ускорять сравнение, а перестать перечитывать общие префиксы.

Теперь сам

Отсортируй трёхпутевой поразрядной быстрой строки ab, b, abc, a, abd (опорный символ - у первой строки группы). Сколько раз прочитан первый символ строки abc?

d = 0, опорный «a» (из ab):   равно ab, abd, abc, a    больше b
d = 1, опорный «b»:           меньше a (строка кончилась - меньше
                              любого символа)          равно abd, abc, ab
d = 2, опорный «d» (из abd):  меньше abc, ab           равно abd
d = 2, опорный «c»:           меньше ab (кончилась)    равно abc
итог: a, ab, abc, abd, b