Comparison of linear slice search vs hash-based search

output.txt

n=       5	target=      0	slice-search-time:    169ns	set-search-time:    309ns
n=       5	target=      2	slice-search-time:     82ns	set-search-time:    163ns
n=       5	target=      5	slice-search-time:     68ns	set-search-time:    150ns
n=      10	target=      0	slice-search-time:     30ns	set-search-time:    145ns
n=      10	target=      5	slice-search-time:     60ns	set-search-time:    131ns
n=      10	target=     10	slice-search-time:     55ns	set-search-time:    118ns
n=      50	target=      0	slice-search-time:     33ns	set-search-time:     67ns
n=      50	target=     25	slice-search-time:     55ns	set-search-time:    127ns
n=      50	target=     50	slice-search-time:     70ns	set-search-time:    120ns
n=     100	target=      0	slice-search-time:     47ns	set-search-time:     76ns
n=     100	target=     50	slice-search-time:     82ns	set-search-time:    158ns
n=     100	target=    100	slice-search-time:     83ns	set-search-time:    115ns
n=     500	target=      0	slice-search-time:     63ns	set-search-time:     71ns
n=     500	target=    250	slice-search-time:    166ns	set-search-time:    134ns
n=     500	target=    500	slice-search-time:    199ns	set-search-time:    120ns
n=    1000	target=      0	slice-search-time:     43ns	set-search-time:     61ns
n=    1000	target=    500	slice-search-time:    281ns	set-search-time:    123ns
n=    1000	target=   1000	slice-search-time:    621ns	set-search-time:    218ns
n=   10000	target=      0	slice-search-time:     80ns	set-search-time:     74ns
n=   10000	target=   5000	slice-search-time:   2663ns	set-search-time:    132ns
n=   10000	target=  10000	slice-search-time:   4330ns	set-search-time:    154ns
n=  100000	target=      0	slice-search-time:    330ns	set-search-time:    480ns
n=  100000	target=  50000	slice-search-time:  55775ns	set-search-time:    269ns
n=  100000	target= 100000	slice-search-time:  54890ns	set-search-time:    242ns
n= 1000000	target=      0	slice-search-time:    530ns	set-search-time:    468ns
n= 1000000	target= 500000	slice-search-time: 608233ns	set-search-time:   1244ns
n= 1000000	target=1000000	slice-search-time: 742963ns	set-search-time:    622ns

test_search_efficiency.go

package main

import (
	"fmt"
	"time"

	"github.com/emirpasic/gods/sets/hashset"
)

func SliceContains(s []int, target int) bool {
	for _, v := range s {
		if v == target {
			return true
		}
	}
	return false
}

func Init(n int) ([]int, *hashset.Set) {
	sl := make([]int, n)
	set := hashset.New()

	for i := 0; i < n; i++ {
		sl[i] = i
		set.Add(i)
	}
	return sl, set
}

func TestEfficiency() {
	sizes := []int{5, 10, 50, 100, 500, 1000, 10000, 100000, 1e6}
	for _, n := range sizes {
		sl, set := Init(n)

		// Search for elements that will be at the beginning, middle, and end
		// of the slice, to fairly represent the linearity of the search.
		targets := []int{0, n / 2, n}
		for _, target := range targets {
			t := time.Now()
			SliceContains(sl, target)
			slDur := time.Since(t).Nanoseconds()

			t = time.Now()
			set.Contains(target)
			setDur := time.Since(t).Nanoseconds()

			fmt.Printf(
				"n=%8d\ttarget=%d\tslice-search-time: %6vns\tset-search-time: %6vns\n",
				n, target, slDur, setDur)
		}
	}
}

func main() {
	TestEfficiency()
}