[200分]求高效并集算法

Question

有2串类似的字符串表示2个集合.5|5:1|4:1|3:1|2:0|1:1;4|5:1|4:1|1:0;3|4:0|2:1|1:1;2|2:1|1:0;1|5:1|3:0
5|5:0|3:1|2:1;4|4:1;3|3:1;2|2:1;1|5:1|4:0其中字符串用";"可以分割成5|5:1|4:1|3:1|2:0|1:1
;
4|5:1|4:1|1:0
;
3|4:0|2:1|1:1
;
2|2:1|1:0
;
1|5:1|3:0以2|2:1|1:0举例:以"|"分割 第一个2表示组名,后面2:1中2表示组员,1表示存在;1:0中1表示组员,0表示不存在.
(为什么不存在还要留下用0表示呢,因为这表示它曾经存在过- -!)
现在这2个集合求并集,
要求如下
例如集合 1|1:0|2:1;2|1:1|2:0 
  和集合 1|1:1|2:0;3|1:1 的并集
  结果为 1|1:1|2:1;2|1:1|2:0;3|1:1
        public Hashtable GetGroup(string Source)
        {
            Hashtable Group = new Hashtable { };
            string[] GroupArr = Source.Split(';'); //根据字符串分组
            Array.ForEach(GroupArr, group =>
            {
                if (!string.IsNullOrEmpty(group))
                {
                    string[] groupArr = group.Split('|'); //根据字符串分组员
                    Hashtable Element = new Hashtable { };
                    for (int i = 1; i < groupArr.Count(); i++)
                    {
                        if (!string.IsNullOrEmpty(groupArr[i]))
                        {
                            string[] ElementArr = groupArr[i].Split(':'); //根据字符串分组员状态
                            Element.Add(int.Parse(ElementArr[0]), ElementArr[1]); 
                        }
                    }
                    Group.Add(int.Parse(groupArr[0]), Element);
                }
            });
            return Group;
        }现在我是把它分割然后装在HashTabel里,然后在进行对比合并,感觉不是很理想.不知道哪位大大还有更好的方法吗?谢谢~

Answer 1

 public List<List<string>> GetGroup()
        {
            string Source1 = "5|5:1|4:1|3:1|2:0|1:1;4|5:1|4:1|1:0;3|4:0|2:1|1:1;2|2:1|1:0;1|5:1|3:0";
            string Source2 = "5|5:0|3:1|2:1;4|4:1;3|3:1;2|2:1;1|5:1|4:0";            List<List<string>> Group = new List<List<string>>();
            string[] GroupArr = Source1.Split(';'); //根据字符串分组
            var sp1 = Source1.Split(new char[] { ';', '|' });
            var sp2 = Source2.Split(new char[] { ';', '|' });
            var sp3 = sp1.Concat(sp2).Distinct().ToList();          
            Group.Add(sp3);
            //Array.ForEach(GroupArr, group =>
            //{
            //    if (!string.IsNullOrEmpty(group))
            //    {
            //        string[] groupArr = group.Split('|'); //根据字符串分组员
            //        Hashtable Element = new Hashtable { };
            //        for (int i = 1; i < groupArr.Count(); i++)
            //        {
            //            if (!string.IsNullOrEmpty(groupArr[i]))
            //            {
            //                string[] ElementArr = groupArr[i].Split(':'); //根据字符串分组员状态
            //                Element.Add(int.Parse(ElementArr[0]), ElementArr[1]);
            //            }
            //        }
            //        Group.Add(int.Parse(groupArr[0]), Element);
            //    }
            //});
            return Group;
        }调用 List<List<string>> Group = new List<List<string>>();
 Group = GetGroup();

Answer 2

用控制台试试看看时间using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            string Source1 = "5|5:1|4:1|3:1|2:0|1:1;4|5:1|4:1|1:0;3|4:0|2:1|1:1;2|2:1|1:0;1|5:1|3:0";
            string Source2 = "5|5:0|3:1|2:1;4|4:1;3|3:1;2|2:1;1|5:1|4:0";
            List<List<string>> Group = new List<List<string>>();
            string[] GroupArr = Source1.Split(';'); //根据字符串分组
            var sp1 = Source1.Split(new char[] { ';', '|' });
            var sp2 = Source2.Split(new char[] { ';', '|' });
            var sp3 = sp1.Concat(sp2).Distinct().ToList();
            foreach (string s1 in sp1)
            {
                Console.Write(s1 + "\t");
            }
            Console.WriteLine("\n");
            foreach (string s2 in sp2)
            {
                Console.Write(s2 + "\t");
            }
            Console.WriteLine("\n");
            foreach (string s3 in sp3)
            {
                Console.Write(s3 + "\t");
            }
            Console.WriteLine("\n");
            stopWatch.Stop();
            TimeSpan ts = stopWatch.Elapsed;
            string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
                ts.Hours, ts.Minutes, ts.Seconds,
                ts.Milliseconds / 10);
            Console.WriteLine("RunTime " + elapsedTime);
        }
    }
}

Answer 3

没注意看，竟然是0？
换成方法试试using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;namespace ConsoleApplication2
{
    class Program
    {
        public static void GetGroup()
        {
            string Source1 = "5|5:1|4:1|3:1|2:0|1:1;4|5:1|4:1|1:0;3|4:0|2:1|1:1;2|2:1|1:0;1|5:1|3:0";
            string Source2 = "5|5:0|3:1|2:1;4|4:1;3|3:1;2|2:1;1|5:1|4:0";
            List<List<string>> Group = new List<List<string>>();
            string[] GroupArr = Source1.Split(';'); //根据字符串分组
            var sp1 = Source1.Split(new char[] { ';', '|' });
            var sp2 = Source2.Split(new char[] { ';', '|' });
            var sp3 = sp1.Concat(sp2).Distinct().ToList();
            foreach (string s1 in sp1)
            {
                Console.Write(s1 + "\t");
            }
            Console.WriteLine("\n");
            foreach (string s2 in sp2)
            {
                Console.Write(s2 + "\t");
            }
            Console.WriteLine("\n");
            foreach (string s3 in sp3)
            {
                Console.Write(s3 + "\t");
            }
            Console.WriteLine("\n");        }
        static void Main(string[] args)
        {
            Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();
            GetGroup();
            stopWatch.Stop();
            TimeSpan ts = stopWatch.Elapsed;
            string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}",
                ts.Hours, ts.Minutes, ts.Seconds,
                ts.Milliseconds / 10);
            Console.WriteLine("RunTime " + elapsedTime);
        }
    }
}

Answer 4

请仔细对比一下
例如集合A 1|1:0|2:1;2|1:1|2:0  
  和集合B 1|1:1|2:0;3|1:1 的并集
  结果C为 1|1:1|2:1;2|1:1|2:0;3|1:1
A中1组的 1:0 和B中1组1:1 并为1:1
A中1组的 2:1 和B中1组2:0 并为2:1
A中存在 2组, B中存在3组
并为C的结果中同时存在2和3组

Answer 5

建议先把字符串转化为数据对象。这样更容易操作，也更容易查询，比如：public class Member
{
    public Member(string s)
    {
        string[] tokens = s.Split(':');
        Id = int.Parse(tokens[0]);
        State = int.Parse(tokens[1]) == 1;
    }
    public override string ToString()
    {
        return Id + ":" + (State ? 1 : 0);
    }
    public int Id;
    public bool State;
}public class Group
{
    public int Name { get; set; }
    public List<Member> Members { get; private set; }
    public Group()
    {
        this.Members = new List<Member>();
    }
    public Group(string s) : this()
    {
        string[] tokens = s.Split('|');
        this.Name = int.Parse(tokens[0]);
        this.Members.AddRange(tokens.Skip(1).Select(str => new Member(str)));
    }
    public override string ToString()
    {
        return Name + "|" + string.Join("|", Members.Select(m => m.ToString()).ToArray());
    }
    
    public static Group Union(Group a, Group b)
    {
        if (a == null || b == null || a.Name != b.Name) throw new ArgumentException();
        
        Dictionary<int, Member> dictionary = new Dictionary<int,Member>();
        Action<Member> addToDictionary = (m) => 
        {
            if( dictionary.ContainsKey(m.Id) ) dictionary[m.Id].State |= m.State;
            else dictionary[m.Id] = m;
        };
        a.Members.ForEach(m => addToDictionary(m));
        b.Members.ForEach(m => addToDictionary(m));        Group result = new Group() { Name = a.Name };
        result.Members.AddRange(dictionary.Values.OrderByDescending(v => v.Id));
        return result;
    }
    public static Dictionary<int, Group> GroupsFromString(string s)
    {
        return s.Split(';').Select(str => new Group(str)).ToDictionary(g => g.Name);
    }
}而对数据对象的合并操作就容易多了：private void button1_Click(object sender, EventArgs e)
{
    string s1 = "5|5:1|4:1|3:1|2:0|1:1;4|5:1|4:1|1:0;3|4:0|2:1|1:1;2|2:1|1:0;1|5:1|3:0";
    string s2 = "5|5:0|3:1|2:1;4|4:1;3|3:1;2|2:1;1|5:1|4:0";    Dictionary<int, Group> group1 = Group.GroupsFromString(s1);
    Dictionary<int, Group> group2 = Group.GroupsFromString(s2);    Dictionary<int, Group> unioned = new Dictionary<int, Group>(group1);
    foreach (var pair  in group2)
    {
        Group group = pair.Value;
        if (group1.ContainsKey(pair.Key))
        {
            group = Group.Union(group1[pair.Key], group);
        }
        unioned[pair.Key] = group;
    }    MessageBox.Show(string.Join(";\r\n", unioned.OrderByDescending(p => p.Key).Select(p => p.Value.ToString()).ToArray()));
}

Answer 6

谢谢,我用Chinajiyong
的测速方式和他用sp1.Concat(sp2).Distinct().ToList();
先组装在去重复的方法用的时间一样,并且和我的要求相符.