死机了，有没有更快的算法哦！！

Question

一个List<string>集合，比如list1：{"关闭0","2地方","5法0规","fg","地方","9"}
又是一个List<string>集合，比如list2：{"0","5"}
一个List<int>集合，比如list3：{1,2}
目标：在list1中寻找满足下面条件的元素：对于list1中的某个元素而言，其包含list2中的元素，并且包含的个数是属于list3中规定的个数，那么，list1中的此元素就算满足条件（上例中有"关闭0"、"5法0规"满足条件）
求出list1中所有满足条件的元素，下面是我的方法：        public List<string> get_1(List<string> list1, List<string> list2, List<int> list3)  
        {
            List<string> list_中介 = new List<string>(list1);
            List<string> list_返回值 = new List<string>();
            foreach (string s in list_中介)
            {
                bool b = true;                
                foreach (int i in list3)
                {
                    int i_出 = list2.Where(x => s.Contains(x)).Count();  
                    if (i == i_出)
                    {
                        b = false;
                        break;
                    }
                }
                if (b)
                {
                    list1.Remove(s);
                }
            }
            return list1;            
        }
可是，很慢哦，如果list1有1百万个字符串，list2只有2个元素，list3也只有2个数字，计算结果就是死机...........哪位朋友有更好、更快的算法吗？     

Answer 1

“int i_出 = list2.Where(x => s.Contains(x)).Count(); ”
这句是不是应该移到foreach (int i in list3)外面？

Answer 2

我最多只能改成下面这样了，但提升速度不明显：public List<string> get_1(List<string> list1, List<string> list2, List<int> list3)  
        {
            List<string> list_中介 = new List<string>(list1);
            List<string> list_返回值 = new List<string>();
            bool b = true;
            foreach (string s in list_中介)
            {                    
                b = list3.Contains(list2.Where(x => s.Contains(x)).Count());  
                if (!b)
                {
                    list1.Remove(s);
                }
            }
            return list1;            
        }

Answer 3

b = list3.Contains(list2.Count(x => s.Contains(x)));

Answer 4

“list_返回值”这个没用到...
1. list_中介 感觉没有必要！如果要返回符合条件的元素就直接保存那些元素；若要剔除符合条件的元素则不需要 list_中介，只是用for循环而不用foreach。 这个 list_中介 量太大，耗内存也耗时间！2. list1.Remove（s）;感觉效果不好，list1需要在一百多万条记录中从头到尾地寻找第一个匹配值，并删除。个人觉得如果需要剔除某个元素，最好使用索引，这样可能快点（纯属臆测，你可以试试）

Answer 5

        public List<string> get_1(List<string> list1, List<string> list2, List<int> list3)
        { 
            List<string> result = new List<string>();            list1.ForEach((s) =>
            {
                if (list3.Contains(list2.Count(x => s.Contains(x))))
                {
                    result.Add(s);
                }
            });            return result; 
        }
这不是最优算法，这只是按照你的算法精简之后的写法。

Answer 6

用性能分析器看看那里最消耗,数据量大,总会有瓶颈的,100W数据list切割成100个1W的list,开100个线程做处理,然后汇总数据,删除检测出的元素;你也不必一定用100个线程,先测试下开5个线程,找到一个最大效率的线程数.关于死机,如果是程序死了,有可能是等待太久,内存消耗过大之类的,如果是系统死了,就是运算量超过负荷了,这个时候如果不能在算法上改进,只能用时间来换空间了...

Answer 7

如果是多核CPU,可以考虑下task的多核并行处理,本人也没测试过多核编程,只是突然想到,可以尝试下

Answer 8

 public class Program
    {
        class NewCls
        {
            public string a;
            public int b;
        }
        static void Main(string[] args)
        {
            var list1 = new List<string>() { "关闭0", "2地方", "5法0规", "fg", "地方", "9" };
            List<NewCls> list2 = new List<NewCls>() { new NewCls() { a = "0", b = 1 }, new NewCls() { a = "5", b = 2 } };
            list1 = list1.Where(t => list2.Count(tt => t.Contains(tt.a.Trim()) && t.Length - t.Replace(tt.a, "").Length == tt.b) > 0).ToList();
            foreach (var t in list1)
            {
                Console.WriteLine(t);
            }
            Console.ReadLine();
        }
    }

Answer 9

为啥非要用 =>
直接写都比那个快1/3        public static void get_2(List<string> list1, List<string> list2, List<int> list3)
        {
            List<string> result = new List<string>();
            foreach (string s1 in list1)
            {
                int count = 0;
                foreach (string s2 in list2)
                {
                    if (s1.Contains(s2))
                        count++;
                }
                if (count > 0 && list3.Contains(count))
                    result.Add(s1);
            }

Answer 10

        static public IEnumerable<string> get_1(List<string> list1, List<string> list2, List<int> list3)
        {
            return list1.Where(x => list3.Any(z => list2.Where(y => x.Contains(y)).Count() == z)).ToList();
        }

Answer 11

难道是Add比此方法速度快了不下11倍？ 
难道是Add比Remove快？

Answer 12

大数据量用Contains()方法效率比较慢，建议使用正则的方法来匹配。不要使用循环用indexOf（）来判断      public static List<string> get_1(List<string> list1, List<string> list2, List<int> list3)
        {
            List<string> result = new List<string>();
            string reg = string.Join("|", list2.ToArray());
            int min = list3.Min();
            int max = list3.Max();
            foreach (string str in list1)
            {
                var mc = Regex.Matches(str, reg);              
                if(list3.IndexOf(mc.Count)>-1)
                {
                    result.Add(str);
                    break;
                }               
            }
            return result;
        }

Answer 13

public static List<string> get_1(List<string> list1, List<string> list2, List<int> list3)         {             List<string> result = new List<string>();             string reg = string.Join("|", list2.ToArray());            // int min = list3.Min();            // int max = list3.Max();             foreach (string str in list1)             {                 var mc = Regex.Matches(str, reg);                               if(list3.IndexOf(mc.Count)>-1)                 {                     result.Add(str);                     break;                 }                            }             return result;         }

Answer 14

 public static List<string> get_1(List<string> list1, List<string> list2, List<int> list3)
        {
            List<string> result = new List<string>();
            string reg = string.Join("|", list2.ToArray());
            //int min = list3.Min();
            //int max = list3.Max();
            foreach (string str in list1)
            {
                var mc = Regex.Matches(str, reg);              
                if(list3.IndexOf(mc.Count)>-1)
                {
                    result.Add(str);
                    break;
                }               
            }
            return result;
        }

Answer 15

正则麻烦多，还要进行转义,你的结果条数错了        static void Main()
        {
            string[] l1 = { "关闭0", "2地方", "5法0规", "fg", "地方", "9" };
            string[] l2 = { "0", "5" };
            int[] l3 = { 1, 2 };
            List<string> list1 = new List<string>(l1);
            for (int i = 0; i < 1000000; i++)
                list1.Add(GetMix(20));
            List<string> list2 = new List<string>(l2);
            for (int i = 0; i < 10; i++)
                list2.Add(GetMix(100));
            List<int> list3 = new List<int>(l3);
            for (int i = 3; i < 100; i++)
                list3.Add(i);
            //get_1
            DateTime s = DateTime.Now;
            int cou= get_1(list1, list2, list3).Count;
            Console.WriteLine(cou);
            Console.WriteLine(DateTime.Now.Subtract(s).ToString());
            //get_2
            s = DateTime.Now;
            cou = get_2(list1, list2, list3).Count;
            Console.WriteLine(cou);
            Console.WriteLine(DateTime.Now.Subtract(s).ToString());
            //get_3
            s = DateTime.Now;
            cou = get_3(list1, list2, list3).Count;
            Console.WriteLine(cou);
            Console.WriteLine(DateTime.Now.Subtract(s).ToString());
            Console.Read();
        }        public static List<string> get_1(List<string> list1, List<string> list2, List<int> list3)
        {
            List<string> result = new List<string>();
            list1.ForEach((s) =>
            {
                if (list3.Contains(list2.Count(x => s.Contains(x)))) { result.Add(s); }
            });
            return result;
        }
        public static List<string> get_2(List<string> list1, List<string> list2, List<int> list3)
        {
            List<string> result = new List<string>();
            foreach (string s1 in list1)
            {
                int count = 0;
                foreach (string s2 in list2)
                {
                    if (s1.Contains(s2))
                        count++;
                }
                if (count > 0 && list3.Contains(count))
                    result.Add(s1);
            }
            return result;
        }
        public static List<string> get_3(List<string> list1, List<string> list2, List<int> list3)
        {
            List<string> result = new List<string>();
            string reg = string.Join("|", list2.ToArray());
            foreach (string str in list1)
            {
                var mc = Regex.Matches(str, reg);
                if (list3.IndexOf(mc.Count) > -1)
                {
                    result.Add(str);
                }
            }
            return result;
        }
        #region 得到随机string
        static string str = @"0123456789abcdefghigklmnopqrstuvwxyzABCDEFGHIGKLMNOPQRSTUVWXYZ";
        static Random rd = new Random();
        public static string GetMix(int len)
        {
            StringBuilder sb = new StringBuilder();
            while (len > 0)
            {
                sb.Append(str[rd.Next(str.Length)]);
                len--;
            }
            return sb.ToString();
        }
        #endregion 得到随机string事实说明，用啥也不能用正则
//list1 100W条
//list2 100条
//list3 1-100
//480483
//00:00:16.0229165
//480483
//00:00:14.0078012
//480483
//00:01:23.7747916//list1 100W条
//list2 1000条
//list3 1-100
//480458
//00:02:39.3061118
//480458
//00:02:19.9510047
//480458
//00:15:41.6178575 //15分钟才完

Answer 16

想知道这个程序最后的数据量有多少？（从List1到List3）
看起来其实更像分词的应用。