Qual è la complessità computazionale del metodo Groovy unique ()?

Poiché Lernkurve ha evidenziato nei commenti, l'implementazione fornita nel codice sorgente di Groovy sembra essere O (n ^ 2) .

public static <T> Collection<T> unique(Collection<T> self, boolean mutate) {
    List<T> answer = new ArrayList<T>();
    for (T t : self) {                    // << Outer loop over each item
        boolean duplicated = false;
        for (T t2 : answer) {             // << Inner loop over each found item
            if (coercedEquals(t, t2)) {
                duplicated = true;
                break;
            }
        }
        if (!duplicated)
            answer.add(t);
    }
    if (mutate) {
        self.clear();
        self.addAll(answer);
    }
    return mutate ? self : answer ;
}

Il ciclo esterno assicura che la complessità temporale sia almeno pari a O (n), poiché crescerà in modo lineare man mano che l'elenco di input cresce. Allo stesso modo, il ciclo interno preso da solo è O (n). Per ogni elemento nell'elenco di input, quindi scorre su ogni elemento che è registrato nell'elenco "risposta" per vedere se quell'elemento è già contenuto. Mettili insieme e hai una funzione O (n ^ 2).

Come ho sottolineato nei commenti, ci sono alcuni modi per ottenere prestazioni migliori da questo, per grandi serie. Se sei disposto a spendere un po 'di memoria in più, puoi usare un set di hash di qualche tipo per registrare se un elemento è già stato incluso o meno. Questi hanno generalmente un tempo di ricerca O (1) per verificare se l'elemento corrente è univoco nell'elenco.

In alternativa, l'ordinamento dell'elenco di input (se è ordinabile) con una buona funzione di ordinamento (la maggior parte di quelli inclusi nella libreria standard di una lingua sarà O (n log n)) può aiutare, presumendo che non ti interessi ordine dell'elenco di output "univoco". In questo modo puoi essere sicuro che gli elementi duplicati appariranno sempre in sequenza tra loro e diventa banale rifiutarli dall'output.