У меня есть два сортированных массива a и b целых чисел: 
int[]a={1,3,4,5,7,9,11,17}
int[]b={3,7,17}
Причем множество значений массива b принадлежат множеству значений массива a и являются его подмножеством.
Как можно извлечь отсутствующие элементы в массиве b и сформировать новый массив int[]с, не создавая цикла поэлементного сравнивания и присваивания (чтобы в результате получился int[]c={1,4,5,9,11} )?
Может в C# .net 2.0 есть какието функции для этого?
Так как при большом колличестве элементов будет огромное колличество итераций
и увеличется время выполнения.

Можно попробовать сконвертить массивы во что-нибудь типа Dictionary и сделать поиск по ключу (trygetvalue) или если н подходит хэширование то посмотреть в сторону List с проверкой Contains Тогда понадобится только один проход

Это сообщение отредактировал(а) axelprog - 19.3.2008, 20:35

sedoy, получается, нужно найти {с} = {a} \ {b} - разность двух множеств. Какой-то злостный вредитель не пожелал записать индексы элементов?  Специальных методов нет, но и алгоритм может быть улучшен, так как строки у Вас отсортированы, значит, находясь в большем из массивов в позиции i не обязательно переходить к (i + 1) а назначить какой-нибудь "хороший" или случайный шаг step. Если на новой позиции находится элемент, меньший, чем очередной элемент меньшего массива, то весь блок от i до i + step можно без сравнений копировать в c.

Это сообщение отредактировал(а) marcusmae - 19.3.2008, 20:56

marcusmae, а можно по-подробнее, не совсем уловил идею  

массивы а и b я привел для примера, но дело в том, marcusmae, что так не получится т.к. в массиве b присутствуют элементы из массива а. Ведь они не подряд одинаковы. Или я не так понял? Это правильно, если они одинаковы подряд до определенного элемента и тогда это очень простой вариант

vponomarov, допустим нам надо проверить в массиве, a не нужно ли выкинуть какой-либо элемент из элементов с индексами от M до N. То есть, нам нужно определить индекс элемента, который должен быть удалён. Так вот не обязательно каждый сравнивать с целевым элементом, можно некоторое количество сравнений выпускать, двигаясь либо с одного конца, либо сразу с двух, по аналогии с тем, как методом деления отрезка пополам ищется существующее решение f(x) = 0 на отрезке. Это возможно, поскольку массив по условию отсортирован.

Это сообщение отредактировал(а) marcusmae - 19.3.2008, 22:51

массив а: a[0]==1,a[1]==3,a[2]==4,a[3]==5,a[4]==7,a[5]==9,a[6]==11,a[0]==17
массив b: b[0]==3,b[1]==7,b[2]==17

если массивы отсортированы, то можно сделать так: 

Примерно так.

Реализовал метод по своему описанию :



Поскольку больше интересовала скорость поиска, не стал заморачиваться и аккумулировал в промежуточный массив индексы элементов, которые должны быть удалены (пропущены при перестроении). В идеале, это можно делать "на лету".





В данном случае метод использовал 4 сравнения, по два на итерацию цикла. В принципе, можно напрячься и сделать одно сранвнение на итерацию за счёт замены битовыми и арифметическими операциями. В любом случае, так как сравнивается одно и то же,



то два сравнения можно считать почти за одно.





Количество сравнений выглядит выгодно. Но пара тестов - это ерунда. Для отладки косяков метода был использован агрессивный тест, генерящий серию случайных массиов a и b (см. проект). Побочным результатом явилось то, что на таком псевдослучайном генераторе (System.Random) метод в среднем проигрывает по числу сравнений. Так что, если любите статистику, то можно попробовать поискать условия, при которых он работает эффективнее прямого сравнения. А может, это вообще никуда не годится  Всё же, полагаю, у него сложность = log2(f(a.Length, b.Length)), что не обязательно хуже, чем у прямого сравнения, сложность которого определяется индексом наибольшего из элементов b в массиве a.

А на счёт List-ов - это конечно особенность, в чём-то даже преимущество .NET : любой вычислительный алгоритм, который неохота (некогда, ненужно, ...) писать эффективно можно реализовать стадесятью неэффективными способами, особо не думая. Не каждый язык+средства может предложить такую свободу.  В этом смысле .NET - рай, если требуется что-то сделать "на коленке"  

Это сообщение отредактировал(а) marcusmae - 21.3.2008, 01:57

Присоединённый файл ( Кол-во скачиваний: 2 )
 Exclusion.rar 42,22 Kb

Спасибо всем за ответы, особенно-marcusmae. Я пытался понять твой, marcusmae, код реализации.  Хочу представить свой собственный вариант решения данной задачи нахождения отсутствующих элементов в массиве b (может смысл один и тот же?). В нем я попытался свести к минимуму поиск элементов. Я не тестировал его с помощью генерирования System.Random различных вариантов. Вот то, что получилось:

sedoy, нет, смысл не один и тот же - то, что у Вас я как раз назвал "прямым сравнением". Кстати, результат Array,IndexOf(...) нужно добавить в count.

Это сообщение отредактировал(а) marcusmae - 22.3.2008, 20:12

Обновил. Так вроде должно быть оптимальнее :

sedoy, глядя на count++ в Вашем коде, кажется, что Вы и не подозреваете, каким образом работает Array.IndexOf(...). Сложность Вашего метода по-прежнему выше, чем лучшая достижимая, которая


, поскольку .IndexOf является перебором элементов массива, начиная с самого первого (а достаточно-то перебирать начиная с индекса предыдущего удаляемого!). Но даже если Вы откажетесь от начального определения inEnd (без которого вполне можно обойтись) и от использования IndexOf, то полученое всё ещё будет соответствовать Вашему же замечанию о том, что


Далее улучшать в нём будет нечего (см. звёздочку), нужно по-другому организовывать перебор в зависимости от характерных позиций удаляемых элементов в исходной последовательности (что я и попытался сделать). По технике выбора элементов похоже на метод бисекции (деления отрезка пополам). Можно ещё кучу всего напридумывать, только скорее сидя за алгоритмом на листке бумаги, чем ковыряя код на C#. По части теории Вам в помощь может пригодиться всемирно известный трёхтомник Дональда Кнута о алгоритмах и вычислительных методах : раз, два, три.

Вы скажите, если я улетел в космос, помогая открыть банку с консервами   Казалось, что тот "оптимальный" метод, к которому Вы определённо делаете шаги в последних двух постах - не то, что Вы хотели делать вначале.

(*) А получен будет следующий алгоритм :
1) Движемся в исходном массиве от первого элемента до первого элемента среди тех, которые нужно удалить
2) Движемся в исходном массиве от первого (i-ого) удаляемого до очередного удаляемого паралелльно перенося элементы исходного массива на единицу влево начиная от индекса первого (i-ого) удаляемого элемента (или не сдвигаем, а копируем на новое место - в результирующий массив). Сравниваем элементы исходного массива с очередным удаляемым.
3) Берём очередной i-ый удаляемый элемент из массива удаляемых и проделываем с ним шаг 2). Останавливаемся как только удаляемые элементы массива удаляемых закончились.

Это сообщение отредактировал(а) marcusmae - 23.3.2008, 18:54

    Действительно, я не подозревал, что  IndexOf выполняет перебор элементов массива, начиная с самого первого. В этом случае естественно мой способ является супер неэффективным. Спасибо большое, marcusmae,   за замечание. Твой метод самый эффективный!

В том-то и дело, что нет, и я в этом уже сознался выше 

Эффективность vs Универсальность - палка о двух концах.


Это сообщение отредактировал(а) marcusmae - 23.3.2008, 19:32