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

Ткните, плз, мордой в более-менее валидный вариант организации сравнения.
Re: сравнение массивов
От: ilnar Россия  
Дата: 17.01.06 12:15
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Сравниваются два массива.

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

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


в смысле где A[i]!=B[i] или (A\B)U(B\A) ?
Re[2]: сравнение массивов
От: Аноним  
Дата: 17.01.06 12:26
Оценка:
I>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

Угу, отыскать множество индексов, где A[i]!=B[i]
Re[2]: сравнение массивов
От: Mckey Россия  
Дата: 17.01.06 12:26
Оценка:
Здравствуйте, ilnar, Вы писали:

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


А>>Сравниваются два массива.

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

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


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


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

Создаешь массив X[0..2^32-1]...
Используешь его как аккумулятор для подсчета количества каждого числа из массивов...
Потом проходишь по нему и номера всех элементов количество которых = 1 выводишь в выходной массив...
Делай добро и бросай его в воду...
Re[3]: сравнение массивов
От: ilnar Россия  
Дата: 17.01.06 12:30
Оценка:
Здравствуйте, Аноним, Вы писали:


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


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


ну так в цикли проходишь и сравниваешь
или я задачу твою не понял?
Re[4]: сравнение массивов
От: Аноним  
Дата: 17.01.06 12:32
Оценка:
I>>>в смысле где A[i]!=B[i] или (A\B)U(B\A) ?

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


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

I>или я задачу твою не понял?

А вот как бы избежать "тупого" сравнения?
Re[5]: сравнение массивов
От: ilnar Россия  
Дата: 17.01.06 12:35
Оценка:
Здравствуйте, Аноним, Вы писали:

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


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


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

I>>или я задачу твою не понял?

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


ты его постоянно сравниваешь? или только один раз?
если постоянно, то разделяй на блоки и фиксируй изменения в блоках, потом повторный поиск только в измененных блоках
Re[6]: сравнение массивов
От: Аноним  
Дата: 17.01.06 12:40
Оценка:
А>>А вот как бы избежать "тупого" сравнения?

I>ты его постоянно сравниваешь? или только один раз?

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

Выполнять придется несколько сотен раз сравнивая разные одномерные массивы.
Re[7]: сравнение массивов
От: ilnar Россия  
Дата: 17.01.06 12:42
Оценка:
Здравствуйте, Аноним, Вы писали:


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


I>>ты его постоянно сравниваешь? или только один раз?

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

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


имхо тут от тупого не уйдешь
Re[5]: сравнение массивов
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 17.01.06 12:50
Оценка:
Здравствуйте, Аноним, Вы писали:

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


Отсортировать массив и последовательно просмотреть
Re[3]: сравнение массивов
От: Аноним  
Дата: 17.01.06 13:37
Оценка:
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 }
Re[6]: сравнение массивов
От: Аноним  
Дата: 17.01.06 13:46
Оценка:
M>Отсортировать массив и последовательно просмотреть

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

Что-то в этом роде?
Re[7]: сравнение массивов
От: Mystic Украина http://mystic2000.newmail.ru
Дата: 17.01.06 14:21
Оценка:
Здравствуйте, Аноним, Вы писали:


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] уникально.
Re[8]: сравнение массивов
От: Аноним  
Дата: 17.01.06 14:46
Оценка:
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 содержатся различающиеся числа".
Re[7]: сравнение массивов
От: gear nuke  
Дата: 20.01.06 05:06
Оценка:
Здравствуйте, <Аноним>, Вы писали:

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


Сравнивать при заполнении массивов. Если возможно, конечно.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.