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

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

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

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

Здравствуйте, Аноним, Вы писали:

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

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

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

Перед проходом по B сортируем А и для поиска в А используем бинарный поиск. При использовании для сортировки А того же критерия, что и для В, можно быстро проскакивать в В диапазоны, не содержащиеся в А.

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

B>Здравствуйте, Аноним, Вы писали:

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

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

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

B>Перед проходом по B сортируем А и для поиска в А используем бинарный поиск. При использовании для сортировки А того же критерия, что и для В, можно быстро проскакивать в В диапазоны, не содержащиеся в А.

Спасибо. Критерии разные (собственно экстремальная тяжесть критерия сортировки и заставляет пробовать отсортировать один раз, положить и пытаться использовать в дальнейшем)

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

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

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

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

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

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

Здравствуйте, 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, то заносим в результат.По сути новый массив будет аналогом множества в первом варианте. (будет жрать больше памяти, но и работать быстрее)

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

T>Другой вариант — частный и более быстрый случай предыдущего — если элемнет можно представить некоторым целочисленным идентификатором, находящемся в приемлемом дипозоне для создания массива от 0 до максимального идентификатора.

как вариант, можно сделать hash-таблицу на 10000 элементов.
это будет работать ещё быстрее, чем бинарные поиск и чуть медленнее поиска по таблице идентификаторов.
но не имеет ограничения на диапазон.

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

__>как вариант, можно сделать hash-таблицу на 10000 элементов.

а можно и на 50-100 тыс. элементов.
тогда и бинарный поиск не нужен

тут ещё вопрос в распределении данных.

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

__>>как вариант, можно сделать hash-таблицу на 10000 элементов.

__>а можно и на 50-100 тыс. элементов.
__>тогда и бинарный поиск не нужен

__>тут ещё вопрос в распределении данных.

Всем спасибо! Построение из массива A hash_map с маппингом на int 0|1 в зависимости от того, вставлялся ли уже этот элемент в итоговый массив работает в 1500 раз быстрее моего исходного кода! И с достаточной скоростью.