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

Question

Есть ли самый дешевый способ сравнить 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), Пожалуйста, поправьте меня, если я ошибаюсь.

Answer 1

Позволять 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) является произведением нескольких факторов, любые константы (члены в произведении, которые не зависят от x) опущены.

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

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

Answer 2

Вот мой взгляд на это:

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)

Answer 3

Вы также можете использовать что-то вроде следующего, которое также должно быть 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;
    }
}

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

Мысли?

Answer 4

Я думаю, что этот код делает то же самое. В этом случае это алгоритм 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;
    }