Как в С# самым быстрым способом проверить, содержатся ли все элементы массива Х среди элементов массива Y? Может есть какой способ получше, чем поэлементная проверка?

Здравствуйте, Andrudis, Вы писали:

A>Как в С# самым быстрым способом проверить, содержатся ли все элементы массива Х среди элементов массива Y? Может есть какой способ получше, чем поэлементная проверка?

Если массивы отсортированны, то есть.
Алгоритм приблизительно следующий (писался от руки):

object[] x; // Массив X, отсортированный по возрастанию
object[] y; // Массив Y, отсортированный по возрастанию
int xIndex = 0; // Указатель на элемент массива X
int yIndex = 0; // Указатель на элемент массива Y
int counter = 0; // Счетчик совпадений элементов
while (xIndex < x.Count && yIndex < y.Count) // Пока не кончится хотя бы один из массивов
{
    object currentX = x[xIndex]; // Текущий эламент массива X
    object currentY = y[yIndex]; // Текущий эламент массива Y
    if (currentX == currentY) // Элементы совпадают
    {
        counter++; // Увеличиваем счетчик совпадений
        xIndex++; // Переходим к следующему элементу массива X
    }
    else if (currentX > currentY) // Переходим к следующему элементу в том массиве, в котором текущий элемент меньше
    {
        yIndex++;
    }
    else
    {
        xIndex++;
    }
}
if (counter == x.Length)
{
    bingo(); // Массив X полностью содержится в массиве Y
}

Если массивы не отсортированные, может получиться более эффективно сначала их отсортировать. Не знаю считать издержки надо

мне этот способ не кажется лучшим изза того что в общем случае придется повозится с эквивалентностью объектов.. == в смысле

---

данное сообщение получено с www.gotdotnet.ru
ссылка на оригинальное сообщение

Здравствуйте, dead7man, Вы писали:


D>Если массивы не отсортированные, может получиться более эффективно сначала их отсортировать. Не знаю считать издержки надо

Да нет, вопрос был о наличии чего-то вроде Contans:

string [] arr1;
string [] arr2;
ArrayList alist1 = new ArrayList(arr1);
ArrayList alist2 = new ArrayList(arr2);
if ( alist1.Contains(alist2) == true )
      {...}

Здравствуйте, Аноним, Вы писали:

А>мне этот способ не кажется лучшим изза того что в общем случае придется повозится с эквивалентностью объектов.. == в смысле

А>

---

данное сообщение получено с www.gotdotnet.ru
А>ссылка на оригинальное сообщение

Считаем, что все объекты одного известного типа: string.

Здравствуйте, Karn, Вы писали:

K>мне этот способ не кажется лучшим изза того что в общем случае придется повозится с эквивалентностью объектов.. == в смысле

Если элементы уже не обеспечивают возможность сравнения (а основные типы обеспечивают) — да, придется реализовывать у классов элементов интерфейс IComparable.
Но тут вопрос производительности. Или мы тратим время (должен заметить, мало времени, очень мало) на реализацию IComparable в дизайн-тайм, или тратим время в ран-тайм.
Опять же, не факт, что сортировка + приведенный метод дадут выигрыш по сравнению с поэлементным сравнением (хотя, думаю, выигрыш будет), я же написал — считать надо. К тому же, массивы, возможно, уже отсортированны.

Вообщем отмаз не катит

Здравствуйте, Andrudis, Вы писали:

A>Здравствуйте, dead7man, Вы писали:


D>>Если массивы не отсортированные, может получиться более эффективно сначала их отсортировать. Не знаю считать издержки надо

A>Да нет, вопрос был о наличии чего-то вроде Contans:

A>

A>string [] arr1;
A>string [] arr2;
A>ArrayList alist1 = new ArrayList(arr1);
A>ArrayList alist2 = new ArrayList(arr2);
A>if ( alist1.Contains(alist2) == true )
A>      {...}
A>

Не, оригинальный вопрос звучал "...содержатся ли все элементы массива Х среди элементов массива Y?".
Если нужено проверить содержиться ли один объект в массиве — стандартные механизмы оптимизации поиска: хеширование, построение индекса, двоичный поиск (опять же в отсортированном массиве).

Здравствуйте, dead7man, Вы писали:

D>Здравствуйте, Andrudis, Вы писали:

A>>Здравствуйте, dead7man, Вы писали:


D>>>Если массивы не отсортированные, может получиться более эффективно сначала их отсортировать. Не знаю считать издержки надо

A>>Да нет, вопрос был о наличии чего-то вроде Contans:

A>>

A>>string [] arr1;
A>>string [] arr2;
A>>ArrayList alist1 = new ArrayList(arr1);
A>>ArrayList alist2 = new ArrayList(arr2);
A>>if ( alist1.Contains(alist2) == true )
A>>      {...}
A>>

D>Не, оригинальный вопрос звучал "...содержатся ли все элементы массива Х среди элементов массива Y?".
D>Если нужено проверить содержиться ли один объект в массиве — стандартные механизмы оптимизации поиска: хеширование, построение индекса, двоичный поиск (опять же в отсортированном массиве).

Совсем недавно на интервью у меня была такая задача. Правда там была существенная оговорка, что зарание известно кол-во ( и оно не слишком большое ) _вариатнов_ элементов массива, допустим, что около 100 разных строк.
Тогда заводим отдельный массив флагов присутствует-отсутствует, цепляемся на Collection(Dictionary)Base.OnInsertComplete и выставляем соответствующий флаг в первом массиве.
Теперь если нам нужно проверить _наличие_ какого-либо элемента в нашем массиве( коллекции ), просто берем значение соотв элемента массива флагов.
Для быстрого поиска строковых элементов можно использовать HashCode.

Этот метод больше всего подходит именно тогда, когда вариантов не много, а экземпляров наоборот очень много (например база данных, где очень много записей, но нас интересуюют лишь наборы штатов сша). В таком случае сортировка или поддержание массива в отсортированном виде потребует больших расходов. И лучше применить метод дополнительного массива флагов.