Удаление дубликатов элементов из последовательности...

[I&F]

кста.. второй вариант лучше рассмотреть ;-)

[MadFish]

Сообщение от I&F

кста.. второй вариант лучше рассмотреть ;-)

Это тот где сравниваются рядом стоящие элементы? ну по моему при n->N вероятность удаления элемента ->0. Или я и тут где-то торможу?
Да и собственно на следующем шаге такое сравнение будет сделано неявно и так и так.

[MadFish]

Maximus007, Ого, смелое заявление. Ну ради такого дела считайте что можете получить все байты любого объекта(правда кол-во таких байт ничем не лимитировано)!!!

[maximn]

Сообщение от MadFish

Ну ради такого дела считайте что можете получить все байты любого объекта(правда кол-во таких байт ничем не лимитировано)!!!

бля. ну и сделайте хэш.

кстати, насчет того о чем вам I&F полстраницы объяснял - один и тот же элемент нужно было сравнивать сначала с первым, потом с последним. очевидное уменьшение цикла в 2 раза

[MadFish]

maximn, тыгдым...., опять за рыбу деньги... Приведите мне хоть одну нормальную хеш функцию которая будет мне давать внятный разброс и внятное время построения хеш значения при не фиксированном размере элементов. Жду!!!

во первых вы не поняли объяснения господина I&F. Не один и тотже элемент сравнивать с первым и последним а два разных элемента первый и последний сравнивать с рядомстоящими итп.
по поводу уменьшения в 2 раза еще не все так просто. Это работает во первых только при неравенстве первого элемента последнему, иначе таже фигня. А вот на сколько уменьшается нужно еще посчитать.

[maximn]

я не знаю почему, но форумец MadFish меня раздражает.

[MadFish]

maximn, это Ваши личные трудности.

[maximn]

я понял почему - глупые люди всегда меня раздражают

[Maximus007]

если нельзя отсортировать по каким нить параметрам то количество операций сравнений будет лежать в пределах N-1 < O < (N-1)*(N-1)/2
N-1 - если все объекты одинаковы
(N-1)*(N-1)/2 - если все объекты разные
решение пост №17, чтобы уменьшить число операций сравнений нужно сортировать иначе никак или использовать какие-нибудь ньюансы системы о которой идет речь.
Можно отсортировать по размеру занимаемой объектами памяти, сформировать группы и производить поиски внутри групп.

[MadFish]

Maximus007, Абсолютно согласен с Вашей оценкой для алгоритма №№3,17 (ту же самую оценку я привел в посте №14, только более развернуто). Но неужели нет более быстрого алгоритма? Например, господин I&F, предлагал просматривать массив с двух концов. Я пока не уверен, что это даст выигрыш (не было у меня времени оценить сложность данного алгоритма), но на первый взгляд прирост скорости должен быть.
А на счет сортировки - это затруднительно. Возвращаясь к моей аналогии с картинками одинакового размера, на которых может быть изображено все что угодно, не вижу критериев для сортировки или группировки...

[I&F]

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

[MadFish]

Сообщение от I&F

блиниииннн.. ну скажите счто я тупой а?

Ни в койм случае господин, I&F!!! Это скорее я неправильно Вас вчера понял. Приношу свои извинения(вечер, конец рабочего дня...)!!! А по поводу Вашего предложения, то оценка сложности тут будет явно хуже (этот алгоритм пришел мне на ум в самом начале, когда передо мной встала эта проблема, я делал оценку его сложности, и если Вас интересует, могу ее привести).
Сейчас я занимаюсь оценкой Вашего предложения просматривать массив с двух сторон. Если у Вас уже есть готовые выкладки, не поделитесь ли ими со мной?

[mozg1986]

Как вариант, можно разбить весь массив на несколько более медких и искать одинаковые элементы сначала в них, а потом одинаковые в получившихся после первого прохода. Не знаю почему, но такое разбиение в моем случае дало очень ощутимый прирост в скорости. задача была таже, искал как описал в посте #17 плюс вышенаписанный финт ушами.

[MadFish]

to I&F, И все-таки Гн. I&F, я был прав, вариант с просмотром массива с двух сторон не принесет значимого прироста в скорости по сравнению с алгоритмом №№3,17.
Пусть в нашем массиве элемент А это начальный, а элемент В конечный. А a и b соответственно удаляемые элементы на i том проходе. Рассмотрим случай, когда удаляются по 1 элементу. При таком условии, единственный вариант, который принесет выигрыш в скорости на 1, это когда a и b находятся в своих половинах массива (а вероятность этого 25%) .Если a и b в хвосте выигрыш 0.(улучшение для b нейтрализуется лишним сравнением B c a). Если a и b вначале 0(A и b и так уже сравнили) . a и b не в своих половинах – ухудшение на 1(лишнее сравнение B с a).При бОльшем кол-ве удаляемых элементов, шанс улучшится еще меньше…
mozg1986, врятли Ваш метод может дать улучшение скорости... Ведь у нас не сортировка... (то что не найдено совпадений в какой-то части массива не означает что любой элемент из этой части не повторяется во всем массиве. т. е в любом случае придется делать полный проход по массиву...) Хотя если объеденить Вашу идею и идею Гн. I&F о просмотре массива с двух концов может что-то и получится... Хотя надо еще подумать...

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

[Forrest]

Не очень силен в сортировке, но со своего опыта программирования могу посоветовать сортировать объекты по косвенным признакам (размер, какие-то "особые точки" и т.п.)

Первое же, что нашел в в яндексе:

http://fantom-lab.narod.ru/Python/Le...3/002-3-03.htm

А вообще, в яндексе или гугле много интересных ссылок по запросу "Метод сортировки разнородных"

[MadFish]

to Forrest, две картинки изображающие яблоко но разного размера все равно будут одинаковыми... Смысла в сортировке по размеру (да и вообще в сортировке в данном случае)не вижу...

[OTTO]

))))))))

[mozg1986]

Сообщение от MadFish

mozg1986, врятли Ваш метод может дать улучшение скорости... Ведь у нас не сортировка... (то что не найдено совпадений в какой-то части массива не означает что любой элемент из этой части не повторяется во всем массиве. т. е в любом случае придется делать полный проход по массиву...) Хотя если объеденить Вашу идею и идею Гн. I&F о просмотре массива с двух концов может что-то и получится... Хотя надо еще подумать...
Вопрос все еще открыт....

Я этот алгоритм использовал как раз не для сортировки, а для "склеивания" точек с одинаковыми координатами у 3D объектов после импорта из .3ds и алгоритм замечательно работает. Бегать по всему массиву все равно придется, как не крути.

[MadFish]

to mozg1986, Но даже если просто логически рассуждать... пусть имеются две подпоследовательности {1;2;3;4;5} и {1;2;3;4;5}. по Вашему алгоритму проверим сначала первую, за тем вторую, а вот уж за тем весь массив(тогда и будут удаляться дубликаты) -кол-во сравнений увеличили вдвое, а результат тот же... Негодится...

Выходит, что быстрее автомата с N сенсорами и одной читающей головкой на всех(который мы придумали в постах №3,17) ничего нет... В инете не нашел... Если кто, че придумает, буду крайне признателен.

[Akad]

MadFish, конечно нет другого алгоритма. Есть только вариации этого. Количество переборов будет всегда одинаково.
Единственное что еще могу посоветовать - если размеры в байтах объектов не большие, то стоит их анализировать небольшими группами, что бы они все в процессорный кэш залетали. Скорость должна сильно возрасти.