Сергей Деревяго

Сортировка быстрее возможного



1. Введение

Опять сегодня снова переводы:
  1. Алгоритм сортировки DerSort
  2. DersCountsort: три независимых этапа
Необходимые для Счастья функции уже доступны на любимом Go. И если больше ничего не надобно, то можно сразу же давить на Каталог.

Но есть еще и небольшая Революция... И для нее уже читаем сплошняком!

С уважением, Сергей Деревяго.


2. Производительность

Итак, начнем от той же печки:

perf\perf2\main.go
const (
    N = 1000000
    M = 100
)

func GoSort(arr []int32, out []int32) {
    for i := 0; i < len(arr); i++ {
        out[i] = int32(i)
    }

    slices.SortFunc(out, func(a, b int32) int {
        return cmp.Compare(arr[a], arr[b])
    })
}

func main() {
    // ...

    v := make([]int32, N)
    for i := 0; i < N; i++ {
        v[i] = int32(rand.Intn(card))
    }

    s1, s2, s3 := make([]int32, N), make([]int32, N), make([]int32, N)

    var dbuf lib.DersCountBuf
    cnts := make([]int32, card)
    ids := make([]uint16, N)
    lib.DersCountIds(v, cnts, ids, func(p *int32) uint16 { return uint16(*p) })

    t1 := time.Now().UnixMilli()
    for j := 0; j < M; j++ {
        GoSort(v, s1)
    }
    t2 := time.Now().UnixMilli()
    for j := 0; j < M; j++ {
        lib.DersCountSort(&dbuf, ids, nil, cnts, nil, s2, func(p *uint16) uint16 { return uint16(*p) })
    }
    t3 := time.Now().UnixMilli()
    for j := 0; j < M; j++ {
        DersCountSort_uint16(&dbuf, ids, nil, cnts, nil, s3)
    }
    t4 := time.Now().UnixMilli()

    for i := 0; i < N; i++ {
        lib.Assert(v[s1[i]] == v[s2[i]])
        lib.Assert(s2[i] == s3[i])
    }

    fmt.Printf("go\t%d\t%d\n", card, t2-t1)
    fmt.Printf("my1\t%d\t%d\n", card, t3-t2)
    fmt.Printf("my2\t%d\t%d\n", card, t4-t3)
}

На той же машине, все тот миллион:

cardgomy1my2go/my1go/my2
220592513308.26.2
10365524913614.726.9
100749226010928.868.7
10001110428619338.857.5
100001450144843432.433.4
655351745354556132.031.1

И мы в итоге обгоняем go от 6 до 70 раз!!

Я только обращу внимание, что DersCountSort_uint16() -- это конкретный DersCountSort() без generics и компаратора, т.е. ОБЯЗАН быть быстрее! А он местами не быстрее... Немного неожиданно, не так ли?

А сейчас вспомним C++:

cardstddersstd/ders
2211210719.7
1032149932.5
100510710648.2
1000669619135.1
10000816039620.6
65535955252418.2

И тут все четенько: колонка ders везде быстрее Go! Хотя местами только на один процент... Кругом сплошная неожиданность!

Но, если все-таки смотреть на чистый Go, то my1 и my2 в десятки раз опережают slices.SortFunc()! Что наполняет Смыслом наше времяпровождение.


3. Каталог функций

3.1. DerSort()

lib\dersort.go
func DerSort[S ~[]E, E any](arr S, out []int16, less func(pa *E, pb *E) bool)

Подробности:

  1. DerSort() никак не изменяет слайс arr! Он создает перестановку в out.
  2. Перестановка -- это массив позиций. Присвойте arr2[out[i]]=arr[i] и вы получите отсортированный слайс arr2.
  3. Во время вызова аргумент out должен быть слайсом int16 той же длины, что и arr.
  4. Компаратор less должен возвращать true, если *pa<*pb.

3.2. DerSortAppend()

lib\dersort.go
func DerSortAppend[S ~[]E, E any, E2 SeqElem](arr S, perm []E2, less func(pa *E, pb *E) bool)

Подробности:

  1. DerSortAppend() никак не изменяет слайс arr! Он дополняет перестановку.
  2. Во время вызова аргумент perm должен быть слайсом E2 той же длины, что и arr. Последний элемент перестановки будет перезаписан, а предыдущие изменены.
  3. По сути, DerSortAppend() включает последний элемент слайса arr в уже готовую перестановку на единицу меньшей длины.
  4. Компаратор less должен возвращать true, если *pa<*pb.

3.3. DersOversort()

lib\dersort.go
func DersOversort[S ~[]E, E any, E2 SeqElem](arr S, out []E2, cmp func(pa *E, pb *E) int)

Подробности:

  1. DersOversort() возвращает последовательность! А для получения перестановки, как у DerSort(), нужно вызвать ToSequence().
  2. DersOversort() не устойчив! Т.е. позиции одинаковых элементов будут отличаться от DerSort().

3.4. ToSequence()

lib\dersort.go
func ToSequence[E SeqElem](arr []E, out []E)

Подробности:

  1. ToSequence() создает последовательность из перестановки. А также перестановку из последовательности.
  2. Во время вызова аргумент out должен быть слайсом E той же длины, что и arr.

3.5. DersCountIds()

lib\derscountsort.go
func DersCountIds[S ~[]E, E any](arr S, cnts []int32, ids []uint16, idnt func(p *E) uint16)

Подробности:

  1. DersCountIds() подсчитывает количества уникальных элементов слайса arr и возвращает их в cnts.
  2. Во время вызова аргумент cnts должен быть слайсом int32 длины card (кардинальность arr).
  3. Если передан ids, то он должен быть слайсом uint16 той же длины, что и arr. В него будут записаны идентификаторы элементов.
  4. Функтор idnt должен возвращать идентификатор элемента *p (т.е. значение от 0 до card-1).

3.6. DersCountSort()

lib\derscountsort.go
func DersCountSort[S ~[]E, E any](buf *DersCountBuf, arr S, prev []int32, cnts []int32, seq []uint16,
    out []int32, idnt func(p *E) uint16)

Подробности:

  1. DersCountSort() никак не изменяет слайс arr, а создает последовательность в out.
  2. Последовательность -- это массив позиций. Возьмите arr[out[i]] и вы получите отсортированный слайс.
  3. Во время вызова аргумент out должен быть слайсом int32 той же длины, что и arr.
  4. buf -- просто буфер. Никакой магии: создайте где-нибудь DersCountBuf и много раз его передавайте.
  5. prev -- результат предыдущей сортировки: последовательность той же длины, что и arr. Передавайте, только если нужно досортировать слайс по другому ключу.
  6. cnts -- слайс счетчиков длины card (кардинальность arr), результат DersCountIds().
  7. seq -- cортирующая последовательность длины card. Не передавайте тривиальную последовательность.
  8. Функтор idnt должен возвращать идентификатор элемента *p (т.е. значение от 0 до card-1).

4. Ускорение

Ну а теперь опять производительность! Вы ж не забыли достославную DersCountSort_uint16()?

perf\perf2\main.go
func DersCountSort_uint16(buf *lib.DersCountBuf, arr []uint16, prev []int32, cnts []int32, seq []uint16,
    out []int32) {
    lib.Assert(len(arr) <= math.MaxInt32)
    lib.Assert(len(cnts) <= math.MaxUint16)
//D5|    lib.Assert(len(out) == len(arr))

    buf.Reserve(len(cnts))
    pos := buf.Pos

    sum := int32(0)
    if seq != nil {
//D5|        lib.Assert(len(seq) == len(cnts))

        for i := 0; i < len(cnts); i++ {
            si := seq[i]
            pos[si] = sum
            sum += cnts[si]
        }
    } else {
        for i := 0; i < len(cnts); i++ {
            pos[i] = sum
            sum += cnts[i]
        }
    }
//D5|    lib.Assert(int(sum) == len(arr))

    if prev != nil {
//D5|        lib.Assert(len(prev) == len(arr))

        for i := 0; i < len(arr); i++ {
            pi := prev[i]

            id := arr[pi]
//D5|            lib.Assert(int(id) < len(cnts))

            out[pos[id]] = pi
            pos[id]++
        }
    } else {
        for i := 0; i < len(arr); i++ {
            id := arr[i]
//D5|            lib.Assert(int(id) < len(cnts))

            out[pos[id]] = int32(i)
            pos[id]++
        }
    }
}

А это "обобщенная" DersCountSort():

lib\derscountsort.go
func DersCountSort[S ~[]E, E any](buf *DersCountBuf, arr S, prev []int32, cnts []int32, seq []uint16,
    out []int32, idnt func(p *E) uint16) {
    Assert(len(arr) <= math.MaxInt32)
    Assert(len(cnts) <= math.MaxUint16)
//D5|    Assert(len(out) == len(arr))

    buf.Reserve(len(cnts))
    pos := buf.Pos

    sum := int32(0)
    if seq != nil {
//D5|        Assert(len(seq) == len(cnts))

        for i := 0; i < len(cnts); i++ {
            si := seq[i]
            pos[si] = sum
            sum += cnts[si]
        }
    } else {
        for i := 0; i < len(cnts); i++ {
            pos[i] = sum
            sum += cnts[i]
        }
    }
//D5|    Assert(int(sum) == len(arr))

    if prev != nil {
//D5|        Assert(len(prev) == len(arr))

        for i := 0; i < len(arr); i++ {
            pi := prev[i]

            id := idnt(&arr[pi])
//D5|            Assert(int(id) < len(cnts))

            out[pos[id]] = pi
            pos[id]++
        }
    } else {
        for i := 0; i < len(arr); i++ {
            id := idnt(&arr[i])
//D5|            Assert(int(id) < len(cnts))

            out[pos[id]] = int32(i)
            pos[id]++
        }
    }
}

Отличия? Так вы их видели:

  1. Нету типа параметров [S ~[]E, E any].
  2. Нет параметра функтора idnt func(p *E) uint16.
Все! Пора выяснять отношения:

cardgomy1my2my1/my2
220592513300.76
1036552491361.83
10074922601092.39
1000111042861931.48
10000145014484341.03
65535174535455610.97

Да, любопытно... DersCountSort_uint16() двумя местами даже медленней! На краевых вариантах кардинальности.

Но ведь на Практике важнее середина! И тут уже отличный результат: мы получили в 1.5 - 2.5 раза ускорение.

Ну как, имело смысл почикать ручками DersCountSort() и срезать замедляющий generic?!

Нет, не имело... Потому, что дело сделано (почти) автоматически!

Да-да, у нас опять немножко Революция! И в директории lib\cbgen лежат готовые шаблоны ВСЕХ обобщенных функций сортировки!

Ну, например:

lib\cbgen\derscountsort.clon
func [0[DersCountSort]0](buf *[0[Lib]0]DersCountBuf, arr [][0[E]0], prev []int32, cnts []int32, seq []uint16,
    out []int32) {
    [0[Lib]0]Assert(len(arr) <= math.MaxInt32)
    [0[Lib]0]Assert(len(cnts) <= math.MaxUint16)
    [0[Lib]0]Assert(len(out) == len(arr)) //D5|

    buf.Reserve(len(cnts))
    pos := buf.Pos

    sum := int32(0)
    if seq != nil {
        [0[Lib]0]Assert(len(seq) == len(cnts)) //D5|

        for i := 0; i < len(cnts); i++ {
            si := seq[i]
            pos[si] = sum
            sum += cnts[si]
        }
    } else {
        for i := 0; i < len(cnts); i++ {
            pos[i] = sum
            sum += cnts[i]
        }
    }
    [0[Lib]0]Assert(int(sum) == len(arr)) //D5|

    if prev != nil {
        [0[Lib]0]Assert(len(prev) == len(arr)) //D5|

        for i := 0; i < len(arr); i++ {
            pi := prev[i]

            TODO id := idnt(&arr[pi])
            [0[Lib]0]Assert(int(id) < len(cnts)) //D5|

            out[pos[id]] = pi
            pos[id]++
        }
    } else {
        for i := 0; i < len(arr); i++ {
            TODO id := idnt(&arr[i])
            [0[Lib]0]Assert(int(id) < len(cnts)) //D5|

            out[pos[id]] = int32(i)
            pos[id]++
        }
    }
}

А вот конфиг:

lib\cbgen\derscountsort.cfig
Lib = lib.
DersCountSort = DersCountSort_uint16
E = uint16

Теперь мы просто запускаем кодогенератор cheburgen g derscountsort.cfig derscountsort.clon go.out и получаем:

go.out
func DersCountSort_uint16(buf *lib.DersCountBuf, arr []uint16, prev []int32, cnts []int32, seq []uint16,
    out []int32) {
    lib.Assert(len(arr) <= math.MaxInt32)
    lib.Assert(len(cnts) <= math.MaxUint16)
    lib.Assert(len(out) == len(arr)) //D5|

    buf.Reserve(len(cnts))
    pos := buf.Pos

    sum := int32(0)
    if seq != nil {
        lib.Assert(len(seq) == len(cnts)) //D5|

        for i := 0; i < len(cnts); i++ {
            si := seq[i]
            pos[si] = sum
            sum += cnts[si]
        }
    } else {
        for i := 0; i < len(cnts); i++ {
            pos[i] = sum
            sum += cnts[i]
        }
    }
    lib.Assert(int(sum) == len(arr)) //D5|

    if prev != nil {
        lib.Assert(len(prev) == len(arr)) //D5|

        for i := 0; i < len(arr); i++ {
            pi := prev[i]

            TODO id := idnt(&arr[pi])
            lib.Assert(int(id) < len(cnts)) //D5|

            out[pos[id]] = pi
            pos[id]++
        }
    } else {
        for i := 0; i < len(arr); i++ {
            TODO id := idnt(&arr[i])
            lib.Assert(int(id) < len(cnts)) //D5|

            out[pos[id]] = int32(i)
            pos[id]++
        }
    }
}

Все! Получилось то, что нужно.

Ну, почти... Осталось только заменить TODO id:=idnt(&arr[pi]) на id:=arr[pi]. Да, это ручками, но не напряжно.


5. Перестройка

И вот пришла пора Фундаметального!

Конечно Google не признается, но Ветераны Go давно заметили, что с выходом 1.18 версии у суслика расширились глаза и появилась странная походка...

Да, Google в суслика вкорячила дженерики! Но, как обычно, поперек шушпанчика:

Что пипл хавал до дженериков? Народ использовал text/template и //go:generate: Неудивительно, что чебурген пинает суслика: Итак, давайте перестроим Образ Мысли:
  1. Вы как обычно пишете свои generic функции.
  2. Но дополнительно вы создаете в /cbgen для них шаблоны!
  3. Кого печалит скорость общей функции -- тот сгенерирует себе конкретную.

6. Заключение

Гордиться будем, приготовьтесь!
  1. Мы с облегчением узнали, DersCountSort() в десятки раз опережает slices.SortFunc()!!
  2. А если выбросить все "обобщения", то можно получить прирост еще в 2.5 раза!
  3. Ну и теперь мы знаем КАК все обобщения выбрасывать. А Чебурген друзей не подведет!
Но перед тем как огороды городить, давайте снова заглянем в скрижали: Нет смысла стараться нигде, кроме узкого места!

Убедитесь сначала ГДЕ узкое место! Обычный пипл сортировка вообще не парит...


Copyright © С. Деревяго, 2026

Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.