Эффективно спаривание объектов в списках на основе ключа

Question

Итак, вот сделка. (Мой текущий вариант использования находится в C#, но меня также интересует общий алгоритмический случай) Мне дано два массива объектов (к сожалению, мне не удается изменить код, который создает эти массивы). Каждый объект имеет (как часть его) свойство .Name, строку. Эти строки уникальны для каждого объекта, и у них есть нуль или одна соответствующая строка в другом объекте. Что мне нужно сделать, это эффективно соединить эти объекты на основе этой строки, в какую-то коллекцию, которая позволяет мне получить доступ к сопряженным объектам. Строки должны соответствовать точно, чтобы считаться совпадением, поэтому мне не нужен какой-либо верхний или случайный чувствительный элемент и т. Д. К сожалению, эти списки не сортируются. Списки сами могут быть 30-50 элементов, но мне нужно повторить алгоритм на тысячах этих пар массивов подряд, поэтому эффективность важна.

Поскольку я знаю, что есть 0 или 1 совпадение, и я знаю, что большинство из них будет 1, я считаю, что есть более эффективный алгоритм, чем x * y (элемент Foreach в x, foreach item в y, if х = у, то х и у спичка)

Я считаю, что наиболее вероятные варианты:

Держите несортированный список и вобще х * у, но падение предметов из списка, как только я нашел их поэтому я не проверяю уже найденные, OR: Преобразуйте оба словаря, а затем выполните индексированный поиск по каждому из них (array2 [currentArray1Item]) ИЛИ: Сортируйте списки самостоятельно (Array.Sort()), а затем отсортированные массивы, я, вероятно, могу сделать что-то умное, как прыжок в индекс в B, где я ожидал бы его найти (везде, где он был в A), а затем перемещаться вверх или вниз по строке до тех пор, пока Я либо нахожу его, либо передаю, где он должен был быть.

После этого мне нужно выяснить, как его сохранить, я полагаю, что могу создать собственный класс ObjectPair, который просто держит объекты A и B. Мне не нужно ничего делать, потому что я просто собираюсь ForEach на парах.

Итак, вопросы: Являются ли какие-либо из вышеперечисленных алгоритмов самым быстрым способом сделать это (если нет, что такое?) И существует ли какая-то существующая структура C#, которая бы удобно удерживала найденные пары?

EDIT: Array.Sort() - метод, который существует, поэтому мне не нужно преобразовывать массив в List для сортировки. Хорошо знать. Обновлено выше.

Answer 1

Вопрос, который у меня есть: насколько эффективны мы получаем от специальной обработки, если это требует от нас сортировки и входных массивов? Согласно документации для Array.Sort, это в среднем O(n log n) и O(n^2) в худшем случае (quicksort). После того, как мы отсортировали оба массива, мы получим еще одно количество работы: O(n), потому что мы должны пропустить первый.

Я интерпретирую это как означающий, что общий объем работы может на самом деле увеличить из-за количества итераций, необходимых для сортировки, а затем для обработки. Конечно, это была бы другая история, если бы вы могли гарантировать сортировку массивов с самого начала, но, как вы сказали, вы не можете.(Следует также отметить, что вы должны создать пользовательский IComparer<T> реализации перейти к Array.Sort поэтому знает использовать .Name свойство. Это не во время выполнения работы, но он по-прежнему работает :-)

Вы могли бы рассмотреть возможность использования LINQ join, который только выполняет итерацию внутреннего массива за один раз (see here for psuedocode). Это в отличие от вложенных операторов foreach, которые будут перебирать внутренний массив для каждого элемента внешнего массива. Это примерно так же эффективно, как это может быть в общем случае, и не вводит сложность специальной обработки, которую вы предложили.

Вот пример реализации:

var pairs = 
    from item1 in array1 
    join item2 in array2 on item1.Name equals item2.Name 
    select new { item1, item2 }; 

foreach(var pair in pairs) 
{ 
    // Use the pair somehow 
} 

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

Answer 2

Сортировка второго массива с использованием метода Array.Sort, а затем сопоставление объектов во втором Array с использованием Binary Search Algorithm.

Как правило, для 30-50 предметов это будет немного быстрее, чем грубая сила x * y.