Но есть еще и небольшая Революция... И для нее уже читаем сплошняком!
С уважением, Сергей Деревяго.
| 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)
}
|
На той же машине, все тот миллион:
| card | go | my1 | my2 | go/my1 | go/my2 |
|---|---|---|---|---|---|
| 2 | 2059 | 251 | 330 | 8.2 | 6.2 |
| 10 | 3655 | 249 | 136 | 14.7 | 26.9 |
| 100 | 7492 | 260 | 109 | 28.8 | 68.7 |
| 1000 | 11104 | 286 | 193 | 38.8 | 57.5 |
| 10000 | 14501 | 448 | 434 | 32.4 | 33.4 |
| 65535 | 17453 | 545 | 561 | 32.0 | 31.1 |
И мы в итоге обгоняем go от 6 до 70 раз!!
Я только обращу внимание, что DersCountSort_uint16() -- это конкретный DersCountSort() без generics и компаратора, т.е. ОБЯЗАН быть быстрее! А он местами не быстрее... Немного неожиданно, не так ли?
А сейчас вспомним C++:
| card | std | ders | std/ders |
|---|---|---|---|
| 2 | 2112 | 107 | 19.7 |
| 10 | 3214 | 99 | 32.5 |
| 100 | 5107 | 106 | 48.2 |
| 1000 | 6696 | 191 | 35.1 |
| 10000 | 8160 | 396 | 20.6 |
| 65535 | 9552 | 524 | 18.2 |
И тут все четенько: колонка ders везде быстрее Go! Хотя местами только на один процент... Кругом сплошная неожиданность!
Но, если все-таки смотреть на чистый Go, то my1 и my2 в десятки раз опережают slices.SortFunc()! Что наполняет Смыслом наше времяпровождение.
| lib\dersort.go |
|---|
func DerSort[S ~[]E, E any](arr S, out []int16, less func(pa *E, pb *E) bool) |
DerSort() никак не изменяет слайс arr! Он создает перестановку в out.
arr2[out[i]]=arr[i] и вы получите отсортированный слайс arr2.
out должен быть слайсом int16 той же длины, что и arr.
less должен возвращать true, если *pa<*pb.
| lib\dersort.go |
|---|
func DerSortAppend[S ~[]E, E any, E2 SeqElem](arr S, perm []E2, less func(pa *E, pb *E) bool) |
DerSortAppend() никак не изменяет слайс arr! Он дополняет перестановку.
perm должен быть слайсом E2 той же длины, что и arr. Последний элемент перестановки будет перезаписан, а предыдущие изменены.
DerSortAppend() включает последний элемент слайса arr в уже готовую перестановку на единицу меньшей длины.
less должен возвращать true, если *pa<*pb.
| lib\dersort.go |
|---|
func DersOversort[S ~[]E, E any, E2 SeqElem](arr S, out []E2, cmp func(pa *E, pb *E) int) |
DersOversort() возвращает последовательность! А для получения перестановки, как у DerSort(), нужно вызвать ToSequence().
DersOversort() не устойчив! Т.е. позиции одинаковых элементов будут отличаться от DerSort().
| lib\dersort.go |
|---|
func ToSequence[E SeqElem](arr []E, out []E) |
ToSequence() создает последовательность из перестановки. А также перестановку из последовательности.
out должен быть слайсом E той же длины, что и arr.
| lib\derscountsort.go |
|---|
func DersCountIds[S ~[]E, E any](arr S, cnts []int32, ids []uint16, idnt func(p *E) uint16) |
DersCountIds() подсчитывает количества уникальных элементов слайса arr и возвращает их в cnts.
cnts должен быть слайсом int32 длины card (кардинальность arr).
ids, то он должен быть слайсом uint16 той же длины, что и arr. В него будут записаны идентификаторы элементов.
idnt должен возвращать идентификатор элемента *p (т.е. значение от 0 до card-1).
| 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)
|
DersCountSort() никак не изменяет слайс arr, а создает последовательность в out.
arr[out[i]] и вы получите отсортированный слайс.
out должен быть слайсом int32 той же длины, что и arr.
buf -- просто буфер. Никакой магии: создайте где-нибудь DersCountBuf и много раз его передавайте.
prev -- результат предыдущей сортировки: последовательность той же длины, что и arr. Передавайте, только если нужно досортировать слайс по другому ключу.
cnts -- слайс счетчиков длины card (кардинальность arr), результат DersCountIds().
seq -- cортирующая последовательность длины card. Не передавайте тривиальную последовательность.
idnt должен возвращать идентификатор элемента *p (т.е. значение от 0 до card-1).
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]++
}
}
}
|
Отличия? Так вы их видели:
[S ~[]E, E any].
idnt func(p *E) uint16.
| card | go | my1 | my2 | my1/my2 |
|---|---|---|---|---|
| 2 | 2059 | 251 | 330 | 0.76 |
| 10 | 3655 | 249 | 136 | 1.83 |
| 100 | 7492 | 260 | 109 | 2.39 |
| 1000 | 11104 | 286 | 193 | 1.48 |
| 10000 | 14501 | 448 | 434 | 1.03 |
| 65535 | 17453 | 545 | 561 | 0.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]. Да, это ручками, но не напряжно.
Конечно Google не признается, но Ветераны Go давно заметили, что с выходом 1.18 версии у суслика расширились глаза и появилась странная походка...
Да, Google в суслика вкорячила дженерики! Но, как обычно, поперек шушпанчика:
text/template и //go:generate:
text/template мутноват в простом и, в то же время, недостаточен для сложного.
//go:generate -- корявая замена make!
make и //go:generate!/cbgen для них шаблоны!
DersCountSort() в десятки раз опережает slices.SortFunc()!!
2.5 раза!
Убедитесь сначала ГДЕ узкое место! Обычный пипл сортировка вообще не парит...
Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.