Всем доброго времени суток! Имеется набор из большого количества массивов (~1000). Задача - найти позиции, такие, что числа, стоящие на этой позиции, совпадают для всех массивов. То есть найти i, такое, что A1=A2=...=An. Гугл приводит в основном решения, сводящиеся к линейному перебору. Есть еще вариант построить СЛАУ с соответствующими индексами и минимизировать - тогда все "выпавшие" слагаемые будут искомыми совпадениями. А есть возможность оптимизировать еще дальше?
Первый вопрос: структура данных в этих массивах (дисперсия) Второй вопрос: Данные в массивах упорядочены? третий вопрос и т.д. Очень общий вопрос! В некоторых случаях только прямой перебор.
Lecko Чтобы найти такие элементы надо выполнить сравнение поэлементно для всех матриц. Но можно разбить матрицу на 4 подматрици, а те в свою очередь еще на 4 и так далее. И проверять если подматрица уже при проверке все элементы оказались разные, то не проверять её.
Lecko Если данные в массивах не меняются, то достаточно 1 раз перебрать "линейно" (тут иначе никак). Ну а если данные в массивах меняются, то решения зависят от конкретики.
1) Данные в массивах неупорядочены 2) Структура данных: будем считать, что случайное значение от 0 до 0xFF
Прошу прощения, не совсем верно выразился. В общем, есть некоторая неизвестная структура данных, записанная в виде последовательности байт.Есть поля совпадающие, есть различающиеся. Есть большое количество образцов этой структуры. Задача - выделить все совпадающие байты (доподлинно известно, что они есть)
еще непонятнее. и оптимизировать по какому критерию? по времени выполнения? возможно, достаточно отсортировать - все совпадающие просто лягут рядом. вообще, саму задачу неплохо бы уточнить. условие 1 сильно отличается от условия N условие 1 results = []; for i=0, len m[1]: for j=1, len m: if m[1] != m[j]: break; if j == len m: results.append([ i, m[1] ]); return results; учитывая, что при оптимизации по скорости ключвое время будет иметь доступ к памяти - такое рещение, имхо, будет достаточно неплохо. в случае если мы не можем влиять на исходные массивы. если можем, то я бы их сразу транспонировал. чтоб сравниваемые ячейки шли подряд. тогда можно было бы даже repe scas
qqwe Оптимизировать по количеству операций, т.е времени выполнения разумеется. А какого рода уточнение требуется (прошу прощения за глупый вопрос )
Lecko Сравнить первые два массива. Выписать все совпадающие позиции (использовать односвязный список). Посмотреть эти позиции в третьем массиве. Вычеркнуть те позиции, где элементы не совпали. И так далее. На каждом шаге число проверяемых позиций будет сокращаться, а как сильно - зависит от данных. В худшем случае время работы будет O(N*M), где N - число массивов, M - размер массива. В лучшем случае - O(N), когда первые два массива вообще не совпали. Все зависит от конкретных данных. А вообще, любой алгоритм решения потребует в худшем случае времени O(N*M) или большего - хотя бы из того соображения, что нужно просмотреть все элементы всех массивов по одному разу. P.S. Хотя что-то я перемудрил. Простой двойной цикл, внутренний цикл проверяет A1=A2=...=An, и break из внутреннего цикла при несовпадении. Та же асимптотика получится.
