C # Linq to Objects / Синтаксис и Эффективный поиск, если члены коллекции существуют в другой коллекции вложенных коллекций. - PullRequest
Новая
       12

C # Linq to Objects / Синтаксис и Эффективный поиск, если члены коллекции существуют в другой коллекции вложенных коллекций.

2 голосов
/ 23 сентября 2011

У меня есть первая коллекция чисел: (1,3,5,6,23)

и вторая коллекция коллекций от 1 до n целых чисел 

(3),    (6,1),    (1,3,5,23,6,14,67),    (2,3)

Итак, во второй коллекции есть элементы a, b, c и d, которые сами являются коллекцией целых чисел 

a=(3), b=(6,1), c=(1,3,5,23,6,14,67), d=(2,3)

Так что это может быть в основном зубчатый массив)

Как выполнить Linq для запросов к объектам, используя как синтаксис метода расширения, так и синтаксис выражения запроса выяснить, какую комбинацию чисел в первой коллекции можно найти в коллекции a, b, c или d или нигде. Другими словами, какие номера из второй коллекции содержатся в первой коллекции.

В1: Я хотел бы видеть, что a=(3), b=(6,1) был найден, поскольку члены каждой коллекции a и b c существуют в первой коллекции.

Q2: Я хотел бы видеть противоположный случай, когда мы начинаем со второй коллекции и пытаемся выяснить, принадлежат ли ее члены под коллекции первой коллекции.

Я хотел бы знать плюсы и минусы обоих подходов. На самом деле я буду иметь дело с тысячами коллекций, содержащих до 10 номеров в каждой.

Ответы [ 2 ]

1 голос
/ 23 сентября 2011

Вот, пожалуйста.Попробуйте следующее: 

var xs = new [] { 1, 3, 5, 6, 23, };
var yss = new []
{
    new [] { 3, },
    new [] { 6, 1, },
    new [] { 1, 3, 5, 23, 6, 14, 67, },
    new [] { 2, 3, },
};

Сначала я отвечу на ваш второй вопрос: 

var q2 =
    from ys in yss
    where !ys.Except(xs).Any()
    select ys;

var q2b = yss.Where(ys => !ys.Except(xs).Any());

Эти два запроса идентичны - за исключением одного в LINQ и другого в методе расширениясинтаксис.Компилятор сгенерирует один и тот же код для обоих.

Вопрос первый - кошмар - гораздо сложнее сделать. 

var q1 =
    from z in yss.Zip(
        xs.Aggregate(
            yss.AsEnumerable(),
            (_yss, x) => (
                from ys in _yss
                select ys.Except(new [] { x }).ToArray())),
        (ys, _ys) => new { ys, _ys })
    where !z._ys.Any()
    select z.ys;

var q1b =
    yss.Zip(
        xs.Aggregate(
            yss.AsEnumerable(),
            (_yss, x) => _yss
                .Select(ys =>
                    ys.Except(new [] { x }).ToArray())),
        (ys, _ys) => new { ys, _ys })
    .Where(z => !z._ys.Any())
    .Select(z => z.ys);

Опять и в LINQ, и в синтаксисе метода расширения, и оба скомпилированы в один и тот жеcode.

Я выполнил несколько тестов производительности, и запросы "q2" выполнялись более чем в 10 раз быстрее, чем запросы "q1".

В одном тесте у меня было xs с 61 отдельным элементом, yss с 100 000 различнозначных вложенных коллекций с общим количеством 956 512 элементов, и запросы "q1" выполнялись за 5 354,1 миллисекунды, а "q2" выполнялся за 302,1 миллисекунды - коэффициент 17,7x.

Однако уменьшите это значение доxs из 10 & yss с 10 000 и 95 641, тогда результаты составили 115,3 и 7,4 миллисекунды соответственно.Любой подход, вероятно, будет достаточно быстрым.

1 голос
/ 23 сентября 2011

Что-то вроде этого? 

int[] firstSet = new[] { 1,3,5,6,23 };
int[][] secondSet = new[] 
{
    new [] { 3 },
    new [] { 6, 1 },
    new [] { 1,3,5,23,6,14,67 },
    new [] { 2, 3}
};

// only subsets where each member matces a member of the first set
var matchinSubSets = from subset in secondSet
                     where subset.All(x => firstSet.Contains(x))
                     select subset;

Что касается производительности, не стоит сильно беспокоиться об этом, если вы будете сопоставлять только тысячи записей, это будет сделано для вычисления, прежде чем вы это узнаете

...