Суть в следующем:

есть 2 массива (списка) данных (не важно как организованы - array, коллекция, словарь)
будем для простоты называть их масиивами

массивы проиндексированы (каждая "запись" имеет уникальный ключ)


например:


Массив A

1
2
3
4
5


Массив B

2
4
5


Вопрос: каким образом сравнить два массива по ключам
Важно чтобы на выходе мы получили их разницу

Т.е. аналог LEFT JOIN


Для приведенного примера мы должны получить

Массив C

1
3


Как это сделать наиболее оптимальным способом?
Я имею ввиду кроме полного перебора

Наверняка существуют подобные алгоритмы..
Может ткнете носом?



Пока мне в голову приходит только банальный XOR
Но его можно использовать для макс. 32 элементов ведь?

А если к примеру элементов в массиве 200? (как в моей задаче)

Вообщем жду советов, хотя бы в каком направлении копать...
Сразу оговорюсь, SQL не предлагать.

Shocker.Proесли оба массива отсортированы по ключу, то в чем проблема?
один проход двумя указателями по обоим массивам и все.

Ну это банальный перебор.
Я надеялся, что может есть более оптимальный алгоритм.

Что-то типа XOR...

Игорь Горбонос
> Автор: ЧервьVB
> есть 2 массива (списка) данных (не важно как организованы - array, коллекция, словарь)

Это важно, например для коллекций или словарей, нужно будет сделать только по одному проходу по каждому источнику,
что-бы получить искомое и не плевать на сортировку, для массива нужна сортировка данных.




Для конкретики - пусть будут две коллекции.

Тогда, плевать на сортировку.
Тогда, если 2 прохода, обращений к масиивам будет m+n, где m и n, соответственно размерности массивов.

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

Таким образом, чтобы узнать разницу между массивами, необходимо сделать (m+n)*2 обращений.

Т.е. оптимальнее никак?

Игорь Горбонос
> Автор: ЧервьVB
> Таким образом, чтобы узнать разницу между массивами, необходимо сделать (m+n)*2 обращений.

Ты опять скатился в "свою" терминологию. Коллекция не массив. Почитай в чем различия

> необходимо сделать (m+n)*2 обращений.

С какого перепугу??? Ты снова делаешь неверные выводы из-за подмены понятий. будет только один проход по одной коллекции
и по окончанию будет один проход по второй коллекции. После этих, двух, проходов будет готова "разница" множеств.

> Т.е. оптимальнее никак?

Можно убрать один проход, но тогда "загадим" одну из коллекций :)








Все равно я не понимаю, как будет по ОДНОМУ обращению к элементам коллекции.


Простой пример:








Как мне получить col3 (сравнение идет по ключам!), которая будет выглядеть так


10, "4"
40, "9"



т.е. аналог XOR

Shocker.ProЧервьVB,

Считывается первый элемент одного и второго массива.
Если индексы равны, продвигаемся вперед по обоим массивам. Если у второго массива ключ больше, элемент пераого массива заносим в результат и двигаем указатель только первого массива. Вот и все.

1. Как прочитать ключ у i-го элемента? Такая конструкция: col(i).key не работает.

2. А если коллекции не отсортированы?

Игорь Горбонос
> Автор: ЧервьVB
> Как мне получить col3 (сравнение идет по ключам!), которая будет выглядеть так

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



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

Как раз весь смысл моего изыскания - наиболее оптимальный алгоритм.
Т.к. у меня эти проверки должны выполняться для большого числа коллекций от 100 элементов.
Коллекции динамические, т.е. постоянные Add и Remove
И в каждый момент времени должна вычисляться разница

Игорь Горбонос,
Шокер,


Спасибо!

Пока алгоритм игоря мне кажется для коллекций наиболее оптимальным, если б-дерево.
Еще можно использовать справочник наверное. Там вроде есть exist. Так что наличие ошибки можно не проверять.


ПыСы
за ссылку спасибо, прочту пожалуй