Recherche Linq et binaire - Améliorer cette lente Où l'instruction?

Question

J'ai deux collections, contenant chacune environ 40 000 articles.

Les éléments de la liste 2 sont liés aux éléments de la liste 1 via une clé étrangère.

Pour chaque élément de la liste un, je veux trouver l'élément correspondant dans la liste deux.

Quelque chose comme ceci:

foreach(var item in list1) 
{ 
    var match = list2.Where(child => child.ID == item.ChildID).FirstOrDefault(); 
    item.Child = match; 
} 

Cela fonctionne, mais il est lent comme l'enfer.

Maintenant, list1 et list 2 sont triés par ces clés à partir de la base de données. Ainsi, list1 est trié par ChildID et list2 est ordonné par ID (même valeur).

Je pense qu'une recherche binaire accélérerait considérablement cela, mais j'ai lu quelque part que Linq choisirait la stratégie la plus appropriée pour la liste dans la clause Where. Peut-être que j'ai besoin de lancer explicitement à une liste triée? Ou peut-être ai-je besoin d'implémenter un algorithme de recherche binaire personnalisé avec un comparateur?

Tous les aperçus sont appréciés.

Merci.

Answer 1

Pourquoi ne pas utiliser une jointure?

var query = 
    from a in list1 
    join b in list2 on a.ChildID equals b.ID 
    select new {Item1 = a, Item2 = b}; 

foreach(var item in query) 
{ 
    item.Item1.Child = item.Item2; 
}

Answer 2

Je ne sais pas si cela accélérerait réellement en tout, mais vous pouvez déplacer le prédicat dans la FirstOrDefault() clause et de se débarrasser de l'endroit où tout à fait. Cela peut ne pas aider car cela pourrait implicitement appeler simplement Where().

Voici une question cependant: la méthode est-elle réellement lente ou est-elle lente seulement la première fois qu'elle est exécutée après une compilation? Découvrez la discussion on this post.

Answer 3

J'ai eu ce problème auparavant, la recherche basée sur LINQ est extrêmement lente par rapport à la base de données DB car elle n'utilise aucun index.

Avez-vous envisagé d'utiliser un Dictionary au lieu de List?

Vous pouvez implémenter un dictionnaire, puis au lieu d'utiliser Where, vous pouvez utiliser ContainsKey et, s'il existe, obtenir la valeur en utilisant index accessor.

Exemple de code:

Dictionary<int, Child> list2 = ...; 

... 

foreach(var item in list1) 
{ 
    if (list2.ContainsKey(item.ChildID)) 
    item.Child = list2[item.ChildID]; 
} 

Access à l'aide index serait nettement plus rapide que la recherche d'une liste, sur le coût de la mémoire supplémentaire requise pour l'indice.

Answer 4

Qu'en est-ce:

 var joined = list1.Join(list2, x => x.ChildID, x => x.ID, (x, y) => new { x, y }); 

     foreach (var j in joined) 
     { 
      j.x.Child = j.y; 
     } 

?

Answer 5

Comme les deux listes sont classés sur la même valeur, vous pouvez juste boucle à travers eux en parallèle:

int index1 = 0, index2 = 0; 
while (index1 < list1.Count && index2 < list2.Count) { 
    while (index1 < list1.Count && list1[index1].ChildId < list2[index2].Id) index1++; 
    if (index1 < list1.Count) { 
     while (index2 < list2.Count && list2[index2].Id < list1[index1].ChildId) index2++; 
     if (index2 < list2.Count && list1[index1].ChildId == list2[index2].Id) { 
     list1[index].Child = list2[index2]; 
     index1++; 
     index2++; 
     } 
    } 
} 

ou:

int index1 = 0, index2 = 0; 
while (index1 < list1.Count && index2 < list2.Count) { 
    if (list1[index1].ChildId == list2[index2].Id) { 
     list1[index].Child = list2[index2]; 
     index1++; 
     index2++; 
    } else { 
     if (list1[index1].ChildId < list2[index2].Id) { 
     index1++; 
     } else { 
     index2++; 
     } 
    } 
} 

Une autre alternative efficace, mais qui ne profite pas de l'ordre des listes, est de créer un index en mettant l'une des listes dans un dictionnaire:

Dictionary<int, TypeOfChild> index = new Dictionary<int, TypeOfChild>(); 
foreach (TypeOfChild child in list2) { 
    index.Add(child.Id, child); 
} 
foreach (TypeOfParent parent in list1) { 
    TypeOfChild child; 
    if (index.TryGetValue(parent.ChildId, out child) { 
     parent.Child = child; 
    } 
} 

Answer 6

Je ne pouvais pas résister à répondre à cela :-)

La raison principale pour laquelle votre code devient lent, c'est que vos articles seront lus plusieurs fois. L'art de la vitesse est: Ne lisez la mémoire que si vous en avez besoin et si vous avez besoin de la lire, lisez-la le moins possible.

Voici un exemple:

Code

public class Item 
{  
    private int _id; 
    private List<ItemDetails> _detailItems = new List<ItemDetails>(); 

    public Item(int id)<br> 
    { 
     _id = id; 
    } 

    public void AddItemDetail(ItemDetails itemDetail) 
    { 
     _detailItems.Add(itemDetail); 
    } 

    public int Id 
    { 
     get { return _id; } 
    } 
    public ReadOnlyCollection<ItemDetails> DetailItems 
    { 
     get { return _detailItems.AsReadOnly(); } 
    } 
} 


public class ItemDetails 
{ 
    private int _parentId; 

    public ItemDetails(int parentId) 
    { 
     _parentId = parentId; 
    } 

    public int ParentId 
    { 
     get { return _parentId; } 
    } 
} 

exemple de code:

L'objectif principal est de scanner les listes et comparer l'élément et ItemDetail sur les indices actuels. Quand le parentid est égal à son id de parents. ajoutez-le à la liste et passez au détail suivant. Si c'est différent, passez au parent suivant.

// for performance tests.. 
DateTime startDateTime; 

// create 2 lists (master/child list) 
List<Item> itemList = new List<Item>(); 
List<ItemDetails> itemDetailList = new List<ItemDetails>(); 

Debug.WriteLine("# Adding items"); 
startDateTime = DateTime.Now; 

// add items (sorted) 
for (int i = 0; i < 400000; i++) 
    itemList.Add(new Item(i)); 

// show how long it took 
Debug.WriteLine("Total milliseconds: " + (DateTime.Now - startDateTime).TotalMilliseconds.ToString("0") + "ms"); 

// adding some random details (also sorted) 
Debug.WriteLine("# Adding itemdetails"); 
Random rnd = new Random(DateTime.Now.Millisecond); 

startDateTime = DateTime.Now; 

int index = 0; 
for (int i = 0; i < 800000; i++) 
{ 
    // when the random number is bigger than 2, index will be increased by 1 
    index += rnd.Next(5) > 2 ? 1 : 0; 
    itemDetailList.Add(new ItemDetails(index)); 
} 
Debug.WriteLine("Total milliseconds: " + (DateTime.Now - startDateTime).TotalMilliseconds.ToString("0") + "ms"); 

// show how many items the lists contains 
Debug.WriteLine("ItemList Count: " + itemList.Count()); 
Debug.WriteLine("ItemDetailList Count: " + itemDetailList.Count()); 

// matching items 
Debug.WriteLine("# Matching items"); 
startDateTime = DateTime.Now; 

int itemIndex = 0; 
int itemDetailIndex = 0; 

int itemMaxIndex = itemList.Count; 
int itemDetailMaxIndex = itemDetailList.Count; 

// while we didn't reach any end of the lists, continue... 
while ((itemIndex < itemMaxIndex) && (itemDetailIndex < itemDetailMaxIndex)) 
{ 
    // if the detail.parentid matches the item.id. add it to the list. 
    if (itemList[itemIndex].Id == itemDetailList[itemDetailIndex].ParentId) 
    { 
     itemList[itemIndex].AddItemDetail(itemDetailList[itemDetailIndex]); 
     // increase the detail index. 
     itemDetailIndex++; 
    } 
    else 
     // the detail.parentid didn't matches the item.id so check the next 1 
     itemIndex++; 
} 

Debug.WriteLine("Total milliseconds: " + (DateTime.Now - startDateTime).TotalMilliseconds.ToString("0") + "ms"); 

résultats

j'ai pris 10 fois plus d'articles pour voir un meilleur résultat:

articles Ajout:
millisecondes au total: 140ms
itemdetails Ajout:
millisecondes au total: 203ms
Nombre d'articles: 400000
ItemDetailList Count: 800000
articles correspondants:
millisecondes au total: 265ms

Cela a été tapé rapide et pourrait être plus propre. Donc j'espère que vous pouvez le lire. Joue avec.

Greetz, Jeroen.