Golang Project Structure

Tips and tricks for writing and structuring Go code

Reversing a Slice

Language

  • unknown

by

Slices in Go are equivalent to the data structures known as dynamic arrays or vectors in other programming languages. They simply allow us to collect data of the same type together, making it easy to access and pass around. Sometimes you may want to reverse the current order of your data, and this post discusses some ways to go about doing that.

Naive Approach

The easiest way to reverse all of the items in a Golang slice is simply to iterate backwards and append each element to a new slice. This can be seen in the function below:

func Reverse(input []int) []int {
    var output []int

    for i := len(input) - 1; i >= 0; i-- {
        output = append(output, input[i])
    }

    return output
}

Managing Memory

It may be more efficient, however, to preallocate memory for the new slice, since we already know how large it will need to be. We can work out the reversed index by taking the current index away from the slice’s max index (the length minus one). The example below also makes use of the more idiomatic range loop:

func Reverse(input []int) []int {
	inputLen := len(input)
	output := make([]int, inputLen)

	for i, n := range input {
		j := inputLen - i - 1

		output[j] = n
	}

	return output
}

Incorporating Concurrency

If you have a very large slice, which may contain many thousands or even millions of elements, it may be a good idea to build the task up into chunks. Goroutines are perfect for this. The code below starts a goroutine for every 1000-element chunk in the slice. Because we’ve already allocated the memory for the new slice and because we’re never reading and writing from the same locations at one time, we don’t need to use a mutex or other lock. We do make use of a WaitGroup, however, in order to ensure that the function doesn’t return until all the goroutines have completed their work.

func Reverse(input []int) []int {
    const batchSize = 1000
    inputLen := len(input)
    output := make([]int, inputLen)
    var wg sync.WaitGroup

    for i := 0; i < inputLen; i += batchSize {
        wg.Add(1)

        go func(i int) {
            defer wg.Done()

            l := i + batchSize
            if l > inputLen {
                l = inputLen
            }

            for ; i < l; i++ {
                j := inputLen - i - 1
                n := input[i]

                output[j] = n
            }
        }(i)
    }

    wg.Wait()

    return output
}

Using the code above, if we had a slice of a million integers, the Reverse function would spin up a thousand goroutines, each working in parallel, which would potentially produce more efficient results than just having one long for loop that runs a million times.

Reorder Input

But sometimes you don’t want to create a new slice at all. It can be more efficient to reuse the slice that you already have, but just swap the order of the elements.

func Reverse(input []int) {
    inputLen := len(input)
    inputMid := inputLen / 2

    for i := 0; i < inputMid; i++ {
        j := inputLen - i - 1

        input[i], input[j] = input[j], input[i]
    }
}

Notice how the for loop only has to do half the usual number of iterations in this version, because it handles two elements at a time, starting at those furthest away from the middle (at both the beginning and the end) and then stopping when it reaches the midpoint. If there are an odd number of elements, you never need to reach the element that is exactly in the middle, because it’s already in the right place; in a sense, all of the other elements pivot around it.

In some programming languages, you would have to create a temporary variable in order to swap the elements, since the first element would overwrite the second before we have chance to use it, but this isn’t a concern when you use the Golang one-liner, since the compiler handles it automatically. However, this is how you would write it in Javascript:

const reverse = (input) => {
	const inputLen = input.length;
	const inputMid = inputLen / 2;
	
	for (let i = 0; i < inputMid; ++i) {
		const j = inputLen - i - 1;
		
		const tmp = input[i];
		input[i] = input[j];
		input[j] = tmp;
	}
};

Of course, you can also separate out the swapping functionality into its own Javascript function in order to comply better with the principle of DRY:

const swap = (input, a, b) => {
	const tmp = input[a];
	input[a] = input[b];
	input[b] = tmp;
};

const reverse = (input) => {
	const inputLen = input.length;
	const inputMid = inputLen / 2;
	
	for (let i = 0; i < inputMid; ++i) {
		const j = inputLen - i - 1;
		
		swap(input, i, j);
	}
};

Concurrent Reordering

Just as we did when we were populating a new slice, we can also use concurrency to speed up the reordering of large input slices. No two goroutines ever write to the same memory address, so, again, we don’t need to be concerned with issues of mutual exclusion.

func Reverse(input []int) {
	const batchSize = 1000
	inputLen := len(input)
	inputMid := inputLen / 2
	var wg sync.WaitGroup

	for i := 0; i < inputMid; i += batchSize {
		wg.Add(1)

		go func(i int) {
			defer wg.Done()

			l := i + batchSize
			if l > inputMid {
				l = inputMid
			}

			for ; i < l; i++ {
				j := inputLen - i - 1

				input[i], input[j] = input[j], input[i]
			}
		}(i)
	}

	wg.Wait()
}

And we can also separate the goroutine into its own function, to make it easier to work with.

func reverseBatch(input []int, start, end int, wg *sync.WaitGroup) {
    defer wg.Done()

    for i := start; i < end; i++ {
        j := len(input) - i - 1

        input[i], input[j] = input[j], input[i]
    }
}

func Reverse(input []int) {
    const batchSize = 1000
    inputMid := len(input) / 2
    var wg sync.WaitGroup
    
    for i := 0; i < inputMid; i += batchSize {
        wg.Add(1)
        
        j := i + batchSize
        if j > inputMid {
            j = inputMid
        }

        go reverseBatch(input, i, j, &wg)
    }

    wg.Wait()
}

Notice how we have to pass the WaitGroup by pointer in the code above, in order to preserve its state.

Precalculated Batches

However, we’re still checking to make sure that the calculated end (i + batchSize) is less than the true end (midPoint) on every iteration of the loop. Wouldn’t it be better if we calculate exactly how many whole batches we’ll need in advance, and then just perform an extra one if it’s necessary at the end? That’s what we do below:

func reverseBatch(input []int, start, end int, wg *sync.WaitGroup) {
    defer wg.Done()

    for i := start; i < end; i++ {
        j := len(input) - i - 1

        input[i], input[j] = input[j], input[i]
    }
}

func Reverse(input []int) {
    const batchSize = 1000
    inputMid := len(input) / 2
    wholeBatches := inputMid / batchSize
    wholeBatchElements := wholeBatches * batchSize
    var wg sync.WaitGroup

    if wholeBatches > 0 {
        wg.Add(wholeBatches)
 
        var j int   
        for i := 0; i < wholeBatchElements; i = j {
            j = i + batchSize

            go reverseBatch(input, i, j, &wg)
        }
    }

    if wholeBatchElements < inputMid {
        wg.Add(1)
        
        go reverseBatch(input, wholeBatchElements, inputMid, &wg)
    }

    wg.Wait()
}

Slices Can Hold Any Type

The previous examples have all used integer slices, but sometimes you want to reverse a slice, regardless of its type. The following function uses an interface argument to make this possible:

func Reverse(input interface{}) {
	inputLen := reflect.ValueOf(input).Len()
	inputMid := inputLen / 2
	inputSwap := reflect.Swapper(input)

	for i := 0; i < inputMid; i++ {
		j := inputLen - i - 1
	
		inputSwap(i, j)
	}
}

The reflect.Swapper function returns a curried function that will swap two indices in the given slice. If the argument given is not a slice, the function will panic. Likewise, the Len method on the reflect.Value type will panic if the given argument is not a data structure containing a countable number of elements.

Nice and Concise

Finally, here’s the shortest way to reverse a slice, if you just want to keep things as simple as possible:

func Reverse(input []int) {
    for i, j := 0, len(input)-1; i < j; i, j = i+1, j-1 {
        input[i], input[j] = input[j], input[i]
    }
}

Leave a Reply

Your email address will not be published.