Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

x/exp/slices: runtime complexity of Delete #54699

Closed
Deleplace opened this issue Aug 26, 2022 · 2 comments
Closed

x/exp/slices: runtime complexity of Delete #54699

Deleplace opened this issue Aug 26, 2022 · 2 comments
Milestone

Comments

@Deleplace
Copy link

What version of Go are you using (go version)?

$ go version
go version go1.19 darwin/amd64

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/Users/deleplace/Library/Caches/go-build"
GOENV="/Users/deleplace/Library/Application Support/go/env"
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="darwin"
GOINSECURE=""
GOMODCACHE="/Users/deleplace/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="darwin"
GOPATH="/Users/deleplace/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/usr/local/go"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/usr/local/go/pkg/tool/darwin_amd64"
GOVCS=""
GOVERSION="go1.19"
GCCGO="gccgo"
GOAMD64="v1"
AR="ar"
CC="clang"
CXX="clang++"
CGO_ENABLED="1"
GOMOD="/Users/deleplace/Documents/2022/08/26/slices-Delete-big-O/go.mod"
GOWORK=""
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch x86_64 -m64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/p4/g7fnpss96g5708_mmv3cxzgh0000gn/T/go-build1650505424=/tmp/go-build -gno-record-gcc-switches -fno-common"

What did you do?

I read the documentation comment of Delete

What did you expect to see?

"Delete is O(len(s)-j)"

What did you see instead?

Delete is O(len(s)-(j-i))

It seems to me this is a small error that can be fixed in a small CL.

A slice passed to Delete has 3 areas:

0                         i                j             len(s)
[      ...A...            |   ...B...      |   ...C...      ]

The region A has size i. It is left untouched by Delete. It does not incur a cost.

The region B has size (j-i). Surprisingly, its size does not influence the runtime cost. We may ignore B to compute the cost.

The region C has size (len(s)-j). The cost of Delete is proportional to C, which is the part that needs to be shifted to the left.

This can be derived from the current implementation of Delete, and is verified by this benchmark.

@gopherbot gopherbot added this to the Unreleased milestone Aug 26, 2022
@gopherbot
Copy link

Change https://go.dev/cl/425994 mentions this issue: slices.Delete: fix runtime complexity documentation

@Deleplace
Copy link
Author

The updated cost O(len(s)-j) holds for the current Delete implementation, which does some shifting but no zeroing.

If we ever decide to zero the right tail (#54650) then the cost of Delete would become O(len(s)-i).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants