C# Самое быстрое пересечение 2 наборов отсортированных чисел

Question

C# Самое быстрое пересечение 2 наборов отсортированных чисел

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

Я перепробовал кучу простых вариантов и в настоящее время использую это:

foreach (var index in firstSet)
{
    if (secondSet.BinarySearch(index) < 0)
        continue;

    //do stuff
}

И firstSet, и secondSet имеют тип List.

Я также пробовал использовать LINQ:

var intersection = firstSet.Where(t => secondSet.BinarySearch(t) >= 0).ToList();

И затем петля через intersection.

Но поскольку оба этих набора отсортированы, я чувствую, что есть лучшее способ сделать это. Обратите внимание, что я не могу удалить элементы из наборов, чтобы сделать их меньше. Оба комплекта, как правило, состоят из около 50 пунктов каждый.

Пожалуйста, помогите мне, ребята, так как у меня не так много времени, чтобы сделать это. Спасибо. Примечание: Я делаю это примерно 5,3 миллиона раз. Так что каждая микросекунда на счету.

5 11

c# .net sortedset intersection

5 ответов:

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

Это решение сохраняет "указатель" на ту часть списка, которую мы еще не исследовали, и сравнивает первый неисследованный номер каждого списка между ними. Если один меньше другого, указатель на список, к которому он принадлежит, увеличивается, чтобы указать на следующий номер. Если они равны, то число добавляется к результату пересечения, и оба указателя увеличиваются.
var firstCount = firstSet.Count;
var secondCount = secondSet.Count;
int firstIndex = 0, secondIndex = 0;
var intersection = new List<int>();

while (firstIndex < firstCount && secondIndex < secondCount)
{
    var comp = firstSet[firstIndex].CompareTo(secondSet[secondIndex]);
    if (comp < 0) {
        ++firstIndex;
    }
    else if (comp > 0) {
        ++secondIndex;
    }
    else {
        intersection.Add(firstSet[firstIndex]);
        ++firstIndex;
        ++secondIndex;
    }
}
Вышеописанный подход к решению этой конкретной задачи в стиле учебника C, и учитывая простоту кода, я был бы удивлен, увидев более быстрое решение.

8

Вы используете довольно неэффективный метод Linq для такого рода задач, вы должны выбрать Intersect в качестве отправной точки.
var intersection = firstSet.Intersect(secondSet);
Попробуйте это. Если вы измеряете его производительность и все еще находите его громоздким, обратитесь за дополнительной помощью (или, возможно, следуйте подходу Джона Скита).

5

Я использовал подход Джона, но мне нужно было выполнить это пересечение сотни тысяч раз для массовой операции на очень больших наборах и требовалось больше производительности. Случай, в котором я работал, был сильно несбалансированным размером списков (например, 5 и 80 000) и хотел избежать повторения всего большого списка.
Я обнаружил, что обнаружение дисбаланса и переход на альтернативный алгоритм дают мне огромные преимущества по сравнению с конкретными наборами данных:
public static IEnumerable<T> IntersectSorted<T>(this List<T> sequence1,
        List<T> sequence2,
        IComparer<T> comparer)
{
    List<T> smallList = null;
    List<T> largeList = null;

    if (sequence1.Count() < Math.Log(sequence2.Count(), 2))
    {
        smallList = sequence1;
        largeList = sequence2;
    }
    else if (sequence2.Count() < Math.Log(sequence1.Count(), 2))
    {
        smallList = sequence2;
        largeList = sequence1;
    }

    if (smallList != null)
    {
        foreach (var item in smallList)
        {
            if (largeList.BinarySearch(item, comparer) >= 0)
            {
                yield return item;
            }
        }
    }
    else
    {
        //Use Jon's method
    }
}
Я все еще не уверен в этом пункте при котором вы безубыточны, нужно сделать еще несколько тестов

2

Попробуйте

firstSet.InterSect (secondSet).ToList ()

Или

firstSet.Join(secondSet, o => o, id => id, (o, id) => o)

0

Jon Skeet · Accepted Answer · 2014-02-06 08:57:39

Если у вас есть два набора, которые сортируются, вы можете реализовать более быстрое пересечение, чем все, что предоставляется из коробки с LINQ.

В основном, держите открытыми два курсора IEnumerator<T>, по одному для каждого набора. В любой момент продвигайте то, что имеет меньшее значение. Если они совпадают в любой точке, продвигайте их оба и так далее, пока не дойдете до конца любого итератора.

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

Вот пример реализации - непроверенный, но он компилируется :) предполагается, что обе входящие последовательности не содержат дубликатов и отсортированы, как в соответствии с предоставленным компаратором (pass in Comparer<T>.Default):

(в конце ответа есть еще текст!)
static IEnumerable<T> IntersectSorted<T>(this IEnumerable<T> sequence1,
    IEnumerable<T> sequence2,
    IComparer<T> comparer)
{
    using (var cursor1 = sequence1.GetEnumerator())
    using (var cursor2 = sequence2.GetEnumerator())
    {
        if (!cursor1.MoveNext() || !cursor2.MoveNext())
        {
            yield break;
        }
        var value1 = cursor1.Current;
        var value2 = cursor2.Current;

        while (true)
        {
            int comparison = comparer.Compare(value1, value2);
            if (comparison < 0)
            {
                if (!cursor1.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
            }
            else if (comparison > 0)
            {
                if (!cursor2.MoveNext())
                {
                    yield break;
                }
                value2 = cursor2.Current;
            }
            else
            {
                yield return value1;
                if (!cursor1.MoveNext() || !cursor2.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
                value2 = cursor2.Current;
            }
        }
    }
}
EDIT: как отмечалось в комментариях, в некоторых случаях у вас может быть один вход, который намного больше другого, и в этом случае вы потенциально можете сэкономить много времени, используя двоичный поиск для каждого элемента из меньший набор внутри большего набора. Однако для этого требуется случайный доступ к большему набору (это просто обязательное условие бинарного поиска). Вы даже можете сделать его немного лучше, чем наивный двоичный поиск, используя соответствие из предыдущего результата , чтобы дать нижнюю границу двоичному поиску. Итак, предположим, что вы ищете значения 1000, 2000 и 3000 в наборе с каждым целым числом от 0 до 19 999. В первой итерации вам нужно будет посмотреть на весь набор-ваш старт нижний / верхний индексы будут равны 0 и 19 999 соответственно. Однако после того, как вы нашли совпадение с индексом 1000, следующий шаг (где вы ищете 2000) может начинаться с более низкого индекса 2000. По мере вашего продвижения диапазон, в котором вам нужно искать, постепенно сужается. Однако стоит ли это дополнительных затрат на реализацию или нет-это уже другой вопрос.