Не точное сравнение двух векторов, состоящих из 2 млрд. элементов целого типа , Нужен чисто оптимальный алгоритм

Всем hi!
Сходу введем некоторые ограничения/уточнения:
1. Под целым типом данных понимается 4-байтовый знаковый тип. Т е множество допустимых значений для такого типа [-2^31 ... +2^31 - 1].
2. Оперативная память безразмерна/бесконечна, но в ней нет ни одного участка памяти, который способен вместить массив целого типа, состоящего из 4млрд. элементов. Массив, состоящий из 2 или 3 млрд. элементов целого типа данных вполне допустим, главное, что размер не может превышать 4млрд.
3. Два вектора (вектор - одномерный массив, элементы которого имеют целый тип данных) считаются не точно равными друг другу, тогда и только тогда, когда равны их длины (количество элементов), а также равны значения элементов без учета их взаимного расположения.
Пример не точно равных векторов:
1: 1 2 3 4 4 5
2: 2 4 5 1 4 3

Или еще:
1: 1 2 3 1 2
2: 2 2 3 1 1

Условие задачи: на вход программе подается два вектора длиной в 2млрд.элементов. Проверить данные вектора на не точное совпадение.
Какие я вижу способы/алгоритмы:
1. Отсортировать и сравнить поэлементно. Если в какой-либо i-й позиции значения не совпадут, то вектора не равны друг другу! Считаю, что главная проблема - длительность операции сортировки.
2. Можно было попытаться получить частотность встречаемости значений, например из 1-го вектора (это можно сделать за 1 цикл), а затем пробежаться по 2-му вектору и сравнить частотность встречаемости его элементов с 1-ым вектором. Но тут есть проблема: поскольку целый тип позволяет хранить 2^32 различных значений, а это чуть больше 4млрд, где-то 4.3 млрд., то нет возможности объявить массив такого размера (ограничение №2). Создавать вместо массива динамический список типа ЛОС бессмысленно, т к нет встроенного индексатора - это раз, а во-вторых, когда в исходных векторах практически отсутствуют дубликатные значения, то список может продублировать исходный вектор, не принеся никакой пользы.
3. Можно построить бинарное дерево поиска на значениях из 1-го вектора, а затем начать пробежку по элементам 2-го вектора, удаляя текущее значение из дерева. Для каждого элемента 2-го вектора должно быть соот-щее значение в дереве. После окончания просмотра элементов 2-го вектора дерево должно остаться пустым. Этот способ мне нравится, но существуют ситуации, когда дерево вырождается в простой ЛОС (например, когда элементы 1-го вектора упорядочены по возрастанию, тогда дерево растет лишь по правому потомку).
4. Наверное, можно применить хеш-таблицу, но, ИМХО сложно будет построить грамотную хеш-функцию.

Подскажите самый оптимальный алгоритм решения подобной задачи.

P.S. значения элементов входных векторов не подчиняются никакому закону распределения и имеют хаотичные значения (может быть множество дубликатов при одном тесте или ни одного при другом и т.п.)

Если память безразмерная, то в объяви для каждого вектора статический массив vecnum размером 2^32 = ну там и будет 4 млрд. Занули его.
Тогда значение элемента в векторе vec будет индексом элемента в массиве vecnum. Бежишь по вектору от начала до конца и выполняешь команду: ++vecnum[vec[i]+(2^31)]
И так для каждого вектора.
А потом бежишь по полученным vecnum и сравниваешь. Должны быть одинаковыми.

Цитата Polinom2686 @ 22.10.16, 09:44

И так для каждого вектора.
А потом бежишь по полученным vecnum и сравниваешь. Должны быть одинаковыми.

Проще. Сперва для первого массива плюсим, потом для второго минусим. Если в процессе хотя бы один элемент стал отрицительным - останавливаем и сообщаем, что векторы не равны. Иначе - равны.

Цитата Akina @ 22.10.16, 10:20

Цитата Polinom2686 @ 22.10.16, 09:44

И так для каждого вектора.
А потом бежишь по полученным vecnum и сравниваешь. Должны быть одинаковыми.

Проще. Сперва для первого массива плюсим, потом для второго минусим. Если в процессе хотя бы один элемент стал отрицительным - останавливаем и сообщаем, что векторы не равны. Иначе - равны.

Точно

Цитата FasterHarder @ 22.10.16, 08:32

2. Оперативная память безразмерна/бесконечна, но в ней нет ни одного участка памяти, который способен вместить массив целого типа, состоящего из 4млрд. элементов. Массив, состоящий из 2 или 3 млрд. элементов целого типа данных вполне допустим, главное, что размер не может превышать 4млрд.

память фрагментирована!
Тем более этот способ описан под номером 2!
Нет возможности создать массив статический размером в 4.4 млрд. элементов!!! Специально накладывается такое ограничение, чтобы НЕЛЬЗЯ было создать карту частотности значений.

Цитата FasterHarder @ 22.10.16, 10:49

Цитата FasterHarder @ 22.10.16, 08:32

2. Оперативная память безразмерна/бесконечна, но в ней нет ни одного участка памяти, который способен вместить массив целого типа, состоящего из 4млрд. элементов. Массив, состоящий из 2 или 3 млрд. элементов целого типа данных вполне допустим, главное, что размер не может превышать 4млрд.

память фрагментирована!
Тем более этот способ описан под номером 2!
Нет возможности создать массив статический размером в 4.4 млрд. элементов!!! Специально накладывается такое ограничение, чтобы НЕЛЬЗЯ было создать карту частотности значений.

Ну так сделай два массива по 2 млрд.

Добавлено 22.10.16, 11:00
Один для отрицательных чисел, второй для положительных.

Можно еще завести маску, используя биты. 2^29 байт(536 миллионов) (но 2^32 бит)
i-ый бит - наличие i-го числа в векторе.
по маске для каждого вектора. Сравниваешь маски - если не совпадают - множества уже не равны.
Иначе уже можешь делать сравнение множеств.
Была ещё какая-то хитрая штука, с битами связана, если вспомню напишу.

Цитата dimir @ 22.10.16, 12:59

Была ещё какая-то хитрая штука, с битами связана

вот тоже ПОЧТИ уверен, что задача НА БИТОВУЮ картину, но пока не могу это понять

P.S. Есть в этой задаче пункт б), в котором говорится, что в памяти присутствуют участки длиной непревышающие 32 байта (т е уже не 2 млрд.элементов можно подряд поставить, а лишь 8) и вот тут точно либо БИТЫ брать, либо использовать динамические структуры данных

Добавлено 22.10.16, 13:33
Здесь прекрасно можно было бы использовать всякие ДСД, типа бинарного дерева поиска или ЛОС или просматриваемой таблицы, если бы не было вырожденных случаев, когда в исходных векторах все значения различны + располагаются как-нибудь в отсортированном порядке (причем противоположной направленности)

Добавлено 22.10.16, 13:35
тут еще вроде можно как-то через хеш-коды/контрольную сумму сделать, но очевидно, что суммы чисел 2 + 8 = 4 + 6 хоть и равны, но выражают различные слагаемые..

Вспомнил. Фильтр Блума, возможно, как-то поможет.

А вообще, задача на сравнение двух множеств.

Сообщение отредактировано: dimir - 22.10.16, 13:53

Цитата FasterHarder @ 22.10.16, 13:31

вроде можно как-то через хеш-коды/контрольную сумму сделать

Грубо говоря, нельзя: множество вариантов столь огромно, что вероятность ошибки в ноль загнать не удастся, а сто́ит ли тогда рисковать?..

Можно разделить каждое множество на два (используя две битовых маски по 2^29 байт каждая) на множества уникальных чисел и не уникальных. И дальше что-нибудь придумать.

Цитата FasterHarder @ 22.10.16, 10:49

память фрагментирована!
Тем более этот способ описан под номером 2!
Нет возможности создать массив статический размером в 4.4 млрд. элементов!!!

Что ты так заморочился массивом? создай коллекцию, где ключ имеет тот же тип, что и значение элемента в твоём векторе... или создай двумерный массив, на который отобрази этот не влезающий в непрерывный блок памяти одномерный - всё равно массив у тебя весьма условный, и если под каждую "строку" будет свой блок, никто не обидится.

Добавлено 22.10.16, 15:46

Цитата dimir @ 22.10.16, 12:59

Можно еще завести маску, используя биты. 2^29 байт(536 миллионов) (но 2^32 бит)
i-ый бит - наличие i-го числа в векторе.

Бред. Нигде не написано, что элемент с заданным значением не может встречаться в векторе более одного раза.

Цитата Akina @ 22.10.16, 15:44

Мы сравниваем множества. Если данные маски не совпадут - множества уже не равны. А если завести две маски, то можно будет пометить уникальные числа и повторяющиеся за линию.
Правда я всё равно не понимаю почему не заюзать обычные контейнеры типа multiset

Цитата dimir @ 22.10.16, 16:15

Если данные маски не совпадут

А если совпадут? с учётом мультивхождения это не только ни о чём не говорит, но и не приближает к ответу - а сколько усилий уже угрохано...

Всем спасибо за обсуждение!

Скрытый текст

P.S. кстати, dimir, ты оказывается еще ответил в др. теме про алгоритм MVPC. Только сейчас заметил! Не знаю - правильно или нет! Но в любом случае спс., но много воды уже утекло...

Цитата FasterHarder @ 22.10.16, 08:32

то нет возможности объявить массив такого размера (ограничение №2)

Ограничений создать несколько векторов для первого и второго вектора нет - ну так несколько меньших создай. 4 млрд. низя, а 2 можно - создай 2. Чтобы не пересчитывать постоянно смещение индекса - напиши проходы двумя циклами копипастой. Ну а потом да - сравнение "частотных" векторов до первого несовпадения, или до конца.