| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > сравнение массивов |
| Автор: dengalf 9.10.2011, 16:39 |
| доброго времени суток необходим эффективный алгоритм сравнения массивов целых элементов. задача, собственно, в том, чтобы сделать выборку только из различных массивов первое, что приходит в голову - поэлементное сравнение, но их(массивов) 2^2^n, по 2^n элементов в каждом думаю, нужно посчитать какую-нибудь численную характеристику(навроде суммы всех элементов) и по ней сравнивать. сумма и среднее отпадает, т.к. сумма почти везде одинаковая, а отличаются массивы в основном порядком элементов. напр.: 4 2 2 2 4 2 2 2 2 2 2 2 2 2 4 4 Добавлено через 14 минут и 10 секунд в общем, подумал, и переформулирую вопрос - какая есть(если есть) уникальная численная характеристика последовательности чисел? |
| Автор: DarkProg 9.10.2011, 16:59 |
| И что вы хотите получить от результата сравнения? |
| Автор: Akina 9.10.2011, 17:06 | ||
Значение числа, которое получается, если воспринимать ряд чиел как последовательность цифр числа по соотв. основанию. А вообще - учитесь формулировать свои мысли. Ибо из остального ни хрена не понять... |
| Автор: dengalf 9.10.2011, 17:06 | ||
| элементарно - одинаковые они или нет. если да - то пропуск, если нет - положить в двумерный массив результатов, с которыми, соб-но и нужно сравнивать Добавлено через 2 минуты и 41 секунду
сорри, просто сплю уже((( Добавлено через 4 минуты все, понял, спасибо |
| Автор: DarkProg 9.10.2011, 17:15 |
| Я так понял, вы хотите выполнить попарное сравнение всех массивов и выбрать уникальные - так? |
| Автор: dengalf 9.10.2011, 17:22 |
| да, так Добавлено @ 17:32 ну или не совсем так) алгоритм примерно такой: получаем новый массив сравниваем его с множеством предыдущих если он уникальный - кладем в множество, иначе - идем дальше собственно, на этот ляд мне и нужна была характеристика ряда чисел - если результирующее множество будет упорядочено, то сравнение можно будет сделать практически за логарифмическое время |
| Автор: Фантом 9.10.2011, 17:39 |
| Можно в качестве хэш-функции брать скалярное произведение массива на линейку Голомба соответствующей длины. Если сложно и/или упорядочиваемые массивы вещественнозначны - просто на случайный вектор (естественно, один и тот же). Естественно, массивы с одинаковыми хэш-суммами надо дополнительно проверять на одинаковость. |
| Автор: DarkProg 9.10.2011, 18:28 | ||
Каким образом - от этого можно понять что проще реализовать? |
| Автор: dengalf 10.10.2011, 03:52 |
| массивы это абсолютные значения коэффициентов уолша |
| Автор: esperanto 10.10.2011, 07:34 |
| Если потребовать, ответата на вопрос массивы отличаются меньше чем на 1 процент данных или больше чем на 2 процента, то задача имеет решение в терминах вероятностных алгоритмов за константное время |
| Автор: DarkProg 10.10.2011, 18:10 | ||||
А ну тогда вы их вычисляете, значит, вариант
самый рациональный в данном случае |
