algorithm - 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 :

schema

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 ?

Answer 1

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).