How to delete a foreach and reduce complexity in a go algorithme

Question

I'am trying to implement a custom sort, a schema of my probleme :

Here my current sort function :

func (input Input) Sort() *[]string {
    if input.Media == nil {
        return new([]string)
    }

    var items []string
        
    for _, media := range input.Media {
        if media.IsPrincipal && len(items) < LimitedAmountItems {
            items = append(items, media.URL)
        }
    }
    
    for _, media := range input.Media {
        if !media.IsPrincipal && len(items) < LimitedAmountItems {
            items = append(items, media.URL)
        }
    }

    return &items
}

You can find a full implementation here : https://play.golang.org/p/IoRf0CEfgKY

Any idea on how can I reduce the complexity of this function ?

Please come up with a minimal standalone example showing what you are trying to do. Your code makes no sense whatsoever. — Volker, Jan 11 '21 at 14:04
Is there a reason not to use the `sort.Sort` function by implementing `sort.Interface`? That way you can use the already implemented and optimized sorting algorithm of the `sort` package. — TehSphinX, Jan 11 '21 at 14:16
It isn't possible to reduce the complexity anymore. This is O(n) anyway, as it goes through the list of media twice. — Muhamed Keta, Jan 11 '21 at 14:26

score 3 · Answer 1 · answered Jan 11 '21 at 14:29

3

Here you go: https://play.golang.org/p/dbhVVtS00zJ

A few notes:

This will sort the array.

sort.SliceStable(input.Media, func(i, j int) bool {
    return input.Media[i].IsPrincipal != input.Media[j].IsPrincipal
})

Probably best to just sort and then loop to put them in an output array, even if you're only using a boolean value in the sort comparison. I used StableSort because the url values are currently ordered, imagine you might have wanted to keep that order.

I also replaced *[]string with a []string. A go slice is already a pointer under the hood, to the additional indirection is likely unnecessary.

I think your original solution is likely still faster, so unclear if you actually want this "improvement". Using a sort is likely a more common solution to this problem, but looping over the list twice is not wrong.

answered Jan 11 '21 at 14:29

maxm

3,412
1
19
27

Thanks for your response, is there any option to go through the struct only once ? Because in your answer we go twice, first with the sort and second with the for loop – mbbo128 Jan 11 '21 at 14:48
Yeah, and I mean, sorting is `O(n * log(n))`, so it's (hypothetically) worse than a single loop. – maxm Jan 11 '21 at 15:55
I don't think there is a simpler way. This thread doesn't mention an alternative: https://stackoverflow.com/questions/17387435/javascript-sort-array-of-objects-by-a-boolean-property and it seems pretty well reviewed. – maxm Jan 11 '21 at 15:55
I would just say, anecdotally, that it doesn't really matter. Your data is extremely small so looping twice is incredibly fast. If your data got much bigger then I still don't think looping through twice is acceptable in almost all cases I've run into. If you're looking for something more elegant, I certainly can't think of a way :( – maxm Jan 11 '21 at 15:59

score 1 · Accepted Answer · answered Jan 11 '21 at 16:47

It's certainly not necessary to iterate the list twice, though the below method uses more memory:

func (input Input) Sort() *[]string {
    if input.Media == nil || LimitedAmountItems <= 0 {
        return new([]string)
    }

    isPrinciple = make([]string, 0, LimitedAmountItems
    var notPrinciple []string
    
    for _, media := range input.Media {
        if media.IsPrincipal {
            isPrinciple = append(isPrinciple, media.URL)
        } else {
            notPrinciple = append(notPrinciple, media.URL)
        }
        if len(isPrinciple) >= LimitedAmountItems {
             return &isPrinciple
        }
    }
    
    items := append(isPrinciple, notPrinciple[:LimitedAmountItems-len(isPrinciple)]...)
    return &items
}

This iterates the list only once, while maintaining the same behavior, though it may use some additional memory for the second holding slice (however it should also have fewer allocations as it preallocates one slice).

Nice! Probably worth noting that this is more optimal because of optimizations around append concatenations: https://github.com/golang/go/issues/21266. Since otherwise one might think that `append` here is really just another loop under the hood. — maxm, Jan 11 '21 at 16:52
Thanks, I like this solution, I think it has good readability — mbbo128, Jan 11 '21 at 17:06

score 0 · Answer 3 · answered Jan 11 '21 at 16:59

Ah, I found a way to do it in one shot, just add the IsPincipal items to the front and the !IsPrincipal items to the back.

func (input Input) Sort() []string {
    var length int = LimitedAmountItems
    if len(input.Media) < LimitedAmountItems {
        length = len(input.Media)
    }
    out := make([]string, length)

    start := 0
    end := len(out) - 1
    for i, m := range input.Media {
        if i == LimitedAmountItems {
            break
        }
        if m.IsPrincipal {
            out[start] = m.URL
            start++
        } else {
            out[end] = m.URL
            end--
        }
    }
    return out
}

How to delete a foreach and reduce complexity in a go algorithme

3 Answers3