Сравнение двух списков для уникальных предметов в каждом

Question

У меня есть две коллекции (они являются массивами, но я думаю, что это не имеет значения): L а также R, Они оба отсортированы, и теперь я хочу сравнить их. Я хочу получить две коллекции: по одной для каждого входного массива, содержащего элементы, которых не было в другой.

Я мог бы просто взять первый предмет из L а затем искать R и, если нет совпадения, добавьте его в мою "уникальную" коллекцию (Lu). Но это крайне неэффективно, и я ожидаю, что в ближайшем будущем будет несколько очень больших коллекций для обработки.

Я думал о возможной игре в классики:

• Шаг 1: возьмите два списка, L а также Rи сравните заголовок каждого списка (l :: L а также r :: R):

  • Ветвь 1: если l < r, затем добавьте l в Lu и рекурсировать, проходя в L а также r :: R

  • Ветвь 2: если l > r, затем добавьте r в Ru и рекурсировать, проходя в l :: L а также R

  • Филиал 3: если l знак равно rпотом рекурсировать, проходя в L а также R

• Шаг 2: возврат Lu а также Ru

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

(Также, если есть более узнаваемое имя для этого алгоритма, я хотел бы знать, как он называется.)

Answer 1

(Я написал вопрос выше около 2 часов назад. С тех пор я нашел ответ самостоятельно. Вот что я обнаружил.)

В теории множеств "список" элементов в L, но не в R известен как "относительное дополнение R в L", также известный как "теоретико-множественное различие L и R"

(См. Статью Википедии " Дополнение (теория множеств)")

F#, будучи математическим языком, внедрил эту концепцию прямо в свою библиотеку Core. Во-первых, вам нужно собрать свои коллекции в виде наборов:

// example arrays:
let arr1 = [| 1; 2; 3 |]
let arr2 = [| 2; 3; 4 |]

// build the L and R sets
let L = set arr1
let R = set arr2

Теперь вы можете вызвать функцию "разности" и быстро получить относительное дополнение для каждого массива:

let Lu = Set.difference L R |> Set.toArray
let Ru = Set.difference R L |> Set.toArray

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]

Там также более короткий синтаксис. Тип Set перегружен оператором минус. Set.difference просто вычитает второй параметр из первого, так что вы можете просто использовать следующее:

let Lu = L - R |> Set.toArray
let Ru = R - L |> Set.toArray

> val Lu : int [] = [|1|]
> val Ru : int [] = [|4|]