LINUX.ORG.RU

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


0

0

Есть два массива int A[50000] и int B[50000000]. Нужно построить массив C, который бы содержал все элементы массива A в том порядке, в каком они встречаются в массиве B. Как это сделать быстро?

То есть в массиве A отфильтрованные значения, в массиве B отсортированные по какому-то признаку, нужно получить отфильтрованные и отсортированные.

P.S. это реальная задача, не лабораторная какая-нибудь...

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

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

voronaam ★★ ()
Ответ на: Re: Хитрое объединение массивов от voronaam

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

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

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

или 

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

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

golubeff ()

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

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

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

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

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

или

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

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

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

GPFault ★★ ()
Ответ на: Re: Хитрое объединение массивов от voronaam

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

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

fghj ★★★★★ ()
Ответ на: Re: Хитрое объединение массивов от fghj

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

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

voronaam ★★ ()
Ответ на: Re: Хитрое объединение массивов от GPFault

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

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

voronaam ★★ ()
Ответ на: Re: Хитрое объединение массивов от voronaam

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

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

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

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

GPFault ★★ ()
Ответ на: Re: Хитрое объединение массивов от GPFault

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

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

voronaam ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.