Skip to content

Instantly share code, notes, and snippets.

@skeeto

skeeto/go.mod

Forked from lorenzotinfena/sort.go
Last active May 29, 2024 17:08
Show Gist options
  • Save skeeto/0651f47ba992297f3262236d7bf20fd0 to your computer and use it in GitHub Desktop.
Save skeeto/0651f47ba992297f3262236d7bf20fd0 to your computer and use it in GitHub Desktop.
Download ZIP
Efficient (but ugly) radix sort implementation for uint32
Raw
go.mod
module x
go 1.21.0
Raw
sort.go
package main
func Sort2(vs []uint32, shift int) {
const (
bits = 8
mask = 1<<bits - 1
)
if len(vs) < 1<<6 {
// Insertion sort for small inputs
for i := 0; i < len(vs); i++ {
for j := i; j > 0 && vs[j-1] > vs[j]; j-- {
vs[j-1], vs[j] = vs[j], vs[j-1]
}
}
return
}
// First pass: count each bin size
var bins [1 << bits]int
for _, v := range vs {
b := v >> (32 - bits - shift) & mask
bins[b]++
}
// Locate bin ranges in the sorted array
accum := 0
var ends [1 << bits]int
for b := 0; b < len(bins); b++ {
beg := accum
accum += bins[b]
ends[b] = accum
bins[b] = beg
}
// Second pass: move elements into allotted bins
for b := 0; b < len(bins); b++ {
for i := bins[b]; i < ends[b]; {
bin := int((vs[i] >> (32 - bits - shift)) & mask)
if bin == b {
i++
} else {
vs[bins[bin]], vs[i] = vs[i], vs[bins[bin]]
bins[bin]++
}
}
}
// Recursively sort each bin on the next digit
if shift < 32-bits {
beg := 0
for b := 0; b < len(bins); b++ {
Sort2(vs[beg:ends[b]], shift+bits)
beg = ends[b]
}
}
}
func Sort(v []uint32) {
rec0 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<0) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
}
rec1 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<1) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec0(L, r)
}
if l < R {
rec0(l, R)
}
}
rec2 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<2) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec1(L, r)
}
if l < R {
rec1(l, R)
}
}
rec3 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<3) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec2(L, r)
}
if l < R {
rec2(l, R)
}
}
rec4 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<4) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec3(L, r)
}
if l < R {
rec3(l, R)
}
}
rec5 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<5) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec4(L, r)
}
if l < R {
rec4(l, R)
}
}
rec6 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<6) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec5(L, r)
}
if l < R {
rec5(l, R)
}
}
rec7 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<7) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec6(L, r)
}
if l < R {
rec6(l, R)
}
}
rec8 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<8) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec7(L, r)
}
if l < R {
rec7(l, R)
}
}
rec9 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<9) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec8(L, r)
}
if l < R {
rec8(l, R)
}
}
rec10 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<10) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec9(L, r)
}
if l < R {
rec9(l, R)
}
}
rec11 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<11) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec10(L, r)
}
if l < R {
rec10(l, R)
}
}
rec12 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<12) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec11(L, r)
}
if l < R {
rec11(l, R)
}
}
rec13 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<13) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec12(L, r)
}
if l < R {
rec12(l, R)
}
}
rec14 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<14) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec13(L, r)
}
if l < R {
rec13(l, R)
}
}
rec15 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<15) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec14(L, r)
}
if l < R {
rec14(l, R)
}
}
rec16 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<16) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec15(L, r)
}
if l < R {
rec15(l, R)
}
}
rec17 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<17) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec16(L, r)
}
if l < R {
rec16(l, R)
}
}
rec18 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<18) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec17(L, r)
}
if l < R {
rec17(l, R)
}
}
rec19 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<19) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec18(L, r)
}
if l < R {
rec18(l, R)
}
}
rec20 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<20) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec19(L, r)
}
if l < R {
rec19(l, R)
}
}
rec21 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<21) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec20(L, r)
}
if l < R {
rec20(l, R)
}
}
rec22 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<22) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec21(L, r)
}
if l < R {
rec21(l, R)
}
}
rec23 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<23) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec22(L, r)
}
if l < R {
rec22(l, R)
}
}
rec24 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<24) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec23(L, r)
}
if l < R {
rec23(l, R)
}
}
rec25 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<25) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec24(L, r)
}
if l < R {
rec24(l, R)
}
}
rec26 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<26) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec25(L, r)
}
if l < R {
rec25(l, R)
}
}
rec27 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<27) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec26(L, r)
}
if l < R {
rec26(l, R)
}
}
rec28 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<28) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec27(L, r)
}
if l < R {
rec27(l, R)
}
}
rec29 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<29) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec28(L, r)
}
if l < R {
rec28(l, R)
}
}
rec30 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<30) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec29(L, r)
}
if l < R {
rec29(l, R)
}
}
rec31 := func(L, R int) {
l := L
r := R
for l <= r {
if v[l]&(1<<31) == 0 {
l++
} else {
v[l], v[r] = v[r], v[l]
r--
}
}
if L < r {
rec30(L, r)
}
if l < R {
rec30(l, R)
}
}
rec31(0, len(v)-1)
}
Raw
sort_test.go
package main
import (
"math/rand"
"slices"
"testing"
)
func hash(v uint32) uint32 {
v += 1
v *= 1471805459
v ^= v >> 16
v *= 1471805459
v ^= v >> 16
return v
}
func invhash(v uint32) uint32 {
v ^= v >> 16
v *= 3715666459
v ^= v >> 16
v *= 3715666459
v -= 1
return v
}
func testfill(vs []uint32) {
// Populate slice with a permutation
for i := 0; i < len(vs); i++ {
vs[i] = hash(uint32(i))
}
}
func testvalidate(vs []uint32) bool {
// Validate sort as well as permutation
for i := 0; i < len(vs); i++ {
v := invhash(vs[i])
if i > 0 && vs[i-1] >= vs[i] {
return false
}
if int(v) >= len(vs) {
return false
}
}
return true
}
func TestSort(t *testing.T) {
var vs [1 << 21]uint32
testfill(vs[:])
Sort(vs[:])
if !testvalidate(vs[:]) {
t.Fail()
}
testfill(vs[:])
Sort2(vs[:], 0)
if !testvalidate(vs[:]) {
t.Fail()
}
}
func BenchmarkSort(b *testing.B) {
r := rand.New(rand.NewSource(int64(b.N)))
v := make([]uint32, b.N)
for i := 0; i < b.N; i++ {
v[i] = r.Uint32()
}
b.ResetTimer()
Sort(v)
}
func BenchmarkSlicesSort(b *testing.B) {
r := rand.New(rand.NewSource(int64(b.N)))
v := make([]uint32, b.N)
for i := 0; i < b.N; i++ {
v[i] = r.Uint32()
}
b.ResetTimer()
slices.Sort(v)
}
func BenchmarkSort2(b *testing.B) {
r := rand.New(rand.NewSource(int64(b.N)))
v := make([]uint32, b.N)
for i := 0; i < b.N; i++ {
v[i] = r.Uint32()
}
b.ResetTimer()
Sort2(v, 0)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment