Comparez les membres de l'icollection avec lui-même

Question

Existe-t-il un moyen le moins cher de comparer une icollection avec lui-même.

Voici mon code:

        public IEnumerable<Pet> speciesChecker()
        {
            foreach (Pet pet in _pets)
            {
                bool wantedSpecies = true;
                foreach (Pet pet2 in _pets)
                {
                    if (pet2 != pet && pet.Species == pet2.Species)
                    {
                        wantedSpecies = false;
                        break;
                    }
                }
                if (wantedSpecies) yield return pet;
            }
        }

Quelle est la complexité du temps de mon code, tout ce que je sais, c'est que c'est moins que O (n ^ 2) et si je supprimerai la «rupture» de la boucle intérieure de Foreach, la complexité du temps sera o (n ^ 2) . S'il vous plait corrigez moi si je me trompe.

Answer 1

laisser n est la longueur de _pets collection

Nombre d'étapes requises avec pause:

1+2+3+...+n = n*(n+1)/2 =n^2/2 + n/2 = O(n^2) (for each pet in _pets);

Il existe deux règles simples pour calculer O à partir du wiki:

1. Si F (x) est une somme de plusieurs termes, celui qui a le plus grand taux de croissance est conservé, et tous les autres ont omis.

2. Si f (x) est un produit de plusieurs facteurs, toutes les constantes (termes du produit qui ne dépendent pas de x) sont omis.

Nombre d'étapes requises sans interruption:

n+n+n+...+n = n^2 = O(n^2)

Answer 2

Voici mon point de vue:

var q = list.GroupBy (l => l.Species)
          .Where (l => l.ElementAtOrDefault(1) == null)
          .Select (l => l.Key)

GroupBy utilisera hashset en interne pour o (n)
ElementAtOrDefault(1) aura seulement besoin de déplacer l'énumérateur une étape, donc ne pas être sur)

Answer 3

je pense que ce code fait la même chose. Dans ce cas, il s'agit d'un algorithme O (n). L'astuce consiste à stocker les animaux de compagnie dans un dictionnaire indexé par les espèces.

    public IEnumerable<Pet> speciesChecker()
    {
        var species = new Dictionary<Species, List<Pet>>();
        foreach (Pet pet in _pets)
        {
            // create the list if it doesn't exist
            if (!species.ContainsKey(pet.Species))
                species[pet.Species] = new List<Pet>();
            species[pet.Species].Add(pet);
        }

        // foreach species, if there is only one pet of that species, then return it
        foreach (var speciesPets in species.Values)
        {
            if (speciesPets.Count() == 1)
                yield return speciesPets.First();
        }

        yield break;
    }

Answer 4

Vous pouvez également utiliser quelque chose comme ce qui suit, qui devrait également être O (n):

public IEnumerable<Pet> speciesChecker ()
{
    _pets.GroupBy (p => p.Species)
         .Select (g => new List<Pet> (g))
         .Where (l => l.Count == 1)
         .SelectMany (l => l);
}

L'extra Select (g => new List<Pet> (g)) peut Soyez superflu, mais je crois que cela aidera à éviter d'itréter toute la logique de regroupement une deuxième fois, ce qui, je crois, entraînerait O (n ^ 2).

Éditer: Bon commentaire de Magnus sur le constructeur de la liste opérant en O (n) battant le but ...

Que diriez-vous:

public IEnumerable<Pet> speciesChecker ()
{
    var groups = _pets.GroupBy (p => p.Species);

    foreach (var grp in _pets.GroupBy (p => p.Species))
    using (var e = grp.GetEnumerator ()) {
        if (!e.MoveNext ())
            continue;

        var first = e.Current;

        if (e.MoveNext ())
            continue;

        yield return first;
    }
}

je pense Ceci est aussi optimisé que possible et fonctionnera en o (n). Nous évitons d'utiliser le IEnumerable<T>.Any () ou IEnumerable<T>.Count () Méthode d'extension également.

Les pensées?