читаю
msdn.microsoft.com/ru-ru/library/bb355408.aspx
цитирую:
При перечислении объекта, возвращенного данным методом, Intersect перечисляет элементы first, собирая в коллекцию все различающиеся элементы этой последовательности. Затем выполняется перечисление элементов последовательности second, с пометкой элементов, входящих в обе последовательности. В заключение, помеченные элементы выдаются в том порядке, в котором они были собраны.
если я правильно понимаю, Intersec имел в виду то что ваши массивы отсортированы.
он втупую перечисляет первое множество (возможно тратя кучу времени на убирание дубликатов) затем добавляет к нему второе (опять же, гарантированно тратя кучу времени на проверку нет ли такого же элемента в первом множестве, чтобы «пометить» что элемент присутствует в обоих множествах)
// буду рад ошибаться в оценка трудоемкости алгоритма реализованного в Intersect
в вашем же случае (хожу думаю уже весь вечер) мне кажется очень важным учесть то что ваши массивы отсортированы.
т.е. вам нужно реализовать свою собственную функцию поиска пересекающихся элементов, которая будет учитывать характер ваших входных данных.
ну например, даже эвристики вида: если A[A.length] < B[1] то выходим, нам тут ничего не светит будут экономить вам кучу времени… (правда только в редких случаях :) )
пока я думаю об общем алгоритме такого вида:
берем за A массив у которого A[1] < B[1] (индексацию массива начинаем с 1, не с нуля, хотя это не принципиально)
i=1;
j=1;
count=0;
просматриваем A[] до нахождения элемента >= B[j] естественно увеличивая i
если A[i]==B[j] то j++; продолжаем просмотр A начиная с текущего i (ну да, не забываем count++ :) )
если A[i] > B[j] то нам не судьба найти совпадение с B[j], можно обменивать массивы местами (в том смысле что B[j] теперь у нас «начало» попытки найти первый совпадающий элемент, а значит, и пересекающуюся последовательность.
ну и не забыть окончание массива, а также граничные случаи типа массива в 1 элемент, массивов у которых нет пересекающихся элементов и т.п.
и прежде чем пробовать реализовывать алгоритм на базе моих фантазий (честно, Кормен и Кнут были уже
очень давно, я бы порекомендовал измерить скорость работы intersect, ну например скормив ему два однаковых массива (только не додумайтесь передать один и тот же массив — это могут проверять и время выполнения будет = O(length()) или O(count())), а также варианты двух разных массивов отсортированных в одном и том же и в противоположных направлениях. а также ЭТИ же массивы, но НЕ ОТСОРТИРОВАННЫЕ. т.е. генерите random массивы, тестируете на них intersect, после чего сортируете их и тестируете intersect повторно, все рамках одного тестового прогона. Если я прав — то время выполнения практически не должно будет отличаться. Если же отличается — то в моем предложении наверное нет смысла)
ps пытаюсь без листика и ручки понять смысл алгоритма предложенного
nickme — все больше подозрения что я предложил эту же идею, но в упрощённо-извращённом формате.
pps очень тяжело у вас условие описано — вам нужны ВСЕ возможные массивы, в которых (одновременно) мощность пересечения >= заданной? или вас устроят только пары массивов, удовлетворяющих этому же условию? если пары то какие, есть ли необходимость выводить все или нет, ну и так далее. уточните задачу а ещё лучше будет если вы дадите понимание чуть более высокого уровня — что потом вы будете делать с результатом? может быть проще будет реализовать алгоритм нацеленный на итоговый результат, чем рассчитывать ваш текущий промежуточный шаг.
