已排序uint32类型Go切片的最快去重方法及自定义去重函数的问题排查与优化

Great question! Since your slice is already sorted, we can leverage that order to implement O(n) time, O(1) extra space deduplication—this is the fastest possible approach for sorted data, as we avoid any hashing or nested loops. Let’s break down your current code, its issues, and the optimal solution.

First: Issues in Your Corrected Function #

Your revised loop fixes the out-of-bounds panic, but there are still critical problems:

1. Your Function Doesn’t Modify the Original Slice #

Go passes slices by value (the slice header is copied), so when you do:

s = nil
s = append(s, tmp...)

you’re only modifying the local copy of the slice header inside the function. The original slice in your main code will remain unchanged. This is the biggest bug here.

2. Unnecessary Memory Allocation #

Creating a tmp slice with the same capacity as the original uses more memory than needed. For large slices (like your 4.29B-capacity example), this is a significant waste—we can do better by modifying the slice in-place.

3. Avoidable Type Conversion #

Using uint32 for your loop variable is unnecessary: slice lengths and indices in Go are int types. While your initial len(s) < 2 check prevents overflow issues here, it’s an extra conversion that adds no value and could introduce bugs in edge cases.

The Optimal: In-Place Deduplication with Two Pointers #

Since the slice is sorted, duplicate elements are always adjacent. We can use a two-pointer technique to track the end of the deduplicated portion of the slice, avoiding extra memory allocation entirely:

func RemoveDuplicates(s []uint32) []uint32 {
    // Handle edge cases: empty or single-element slices need no deduplication
    if len(s) < 2 {
        return s
    }

    // idx tracks the last position of the deduplicated slice
    idx := 0
    for i := 1; i < len(s); i++ {
        // If current element is different from the last deduplicated element
        if s[i] != s[idx] {
            idx++
            // Overwrite the next position in the deduplicated slice
            s[idx] = s[i]
        }
    }

    // Truncate the slice to the length of the deduplicated data
    return s[:idx+1]
}

How This Works: #

• We use idx to mark the end of the unique elements we’ve kept so far.
• For each element from index 1 onward, if it’s not equal to s[idx], we move idx forward and copy the element to that position.
• Finally, we return a slice pointing to the same underlying array but truncated to the unique length.

Why This Is Better: #

• No extra memory: We reuse the original slice’s underlying array, so no new allocations are needed.
• Faster: No append operations (which can trigger reallocations) or copying of the entire slice.
• Correct: Returns the deduplicated slice, so you can assign it back to your original variable (e.g., mySlice = RemoveDuplicates(mySlice)).

If You Prefer a Non-In-Place Approach #

If you need to preserve the original slice, you can adjust your method to be cleaner and avoid the final append of the last element:

func RemoveDuplicatesCopy(s []uint32) []uint32 {
    if len(s) < 2 {
        return append([]uint32(nil), s...)
    }

    tmp := make([]uint32, 0, len(s))
    tmp = append(tmp, s[0])
    for i := 1; i < len(s); i++ {
        if s[i] != tmp[len(tmp)-1] {
            tmp = append(tmp, s[i])
        }
    }
    return tmp
}

This avoids checking the next element and appending the last one separately—we just track the last element in the tmp slice instead.

Final Recommendations #

• Use the two-pointer in-place method for maximum speed and memory efficiency, especially with large slices like yours.
• Always assign the returned slice back to your original variable (since Go slices are value types, the function can’t modify the original header directly).
• Stick to int for loop variables when working with slices to avoid type conversion headaches.

内容的提问来源于stack exchange，提问作者Megidd