Поиск дубликатов в списке списка

Question

Простая ситуация.У меня есть список списков, почти как таблица, и я пытаюсь выяснить, дублируется ли какой-либо из списков.

Пример:

List<List<int>> list = new List<List<int>>(){
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
  new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
};

Я хотел бы знать, что тамВсего 4 элемента, 2 из которых являются дубликатами.Я думал о том, чтобы сделать что-то вроде контрольной суммы SQL , но я не знал, есть ли лучший / более простой способ.

Я забочусь о производительности, и я забочусь о заказе.

Дополнительная информация, которая может помочь

• Элементы, включенные в этот список, никогда не будут удалены
• Не привязан к какой-либо конкретной коллекции.
• Не заботьтесь о сигнатуре функции
• Их тип не ограничен int

Answer 1

Давайте попробуем добиться наилучших результатов.если n - количество списков, а m - длина списков, то мы можем получить O (n m + n logn + n) плюс некоторую вероятность того, что хеш-коды будут равны для разных списков.

Основные шаги:

1. Рассчитать хэш-коды *
2. Сортировать их
3. Перейти по списку, чтобы найти дубликаты

* это важношаг.для простоты вы можете вычислить хеш как = ... ^ (список [i] << i) ^ (список [i + 1] << (i + 1)) </p>

Редактировать для тех людей, которые думают, что PLINQ может улучшить ситуацию, но не хороший алгоритм.Здесь также можно добавить PLINQ, потому что все шаги легко распараллеливаются.

Мой код:

static public void Main()
{
    List<List<int>> list = new List<List<int>>(){
      new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
      new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
      new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
      new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
    };
    var hashList = list.Select((l, ind) =>
    {
        uint hash = 0;
        for (int i = 0; i < l.Count; i++)
        {
            uint el = (uint)l[i];
            hash ^= (el << i) | (el >> (32 - i));
        }
        return new {hash, ind};
    }).OrderBy(l => l.hash).ToList();
    //hashList.Sort();
    uint prevHash = hashList[0].hash;
    int firstInd = 0;            
    for (int i = 1; i <= hashList.Count; i++)
    {
        if (i == hashList.Count || hashList[i].hash != prevHash)
        {
            for (int n = firstInd; n < i; n++)
                for (int m = n + 1; m < i; m++)
                {
                    List<int> x = list[hashList[n].ind];
                    List<int> y = list[hashList[m].ind];
                    if (x.Count == y.Count && x.SequenceEqual(y))
                        Console.WriteLine("Dupes: {0} and {1}", hashList[n].ind, hashList[m].ind);
                }                    
        }
        if (i == hashList.Count)
            break;
        if (hashList[i].hash != prevHash)
        {
            firstInd = i;
            prevHash = hashList[i].hash;
        }
    }
}

Answer 2

Если вы не занимаетесь чем-то серьезным, возможно, вам подойдет следующий простой код:

var lists = new List<List<int>>()
{
   new List<int>() {0 ,1, 2, 3, 4, 5, 6 },
   new List<int>() {0 ,1, 2, 3, 4, 5, 6 },
   new List<int>() {0 ,1, 4, 2, 4, 5, 6 },
   new List<int>() {0 ,3, 2, 5, 1, 6, 4 }
};

var duplicates = from list in lists
                 where lists.Except(new[] { list }).Any(l => l.SequenceEqual(list))
                 select list;

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

(Кроме того, благодаря Awesomeness из LINQ®, добавив вызов .AsParallel () к приведенному выше коду, алгоритм будет работать на нескольких ядрах, и, следовательно, работать потенциально быстрее, чем сложные, отрегулированные вручную решения, упомянутые в этом нить.)

Answer 3

Нечто подобное даст вам правильные результаты:

List<List<int>> list = new List<List<int>>(){
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
  new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
};

list.ToLookup(l => String.Join(",", l.Select(i => i.ToString()).ToArray()))
    .Where(lk => lk.Count() > 1)
    .SelectMany(group => group);

Answer 4

Вам придется проходить по каждому индексу каждого списка хотя бы один раз, но вы можете потенциально ускорить процесс, создав собственную хеш-таблицу, чтобы вы могли быстро отклонять неповторяющиеся списки, не выполняя сравнения пункт.

Алгоритм:

Create a custom hashtable (dictionary: hash -> list of lists)
For each list
  Take a hash of the list (one that takes order into account)
  Search in hashtable
  If you find matches for the hash
    For each list in the hash entry, re-compare the tables
      If you find a duplicate, return true
  Else if you don't find matches for the hash
    Create a temp list
    Append the current list to our temp list
    Add the temp list to the dictionary as a new hash entry
You didn't find any duplicates, so return false

Если у вас достаточно сильный алгоритм хеширования для ваших входных данных, вам, возможно, даже не придется выполнять субсравнения, так как не будет никаких коллизий хешей.

У меня есть пример кода. Недостающие биты:

• Оптимизация, так что мы делаем поиск по словарю только один раз для списка (для поиска и вставки). Возможно, для этого нужно создать собственный класс Dictionary / Hash Table?
• Лучший алгоритм хеширования, который вы найдете, профилировав их по вашим данным

Вот код:

public bool ContainsDuplicate(List<List<int>> input)
{
    var encounteredLists = new Dictionary<int, List<EnumerableWrapper>>();

    foreach (List<int> currentList in input)
    {
        var currentListWrapper = new EnumerableWrapper(currentList);
        int hash = currentListWrapper.GetHashCode();

        if (encounteredLists.ContainsKey(hash))
        {
            foreach (EnumerableWrapper currentEncounteredEntry in encounteredLists[hash])
            {
                if (currentListWrapper.Equals(currentEncounteredEntry))
                    return true;
            }
        }
        else
        {
            var newEntry = new List<EnumerableWrapper>();
            newEntry.Add(currentListWrapper);
            encounteredLists[hash] = newEntry;
        }
    }

    return false;
}

sealed class EnumerableWrapper
{
    public EnumerableWrapper(IEnumerable<int> list)
    {
        if (list == null)
            throw new ArgumentNullException("list");
        this.List = list;
    }

    public IEnumerable<int> List { get; private set; }

    public override bool Equals(object obj)
    {
        bool result = false;

        var other = obj as EnumerableWrapper;
        if (other != null)
            result = Enumerable.SequenceEqual(this.List, other.List);

        return result;
    }

    public override int GetHashCode()
    {
        // Todo: Implement your own hashing algorithm here
        var sb = new StringBuilder();
        foreach (int value in List)
            sb.Append(value.ToString());
        return sb.ToString().GetHashCode();
    }
}

Answer 5

Здесь уже есть ряд хороших решений, но я считаю, что это будет стабильно работать быстрее , если не будет структуры данных, о которой вы еще не сказали нам.

• Создайте карту из целочисленного ключа для списка и карту от ключа до List<List<int>>
• Для каждого List<int> вычислить хеш, используя некоторую простую функцию, такую ​​как (...((x0)*a + x1)*a + ...)*a + xN), которую вы можете вычислить рекурсивно; a должно быть чем-то вроде 1367130559 (то есть некоторого большого простого числа, которое случайно не близко к любой интересной степени 2).
• Добавьте хеш и список, из которого он получен, в виде пары ключ-значение, если он не существует. Если он существует, посмотрите на второй карте. Если вторая карта имеет этот ключ, добавьте новый List<int> в список накоплений. Если нет, возьмите List<int>, который вы посмотрели с первой карты, и List<int>, который вы тестировали, и добавьте новую запись на вторую карту, содержащую список этих двух элементов.
• Повторяйте, пока не пройдете весь первый список. Теперь у вас есть хеш-карта со списком потенциальных коллизий (вторая карта) и хеш-карта со списком ключей (первая карта).
• Итерация по второй карте. Для каждой записи возьмите List<List<int>> и отсортируйте ее лексикографически. Теперь просто проведите сравнение на равенство, чтобы посчитать количество различных блоков.
• Ваше общее количество предметов равно длине вашего исходного списка.
• Количество ваших отдельных элементов равно размеру вашего первого хеш-карты плюс сумма (количество блоков - 1) для каждой записи во втором хэш-карте.
• Ваше количество дублирующихся предметов - это разница между этими двумя числами (и вы можете узнать все виды других вещей, если хотите).

Если у вас есть N неповторяющихся элементов и M записей, которые являются дубликатами из набора из K элементов, то вам потребуется O (N + M + 2K) для создания начальных хеш-карт, в худшем случае O (M log M), чтобы выполнить сортировку (и, вероятно, больше похоже на O (M log (M / K))), и O (M), чтобы выполнить окончательный тест на равенство.

Answer 6

Как насчет того, чтобы написать свой собственный список сравнения:

class ListComparer:IEqualityComparer<List<int>>
{
     public bool Equals(List<int> x, List<int> y)
     {
        if(x.Count != y.Count)
          return false;

        for(int i = 0; i < x.Count; i++)
          if(x[i] != y[i])
             return false;

       return true;
     }

     public int GetHashCode(List<int> obj)
     {
        return base.GetHashCode();
     }
}

, а затем просто:

var nonDuplicatedList = list.Distinct(new ListComparer());
var distinctCount = nonDuplicatedList.Count();

Answer 7

Вы также можете попробовать вероятностные алгоритмы, если дубликаты либо очень редки, либо очень распространены. например фильтр Блума

Answer 8

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

тогда у вас будет список {123456, 123456, 142456, 325164}

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

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

for(int i = 0; i< list.length; i++)
{
    List<int> tempList = list[i];
    int temp = 0;
    for(int j = tempList.length - 1;i > = 0; j--)
    {
        temp = temp * 10 + tempList[j];
    }
    combinded.add(temp);
}

for(int i =0; i< combined.length; i++)
{
    for(int j = i; j < combined.length; j++)
    {
        if(combined[i] == combined[j])
        {
            return true;
        }
    }
}
return false;

Answer 9

Вот потенциальная идея (предполагается, что значения являются числовыми):

Реализуйте компаратор, который умножает каждый элемент каждой коллекции на его индекс, а затем суммирует все:

Value:    0  5  8  3  2  0  5  3  5  1
Index:    1  2  3  4  5  6  7  8  9  10
Multiple: 0  10 24 12 10 0  35 24 45 10

Контрольная сумма члена: 170

Итак, вся «строка» имеет номер, который меняется в зависимости от членов и порядка.Быстро вычислить и сравнить.

Answer 10

Извлечение C # 3.0: необходимо вернуть дубликаты из списка. <> показывает, как вернуть дубликаты из списка.

Пример с этой страницы:

var duplicates = from car in cars
             group car by car.Color into grouped
             from car in grouped.Skip(1)
             select car;