Хитрое объединение массивов

Упс, совсем уже башку сломал на этой задаче. Я имел в виду пересечение массивов... :(

Могу предложить вариант на Perl. Думаю, в C есть что-нибудь подобное.

@c = grep { $b[ $_ ] }  @a;

или 

foreach my $element( @a ) {
   if ( $b[$element] ) {
      push @c, $element;
   }
}

Создаст массив @c, в котором элементы в том же порядке, что и в @a, но пересеченные с @b. 

Массивы действительно содержат инты?

Тогда, наверное идея такая - перебирать элементы B и для каждого из них эффективно проверять, содержится ли он в A.

Для эффективной проверки потребуется предварительная подготовка:

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

или

-Запихнуть все элементы A в хэш-множество.

В первом случае будет гарантированное O(sizeof(A)+sizeof(B))*log(sizeof(A)) операций

Во втором, при выборе подходящей хэш-функции и числа корзин, в среднем будет O(sizeof(A)+sizeof(B)) но с бОльшей, чем в первом случае константой - оптимальность того или иного решения зависит от размера массива A.

Что-то ты не то написал, как мне кажется.

сортируем и А, а потом двигаемся по обоим масивам,
типа пока
i = 0;
j = 0;
пока b[i] < a[j] увеличиваем i,
потом или совпадение, или нужно увеличивать j и т.д.

Массив A отсортирован по некоторому внешнему и очень дорогому при вычислении критерию. То есть с точки зрения такого сровнения просто не отсортирован. в массивах содержатся id объектов. Или я чего-то не понял, или мне не подойдёт...

В принципе, у меня сейчас работает перебор B с проверкой на наличие в A. Но всё равно слишком долго получается. Попробую хэш-множество.

в массивах дейтствительно инты, это id элементов.

Спасибо за советы!

>В принципе, у меня сейчас работает перебор B с проверкой на наличие в A. Но всё равно слишком долго получается. Попробую хэш-множество.

Проверка на наличие в A за sizeof(A) или log(sizeof(A))? (Если вдруг была за sizeof(A), то прежде чем пробовать хэш-множество, ИМХО, стоит попробовать отсортировать (не по "тяжёлой" функции сравнения, а тупо как инты) и искать бинарным поиском).

Если массив был отсортирован и использовался-таки бинарный поиск, но при этом из стандартной библиотеки - то может помочь (правда совсем-совсем немного) замена его на самописный - на некоторых компиляторах у C-шного bsearch могут возникнуть большие проблемы с инлайнингом операции сравнения (тем более для такой тривиальной, как сравнение 2-х интов это очень существенно), а у С++ binary_search мелкие проблемы с оптимизацией из-за того, что там не итераторы не randomaccess, а более общие forward.

Ура! Большое спасибо! Ускорение работы 1500 раз это даже больше, чем я надеялся. Вот только сейчас это надо в сам рабочий проект вписывать, а это надолго... :)