intersection performant et extraction de l'élément distinct?

Question

J'ai une ligne comme ce qui suit dans mon code:

potentialCollisionsX.Intersect(potentialCollisionsY).Distinct().ToList();

Ce qui, à travers le profilage, j'ai déterminé qu'il mange environ 56 pour cent de mon temps. Je dois comprendre comment fournir une mise en œuvre efficace. J'ai essayé

        List<Extent> probableCollisions = new List<Extent>();
        for (int j = 0; j < potentialCollisionsX.Count; j++)
        {
            if (potentialCollisionsY.Contains(potentialCollisionsX[j]) && !probableCollisions.Contains(potentialCollisionsX[j]))
            {
                probableCollisions.Add(potentialCollisionsX[j]);
            }
        }

mais qu'il ne baisse que de 42 pour cent. Optimisations ou d'autres idées seraient appréciées.

Edit:. Quelqu'un a demandé des informations sur la classe étendue, et je ne peux pas penser à une meilleure façon de leur donner des informations que de fournir la définition de classe

    private enum ExtentType { Start, End }
    private sealed class Extent
    {
        private ExtentType _type;
        public ExtentType Type
        {
            get
            {
                return _type;
            }
            set
            {
                _type = value;
                _hashcode = 23;
                _hashcode *= 17 + Nucleus.GetHashCode();
            }
        }
        private Nucleus _nucleus; //Nucleus is the main body class in my engine
        public Nucleus Nucleus
        {
            get
            {
                return _nucleus;
            }
            set
            {
                _nucleus = value;
                _hashcode = 23;
                _hashcode *= 17 + Nucleus.GetHashCode();
            }
        }

        private int _hashcode;

        public Extent(Nucleus nucleus, ExtentType type)
        {
            Nucleus = nucleus;
            Type = type;
            _hashcode = 23;
            _hashcode *= 17 + Nucleus.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            return Equals(obj as Extent);
        }
        public bool Equals(Extent extent)
        {
            if (this.Nucleus == extent.Nucleus) //nucleus.Equals does an int comparison
            {
                return true;
            }
            return false;
        }
        public override int GetHashCode()
        {
            return _hashcode;
        }
    }

Edit2: Il semblerait que l'utilisation HashSet fait cette partie de mon code comme j'ai besoin que performant, donc merci pour l'aide de votre type

Answer 1

Essayez ceci:

HashSet<Extent> result = new HashSet<Extent>();
HashSet<Extent> potentialSetY = new HashSet<Extent>(potentialCollisionsY);
foreach (Extent ex in potentialCollisionsX)
    if (potentialSetY.Contains(ex))
        result.Add(ex);

ensembles Hash sont bonnes à faire Contains rapidement, mais ne « t maintien de l'ordre

---

Si vous avez besoin de préserver l'ordre, voici quelque chose d'un peu plus compliqué: Un ensemble de hachage commandé. Il utilise la sémantique de jeu de hachage normale (bien, un dictionnaire, mais il est la même chose), mais avant l'énumération, il réorganise les éléments en fonction de l'ordre d'insertion.

// Unchecked code

public class OrderedHashSet<T> : IEnumerable<T> {
    int currentIndex = 0;
    Dictionary<T, index> items = new Dictionary<T, index>();

    public bool Add(T item) {
        if (Contains(item))
            return false;
        items[item] = currentIndex++;
        return true;
    }

    public bool Contains(T item) {
        return items.ContainsKey(item);
    }

    public IEnumerator<T> GetEnumerator() {
        return items.Keys.OrderBy(key => items[key]).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

Maintenant, il suffit de changer HashSet à OrderedHashSet dans l'exemple ci-dessus et devraient travail.

Answer 2

Intersect retourne des éléments distincts de toute façon, ce qui rend l'appel à Distinct() inutile. Ce sera de manger au moins une partie de votre temps.

En outre, vous avez réellement besoin d'appeler ToList? Que faites-vous alors le résultat?

L'ordre d'importance? Dans le cas contraire, vous devriez envisager d'utiliser un HashSet<T> au lieu d'un List<T> pour votre code « manuel ». (Et sans doute créer un HashSet<T> pour potentialCollisionsY aussi bien.) Cela fera l'appel Contains plus rapidement, au moins si les collections sont assez grandes ...

Par ailleurs, ne croient pas la documentation pour Intersect - il est tort au sujet de l'ordre des opérations (au moins dans .NET 3.5)

Answer 3

OK, je vois la définition de la classe étendue. Tout d'abord, il viole la règle que si obj1.Equals(obj2)==true obj1.GetHashCode()==obj2.GetHashCode() alors. Mais c'est d'ailleurs le point et peut être fixé (si vous ne les algorithmes qui dépendent de hachage, comme un HashSet échouerez).

Maintenant, si la seule opération que l'on peut faire sur l'objet étendue est de comparer l'égalité, alors il ne sera pas possible d'obtenir la plus mauvaise performance de cas ci-dessus O (N * M) ( où N est la taille de la première collection, et M est la taille de la deuxième collection). C'est parce que vous aurez finalement à comparer chaque élément avec chaque élément.

Cela peut être amélioré par l'utilisation de GetHashCode() et le fait que les objets avec des codes de hachage différents seront également différentes elles-mêmes. D'autres personnes ont suggéré d'utiliser la classe HashSet, ce serait une telle solution. La meilleure performance de cas dans ce cas serait O (N + M) , et le pire des cas - O (N + N * M) . En moyenne, si vous devez gagner, à moins que la méthode GetHashCode() est très mal mis en œuvre et renvoie les mêmes codes de hachage pour de nombreux objets.

Je me préfère une solution plus stable. Si la classe de mesure peut être triée de manière fiable (c'est, si vous pouvez comparer deux objets étendue voir que l'on était plus grand et que l'on était plus petit), vous pouvez trier les listes et la performance pourrait être ramené à O (tri + M + N) . L'idée est que lorsque les listes sont triées, vous pouvez passer par les deux simultanément et rechercher des éléments égaux là-bas.

Maintenant, la performance de tri est la chose la plus délicate ici. Si vous ne mettre en œuvre l'opération de comparaison (comme dans l'interface IComparable), vous serez en mesure de trier les listes en temps O (N + M * log * logM) . La méthode standard de List.Sort() doit le faire pour vous. Dans l'ensemble, la performance totale serait O (N + M * log * logM + N + M) . Il faut noter cependant que celui-ci utilise l'algorithme QuickSort qui fonctionne mal sur les listes presque triés. Le pire des cas est une liste complètement triée dans ce cas, il est O (N * M) . Si vos listes sont proches d'être triés déjà, vous devriez envisager un autre algorithme de tri (et mettre en œuvre vous-même).

Le nec plus ultra de la vitesse fiable serait si vous pouvez convertir chaque étendue à un nombre entier (ou plus généralement, une chaîne de caractères) avec la propriété que si les chaînes sont égales, les Étendues sont égales aussi bien, et si les chaînes ne sont pas égales, les Étendues ne sont pas égaux non plus. La chose avec des chaînes est qu'ils peuvent être classés dans le temps linéaire avec des algorithmes comme radix sorte , < a href = "http://en.wikipedia.org/wiki/Radix_tree" rel = "nofollow noreferrer"> arbre radix , etc. Ensuite, le tri ne prendra que le temps de O (N + M) . En fait, si vous avez construit un arbre Radix, vous ne devez trier la première liste et vous pouvez rechercher des chaînes dans directement (avec chaque recherche prenant O (1) Heure). Dans l'ensemble, la performance totale serait O (N + M) qui est le meilleur disponible.

Une chose que vous devez toujours garder à l'esprit - grands algorithmes ont de grandes constantes. L'approche radix pourrait regarder le meilleur sur le papier, mais il sera très difficile à mettre en œuvre et généralement plus lent que les approches plus simples pour les petites quantités de données. Seulement si vos listes comportent des éléments dans les gammes de milliers et des dizaines de milliers devriez-vous commencer à penser à ce sujet. En outre, ces algorithmes ont besoin pour créer beaucoup de nouveaux objets et le coût de chaque opération de new() devient importante aussi bien. Vous devriez réfléchir pour réduire au minimum le nombre d'allocations nécessaires.

Answer 4

Si vous ne pouvez pas trouver une meilleure solution, envisager d'utiliser le code non géré en dernier recours.

Answer 5

Deux approches:

Mettre les articles dans un hashmap si elles ne sont pas là déjà, marquer les autres dans la hashmap reproduite. Ceci est O (n). Vous parcourons ensuite sur tous les éléments du hashmap et de voir si elles sont marquées comme doublon ou non -. O (n) à nouveau

Une autre approche:

Trier les deux listes. Ceci est un O (nlogn) opération, mais il pourrait être cruciale que vous pouvez heureusement maintenir les deux listes triées en tout temps, et donc le coût n'a pas été prise lors de la recherche spécifiquement pour l'intersection etc.

Ensuite, passer par les deux listes dans l'ordre, trouver distinct et dupliquer etc entrées. Ceci est O (n).