Сравните членов ICollection с самим собой - PullRequest
Новая
       15

Сравните членов ICollection с самим собой

2 голосов
/ 17 января 2012

Есть ли самый дешевый способ сравнить ICollection с самим собой.

Вот мой код: 

        public IEnumerable<Pet> speciesChecker()
        {
            foreach (Pet pet in _pets)
            {
                bool wantedSpecies = true;
                foreach (Pet pet2 in _pets)
                {
                    if (pet2 != pet && pet.Species == pet2.Species)
                    {
                        wantedSpecies = false;
                        break;
                    }
                }
                if (wantedSpecies) yield return pet;
            }
        }

Какова временная сложность моего кода, все, что я знаю, это то, что он меньше O (N ^ 2), и если я уберу 'break' из внутреннего цикла foreach, временная сложность будет O (N ^ 2). Пожалуйста, поправьте меня, если я ошибаюсь.

Ответы [ 4 ]

2 голосов
/ 17 января 2012

Вот мое мнение: 

var q = list.GroupBy (l => l.Species)
          .Where (l => l.ElementAtOrDefault(1) == null)
          .Select (l => l.Key)

GroupBy будет использовать HashSet для внутреннего использования, поэтому O (N)
ElementAtOrDefault(1) потребуется переместить перечислитель только на один шаг, так что не быть O (n)

1 голос
/ 17 января 2012

Вы также можете использовать что-то вроде следующего, которое также должно быть O (N): 

public IEnumerable<Pet> speciesChecker ()
{
    _pets.GroupBy (p => p.Species)
         .Select (g => new List<Pet> (g))
         .Where (l => l.Count == 1)
         .SelectMany (l => l);
}

Дополнительные Select (g => new List<Pet> (g)) могут быть излишними, но я считаю, что это поможет избежать повторения всей логики группировки во второй раз, что, как я полагаю, приведет к O (N ^ 2).

Редактировать: Хороший комментарий от Магнуса о конструкторе List, работающем в O (n), побеждающем цель ...

Как насчет: 

public IEnumerable<Pet> speciesChecker ()
{
    var groups = _pets.GroupBy (p => p.Species);

    foreach (var grp in _pets.GroupBy (p => p.Species))
    using (var e = grp.GetEnumerator ()) {
        if (!e.MoveNext ())
            continue;

        var first = e.Current;

        if (e.MoveNext ())
            continue;

        yield return first;
    }
}

I думаю, это оптимизировано настолько, насколько вы можете, и будет работать в O (n). Мы также избегаем использования метода расширения IEnumerable<T>.Any () или IEnumerable<T>.Count ().

Мысли

1 голос
/ 17 января 2012

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

    public IEnumerable<Pet> speciesChecker()
    {
        var species = new Dictionary<Species, List<Pet>>();
        foreach (Pet pet in _pets)
        {
            // create the list if it doesn't exist
            if (!species.ContainsKey(pet.Species))
                species[pet.Species] = new List<Pet>();
            species[pet.Species].Add(pet);
        }

        // foreach species, if there is only one pet of that species, then return it
        foreach (var speciesPets in species.Values)
        {
            if (speciesPets.Count() == 1)
                yield return speciesPets.First();
        }

        yield break;
    }
0 голосов
/ 17 января 2012

let n - длина _pets collection

количество необходимых шагов с перерывом: 

1+2+3+...+n = n*(n+1)/2 =n^2/2 + n/2 = O(n^2) (for each pet in _pets);

Существует два простых правила вычисления O из вики:

  1. Если f (x) является суммой нескольких слагаемых, один с наибольшим темп роста сохраняется, а все остальные опущены.

  2. Если f (x) является произведением нескольких факторов, любые константы (термины в продукт, не зависящий от х), опущен.

количество необходимых шагов без перерыва: 

n+n+n+...+n = n^2 = O(n^2)
...