Comment effectuer un tri de fusion à l'aide de LINQ?

Question

Supposons que vous avez deux objets IEnumerbale. Comment pouvons-nous les fusionner (dans certaines conditions, par exemple, fusionner dans un tri par fusion ...) et créer un IEnumerable unique? J'ai essayé ceci avec Zip, mais dans Zip les deux tailles de liste devraient être égales (peut-être vous n'avez pas eu l'exception mais peut-être nous avons quelques données perdues.)

En outre, je l'essaie en utilisant Enumerable.Range (. ..). Sélectionnez (...) mais je n'ai pas obtenu un résultat acceptable. En outre, ma question est totalement différente de l'utilisation de Union ou this one, en fait, comme je l'ai dit comme fusion dans le tri de fusion, j'aime préserver l'ordre des listes (en fait, je veux juste combler certaines lacunes dans la première liste).

Il est facile de le gérer avec une boucle for, mais je ne vois pas de chemin linq complet.

Edit:

Sample input: 

lst1 = {5,10,12} 
lst2 = {7,9,16,20,25} 

result: {5,7,9,10,12,16,20,25} 

cela peut se faire avec une boucle et deux pointeur dans O(n + m) mais je suis à la recherche d'une solution LINQ dans O(n+m)

pour la solution de boucle:

 var lst1 = new List<int> { 5, 10, 12 }; 
     var lst2 = new List<int> { 7, 9, 16, 20, 25 }; 

     var result = new List<int>(); 

     int j = 0; 
     for (int i = 0; i < lst1.Count; i++) 
     { 
      while (j < lst2.Count && lst2[j] < lst1[i]) 
      { 
       result.Add(lst2[j]); 
       j++; 
      } 
      result.Add(lst1[i]); 
     } 

     while (j < lst2.Count) 
     { 
      result.Add(lst2[j]); 
      j++; 
     } 
     Console.WriteLine(string.Join(",", result.ToArray())); 

Answer 1

Il n'existe aucune méthode de ce type dans LINQ. Et je ne pense pas qu'il soit possible de combiner les méthodes existantes pour faire exactement ce que vous voulez (si c'était le cas, ce serait trop compliqué).

Mais la mise en œuvre cette méthode vous est pas difficile:

static IEnumerable<T> Merge<T>(this IEnumerable<T> first, 
           IEnumerable<T> second, 
           Func<T, T, bool> predicate) 
{ 
    // validation ommited 

    using (var firstEnumerator = first.GetEnumerator()) 
    using (var secondEnumerator = second.GetEnumerator()) 
    { 
     bool firstCond = firstEnumerator.MoveNext(); 
     bool secondCond = secondEnumerator.MoveNext(); 

     while (firstCond && secondCond) 
     { 
      if (predicate(firstEnumerator.Current, secondEnumerator.Current)) 
      { 
       yield return firstEnumerator.Current; 
       firstCond = firstEnumerator.MoveNext(); 
      } 
      else 
      { 
       yield return secondEnumerator.Current; 
       secondCond = secondEnumerator.MoveNext(); 
      } 
     } 

     while (firstCond) 
     { 
      yield return firstEnumerator.Current; 
      firstCond = firstEnumerator.MoveNext(); 
     } 

     while (secondCond) 
     { 
      yield return secondEnumerator.Current; 
      secondCond = secondEnumerator.MoveNext(); 
     } 
    } 
} 

Et vous pouvez l'utiliser comme ceci:

lst1.Merge(lst2, (i, j) => i < j) 

Answer 2

Utiliser la méthode LINQ Concat()http://msdn.microsoft.com/en-us/library/bb302894.aspx

Answer 3

Il n'existe pas de méthode de fusion dans System.Linq.Enumerable. Si vous en voulez un, vous devez l'écrire (avec une boucle for et une déclaration de rendement).

Comme avec beaucoup de questions "juste par linq" - vous devez supposer que chaque méthode linq est soutenue par un code .NET vieux ordinaire que vous auriez pu écrire vous-même.

---

est ici une implémentation Freehand non testé non générique

public static IEnumerable<int> Merge 
(
this IEnumerable<int> source1, 
IEnumerable<int> source2 
) 
{ 
    using(Enumerator<int> e1 = source1.GetEnumerator()) 
    { 
    bool more1 = e1.MoveNext(); 
    using(Enumerator<int> e2 = source2.GetEnumerator() 
    { 
     bool more2 = e2.MoveNext(); 

     while (more1 && more2) 
     { 
     int v1 = e1.Current; 
     int v2 = e2.Current; 
     if (v1 < v2) 
     { 
      yield return v1; 
      more1 = e1.MoveNext(); 
     } 
     else 
     { 
      yield return v2; 
      more2 = e2.MoveNext(); 
     } 

     } 
     while (more1 && ! more2) 
     { 
     yield return e1.Current; 
     more1 = e1.MoveNext(); 
     } 
     while (more2 && ! more1) 
     { 
     yield return e2.Current; 
     more2 = e2.MoveNext(); 
     } 
    } 
    } 
} 

Answer 4

Avec vos données d'exemple que je peux obtenir votre résultat simplement en triant:

lst1.Concat(lst2).OrderBy(i => i) 

Que voulez-vous dire par la fusion ? Fusionner comment?

Answer 5

Pour une solution impromptu consultez MoreLinq.

Il fournit, parmi beaucoup d'autres, la méthode d'extension IEnumerableSortedMerge.