Quelle est la façon la plus efficace de comparer une grande liste d'entiers à une petite liste d'entiers?

Question

Pour le moment, j'ai un list de 1 million integers , et je compare chaque integer à une liste noire de 2000 integer s. Cela prend environ 2 minutes.

 for(int i = 0; i< MillionIntegerList.Length ; i++)
{
    for(int blacklisted = 0; blacklisted < TwoThousandIntegerList.Length ; blacklisted++)
        if(i==blacklisted)
            i = 0; //Zero is a sentinel value 
}
 

Cela fait 2 000 000 000 d'itérations (boucles) au total. Y a-t-il une meilleure façon de ne pas voir? Merci

Answer 1

Trois options - les deux premiers sont plus générales, en ce qu'elles ne reposent pas sur des MillionIntegerList triées (ce qui n'était pas initialement prévu). Le troisième est préférable dans le cas où la liste est déjà triée.

Option 1

Oui, il y a certainement une meilleure façon de le faire, à l'aide de LINQ:

var common = MillionIntegerList.Intersect(TwoThousandIntegerList).ToList();

Qui va utiliser à l'interne un HashSet<int> construits par l'intermédiaire de l' TwoThousandIntegerList, puis de regarder chaque élément de l' MillionIntegerList au sein de ce qui sera beaucoup plus efficace que de passer par l'ensemble de l' TwoThousandIntegerList à chaque fois.

Si vous voulez seulement le non sur la liste noire, vous devez:

var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();

Notez que si vous avez seulement besoin d'itérer sur les résultats une fois, vous devez supprimer l' ToList appelez - je l'ai inclus pour matérialiser les résultats de manière à ce qu'ils puissent être examinés à plusieurs reprises à moindre coût. Si vous êtes juste de l'itération, la valeur de retour de l' Intersect ou Except sera juste stream les résultats, ce qui rend beaucoup moins cher en termes de l'utilisation de la mémoire.

Option 2

Si vous ne voulez pas compter sur les détails de mise en œuvre de LINQ to Objects, mais vous voulez une base de hachage approche:

var hashSet = new HashSet<int>(TwoThousandIntegerList);
hashSet.IntersectWith(MillionIntegerList);
// Now use hashSet

Option 3

L'approche de l'aide du fait que la grande liste est triée serait certainement utile.

En supposant que vous n'avez pas l'esprit de tri de la liste noire de la liste de la première, vous pourriez écrire un streaming (et générale) de la mise en œuvre de cette façon (non testé):

// Note: to use this, you'd need to make sure that *both* sequences are sorted.
// You could either sort TwoThousandIntegerList in place, or use LINQ's OrderBy
// method.

public IEnumerable<T> SortedIntersect<T>(this IEnumerable<T> first,
    IEnumerable<T> second) where T : IComparable<T>
{
    using (var firstIterator = first.GetEnumerator())
    {
        if (!firstIterator.MoveNext())
        {
            yield break;
        }

        using (var secondIterator = second.GetEnumerator())
        {
            if (!secondIterator.MoveNext())
            {
                yield break;
            }
            T firstValue = firstIterator.Current;
            T secondValue = secondIterator.Current;

            while (true)
            {
                int comparison = firstValue.CompareTo(secondValue);
                if (comparison == 0) // firstValue == secondValue
                {
                    yield return firstValue;
                }
                else if (comparison < 0) // firstValue < secondValue
                {
                    if (!firstIterator.MoveNext())
                    {
                        yield break;
                    }
                    firstValue = firstIterator.Current;
                }
                else // firstValue > secondValue
                {
                    if (!secondIterator.MoveNext())
                    {
                        yield break;
                    }
                    secondValue = secondIterator.Current;
                }  
            }                
        }
    }
}

(Vous pourriez prendre un IComparer<T> si vous vouliez plutôt que de s'appuyer sur des T être comparables.)

Answer 2

Depuis la grande liste est triée. Vous pouvez obtenir les meilleurs résultats en triant la petite liste (très rapidement) puis en effectuant une fusion linéaire. Vous n'aurez besoin de regarder chaque élément de la grande (et petite) liste qu'une seule fois, et il ne sera pas nécessaire de créer une table de hachage en arrière-plan.

Voir la partie fonction de fusion de MergeSort pour une idée sur la façon de procéder.

Answer 3

Ce dont vous avez besoin est Enumerable.Except, méthode (IEnumerable, IEnumerable) à mon avis

vérifiez ici http://msdn.microsoft.com/en-us/library/bb300779.aspx

Answer 4

Votre approche nécessite O(n*n) fois. Tenir compte de ces optimisations:

• 1)

  Si votre entiers ne sont pas trop grandes, vous pouvez utiliser le tableau de bool (par exemple, si le plus grand possible entier est 1000000 utiliser bool[] b = new boolean[1000000]). Maintenant pour ajouter un nombre K à la liste noire de l'utilisation de b[K] = true. Case est trivial. Cela fonctionne en O(n). Vous pouvez également utiliser BitArray

• 2)

  Les nombres entiers peuvent être assez grande. Utiliser les binaires un arbre de recherche pour le stockage de la liste noire (par exemple SortedSet). il a O(logN) insérer et extraire le temps. Donc dans l'ensemble c'est O(N*logN). La syntaxe est la même que pour la Liste (Ajouter(int K), Contient(int K)), les doublons sont ignorés

Answer 5

Utilisez un HashSet pour la liste bloquée.

 foreach(integer i in MillionIntegerList)
{
        //check if blockedlist contains i
        //do what ever you like. 
}