集合里查找数据

Question

比如
List<string> a=new List<string>();
a里面有{111,222,333,444,555,666,777,888,999,111,222,333,444}
找出交集得到结果是
111,222,333,444速度要快的，数据量是在百万条之上。什么算法最快？

Answer 1

List<string> list = a.Where(s => a.Count(s2 => s == s2) >= 2).Distinct().ToList();

Answer 2

用字典试试：Dictionary<string,int> dic = new Dictionary<string,int>();
foreach(string s in a)
{
    if(dic.ContainsKey(s))
        dic[s]++;
    else 
        dic.Add(s,1);
}
List<string> list = new List<string>();
foreach(string s in dic)
{
    if(dic[s]>1)
       list.Add(s);
}

Answer 3

//写了一个DEMO 测试了一下不同的方法所有的时间
//DEMO中的LIST中有100条数据  每个方法重复执行100次
void Main()
{
InitList();
 
System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start();
for(int i=1;i<=100;i++)
{
  GetLINQFunctionTestTime();
}
stopwatch.Stop();
Console.WriteLine("使用 LINQ 总共用时 {0} 毫秒,平均 {1}毫秒/次",stopwatch.ElapsedTicks,stopwatch.ElapsedTicks/100);


stopwatch.Start();
for(int i=1;i<=100;i++)
{
  GetOtherFunctionTestTime();
}
stopwatch.Stop();
Console.WriteLine("使用 Other 总共用时 {0} 毫秒,平均 {1}毫秒/次",stopwatch.ElapsedTicks,stopwatch.ElapsedTicks/100);


stopwatch.Start();
for(int i=1;i<=100;i++)
{
  GetDictionaryFunctionTestTime();
}
stopwatch.Stop();
Console.WriteLine("使用 Dictionary 总共用时 {0} 毫秒,平均 {1}毫秒/次",stopwatch.ElapsedTicks,stopwatch.ElapsedTicks/100);

/*
使用 LINQ 总共用时 7344 毫秒,平均 73毫秒/次
使用 Other 总共用时 15501 毫秒,平均 155毫秒/次
使用 Dictionary 总共用时 22191 毫秒,平均 221毫秒/次 */
}void  GetLINQFunctionTestTime()
{ 
  var query=list.GroupBy(l=>l).Where(g=>g.Count()>1).Select(g=>g.Key).ToList();
}void GetOtherFunctionTestTime()
{
  ArrayList ay=new ArrayList();
  List<int> result=new List<int>();
  foreach(int str in list)
  {
if(ay.Contains(str))
{
  result.Add(str);
}
else
{ 
  ay.Add(str);
}
  }
}void GetDictionaryFunctionTestTime()
{  
    Dictionary<int,int> dic = new Dictionary<int,int>();
foreach(int s in list)
{
if(dic.ContainsKey(s))
dic[s]++;
else 
dic.Add(s,1);
}
List<int> result = new List<int>();
foreach(var s in dic)
{
if(dic[s.Key]>1)
result.Add(s.Key);
}}
public List<int> list = new List<int>();
void InitList()
{
  var list1=Enumerable.Range(10,50);  // 10 -  59
  var list2=Enumerable.Range(20,20);  // 20 -  39
  var list3=Enumerable.Range(40,30);  // 40 -  69
  list=list1.Concat(list2).Concat(list3).ToList();
}

Answer 4

Linq很简单，但是不知道运行起来，效率上是否也给力？？

Answer 5

List<string> list = a.AsParallel().Where(s => a.Count(s2 => s == s2) >= 2).Distinct().ToList();看看能否利用多核心加速。一般在 Core i7 上可以提高5倍速度。