- Для заданного условия уникальности нужно соединить строки структуры в одну, и использовать её для проверки уникальности всей структуры.
- Уникальные значения выявить просто. Нужно сделать массив повторов (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
Вот теперь это правильно демонстрирует работу различных алгоритмов.
Вывод: Использование хэша, уникального в пределах не менее количества объектов, позволяет упорядочить коллекцию объектов и, таким образом, проверить уникальность объектов без попарного сравнения.
linq
взял.Distinct()
Equals
по умолчанию и так проверяет равенство всех полей.