C # быстрое объединение 2 наборов отсортированных значений

Question

Какой самый быстрый способ объединить 2 набора отсортированных значений?Скорость (big-O) здесь важна;не ясность - предположим, что это делается миллионы раз.

Предположим, вы не знаете тип или диапазон значений, но имеете эффективный IComparer<T> и / или IEqualityComparer<T>.

Учитывая следующий набор чисел:

var la = new int[] { 1, 2, 4, 5, 9 };
var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

Я ожидаю 1, 2, 3, 4, 5, 6, 7, 8, 9. Для проверки кода можно использовать следующую заглушку:

static void Main(string[] args)
{
    var la = new int[] { 1, 2, 4, 5, 9 };
    var ra = new int[] { 3, 4, 5, 6, 6, 7, 8 };

    foreach (var item in UnionSorted(la, ra, Int32Comparer.Default))
    {
        Console.Write("{0}, ", item);
    }
    Console.ReadLine();
}

class Int32Comparer : IComparer<Int32>
{
    public static readonly Int32Comparer Default = new Int32Comparer();
    public int Compare(int x, int y)
    {
        if (x < y)
            return -1;
        else if (x > y)
            return 1;
        else
            return 0;
    }
}

static IEnumerable<T> UnionSorted<T>(IEnumerable<T> sortedLeft, IEnumerable<T> sortedRight, IComparer<T> comparer)
{
}

Answer 1

Следующий метод возвращает правильные результаты:

static IEnumerable<T> UnionSorted<T>(IEnumerable<T> sortedLeft, IEnumerable<T> sortedRight, IComparer<T> comparer)
{
    var first = true;

    var continueLeft = true;
    var continueRight = true;

    T left = default(T);
    T right = default(T);

    using (var el = sortedLeft.GetEnumerator())
    using (var er = sortedRight.GetEnumerator())
    {
        // Loop until both enumeration are done.
        while (continueLeft | continueRight)
        {
            // Only if both enumerations have values.
            if (continueLeft & continueRight)
            {
                    // Seed the enumeration.
                    if (first)
                    {
                        continueLeft = el.MoveNext();
                        if (continueLeft)
                        {
                            left = el.Current;
                        }
                        else 
                        {
                            // left is empty, just dump the right enumerable
                            while (er.MoveNext())
                                yield return er.Current;
                            yield break;
                        }

                        continueRight = er.MoveNext();
                        if (continueRight)
                        {
                            right = er.Current;
                        }
                        else
                        {
                            // right is empty, just dump the left enumerable
                            if (continueLeft)
                            {
                                // there was a value when it was read earlier, let's return it before continuing
                                do
                                {
                                    yield return el.Current;
                                }
                                while (el.MoveNext());
                            } // if continueLeft is false, then both enumerable are empty here.
                            yield break;
                        }

                        first = false;
                    }

                // Compare them and decide which to return.
                var comp = comparer.Compare(left, right);
                if (comp < 0)
                {
                    yield return left;
                    // We only advance left until they match.
                    continueLeft = el.MoveNext();
                    if (continueLeft)
                        left = el.Current;
                }
                else if (comp > 0)
                {
                    yield return right;
                    continueRight = er.MoveNext();
                    if (continueRight)
                        right = er.Current;
                }
                else
                {
                    // The both match, so advance both.
                    yield return left;
                    continueLeft = el.MoveNext();
                    if (continueLeft)
                        left = el.Current;
                    continueRight = er.MoveNext();
                    if (continueRight)
                        right = er.Current;
                }
            }
            // One of the lists is done, don't advance it.
            else if (continueLeft)
            {
                yield return left;
                continueLeft = el.MoveNext();
                if (continueLeft)
                    left = el.Current;
            }
            else if (continueRight)
            {
                yield return right;
                continueRight = er.MoveNext();
                if (continueRight)
                    right = er.Current;
            }
        }
    }
}

Пробел составляет ~ O (6), а время ~ O (max (n, m)) (где m - второй набор).

Answer 2

Это сделает вашу функцию UnionSorted немного менее универсальной, но вы можете сделать небольшое улучшение, сделав предположение о типах. Если вы сделаете сравнение внутри самого цикла (вместо вызова Int32Comparer), это сэкономит некоторые накладные расходы на вызов функции.

Итак, ваша UnionSorted декларация становится такой ...

static IEnumerable<int> UnionSorted(IEnumerable<int> sortedLeft, IEnumerable<int> sortedRight)

И затем вы делаете это внутри цикла, избавляясь от вызова на comparer.Compare() ...

//var comp = comparer.Compare(left, right); // too slow

int comp = 0;
if (left < right)
    comp = -1;
else if (left > right)
    comp = 1;

В моем тестировании это было примерно на 15% быстрее.

Answer 3

Я собираюсь дать LINQ преимущество сомнений и сказать, что это, вероятно, так же быстро, как вы собираетесь без написания чрезмерного кода:

var result = la.Union(ra);

Редакция: Спасибо, я пропустил отсортированную часть.

Вы можете сделать:

var result = la.Union(ra).OrderBy(i => i);

Answer 4

Я бы решил проблему таким образом. (Я делаю предположение, которое значительно облегчает сложность этой проблемы, только чтобы проиллюстрировать эту идею.)

Предположение: все числа, содержащиеся в наборах, неотрицательны.

Создайте слово длиной не менее n битов, где n - это наибольшее ожидаемое значение. (Если наибольшее ожидаемое значение равно 12, то вы должны создать слово из 16 битов.).

Итерация по обоим наборам. Для каждого значения val, or val -й бит с 1.

После этого подсчитайте количество бит, установленное в 1. Создайте массив такого размера. Просмотрите каждый бит по одному, добавляя n к новому массиву, если установлен n -й бит.