Big O gắn thêm vào golang

Question

Độ phức tạp của hàm dựng sẵn append của go là gì? Điều gì về chuỗi nối bằng cách sử dụng +?

Tôi muốn xóa phần tử khỏi một lát bằng cách thêm hai lát trừ phần tử đó, ví dụ: http://play.golang.org/p/RIR5fXq-Sf

nums := []int{0, 1, 2, 3, 4, 5, 6, 7} 
fmt.Println(append(nums[:4], nums[5:]...)) 

=> [0 1 2 3 5 6 7] 

http://golang.org/pkg/builtin/#append nói rằng nếu các đích có đủ năng lực, sau đó lát đó là resliced. Tôi hy vọng rằng "reslicing" là một hoạt động liên tục thời gian. Tôi cũng hy vọng cùng áp dụng cho chuỗi nối bằng cách sử dụng +.

Answer 1

Tất cả điều này phụ thuộc vào việc triển khai thực tế được sử dụng, nhưng tôi dựa trên tiêu chuẩn Go cũng như gccgo.

Slices

Reslicing nghĩa là thay đổi một số nguyên trong một cấu trúc (một lát là một cấu trúc với ba lĩnh vực: chiều dài, năng lực và con trỏ đến ủng hộ bộ nhớ).

Nếu lát không có đủ dung lượng, phụ thêm sẽ cần cấp phát bộ nhớ mới và sao chép bộ nhớ cũ. Đối với các slice có các phần tử < 1024, nó sẽ tăng gấp đôi dung lượng, đối với các lát có> 1024 phần tử, nó sẽ tăng nó theo hệ số 1.25.

Strings

Kể từ chuỗi là không thay đổi, mỗi chuỗi nối với + sẽ tạo ra một chuỗi mới, có nghĩa là sao chép một tuổi. Vì vậy, nếu bạn đang làm nó N lần trong một vòng lặp, bạn sẽ phân bổ N chuỗi và sao chép bộ nhớ khoảng N lần.