Сравниваются два массива.
Размер обоих массивов одинаковый.
Содержат 32-битовые положительные числа.
Числа в пределах одного массива могут повторяться произвольное количество раз.
Надо найти номера всех различающихся элементов.
Количество элементов в массивах — миллионы.
Оперативки можно задействовать 2-3 метра.

Ткните, плз, мордой в более-менее валидный вариант организации сравнения.

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

А>Сравниваются два массива.
А>Размер обоих массивов одинаковый.
А>Содержат 32-битовые положительные числа.
А>Числа в пределах одного массива могут повторяться произвольное количество раз.
А>Надо найти номера всех различающихся элементов.
А>Количество элементов в массивах — миллионы.
А>Оперативки можно задействовать 2-3 метра.

А>Ткните, плз, мордой в более-менее валидный вариант организации сравнения.

в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

I>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

Угу, отыскать множество индексов, где A[i]!=B[i]

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

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

А>>Сравниваются два массива.
А>>Размер обоих массивов одинаковый.
А>>Содержат 32-битовые положительные числа.
А>>Числа в пределах одного массива могут повторяться произвольное количество раз.
А>>Надо найти номера всех различающихся элементов.
А>>Количество элементов в массивах — миллионы.
А>>Оперативки можно задействовать 2-3 метра.

А>>Ткните, плз, мордой в более-менее валидный вариант организации сравнения.

I>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

Если я правильно понял вопрос, то:

Создаешь массив X[0..2^32-1]...
Используешь его как аккумулятор для подсчета количества каждого числа из массивов...
Потом проходишь по нему и номера всех элементов количество которых = 1 выводишь в выходной массив...

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


I>>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

А>Угу, отыскать множество индексов, где A[i]!=B[i]

ну так в цикли проходишь и сравниваешь
или я задачу твою не понял?

I>>>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

А>>Угу, отыскать множество индексов, где A[i]!=B[i]

I>ну так в цикли проходишь и сравниваешь
I>или я задачу твою не понял?

А вот как бы избежать "тупого" сравнения?

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

I>>>>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

А>>>Угу, отыскать множество индексов, где A[i]!=B[i]

I>>ну так в цикли проходишь и сравниваешь
I>>или я задачу твою не понял?

А>А вот как бы избежать "тупого" сравнения?

ты его постоянно сравниваешь? или только один раз?
если постоянно, то разделяй на блоки и фиксируй изменения в блоках, потом повторный поиск только в измененных блоках

А>>А вот как бы избежать "тупого" сравнения?

I>ты его постоянно сравниваешь? или только один раз?
I>если постоянно, то разделяй на блоки и фиксируй изменения в блоках, потом повторный поиск только в измененных блоках

Выполнять придется несколько сотен раз сравнивая разные одномерные массивы.

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


А>>>А вот как бы избежать "тупого" сравнения?

I>>ты его постоянно сравниваешь? или только один раз?
I>>если постоянно, то разделяй на блоки и фиксируй изменения в блоках, потом повторный поиск только в измененных блоках

А>Выполнять придется несколько сотен раз сравнивая разные одномерные массивы.

имхо тут от тупого не уйдешь

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

А>А вот как бы избежать "тупого" сравнения?

Отсортировать массив и последовательно просмотреть

M>Если я правильно понял вопрос, то:

M>Создаешь массив X[0..2^32-1]...

sizeof(X) будет зависит от того сколько раз может повторятся число.

Если предположить что число может повторяться не более 256 раз, то sizeof(X) будет из элементов по одному байту, то минимум 2^32 = 4Гига.
В то время как оперативки можно задействовать 2-3 Мбайта, а 4 гигов может просто не быть на диске для такого файла. Не считая издержек на файловые операции.

M>Используешь его как аккумулятор для подсчета количества каждого числа из массивов...
M>Потом проходишь по нему и номера всех элементов количество которых = 1 выводишь в выходной массив...

А если числа всего лишь переставленны?
A = { 11, 9, 2, 7, 11, 13, 7 }
B = { 11, 2, 7, 9, 11, 13, 7 }

M>Отсортировать массив и последовательно просмотреть

1.Отсортировать массив B.
2.Идти последовательно по массиву A
3.Через бинарный поиск убеждаясь, что в массиве B присутствует A[i].
3.При каждом поиске контролируя количество возможных повторений числа из A[i].

Что-то в этом роде?

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


M>>Отсортировать массив и последовательно просмотреть

А>1.Отсортировать массив B.
А>2.Идти последовательно по массиву A
А>3.Через бинарный поиск убеждаясь, что в массиве B присутствует A[i].
А>3.При каждом поиске контролируя количество возможных повторений числа из A[i].

А>Что-то в этом роде?

А зачем бинарный поиск? Достаточно последовательного :sm12: Если A[i-1] <> A[i] и A[i] <> A[i+1], то A[i] уникально.

M>>>Отсортировать массив и последовательно просмотреть

А>>1.Отсортировать массив B.
А>>2.Идти последовательно по массиву A
А>>3.Через бинарный поиск убеждаясь, что в массиве B присутствует A[i].
А>>3.При каждом поиске контролируя количество возможных повторений числа из A[i].

А>>Что-то в этом роде?

M>А зачем бинарный поиск? Достаточно последовательного :sm12: Если A[i-1] <> A[i] и A[i] <> A[i+1], то A[i] уникально.

В целом не валидно.
Проходя с п.1 по п.4 нет возможности убедиться, что число A[i] стоит в той же позиции в изначальном(неотсортированном) массиве B.

Годится лишь для другой задачи "присутствуют ли в массиве B такие же числа и в таком же количестве, что и в массиве A".

А надо "в каких позициях массивов A и B содержатся различающиеся числа".

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

А>Выполнять придется несколько сотен раз сравнивая разные одномерные массивы.

Сравнивать при заполнении массивов. Если возможно, конечно.