Skip to content

Instantly share code, notes, and snippets.

@rahulghangas
Last active September 19, 2020 11:10
Show Gist options
  • Save rahulghangas/e823bb3c45229c0a4460c44898299d05 to your computer and use it in GitHub Desktop.
Save rahulghangas/e823bb3c45229c0a4460c44898299d05 to your computer and use it in GitHub Desktop.
Element removal in LinkedList vs Element Removal in Arrays using reslicing
package main
import (
"container/list"
"fmt"
"math/rand"
"os"
"strconv"
"testing"
)
var toRemove []int
var numEls int
var alpha int
func removeFromList(arr *list.List, toRemove []int) {
toRemoveCounter := 0
for {
currCounter := 0
removeIndex := toRemove[toRemoveCounter]
for i := arr.Front(); i != nil; i = i.Next() {
if removeIndex == currCounter {
arr.Remove(i)
toRemoveCounter++
break
}
currCounter++
}
if toRemoveCounter == len(toRemove) {
break
}
}
}
func removeFromSlice(arr []int, toRemove []int) {
toRemoveCounter := 0
for {
currCounter := 0
removeIndex := toRemove[toRemoveCounter]
for i := 0; i < len(arr); i++ {
if removeIndex == i {
arr = append(arr[:i], arr[i+1:]...)
toRemoveCounter++
break
}
currCounter++
}
if toRemoveCounter == len(toRemove) {
break
}
}
}
func BenchMarkSlice(b *testing.B) {
arr := make([]int, numEls)
for i := 0; i < numEls; i++ {
arr[i] = rand.Int()
}
b.ResetTimer()
removeFromSlice(arr, toRemove)
}
func BenchMarkList(b *testing.B) {
arr := list.New()
for i := 0; i < numEls; i++ {
arr.PushBack(rand.Int())
}
b.ResetTimer()
removeFromList(arr, toRemove)
}
func main() {
args := os.Args[1:]
a, _ := strconv.Atoi(args[0])
b, _ := strconv.Atoi(args[1])
numEls = a
alpha = b
toRemove = make([]int, alpha)
for i := 0; i < alpha; i++ {
for j := i; j < alpha-i; j++ {
if rand.Float64() < 0.25 {
toRemove[i] = j
break
}
}
}
resultSlice := testing.Benchmark(BenchMarkSlice)
resultList := testing.Benchmark(BenchMarkList)
fmt.Printf("benchmarkSlice\t%v\n", resultSlice.T)
fmt.Printf("benchmarkList\t%v\n", resultList.T)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment