пересечение множеств (2d массивов)

Модераторы: Duncon, Naeel Maqsudov, Игорь Акопян, Хыиуду

Ответить
buletz
Сообщения: 22
Зарегистрирован: 01 мар 2005, 16:54

есть два 2d массива , каждый размером N x 4
необходимо найти построчное пересечение этих массивов, т.е.
если представить каждую строчку как элемент, а массив - как множество элементов, то задача сводится к нахождению пересечения двух множеств.

ЗАДАЧА.

Как быстро (эффективно) найти данное пересечение ?

В данный момент у меня реализовано так :
(обознач.массивы как A и B)

цикл по i для всех строк из массива A
цикл по j для всех строк из массива B
если строка (i) из A совпадает со строкой (j) из B то
{
добавляем строку (i) из А в выходной массив.
переход к след.итерации по i
}
конец цикла по j
конец цикла по i


Данный алгоритм работает ОООЧЕНЬ медленно при больших массивах.

Как можно оптимизировать его ?
YurikGL
Сообщения: 142
Зарегистрирован: 16 фев 2005, 21:54
Откуда: Уфа
Контактная информация:

>если строка (i) из A совпадает со строкой (j) из B то
Приведите код процедуры сравнения....
Blood_Magic
Сообщения: 273
Зарегистрирован: 30 июн 2005, 14:53

;)
- Чем юзер похож на обезьяну?
- Он жмет на все, что жмется, дергает все, что дергается и крутит все, что крутится.
- Чем юзер отличается от обезьяны?
- У обезьяны хватает ума не воспроизводить ту последовательность, которая приводит к краху системы.
buletz
Сообщения: 22
Зарегистрирован: 01 мар 2005, 16:54

NN, NN2 : array [1..4] of integer
f:boolean;


f:=(NN[1]=NN2[1]) and (NN[2]=NN2[2]) and (NN[3]=NN2[3]) and (NN[4]=NN2[4])


Вот и все сравнение.
Аватара пользователя
Игорь Акопян
Сообщения: 1440
Зарегистрирован: 13 окт 2004, 17:11
Откуда: СПБ
Контактная информация:

хм... если найти достаточно первое пересечение - сделать Break из цикла не забыть ;)
Изображение
Ответить