go implementation of timsort

Related tags

Utilities timsort
Overview

timsort Build Status codecov

timsort is a Go implementation of Tim Peters's mergesort sorting algorithm.

For many input types it is 2-3 times faster than Go's built-in sorting.

The main drawback of this sort method is that it is not in-place (as any mergesort), and may put extra strain on garbage collector.

This implementation was derived from Java's TimSort object by Josh Bloch, which, in turn, was based on the original code by Tim Peters.

Installation

$ go get -u github.com/psilva261/timsort/v2

Testing

Inside the source directory, type

go test

to run test harness.

Benchmarking

Inside the source directory, type

go test -test.bench=.*

to run benchmarks. Each combination of input type/size is presented to timsort, and, for comparison, to the standard Go sort (sort.Sort for ints or sort.Stable otherwise). See BENCHMARKS.md for more info and some benchmarking results.

Examples

As drop-in replacement for sort.Sort

package main

import (
	"github.com/psilva261/timsort/v2"
	"fmt"
	"sort"
)

func main() {
	l := []string{"c", "a", "b"}
	timsort.TimSort(sort.StringSlice(l)
	fmt.Printf("sorted array: %+v\n", l)
}

Explicit "less" function

package main

import (
	"github.com/psilva261/timsort/v2"
	"fmt"
)

type Record struct {
	ssn  int
	name string
}

func BySsn(a, b interface{}) bool {
	return a.(Record).ssn < b.(Record).ssn
}

func ByName(a, b interface{}) bool {
	return a.(Record).name < b.(Record).name
}

func main() {
	db := make([]interface{}, 3)
	db[0] = Record{123456789, "joe"}
	db[1] = Record{101765430, "sue"}
	db[2] = Record{345623452, "mary"}

	// sorts array by ssn (ascending)
	timsort.Sort(db, BySsn)
	fmt.Printf("sorted by ssn: %v\n", db)

	// now re-sort same array by name (ascending)
	timsort.Sort(db, ByName)
	fmt.Printf("sorted by name: %v\n", db)
}
Issues
  • Broken algorithm?

    Broken algorithm?

    After a quick review of the code, I've noticed a few suspects.

    1) Binary search integer overflow

    https://github.com/psilva261/timsort/blob/4537dc9bd679bfb730b72f2e8c33b46676521337/timsort.go#L277

    This fails for large values of low and high. If the sum overflows to a negative value, this will fail with an out of bounds error. There are two ways to fix this.

    mid := left + (right - left) / 2
    
    mid := int(uint(left + right) >> 1) // Used in Go package sort.Search
    

    See: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

    2) Timsort invariant violation

    I noticed that the implementation of mergeCollapse is similar to the one in an old version of CPython.

    https://github.com/psilva261/timsort/blob/4537dc9bd679bfb730b72f2e8c33b46676521337/timsort.go#L434-L440

    See: Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it)

    opened by dsamarin 3
  • Some small changes

    Some small changes

    1. In makeVector of bench_test, I added a line to allocation a slice for v before appending it, this avoids small slices allocated. Without this change, I can't run all benchmark successfully under default go configs.
    2. records.Less is modified to use less function call, which makes the comparison more fair.
    3. Some lines are rewrite in go idiomic style.(exchange values)

    David

    opened by daviddengcn 3
  • TimSort for sort.Interface

    TimSort for sort.Interface

    In this merge:

    1. An Ints function is provided. It sorts []int. It is faster than normal sort.Sort in every shape.
    2. TimSort sorts data with sort.Interface. It is generally faster than Sort, if the data is stored in a slice of the original data-structure(e.g. []record). Faster than sort.Sort if the data is partially sorted (or reverse). But slower than build-in sort.Sort for totally random data.
    3. If the data to be sorted is in []interface{}, Sort is the best choice. It is faster than build-in sort.
    4. I fixed a vital bug in IsSorted.

    In the benchmarks, I let the standard-sort use []record instead of []interface{}, since I think that is a more commonly used pattern and runs much faster.

    opened by daviddengcn 2
  • Using timsort on sort.Interface

    Using timsort on sort.Interface

    1. The timsort algorithm was rewritten on int slice([]int)(The Ints function in timsortint.go). The benchmarks(in benchint_test.go) show it's faster than build-in sort
    2. The function TimSort(), defined in timsortint.go, creates an index slice(an int slice), and sort the index slice with timsort (Ints function). Finally swapping on the original data with the sorted indexes.
    3. The benchmarks was changed.
      1. Standard-sort is performed on a record slice, instead of an interface{} slice.
      2. The record slice is also sorted by TimSort function
      3. Benchmark results show the interface{} has quite a lot overhead, which makes the standand sorting on random data the fastest. (You can run the benchmarks to see details)
    opened by daviddengcn 2
  • why comparing with quicksort?

    why comparing with quicksort?

    It seems that the benchmark is comparing with GO's implementation of quicksort (which is standard in go)

    https://github.com/psilva261/timsort/blob/13f2155f4809c8735e0186f3d80848200d92f876/bench_test.go#L143

    Given that timsort is a stable sort, would not it be right to compare with sort.Stable() instead?

    I got much worse results with that:

    RevSorted100: 1500          (7806)        1582          (7759)        1469          (7773)        
    Xor100:       4838          (5802)        4828          (5845)        4819          (5834)        
    Random100:    5244          (7891)        5250          (7887)        5242          (7911)        
    
    Sorted1K:     5597          (4837)        5584          (4838)        5633          (4846)        
    RevSorted1K:  6588          (87094)       6523          (85785)       6562          (88508)       
    Xor1K:        45714         (114406)      45331         (113812)      46041         (114143)      
    Random1K:     114125        (202941)      132139        (203927)      114355        (202147)      
    
    Sorted1M:     4129627       (8783352)     4129406       (8771254)     4148070       (8678536)     
    RevSorted1M:  6239082       (114131971)   6189573       (115857436)   6199218       (114664717)   
    Xor1M:        99852677      (224848697)   98523482      (228193397)   100662027     (222984886)   
    Random1M:     362650134     (665379425)   348801121     (669130321)   340476927     (670888160)```
    opened by andrewmed 1
Owner
Philip Silva
Philip Silva
Go implementation of the Heaven's Gate technique

gopherheaven is a Go implementation of the classic Heaven's Gate technique originally published by roy g biv on VX Heaven in 2009. gopherheaven can be used as an evasion technique to directly call 64-bit code from a 32-bit process.

aus 67 Jun 23, 2022
Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation

stack Lightweight, Simple, Quick, Thread-Safe Golang Stack Implementation Purpose Provide a fast, thread safe, and generic Golang Stack API with minim

Brendan Wilson 5 May 3, 2022
Optimal implementation of ordered maps for Golang - ie maps that remember the order in which keys were inserted.

Goland Ordered Maps Same as regular maps, but also remembers the order in which keys were inserted, akin to Python's collections.OrderedDicts. It offe

Jean Rougé 195 Jun 20, 2022
An idiomatic Go implementation of Leaky bucket.

lbucket lbucket is an idiomatic Go leaky bucket implementation. The library make use of plain old Go stdlib; in other words, there are no third-party

Alex Rios 11 Apr 17, 2022
A faster RWLock primitive in Go, 2-3 times faster than RWMutex. A Go implementation of concurrency control algorithm in paper

Go Left Right Concurrency A Go implementation of the left-right concurrency control algorithm in paper <Left-Right - A Concurrency Control Technique w

wangyi 40 Apr 4, 2022
Go implementation of the geodesic routines from GeographicLib

geodesic This package is a Go implementation of the geodesic routines from GeographicLib. Features Pure Go implementation Distance calculations with n

Josh Baker 50 May 25, 2022
go-logr implementation with pterm

plogr go-logr implementation with pterm Usage See examples Add more colors and levels By default, only level 0 (info) and level 1 (debug) are supporte

Chris 4 Dec 22, 2021
Reference go implementation of globaldce protocol

globaldce-go This is the reference implementation of the command line interface of globaldce coded in the go programming language. This project is sti

globaldce 10 Nov 8, 2021
Go implementation Welford’s method for one-pass variance computation

Welford - Online method of calculating variance and standard deviation Go implementation Welford’s method for one-pass variance computation with D. H.

Axiom, Inc. 7 Jun 5, 2022
Sliding window counters Redis rate limiting implementation for Golang

Sliding window counters Redis rate limiting implementation for Golang (Based on the Figma API rate limit algorithm)

Barnaby Keene 5 Apr 4, 2022
Implementation for validating the NZ COVID Pass.

NZCP validator Validates NZCP passes according to https://nzcp.covid19.health.nz. Example See example_test.go and tests for more examples. func Exampl

Jonathan Chow 8 Dec 20, 2021
Generic Free List implementation to reuse memory and avoid allocations

gofl GOFL provides a Generic Free List implementation for Go. Installation This

Akshay Bharambe 1 Dec 26, 2021
A pure Golang implementation of Rockchip rknand vendor storage interface.

go-rkvendorstorage A pure Golang implementation of Rockchip rknand vendor storage interface. Usage package main import ( "fmt" "github.com/jamesits

James Swineson 3 May 31, 2022
yaml-patch is a version of Evan Phoenix's json-patch, which is an implementation of JSON Patch, directly transposed to YAML

yaml-patch yaml-patch is a version of Evan Phoenix's json-patch, which is an implementation of JavaScript Object Notation (JSON) Patch, directly trans

Steve Coffman 0 Jan 15, 2022
Golang 1.18+ Generics implementation of Set methods

Golang Generics: Set A golang 1.18+ implementation of Set using Go generics Installation $ go get -u github.com/chrispappas/golang-generics-set Quick

Chris Pappas 10 Jun 26, 2022
Go language implementation of a blockchain based on the BDLS BFT protocol. The implementation was adapted from Ethereum and Sperax implementation

BDLS protocol based PoS Blockchain Most functionalities of this client is similar to the Ethereum golang implementation. If you do not find your quest

Yongge Wang 0 Jan 1, 2022
CVE-2021-4034 - A Golang implementation of clubby789's implementation of CVE-2021-4034

CVE-2021-4034 January 25, 2022 | An00bRektn This is a golang implementation of C

Ryan S. 10 Feb 3, 2022
An implementation of JOSE standards (JWE, JWS, JWT) in Go

Go JOSE Package jose aims to provide an implementation of the Javascript Object Signing and Encryption set of standards. This includes support for JSO

Square 1.9k Jun 23, 2022
goRBAC provides a lightweight role-based access control (RBAC) implementation in Golang.

goRBAC goRBAC provides a lightweight role-based access control implementation in Golang. For the purposes of this package: * an identity has one or mo

Xing 1.3k Jun 26, 2022
This is an implementation of JWT in golang!

jwt This is a minimal implementation of JWT designed with simplicity in mind. What is JWT? Jwt is a signed JSON object used for claims based authentic

John Rowley 99 May 9, 2022
Golang implementation of JSON Web Tokens (JWT)

jwt-go A go (or 'golang' for search engine friendliness) implementation of JSON Web Tokens NEW VERSION COMING: There have been a lot of improvements s

Dave Grijalva 10.4k Jul 4, 2022
Platform-Agnostic Security Tokens implementation in GO (Golang)

Golang implementation of PASETO: Platform-Agnostic Security Tokens This is a 100% compatible pure Go (Golang) implementation of PASETO tokens. PASETO

Oleg Lobanov 608 Jun 26, 2022
s3fs provides a S3 implementation for Go1.16 filesystem interface.

S3 FileSystem (fs.FS) implementation.Since S3 is a flat structure, s3fs simulates directories by using prefixes and "/" delim. ModTime on directories is always zero value.

Jacek Szwec 132 Jun 29, 2022
[NO LONGER MAINTAINED} oauth 2 server implementation in Go

hero hero is a feature rich oauth 2 server implementation in Go. Features User account management Client management oauth 2 rfc 6749 compliant Configu

Geofrey Ernest 214 Feb 9, 2022
OAuth 1.0a implementation in Go

Package oauth1a Summary An implementation of OAuth 1.0a in Go1. API reference Installing Run: go get github.com/kurrik/oauth1a Include in your source

Arne Roomann-Kurrik 23 Sep 17, 2021
OAuth 1.0 implementation in go (golang).

OAuth 1.0 Library for Go (If you need an OAuth 2.0 library, check out: https://godoc.org/golang.org/x/oauth2) Developing your own apps, with this libr

Matt Jones 258 Jun 16, 2022
A golang implementation of a console-based trading bot for cryptocurrency exchanges

Golang Crypto Trading Bot A golang implementation of a console-based trading bot for cryptocurrency exchanges. Usage Download a release or directly bu

Alessandro Sanino 794 Jun 27, 2022
Pure Go termbox implementation

IMPORTANT This library is somewhat not maintained anymore. But I'm glad that it did what I wanted the most. It moved people away from "ncurses" mindse

null 4.3k Jul 1, 2022
go implementation of lightbend's HOCON configuration library https://github.com/lightbend/config

HOCON (Human-Optimized Config Object Notation) Configuration library for working with the Lightbend's HOCON format. HOCON is a human-friendly JSON sup

Gürkan Kaymak 44 Jun 7, 2022