Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Общие вопросы по .NET и C# > Как сформировать массив,содержащий подмножество эл

Автор: sedoy 19.3.2008, 20:04

У меня есть два сортированных массива 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 есть какието функции для этого? Так как при большом колличестве элементов будет огромное колличество итераций и увеличется время выполнения.

Автор: axelprog 19.3.2008, 20:24

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

Автор: marcusmae 19.3.2008, 20:54

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

Автор: vponomarov 19.3.2008, 22:18

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

Автор: sedoy 19.3.2008, 22:41

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

Автор: marcusmae 19.3.2008, 22:42

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

Автор: sedoy 19.3.2008, 23:05

массив а: 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

Автор: axelprog 20.3.2008, 15:38

если массивы отсортированы, то можно сделать так:  Код List<int> c = new List<int>(); int j = 0; for( int i = 0; i< количество эл-тов в a; i++ ) {      if(a[i] != b[j])      {          c.Add(a[i]);      }       else       {            j++;       } } Примерно так.

Автор: marcusmae 21.3.2008, 01:41

Реализовал метод по своему описанию : Код         static int[] Exclude(int[] source, int[] filter, out int ifCount)         {             // Assume the source and filter arrays are SORTED in ASCENDING order.             int[] indices = new int[filter.Length + 2];             indices[0] = -1; indices[filter.Length + 1] = source.Length;             // Here to sum the comparisions count.             ifCount = 0;             int beginIndex = 0;             for (int filterIndex = 0; filterIndex < filter.Length; filterIndex++)             {                 int endIndex = source.Length - 1,                     centerIndex = endIndex;                 int diffrent = source[centerIndex] - filter[filterIndex];                 while (diffrent != 0)                 {                     int newCenterIndex = beginIndex + (endIndex - beginIndex) / 2;                     if (centerIndex == newCenterIndex)                         throw new ArgumentException("Filter value " +                             filter[filterIndex] + " not found.");                     centerIndex = newCenterIndex;                     diffrent = source[centerIndex] - filter[filterIndex];                     if (diffrent < 0)                         beginIndex = centerIndex;                     else                         endIndex = centerIndex;                     ifCount++;                 }                 beginIndex = centerIndex;                 indices[filterIndex + 1] = centerIndex;             }             // Eliminate elements with known indices.             int[] result = new int[source.Length - filter.Length];             int resultIndex = 0;             for (int indicesIndex = 0; indicesIndex < indices.Length - 1; indicesIndex++)                 for (int index = indices[indicesIndex] + 1; index < indices[indicesIndex + 1];                     index++)                 {                     result[resultIndex] = source[index]; resultIndex++;                 }             return result;         } Поскольку больше интересовала скорость поиска, не стал заморачиваться и аккумулировал в промежуточный массив индексы элементов, которые должны быть удалены (пропущены при перестроении). В идеале, это можно делать "на лету". Код         static void Main(string[] args)         {             int ifCount;             int[] a = new int[] { 2, 9, 27, 34, 47, 52, 77, 83 };             int[] b = new int[] { 52, 83 };             int[] c = Exclude(a, b, out ifCount);             for (int index = 0; index < c.Length; index++)                 Console.Write(c[index] + " ");             Console.WriteLine();             Console.WriteLine(ifCount * 2 + " (" + ifCount + ") comparisions used.");             Console.ReadKey();         } Код 2 9 27 34 47 77 4 (2) comparisons used. В данном случае метод использовал 4 сравнения, по два на итерацию цикла. В принципе, можно напрячься и сделать одно сранвнение на итерацию за счёт замены битовыми и арифметическими операциями. В любом случае, так как сравнивается одно и то же, Код                 while (diffrent != 0)                     ...                     if (diffrent < 0) то два сравнения можно считать почти за одно. Код         static void Main(string[] args)         {             int ifCount;             int[] a = new int[] { 1, 3, 4, 5, 7, 9, 11, 17 };             int[] b = new int[] { 3, 7, 17 };             int[] c = Exclude(a, b, out ifCount);             for (int index = 0; index < c.Length; index++)                 Console.Write(c[index] + " ");             Console.WriteLine();             Console.WriteLine(ifCount * 2 + " (" + ifCount + ") comparisions used.");             Console.ReadKey();         } Код 1 4 5 9 11 6 (3) comparisons used. Количество сравнений выглядит выгодно. Но пара тестов - это ерунда. Для отладки косяков метода был использован агрессивный тест, генерящий серию случайных массиов a и b (см. проект). Побочным результатом явилось то, что на таком псевдослучайном генераторе (System.Random) метод в среднем проигрывает по числу сравнений. Так что, если любите статистику, то можно попробовать поискать условия, при которых он работает эффективнее прямого сравнения. А может, это вообще никуда не годится  Всё же, полагаю, у него сложность = log2(f(a.Length, b.Length)), что не обязательно хуже, чем у прямого сравнения, сложность которого определяется индексом наибольшего из элементов b в массиве a. А на счёт List-ов - это конечно особенность, в чём-то даже преимущество .NET : любой вычислительный алгоритм, который неохота (некогда, ненужно, ...) писать эффективно можно реализовать стадесятью неэффективными способами, особо не думая. Не каждый язык+средства может предложить такую свободу.  В этом смысле .NET - рай, если требуется что-то сделать "на коленке"

Автор: sedoy 22.3.2008, 17:49

Спасибо всем за ответы, особенно-marcusmae. Я пытался понять твой, marcusmae, код реализации.  Хочу представить свой собственный вариант решения данной задачи нахождения отсутствующих элементов в массиве b (может смысл один и тот же?). В нем я попытался свести к минимуму поиск элементов. Я не тестировал его с помощью генерирования System.Random различных вариантов. Вот то, что получилось: Код static void Main(string[] args)         {             int count;             int[] a = new int[] { 1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 18, 20 };             int[] b = new int[] { 3, 11, 18 };             int[] c = retC(a,b,out count);             Console.WriteLine("The results by myMethod: ");             for (int ind = 0; ind < c.Length; ind++) Console.Write(c[ind] + " ");             Console.WriteLine();             Console.WriteLine(" {0} comparisions used.", count);             Console.WriteLine();             Console.ReadKey();         }         static int[] retC(int[] source, int[] filter, out int count)         {             count=0;             int[] result = new int[source.Length - filter.Length];             int indBeg = Array.IndexOf(source, filter[0]);             int indEnd = Array.IndexOf(source, filter[filter.Length - 1]);             if (indBeg > 0) for (int i = 0; i < indBeg; i++) {result[i] = source[i]; }             int jb = 1; int jr = indBeg; indBeg++;             while (indBeg < indEnd)             {                 count++;                 if (source[indBeg] != filter[jb]) { result[jr] = source[indBeg]; jr++; }                 else { jb++; }                 indBeg++;             }             for (int i = (indEnd + 1); i < source.Length; i++)             {                 result[jr] = source[i];                 jr++;             }             return result;         }

Автор: marcusmae 22.3.2008, 20:10

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

Автор: sedoy 23.3.2008, 17:21

Обновил. Так вроде должно быть оптимальнее : Код     static void Main(string[] args)         {             int count;             int[] a = new int[] { 1, 3, 4, 5, 6, 7,  8,  9,  11, 12, 14, 18, 20, 21 };             int[] b = new int[] { 1, 9, 11,  18,  21 };             int[] c = retC(a,b,out count);             Console.WriteLine("The results : ");             for (int ind = 0; ind < c.Length; ind++) Console.Write(c[ind] + " ");             Console.WriteLine();             Console.WriteLine(" {0} comparisions used.", count);             Console.WriteLine();             Console.ReadKey();         }         static int[] retC(int[] source, int[] filter, out int count)         {   count=0;             int[] result = new int[source.Length - filter.Length];             int indBeg = Array.IndexOf(source, filter[0]); count++;             int indEnd = Array.IndexOf(source, filter[filter.Length - 1]); count++;             if (indBeg > 0) for (int i = 0; i < indBeg; i++) {result[i] = source[i]; }             int ifrom = indBeg; int to; int fi = 1; int ri = indBeg;             while ( indEnd-(ifrom+1) > filter.Length-1-fi ) {                 to = Array.IndexOf(source, filter[fi]); count++;                 for (int i = (ifrom + 1); i < to; i++) { result[ri] = source[i]; ri++; }                 fi++; ifrom = to;             }             for (int i = (indEnd + 1); i < source.Length; i++) { result[ri] = source[i]; ri++; }             return result;         }

Автор: marcusmae 23.3.2008, 18:14

sedoy, глядя на count++ в Вашем коде, кажется, что Вы и не подозреваете, каким образом работает Array.IndexOf(...). Сложность Вашего метода по-прежнему выше, чем лучшая достижимая, которая Цитата(marcusmae @  21.3.2008,  01:41 ) определяется индексом наибольшего из элементов b в массиве a. , поскольку .IndexOf является перебором элементов массива, начиная с самого первого (а достаточно-то перебирать начиная с индекса предыдущего удаляемого!). Но даже если Вы откажетесь от начального определения inEnd (без которого вполне можно обойтись) и от использования IndexOf, то полученое всё ещё будет соответствовать Вашему же замечанию о том, что Цитата(sedoy @  19.3.2008,  20:04 ) при большом количестве элементов будет огромное количество итераций и увеличется время выполнения Далее улучшать в нём будет нечего (см. звёздочку), нужно по-другому организовывать перебор в зависимости от характерных позиций удаляемых элементов в исходной последовательности (что я и попытался сделать). По технике выбора элементов похоже на http://ru.wikipedia.org/wiki/Метод_бисекции. Можно ещё кучу всего напридумывать, только скорее сидя за алгоритмом на листке бумаги, чем ковыряя код на C#. По части теории Вам в помощь может пригодиться всемирно известный трёхтомник Дональда Кнута о алгоритмах и вычислительных методах : http://masterpc.alfaspace.net/books/CCScience/knut_part1-www.masterpc.alfaspace.net.djvu, http://masterpc.alfaspace.net/books/CCScience/knut_part2-www.masterpc.alfaspace.net.djvu, http://masterpc.alfaspace.net/books/CCScience/knut_part3-www.masterpc.alfaspace.net.djvu. Вы скажите, если я улетел в космос, помогая открыть банку с консервами   Казалось, что тот "оптимальный" метод, к которому Вы определённо делаете шаги в последних двух постах - не то, что Вы хотели делать вначале. (*) А получен будет следующий алгоритм : 1) Движемся в исходном массиве от первого элемента до первого элемента среди тех, которые нужно удалить 2) Движемся в исходном массиве от первого (i-ого) удаляемого до очередного удаляемого паралелльно перенося элементы исходного массива на единицу влево начиная от индекса первого (i-ого) удаляемого элемента (или не сдвигаем, а копируем на новое место - в результирующий массив). Сравниваем элементы исходного массива с очередным удаляемым. 3) Берём очередной i-ый удаляемый элемент из массива удаляемых и проделываем с ним шаг 2). Останавливаемся как только удаляемые элементы массива удаляемых закончились.

Автор: sedoy 23.3.2008, 19:23

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

Автор: marcusmae 23.3.2008, 19:29

Цитата(sedoy @  23.3.2008,  19:23 ) Твой метод самый эффективный! В том-то и дело, что нет, и я в этом уже сознался выше  Эффективность vs Универсальность - палка о двух концах.

Автор: Optimus 23.3.2008, 19:53

Цитата(marcusmae @  19.3.2008,  22:42 ) как методом деления отрезка пополам ищется существующее решение f(x) = 0 на отрезке. Это возможно, поскольку массив по условию отсортирован. Как я понял, это бинарный поиск, тогда можно использовать List<int>, у него есть метод BinarySearch().

Автор: marcusmae 23.3.2008, 20:40

Цитата(Optimus @  23.3.2008,  19:53 ) Как я понял, это бинарный поиск, тогда можно использовать List<int>, у него есть метод BinarySearch(). Да, но не совсем. Во-первых, массив, а не список, а во-вторых поиск не во всём массиве, а в постоянно сужающемся подмножестве его элементов.

Автор: Optimus 23.3.2008, 21:05

Цитата(marcusmae @  23.3.2008,  20:40 ) поиск не во всём массиве Код public int BinarySearch (     int index,     int count,     T item,     IComparer<T> comparer) http://algolist.manual.ru/search/bin_search.php

Автор: marcusmae 23.3.2008, 21:21

Optimus, Вы правы - http://msdn2.microsoft.com/en-us/library/2cy9f6wb(VS.80).aspx (не List<int>)

Автор: Optimus 23.3.2008, 21:27

Да, так долго работал с List<> что забыл про Array

Автор: sedoy 24.3.2008, 10:56

Если я правильно понял, то так должна соблюдаться идея marcusmae (изложенная в представленной им ранее реаализации): Код static int[] retC(int[] source, int[] filter, out int count)         {   count=0;             int[] result = new int[source.Length - filter.Length];             int indBeg = Array.BinarySearch(source, filter[0]); count++;             int indEnd = Array.BinarySearch(source, filter[filter.Length - 1]); count++;             if (indBeg > 0) for (int i = 0; i < indBeg; i++) {result[i] = source[i]; }             int ifrom = indBeg; int to; int fi = 1; int ri = indBeg;             while ( indEnd-(ifrom+1) > filter.Length-1-fi ) {                 to = Array.BinarySearch(source, filter[fi]); count++;                 for (int i = (ifrom + 1); i < to; i++) { result[ri] = source[i]; ri++; }                 fi++; ifrom = to;             }             for (int i = (indEnd + 1); i < source.Length; i++) { result[ri] = source[i]; ri++; }             return result;         }  если это так, то может кому тоже пригодиться

Автор: marcusmae 24.3.2008, 13:35

я извиняюсь за занудство, но НЕТ, не соблюдается  Читайте внимательнее предыдущие посты.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)