Здравствуйте, Tiendil, Вы писали:

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

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

А>>Пока быстрее всего работало решение, в котором я шёл по массиву B последовательно, искал каждое значение в массиве A и если оно найдено клал его в C. Но есть надежда, что это как сортировка пузырьком...

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

T>Есть вариант сформировать множество из элемнетов массива А (или их идентификаторов), бежать по В и проверять наличие элемнета в данном множестве.
T>Выигрыш заключается в том, что поиск элемнета в множестве будет происходить быстрее чем прямой поиск в массиве (конечно, если, элементы множества организованы деревом или похожим методом, как, например, в С++ std::set) : O(ln(n)) против O(n), если не ошибаюсь

T>Другой вариант — частный и более быстрый случай предыдущего — если элемнет можно представить некоторым целочисленным идентификатором, находящемся в приемлемом дипозоне для создания массива от 0 до максимального идентификатора. Сначала забиваем массив нулями (или значениями false), затем идём по А и элемнеты нового массива с индексами равными уникальному идентификатору элемента А присваеваем 1. Затем идём по В и смотрим, значение ячейки соответствующей каждому элементы В, еслиона ==1, то заносим в результат.По сути новый массив будет аналогом множества в первом варианте. (будет жрать больше памяти, но и работать быстрее)

Да, это можно попробовать, спасибо.