Большой Воронежский Форум Mobile

Опять я с вопросом по алгоритмам...
Есть последовательность элементов. Над элементами возможна ТОЛЬКО операция сравнение на равенство (никаких <,>,<=,>=). Мощность множества элементов - бесконечность (но последовательность как Вы понимаете конечна). Нужен алгоритм, который удалит из последовательности повторяющиеся элементы. Основной критерий скорость. Есть ли в природе что-нибудь быстрее тупого перебора?
... да... не понятно как-то написал, попытаюсь объяснить на примере...
есть, к примеру, массив записей. Каждая запись размером ну допустим 1Mb(кому нравится цифры побольше - не стесняйтесь ). Допустим, для любых двух записей мы можем мгновенно сказать, равны они или нет, а вот кто больше кто меньше это уже труднее...те. с сортировками тут небольшой облом...Нужно удалить из массива повторяющиеся элементы. Как ( кроме тупого перебора )? [Ответ]

В данной задаче количество переборов будет количеством сочетаний. Ни как иначе. :-)
Надо все-таки сортировать по какому-то принципу. Не бывает в компьютерах информации, которую нельзя соотносить как <, > и =. Ну не бывает. Сортируй по алфавиту, размеру, как хочешь еще. Если сам не сможешь, озвучь задачу нормально - подумаем. [Ответ]

Ну, например, так: есть куча картинок с различными изображениями (формат не важен) яблочки там, груши, цветочки-лютики, циферки, да все что угодно.... их куча. Удалить дубликаты.
...
В общем случае - двоичные объекты неизвестного размера и содержания, с признаком что это есть объект(GUID и интерфейс). Для объектов реализована ТОЛЬКО операция сравнения (грубо говоря метод IsEqual() ) и все. Надо поудалять лишнее.
Пока дотумкал только до следующего алгоритма:
Взять первый элемент, поудалять к четям все такие же. Взять первый из оставшихся итп... [Ответ]

Сообщение от MadFish:
двоичные объекты неизвестного размера и содержания

приведите их к удобоваримому виду. хэши какие-нибудь [Ответ]

maximn, говорю же -мощность множества бесконечность, объекты различной природы. как построить вменяемую хеш функцию???? [Ответ]

MadFish, какие проблемы? Ты можешь обратиться к этим данным, значит ты можешь их сотрировать, хэшить и все что угодно еще делать. Бесконечного множества данных не бывает в памяти компьютеров. :-) [Ответ]

Akad,Как, ну как блин мне их хешить????? Хеширование- процесс отображения КОНЕЧНОГО множества элементов в КОНЕЧНОЕ множество, но большей мощности. У меня БЕСКОНЕЧНОЕ множество элементов.
ладно, раз Вы так вцепились в понятие данных и компьютеры, специально для Вас упрощу задачу. Есть последовательность блоков данных размером ну, например 1024 Терабайта (не помню, как это обзывается). Длина последовательности гораздо меньше (несколько тысяч элементов). Нужно удалить дубликаты за разумное время. Сортировка невозможна т.к. на выяснение кто больше 0 или 1 элемент уйдет оч. много времени. Хеширование как Вы понимаете, тоже будет идти довольно долго. А узнать, что элементы не равны друг другу просто- первый не нулевой XOR двух байт и все. [Ответ]

Считай контрольные суммы и т.п. В чем проблема-то?
Я так понимаю, что у тебя какая-то абстрактная задача, которая реально решаться не будет. Видишь ли. Программирование это прикладная наука. в ней не бывает гугл элементов по гугл байт. Просто не создано до сих компьютеров, которые смогут ворочить такими данными. Так что или описывай конкретную задачу из реальной жизни, или иди к математикам. [Ответ]

а на чём пишешь? [Ответ]

Akad,нет, это утомительно... Вы как ребенок цепляетесь к словам. Ну, естественно я не гуглы сортирую (сказал же что "специально для Вас упрощу задачу"). Конкретика моей задачи Вам ничего не даст, но если так угодно, пожалуйста. Есть двоичные объекты, пронаследованные от одного интерфейса IObject, в котором описан метод IsEqual(IObject &) возвращающий булевское значение. Есть последовательность объектов IObject. надо удалить из нее дубликаты. Размещение объектов в памяти не известно, механизмы работы IsEqual(IObject &) тоже на совести разработчиков объектов.
Помогло?
А про прикладную науку и математиков не надо мне ля-ля. Я уже больше десятка лет работаю программером. Я спросил помощи по тривиальному алгоритму (до одного варианта я своим скудным умишком дотумкал, но может, есть что побыстрее). От Вас я пока помощи (к сожалению) не вижу.
Вопрос посему остается открытым.
mike_s, да какая разница??? Я алгоритм спрашиваю, а уж на чем реализовывать это дело десятое. [Ответ]

MadFish
Пишешь на яве? Там есть toString() или напиши что-нибудь свое, что будет отдавать byte[] т.е. получить в бинарном виде свои данные объекта. Дальше сортировка/хэширование/... по вкусу.
Если это РЕАЛЬНО не возможно (в чем я сомневаюсь) тогда только полный перебор. Другого метода естественно нет. [Ответ]

MadFish, а объекты могут различаться на любом байте?? или на блоках?? [Ответ]

MadFish, разница есть. На РНР это, к примеру, элементарно делается. [Ответ]

Akad, Реально такое не возможно. Архитектура системы создана так, что управляющая чисть практически ничего не должна знать об объектах которыми она манипулирует. И нигде больше доп. информация об объекте не требуетя, а накладывать ограничение на объект об обязательной сериализации только для данной процедурки не имеет смысла.
Ну скажем не полный перебор. Для того рекурсивного алгоритма который я описал выше- уже не полный перебор а поменьше:
N - колво элементов
n - колво не повторяющихся
a(j) - колво повторений j того элемента (0<=j<=n)
соответственно число проходов n, кол-во сравнений N*n-a(1)*(n-1)-a(2)*(n-2)...-a(n)
Но чует моя программистская пятая точка, что можно быстрее...

to olexus, объекты-сущности о которых я ничего не могу сказать.

to mike_s, не вижу особой разницы... [Ответ]

MadFish, я бы тебе советовал бы пробиться к самим данным. Возможность есть практически всегда. Можно на низком уровне и т.п.
Если делать рекурсией, то получится от N!-n до (N-n)! вариантов, как повезет (в какой последовательности будут тебе попадаться повторяющиеся элементы). Откуда ты взял формулу N*n-a(1)*(n-1)-a(2)*(n-2)...-a(n) - не понятно. [Ответ]

Akad, Пойми же мил человек, если я лезу к данным, тогда управляющая часть должна знать, как долезть к данным ЛЮБОГО объекта, а что придумает конечный разработчик объектов- хрен его знает. т.е. при добавлении нового типа объектов придется переделывать и управляющую часть, либо обязать разработчика объекта делать никому нафиг не нужную сериализацию!!! А на самом деле управляющей части похрену, что за объект. Ей НЕВАЖНО (и соответственно знать ничего не надо). Да и вообще дело не в данных. Нужен алгоритм по заданным условиям, а так мы доберемся до того как упаковываютя биты в структурах объектов. Это частности, не забивайте себе голову!!! Считайте что мы имеем дело с картинками, где нарисовано все что угодно!!!
...
Как откуда я взял формулу??? На первом проходе я удалил a(1)-1 элемент, т.е. на втором проходе я уже буду сравнивать N-a(1) элементов (первый элемент мне тоже больше не нужен, так как он остался единственный) итд.

Вопрос остается открыт.... [Ответ]

Берешь 1-й элемент, удаляешь такие-же, как он, потом, если были его копии, помечаешь его как-либо, чтобы больше не проверять ВООБЩЕ, далее берешь первый неотмеченный элемент и пошел сравнивать с непроверенными. И т. д. В начале проверка будет происходить долго, а потом все быстрее и быстрее, т. к. исключаются уже проверенные объекты. [Ответ]

mozg1986, ага, именно про это я и написал в посте №3 и даже проанализировал быстродействие в последующих постах.
Но как я и говорил, сдается мне, что можно быстрее...

Вопрос все еще открыт... [Ответ]

попробуй идти с двух концов [Ответ]

I&F, это ничего не даст! У меня НЕТ упорядочивания элементов по <,> только =... [Ответ]

да? а а1......аn? [Ответ]

Сообщение от I&F:
да? а а1......аn?

что Вы имели в виду??? а1...аn количество повторений соответствующих элементов... при чем здесь это ??? [Ответ]

сравниваешь одним циклом а1 с а2 а3 по возрастанию и аn с an-1....
по убыванию [Ответ]

Сообщение от I&F:
сравниваешь одним циклом а1 с а2 а3 по возрастанию и аn с an-1....
по убыванию

Вы бредите!!! Почитайте внимательнее условие!!!( пост №1) [Ответ]

Если я брежу, значит слово массив сюда не подходит
Если не правильно понято еще раз русским по белому
Первый элемент проверяется на совпадение со вторым, третьим и тд
Последний элемент проверяется на совпадение с предпоследним и тд [Ответ]

I&F, И все-таки Вы бредите!!!

Сообщение от I&F:
Если не правильно понято еще раз русским по белому
Первый элемент проверяется на совпадение со вторым, третьим и тд
Последний элемент проверяется на совпадение с предпоследним и тд

И ЧТО МНЕ ЭТО ДАСТ??? Этот пост № 26 а я до сих пор объясняю условие. Что-то тут не так. Ну попробую еше раз. В массиве находятся элементы к которым применима ТОЛЬКО операция сравнения на равенство(см пост №1). Необходимо из массива удалить дубликаты.
Упорядочивания по <,> нет, соответственно поиск с двух концов мне НИЧЕГО НЕ ДАСТ. Будет тоже самое кол-во проверок!!!
Ну что тут непонятного???? [Ответ]

Даст что за один шаг цикла будет два сравнения и возможно уменьшение массива на две единицы содержимого
Есть еще вариант сравнивать на совпадение (читай равенство) каждый последующий элемент с предидущими, при совпадении удалять, таким образом у тебя в начале массива будут скапливаться уникальные,
но не уверен в выигрыше в скорости ... эт так как идея - это может быть бредом [Ответ]

Сообщение от I&F:
Даст что за один шаг цикла будет два сравнения.

Ну и какая разница двадцать раз по одному сравнению или 10 раз по два? Сравнений от этого меньше не стало!!!

Сообщение от I&F:
Есть еще вариант сравнивать на совпадение (читай равенство) каждый последующий элемент с предидущими, при совпадении удалять, таким образом у тебя в начале массива будут скапливаться уникальные,
но не уверен в выигрыше в скорости ... эт так как идея - это может быть бредом

Вы сами все и сказали. Сравнение соседних элементов практически не повлияет на ход алгоритма. Уменьшение количества дубликатов при таком виде сравнений стремится к 0. Могу доказать с формулами в руках(хотя я думаю Вы и сами справитесь). [Ответ]

читаем первые две строчки...
и вообще чегоя за советскую власть агитирую...
можно просто попробовать алгоритм на массивчике и посмотреть....
ухожу, удачи..
жду с нетерпением оптимального решения [Ответ]