БЛОГ НА HUSL


Фильтрация списка объектов по уникальным значениям

Автор вопроса: Nikitos Kiwi

Все привет, столкнулся с проблемой фильтрации списка по уникальным значениям. Есть структура

public struct MyStruct
{
    public string Name;
    public string City;
    public string Division;
}

Нужно вытащить из List<MyStruct> уникальные значения. Причем уникальным считается значение, где хотя бы одно поле из трех чем-то отличается


Источник

Ответы (2 шт):

Автор решения: rotabor
  1. Для заданного условия уникальности нужно соединить строки структуры в одну, и использовать её для проверки уникальности всей структуры.
  2. Уникальные значения выявить просто. Нужно сделать массив повторов (bool) такого же размера. Пройтись по всему списку циклом. В начале цикла проверить признак повтора, если он ложь, то вывести элемент как уникальный и пройтись вложенным циклом по оставшимся до конца элементам списка: сравнить текущий элемент из вневнего цикла с текущим из вложенного, если равны, то поставить признак повтора для текущего вложенного в истину.

Сделал тестовую программу:

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
namespace BankRobbery{
    public struct MyStruct{
        public string Name;
        public string City;
        public string Division;
        public MyStruct(string[] n, string[] c, string[] d, Random r){
            Name = n[r.Next(n.Length)];
            City = c[r.Next(c.Length)];
            Division = d[r.Next(d.Length)];
        }
        public static bool operator == (MyStruct ms1, MyStruct ms2){
            return String.Concat(ms1.Name, ms1. City, ms1.Division) == String.Concat(ms2.Name, ms2. City, ms2.Division);
        }
        public static bool operator != (MyStruct ms1, MyStruct ms2){
            return String.Concat(ms1.Name, ms1. City, ms1.Division) != String.Concat(ms2.Name, ms2. City, ms2.Division);
        }
        public override int GetHashCode() {return base.GetHashCode();}
        public override bool Equals(object ms) {return base.Equals((MyStruct)ms);}
    }
    class ClippyNMerlin{
        static void Main(string[] args){
            var N = Convert.ToInt32(args[0]);
            var Names = File.ReadAllLines("Names.txt"); // 64 entries
            var Cities = File.ReadAllLines("Cities.txt"); // 39 entries
            var Divisions = File.ReadAllLines("Divisions.txt"); // 7 entries
            var Rand = new Random();
            var MyList = new List<MyStruct>();
            for (int i = 0; i < N; i++) MyList.Add(new MyStruct(Names, Cities, Divisions, Rand));
            var watch = new System.Diagnostics.Stopwatch();
            watch.Start(); var MyResult = MyList.Distinct().Count(); watch.Stop();
            Console.WriteLine("Count by List.Distinct {0}", MyResult);
            Console.WriteLine("Elapsed time {0}", watch.ElapsedMilliseconds / 1000.0);
            var MyArray = MyList.ToArray();
            watch.Reset(); watch.Start();
            var r = new bool[N]; MyResult = 0;
            for (int j = 0; j < N; j++)
                if (!r[j]) {MyResult++; for (int k = j + 1; k < N; k++) if (!r[k]) r[k] = MyArray[j].Equals(MyArray[k]);}  
            watch.Stop();
            Console.WriteLine("Count by Equals {0}", MyResult);
            Console.WriteLine("Elapsed time {0}", watch.ElapsedMilliseconds / 1000.0);
            watch.Reset(); watch.Start();
            r = new bool[N]; MyResult = 0;
            for (int j = 0; j < N; j++)
                if (!r[j]) {MyResult++; for (int k = j + 1; k < N; k++) if (!r[k]) r[k] = MyArray[j] == MyArray[k];}  
            watch.Stop();
            Console.WriteLine("Count by fields concatenation {0}", MyResult);
            Console.WriteLine("Elapsed time {0}", watch.ElapsedMilliseconds / 1000.0);
            watch.Reset(); watch.Start(); // потерянный код :-(
            r = new bool[N]; MyResult = 0;
            for (int j = 0; j < N; j++)
                if (!r[j]) {MyResult++; for (int k = j + 1; k < N; k++)
                    if (!r[k]) r[k] = MyArray[j].Name == MyArray[k].Name && MyArray[j].City == MyArray[k].City
                        && MyArray[j].Division == MyArray[k].Division;}  
            watch.Stop();
            Console.WriteLine("Count by fields comparison  {0}", MyResult);
            Console.WriteLine("Elapsed time {0}", watch.ElapsedMilliseconds / 1000.0);
        }
    }
}

Результаты на списке из 10000 элементов:

Count by List.Distinct 7638

Elapsed time 0,164

Count by Equals 7638

Elapsed time 7,184

Count by fields concatenation 7638

Elapsed time 1,921

Count by fields comparison 7638

Elapsed time 1,921

Вот и посмотри теперь, что даёт наихудший результат.

И что интересно (закономерно, конечно), если сделать больше повторов (32 имени вместо 64), то Distinct работет медленнее, а остальные методы быстрее. Но как, скажите, сделан Distinct, если он работает быстрее всех? Возможно, он использует быструю сортировку?

Потерялся сброс и пуск таймера перед последним тестом. Вот результаты:

Count by List.Distinct 5889

Elapsed time 0,239

Count by Equals 5889

Elapsed time 5,38

Count by fields concatenation 5889

Elapsed time 1,592

Count by fields comparison 5889

Elapsed time 0,223

Теперь всё выглядит очень логично.

Под руководством @MaxS довёл до ума:

using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
namespace DistinctTestTask{
    public struct MyStruct{
        public string Name;
        public string City;
        public string Division;
        public MyStruct(string[] n, string[] c, string[] d, Random r){
            Name = n[r.Next(n.Length)];
            City = c[r.Next(c.Length)];
            Division = d[r.Next(d.Length)];
        }
        public static bool operator == (MyStruct ms1, MyStruct ms2){
            return String.Concat(ms1.Name, ms1. City, ms1.Division) == String.Concat(ms2.Name, ms2. City, ms2.Division);}
        public static bool operator != (MyStruct ms1, MyStruct ms2){
            return String.Concat(ms1.Name, ms1. City, ms1.Division) != String.Concat(ms2.Name, ms2. City, ms2.Division);}
        public bool Equals(MyStruct other){ return Name == other.Name && City == other.City && Division == other.Division;}
        public override int GetHashCode(){ return ((Name.GetHashCode() * 31) ^ City.GetHashCode() * 31) ^ Division.GetHashCode();}
    }
    class DistinctTest{
        static void Main(string[] args){
            var N = Convert.ToInt32(args[0]);
            var Names = File.ReadAllLines("Names.txt");
            var Cities = File.ReadAllLines("Cities.txt");
            var Divisions = File.ReadAllLines("Divisions.txt");
            var Rand = new Random();
            var MyList = new List<MyStruct>();
            for (int i = 0; i < N; i++) MyList.Add(new MyStruct(Names, Cities, Divisions, Rand));
            var watch = new System.Diagnostics.Stopwatch();
            watch.Start(); var MyResult = MyList.Distinct().Count(); watch.Stop();
            Console.WriteLine("Count {0}, elapsed time {1} by List.Distinct\r\n", MyResult, watch.ElapsedMilliseconds / 1000.0);
            var MyArray = MyList.ToArray();
            watch.Reset(); watch.Start();
            var r = new bool[N]; MyResult = 0;
            for (int j = 0; j < N; j++)
                if (!r[j]) {MyResult++; for (int k = j + 1; k < N; k++) if (!r[k]) r[k] = MyArray[j].Equals(MyArray[k]);}  
            watch.Stop();
            Console.WriteLine("Count {0}, elapsed time {1} by Equals\r\n", MyResult, watch.ElapsedMilliseconds / 1000.0);
            watch.Reset(); watch.Start();
            r = new bool[N]; MyResult = 0;
            for (int j = 0; j < N; j++)
                if (!r[j]) {MyResult++; for (int k = j + 1; k < N; k++) if (!r[k]) r[k] = MyArray[j] == MyArray[k];}  
            watch.Stop();
            Console.WriteLine("Count {0}, elapsed time {1} by fields concatenation\r\n", MyResult, watch.ElapsedMilliseconds / 1000.0);
            watch.Reset(); watch.Start();
            r = new bool[N]; MyResult = 0;
            for (int j = 0; j < N; j++)
                if (!r[j]) {MyResult++; for (int k = j + 1; k < N; k++)
                    if (!r[k]){ var maj = MyArray[j]; var mak = MyArray[k];
                        r[k] = maj.Name == mak.Name && maj.City == mak.City
                        && maj.Division == mak.Division;}}  
            watch.Stop();
            Console.WriteLine("Count {0}, elapsed time {1} by fields comparison\r\n", MyResult, watch.ElapsedMilliseconds / 1000.0);
            watch.Reset(); watch.Start();
            var set = new HashSet<MyStruct>();
            for (int j = 0; j < N; j++) set.Add(MyArray[j]);  
            MyResult = set.Count; watch.Stop();
            Console.WriteLine("Count {0}, elapsed time {1} by hash code\r\n", MyResult, watch.ElapsedMilliseconds / 1000.0);
        }
    }
}

Результаты:

Count 5972, elapsed time 0,01 by List.Distinct

Count 5972, elapsed time 0,217 by Equals

Count 5972, elapsed time 1,448 by fields concatenation

Count 5972, elapsed time 0,225 by fields comparison

Count 5972, elapsed time 0,012 by hash code

Вот теперь это правильно демонстрирует работу различных алгоритмов.

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

→ Ссылка
Автор решения: Max S

Для ValueType (от которого неявно наследуются все пользовательские структуры) переопределен метод Equals, который по умолчанию сравнивает инстансы структур по равенству полей в отличие от классов, где по умолчанию вызывается ReferenceEquals (сравнение ссылок на объекты).

Это позволяет вам использовать любые конструкции, явно или неявно вызывающие сравнение экземпляров через Equals, и получать ожидаемое поведение. Например, вы можете решить вашу задачу через LINQ и его метод Distinct (который под капотом вызывает Equals) в одну строчку кода:

var list = new List<MyStruct>() { /* инициализация */ };
var result = list.Distinct(); // результат в виде IEnumerable<MyStruct>
var resultList = result.ToList(); // при необходимости, можно привести к List<MyStruct>

Обратите внимание: переопределение Equals для структур может использовать быструю проверку равенства структур через побитовую проверку, но только в некоторых случаях, а именно (сведения неполные, на самом деле структура ещё должна быть "tightly packed", подробнее здесь):

  1. Тип значения содержит только поля простых типов и не переопределяет метод Equals.

  2. Тип значения содержит только поля типов значений, для которых выполняется условие (1) и не переопределяет метод Equals.

  3. Тип значения содержит только поля типов значений, для которых выполняется условие (2) и не переопределяет метод Equals.

Если быстрая проверка равенства экземпляров не может быть проведена, равенство будет устанавливаться поочерёдным сравнением полей с использованием рефлексии, что является дорогой по времени операцией. Если быстродействие критично для вас на этом участке кода, вы можете реализовать интерфейс IEquatable<MyStruct> для своей структуры (желательно) и (или) переопределить метод Equals и тогда уже и GetHashCode самостоятельно. Также можно переопределить эти методы, если вам нужно реализовать какую-то свою логику сравнения (например, считать, что экземпляры структуры равны, если равны поля Name и City, а на Division не обращать внимания).

→ Ссылка

licensed under cc by-sa 3.0 with attribution.