Как я могу быстро сказать, содержит ли список только дубликаты?

Question

Есть несколько связанных вопросов, но я ищу решение, специфичное для моего случая. Существует множество (обычно) 14 целых чисел. Как я могу быстро сказать, появляется ли каждый int ровно дважды (т.е. есть 7 пары)? Диапазон значений от 1 до 35. Основным аспектом здесь является производительность.

Для справки, это мое текущее решение. Он был написан, чтобы напоминать спецификацию как можно более близко и без учета работы, поэтому я уверен, что это может быть значительно улучшить:

var pairs = Array
    .GroupBy (x => x)
    .Where (x => x.Count () == 2)
    .Select (x => x.ToList ())
    .ToList ();
IsSevenPairs = pairs.Count == 7;

Использование LINQ необязательно. Мне все равно, как, пока это быстро :)

Редактировать: Существует особый случай, когда INT появляется 2n раза с n> 1. В этом случае чек должен потерпеть неудачу, IE должно быть 7 различных пар.

РЕДАКТИРОВАТЬ: РезультатЯ проверил решения ANI и JON с крошечными модификациями и обнаружил во время нескольких тестов-прогонов в приложении Target, что ANI имеет примерно дважды пропускную способность Джона на моей машине (немного дуэта Core 2 на Win7-64). Создание массива INT уже занимает около того, как и соответствующие проверки, поэтому я доволен результатом. Спасибо всем!

Answer 1

Очевидно, LINQ не предоставит оптимальный Решение здесь, хотя я бы улучшил ваше текущее решение LINQ до:

// checks if sequence consists of items repeated exactly once
bool isSingleDupSeq = mySeq.GroupBy(num => num)
                           .All(group => group.Count() == 2);

// checks if every item comes with atleast 1 duplicate
bool isDupSeq = mySeq.GroupBy(num => num)
                     .All(group => group.Count() != 1);

Для конкретного случая, который вы упоминаете (0 - 31), вот более быстрое решение на основе массива. Он не очень хорошо масштабируется, когда диапазон возможных чисел велик (в этом случае используйте решение хеширования).

// elements inited to zero because default(int) == 0
var timesSeenByNum = new int[32];

foreach (int num in myArray)
{
    if (++timesSeenByNum[num] == 3)
    {
        //quick-reject: number is seen thrice
        return false;
    }
}

foreach (int timesSeen in timesSeenByNum)
{
    if (timesSeen == 1)
    {
        // only rejection case not caught so far is
        // if a number is seen exactly once
        return false;
    }
}

// all good, a number is seen exactly twice or never
return true;   

РЕДАКТИРОВАТЬ: Исправлены ошибки, как указано Джоном Скитом. Я должен также отметить, что его алго умнее и вероятно Быстрее.

Answer 2

Ну, учитывая ваши точные требования, мы можем быть немного умнее. Что-то вроде этого:

public bool CheckForPairs(int[] array)
{
    // Early out for odd arrays.
    // Using "& 1" is microscopically faster than "% 2" :)
    if ((array.Length & 1) == 1)
    {
        return false;
    }

    int[] counts = new int[32];
    int singleCounts = 0;
    foreach (int item in array)
    {
        int incrementedCount = ++counts[item];
        // TODO: Benchmark to see if a switch is actually the best approach here
        switch (incrementedCount)
        {
            case 1:
                singleCounts++;
                break;
            case 2:
                singleCounts--;
                break;
            case 3:
                return false;
            default:
                throw new InvalidOperationException("Shouldn't happen");
        }
    }
    return singleCounts == 0;
}

По сути, это отслеживает, сколько у вас непарных значений, и имеет «рано», если он когда -либо найдет три в своем роде.

(Я не знаю, будет ли это быстрее или медленнее, чем подход Ани к увеличению, а затем проверять непревзойденные пар.)

Answer 3

Я бы создал массив из 32 целочисленных элементов, инициализированных до нуля. Назовем это "Билли".

Для каждого элемента входного массива я бы увеличил Билли [элемент] 1.

В конце, проверьте, содержит ли Билли только 0 или 2.

Answer 4

Почти наверняка излишне, когда у вас есть только 14 пар и только 32 возможных ценностей, но в общем случае вы можете сделать что-то вроде этого:

bool onlyPairs = yourArray.ContainsOnlyPairs();

// ...

public static class EnumerableExtensions
{
    public static bool ContainsOnlyPairs<T>(this IEnumerable<T> source)
    {
        var dict = new Dictionary<T, int>();

        foreach (T item in source)
        {
            int count;
            dict.TryGetValue(item, out count);

            if (count > 1)
                return false;

            dict[item] = count + 1;
        }

        return dict.All(kvp => kvp.Value == 2);
    }
}

Answer 5

Если диапазон предметов составляет 0-31, вы можете хранить 32 однобитных флажков в UINT32. Я бы посоветовал взять каждый элемент и вычислить Маску = (1 SHL -элемент) и посмотреть, что произойдет, если вы попробуете 'или', 'xor'ing, или добавление значений маски. Посмотрите на результаты для действительных и недействительных случаев. Чтобы избежать переполнения, вы можете использовать UINT64 для добавления (поскольку UINT32 может переполняться, если есть два 31, или четыре 30 -х, или восемь 29).

Answer 6

Я предполагаю, что (никогда не измерял скорость). Этот кодамнипет может дать вам новую точку зрения:

int[] array = { 0, 1, 2, 3, 1, 1, 3, 5, 1, 2, 7, 31 }; // this is your sample array

uint[] powOf2 = {
    1, 2, 4, 8,
    16, 32, 64, 128,
    256, 512, 1024, 2048,
    4096, 8192, 16384, 32768,
    65536, 131072, 262144, 524288,
    1048576, 2097152, 4194304, 8388608,
    16777216, 33554432, 67108864, 134217728,
    268435456, 536870912, 1073741824, 2147483648
               };

uint now;
uint once = 0;
uint twice = 0;
uint more = 0;

for (int i = 0; i < array.Length; i++)
{
    now = powOf2[array[i]];

    more |= twice & now;
    twice ^= (once & now) & ~more;
    twice ^= more;
    once |= now;
}

Вы можете иметь удвоенные значения в переменной «дважды»; Конечно, это работает только для значений менее 32;