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

Question

Я вычисляю пересечение 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 миллиона раз.Так что каждая микросекунда имеет значение.

Answer 1

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

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

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

Вот пример реализации - не тестировался, но он компилируется :) Предполагается, что обе входящие последовательности не содержат дубликатов и отсортированы, как в соответствии с предоставленным компаратором (passв 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;
            }
        }
    }
}

РЕДАКТИРОВАТЬ: Как отмечено в комментариях, в некоторых случаях вы можете иметь один вход, которыйнамного больше, чем другие, и в этом случае вы могли бы потенциально сэкономить много времени, используя бинарный поиск для каждого элемента из меньшего набора в большем наборе.Однако для этого требуется произвольный доступ к большему набору (это просто предпосылка бинарного поиска).Вы даже можете сделать его немного лучше, чем простой двоичный поиск, используя совпадение из результата предыдущий , чтобы дать нижнюю границу для двоичного поиска.Предположим, вы искали значения 1000, 2000 и 3000 в наборе с каждым целым числом от 0 до 19,999.На первой итерации вам нужно будет просмотреть весь набор - ваши начальные нижний / верхний индексы будут 0 и 19,999 соответственно.Однако после того, как вы нашли совпадение с индексом 1000, шаг следующий (где вы ищете 2000) может начинаться с более низкого индекса 2000. По мере продвижения, диапазон, в котором вам нужноискать постепенно сужается.Однако стоит ли это дополнительных затрат на реализацию или нет, это другой вопрос.

Answer 2

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

ЭтоРешение сохраняет «указатель» на часть списка, которую мы еще не исследовали, и сравнивает первое неисследованное число каждого списка между ними.Если один из них меньше другого, указатель на список, которому он принадлежит, увеличивается, чтобы указывать на следующее число.Если они равны, число добавляется к результату пересечения, и оба указателя увеличиваются.

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 для решения этой конкретной проблемы, и с учетом простоты кодаЯ был бы удивлен, увидев более быстрое решение.

Answer 3

Вы используете довольно неэффективный метод Linq для такого рода задач, вам следует выбрать Intersect в качестве отправной точки.

var intersection = firstSet.Intersect(secondSet);

Попробуй это. Если вы оцениваете производительность и по-прежнему считаете ее громоздкой, требуйте дополнительной помощи (или, возможно, следуйте подходу Джона Скита).

Answer 4

Я использовал подход Джона, но мне нужно было выполнить это пересечение сотни тысяч раз для массовых операций на очень больших наборах, и мне требовалось больше производительности.Случай, в котором я участвовал, был сильно несбалансированными размерами списков (например, 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
    }
}

Я все еще не уверен насчет точки, в которой вы безубыточны, нужно провести еще какое-то тестирование

Answer 5

попробуй

firstSet.InterSect (secondSet).ToList ()

или

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