Implémenter votre propre LINQ & IEnumerable <T>

Question

Dans un projet sur lequel je travaille, il y a de très grandes collections (éléments 1M-1B), et les choses sont principalement modifiées en tant que collections.

C'est une application en temps réel, et les performances sont donc primordiales.

Pour certaines opérations, comme inverse, BinarySearch (possible?), Etc souffriront plus que d'autres comme Select, etc.

Est-il possible de mettre en œuvre son propre IEnumerable avec MoveNext possible, MovePrev, etc et propres extensions LINQ implémentées qui en profitent?

Si cela se produit, cela arrivera à la fin du projet. Parce que nous devons d'abord le faire fonctionner, puis le rendre plus rapide.

Dans l'ensemble, cela ne devrait pas être trop de travail, non?

Answer 1

Il est très certainement possible de créer votre propre implémentation de Enumerable qui peut être un cas particulier dans certaines situations. Vous souhaitez essentiellement détecter vos propres types de collection (ou éventuellement uniquement les collections telles que List<T>) et utiliser une implémentation plus efficace le cas échéant.

J'ai un sample project que j'ai utilisé pour faire la démonstration de "l'implémentation de LINQ to Objects en une heure" que vous pourriez vouloir regarder par exemple. Ce n'est pas une implémentation complète et en particulier moins efficace que le vrai LINQ to Objects - mais vous pouvez toujours trouver cela intéressant.

Alternativement, vous pouvez trouver que i4o (Indexed LINQ) fait tout ce dont vous avez besoin hors de la boîte - ou que vous feriez mieux de contribuer à cela que de partir de zéro. Ça vaut le coup de vérifier. N'oubliez pas qu'à la fin de la journée, LINQ est un joli design couplé à du sucre syntaxique. Le compilateur C# ne connaît pas quoi que ce soit spécial à propos de System.Linq.Enumerable, par exemple.

Answer 2

Si vous voulez vraiment des performances, vous pouvez en faire beaucoup. Rappelez-vous que la sélection suivante:

var result = from element in collection 
      where element.Id == id 
      select element; 

Compile comme:

var result = collection.Where(element => element.Id == id); 

Si vous créez la méthode suivante pour le type de collection, alors vous pouvez exploiter le fait que l'action principale est l'égalité de l'Id membre et gérer la demande de manière optimisée. L'important est d'identifier correctement les opérations critiques pour la performance de votre collection et de choisir les algorithmes corrects (c'est-à-dire la complexité) pour les exécuter.

public IEnumerable<TElement> Where(Expression<Func<TElement, bool>> selector) 
{ 
    // detect equality of the Id member and return some special value 
} 

Answer 3

Tenir compte System.Linq.Enumerable.Reverse() - cette méthode entièrement IEnumerable énumère avant de retourner le premier résultat. Si votre requête est myCollection.Reverse(). Take (10), et votre collection a des milliards d'objets, c'est une idée horrible d'énumérer les milliards d'objets pour obtenir 10 out.

Si vous avez fourni une méthode Reverse sur votre propre type, vous pouvez fournir une meilleure implémentation qui boucle simplement en arrière sur la collection (éventuellement par index).

La clé pour cela est de fournir votre propre type où vous contrôlez les implémentations. Vous ne pouvez pas utiliser les implémentations qui fonctionnent pour tous IEnumerable<T> car ces implémentations ne tireront pas pleinement parti des fonctionnalités de votre type de collection personnalisé.

Answer 4

Est-il possible de mettre en œuvre son propre IEnumerable avec MoveNext possible, MovePrev, etc et posséder mis en œuvre LINQ extensions qui ont des avantages de ceux-ci?

IEnumerable (ou plus correctement, IEnumerator) n'a pas MovePrev. Vous pouvez définir une interface:

public interface IReversable<T> : IEnumerable<T> 
{ 
    IEnumerator<T> GetReverseEnumerator(); 
} 

Cela peut être implémenté par n'importe quel conteneur qui prend en charge l'énumération inverse efficace.

Vous pouvez alors écrire une surcharge de Reverse (la méthode d'extension) pour travailler sur cette nouvelle interface, et les classes de collection qui implémentent l'interface, etc. Et puis vous devrez utiliser ces classes de collection au lieu des classes standard comme List<T>.

Mais (je n'ai pas réflecteur à portée de main pour vérifier) ​​il se peut que le haut-Reverse est assez intelligent pour faire les choses rapidement si elle peut obtenir l'interface IList de la collection, ce qui optimiserait le plus cas communs juste bien quand même.

Il n'y a peut-être pas beaucoup de points dans ce genre d'approche.