La plupart algorithme efficace pour la fusion triés IEnumerable<T>

Question

J'ai plusieurs énormes triés énumérable séquences que je veux fusionner. Ces listes sont manipulées en tant que IEnumerable mais sont déjà triés. Depuis l'entrée listes sont triées, il devrait être possible de les fusionner en un seul voyage, sans re-trier quoi que ce soit.

Je tiens à garder les différés de comportement à l'exécution.

J'ai essayé d'écrire un algorithme naïf qui le faire (voir ci-dessous). Cependant, il semble assez moche et je suis sûr qu'il peut être optimisé. Il peut exister un plus académique de l'algorithme...

IEnumerable<T> MergeOrderedLists<T, TOrder>(IEnumerable<IEnumerable<T>> orderedlists, 
                                            Func<T, TOrder> orderBy)
{
    var enumerators = orderedlists.ToDictionary(l => l.GetEnumerator(), l => default(T));
    IEnumerator<T> tag = null;

    var firstRun = true;
    while (true)
    {
        var toRemove = new List<IEnumerator<T>>();
        var toAdd = new List<KeyValuePair<IEnumerator<T>, T>>();
        foreach (var pair in enumerators.Where(pair => firstRun || tag == pair.Key))
        {
            if (pair.Key.MoveNext())
                toAdd.Add(pair);
            else
                toRemove.Add(pair.Key);
        }

        foreach (var enumerator in toRemove)
            enumerators.Remove(enumerator);

        foreach (var pair in toAdd)
            enumerators[pair.Key] = pair.Key.Current;

        if (enumerators.Count == 0)
            yield break;

        var min = enumerators.OrderBy(t => orderBy(t.Value)).FirstOrDefault();
        tag = min.Key;
        yield return min.Value;

        firstRun = false;
    }
}

La méthode peut être utilisée comme ça:

// Person lists are already sorted by age
MergeOrderedLists(orderedList, p => p.Age);

en supposant que les suivantes, Person classe existe quelque part:

    public class Person
    {
        public int Age { get; set; }
    }

Les doublons doivent être conservées, nous ne se soucient pas de leur ordre dans la nouvelle séquence. Voyez-vous une optimisation évidente que je pourrais utiliser?

Answer 1

Voici ma quatrième (merci à @tanascius pour pousser le long de quelque chose de beaucoup plus LINQ) couper à ça:

public static IEnumerable<T> MergePreserveOrder3<T, TOrder>(
    this IEnumerable<IEnumerable<T>> aa,
    Func<T, TOrder> orderFunc)
where TOrder : IComparable<TOrder>
{
    var items = aa.Select(xx => xx.GetEnumerator()).Where(ee => ee.MoveNext())
        .OrderBy(ee => orderFunc(ee.Current)).ToList();

    while (items.Count > 0)
    {
        yield return items[0].Current;

        var next = items[0];
        items.RemoveAt(0);
        if (next.MoveNext())
        {
            // simple sorted linear insert
            var value = orderFunc(next.Current);
            var ii = 0;
            for ( ; ii < items.Count; ++ii)
            {
                if (value.CompareTo(orderFunc(items[ii].Current)) <= 0)
                {
                    items.Insert(ii, next);
                    break;
                }
            }

            if (ii == items.Count) items.Add(next);
        }
        else next.Dispose(); // woops! can't forget IDisposable
    }
}

Résultats:

for (int p = 0; p < people.Count; ++p)
{
    Console.WriteLine("List {0}:", p + 1);
    Console.WriteLine("\t{0}", String.Join(", ", people[p].Select(x => x.Name)));
}

Console.WriteLine("Merged:");
foreach (var person in people.MergePreserveOrder(pp => pp.Age))
{
    Console.WriteLine("\t{0}", person.Name);
}

List 1:
        8yo, 22yo, 47yo, 49yo
List 2:
        35yo, 47yo, 60yo
List 3:
        28yo, 55yo, 64yo
Merged:
        8yo
        22yo
        28yo
        35yo
        47yo
        47yo
        49yo
        55yo
        60yo
        64yo

Amélioré avec .Net 4.0 n-uplet de soutien:

public static IEnumerable<T> MergePreserveOrder4<T, TOrder>(
    this IEnumerable<IEnumerable<T>> aa,
    Func<T, TOrder> orderFunc) where TOrder : IComparable<TOrder>
{
    var items = aa.Select(xx => xx.GetEnumerator())
                  .Where(ee => ee.MoveNext())
                  .Select(ee => Tuple.Create(orderFunc(ee.Current), ee))
                  .OrderBy(ee => ee.Item1).ToList();

    while (items.Count > 0)
    {
        yield return items[0].Item2.Current;

        var next = items[0];
        items.RemoveAt(0);
        if (next.Item2.MoveNext())
        {
            var value = orderFunc(next.Item2.Current);
            var ii = 0;
            for (; ii < items.Count; ++ii)
            {
                if (value.CompareTo(items[ii].Item1) <= 0)
                {   // NB: using a tuple to minimize calls to orderFunc
                    items.Insert(ii, Tuple.Create(value, next.Item2));
                    break;
                }
            }

            if (ii == items.Count) items.Add(Tuple.Create(value, next.Item2));
        }
        else next.Item2.Dispose(); // woops! can't forget IDisposable
    }
}

Answer 2

On suppose que je ferais ce qui peut améliorer la clarté et la performance est ceci:

• Créer une file d'attente de priorité sur les paires de T, IEnumerable<T> ordonnées selon votre fonction de comparaison sur T
• Pour chaque IEnumerable<T> de les fusionner, ajouter l'élément à la file d'attente de priorité annoté avec une référence à l' IEnumerable<T> , d'où il provient
• Alors que la priorité de la file d'attente n'est pas vide
  • Extraire l'élément minimum à partir de la file d'attente de priorité
  • L'avance de l' IEnumerable<T> dans son annotation à l'élément suivant
  • Si MoveNext() a renvoyé true, ajouter l'élément suivant de la file d'attente de priorité annoté avec une référence à l' IEnumerable<T> vous avez juste avancé
  • Si MoveNext() retourné false, ne rien ajouter à la file d'attente de priorité
  • Le rendement de l'élément retiré

Answer 3

Voici une solution qui a une très bonne analyse de la complexité et qui est considérablement plus courte que les autres solutions proposées.

public static IEnumerable<T> Merge<T>(this IEnumerable<IEnumerable<T>> self) 
    where T : IComparable<T>
{
    var es = self.Select(x => x.GetEnumerator()).Where(e => e.MoveNext());
    var tmp = es.ToDictionary(e => e.Current);
    var dict = new SortedDictionary<T, IEnumerator<T>>(tmp);
    while (dict.Count > 0)
    {
        var key = dict.Keys.First();
        var cur = dict[key];
        dict.Remove(key);
        yield return cur.Current;
        if (cur.MoveNext())
            dict.Add(cur.Current, cur);                    
    }
}

Answer 4

Le nombre de listes que vous vous attendez à besoin de fusionner? Il ressemble à votre algorithme ne sera pas efficace si vous avez beaucoup de différentes listes à fusionner. Cette ligne est la question:

var min = enumerators.OrderBy(t => orderBy(t.Value)).FirstOrDefault();

Ce sera exécuté une fois pour chaque élément dans toutes les listes, de sorte que votre moteur d'exécution O(n * m), où n est le nombre TOTAL d'éléments dans toutes les listes, et n est le nombre de listes. Exprimée en termes de la moyenne de la longueur d'une liste dans la liste de listes, le temps d'exécution est O(a * m^2).

Si vous allez avoir besoin de fusionner un lot de des listes, je voudrais suggérer à l'aide d'un tas. Ensuite, à chaque itération, vous pouvez enlever la plus petite valeur dans le tas, et ajouter l'élément suivant sur le segment de la liste qui a la plus petite valeur de provenance.

Answer 5

Voici une solution avec l'ABSENCE de TRI ... juste le minimum nombre de comparaisons. (J'ai omis la commande func passant pour des raisons de simplicité). Mise à jour de construire un équilibre de l'arbre:-

    /// <summary>
    /// Merge a pair of ordered lists
    /// </summary>
    public static IEnumerable<T> Merge<T>(IEnumerable<T> aList, IEnumerable<T> bList)
        where T:IComparable<T>
    {
        var a = aList.GetEnumerator();
        bool aOK = a.MoveNext();

        foreach (var b in bList)
        {
            while (aOK && a.Current.CompareTo(b) <= 0) {yield return a.Current; aOK = a.MoveNext();}
            yield return b;
        }
        // And anything left in a
        while (aOK) { yield return a.Current; aOK = a.MoveNext(); }
    }

    /// <summary>
    /// Merge lots of sorted lists
    /// </summary>
    public static IEnumerable<T> Merge<T>(IEnumerable<IEnumerable<T>> listOfLists)
        where T : IComparable<T>
    {
        int n = listOfLists.Count();
        if (n < 2) 
            return listOfLists.FirstOrDefault();
        else
            return Merge (Merge(listOfLists.Take(n/2)), Merge(listOfLists.Skip(n/2)));
    }


public static void Main(string[] args)
{

    var sample = Enumerable.Range(1, 5).Select((i) => Enumerable.Range(i, i+5).Select(j => string.Format("Test {0:00}", j)));

    Console.WriteLine("Merged:");
    foreach (var result in Merge(sample))
    {
        Console.WriteLine("\t{0}", result);
    }