求一高效率算法! -实在搞不定了

求一高效算法! --实在搞不定了
本帖最后由 ChargeForward 于 2011-04-16 13:34:15 编辑 情况说明:
  50000个字符串
  字符串是有特点的, 形如 "1,3,5,54,68,998,52,34,65"  只有数字和英文逗号
需求说明: 
  从这50000个字符串中提取出其中的数字,并去重(distinct),时间要求:普通PC机(酷睿双核2.5GHZ,2G内存)50ms以内,如果能进30ms,那就更好了
我的代码如下

    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Stopwatch timer = new Stopwatch();
                timer.Reset();
                HashSet<string> ht = new HashSet<string>();              
                timer.Start();                
                for (int i = 0; i <= 50000; i++)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";

                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;                   
                    int startIndex = 0;
                    char[] tempcharArr = new char[] { '\0', '\0', '\0', '\0' };
                    #region
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            string s = new string(tempcharArr); 
 
                            if (!ht.Contains(s))
                            {
                                ht.Add(s);                                
                            }
                            startIndex = 0;
                            tempcharArr = new char[] { '\0', '\0', '\0', '\0' };
                        }
                        else
                        {
                            tempcharArr[startIndex] = c;
                            startIndex++;
                        }
                    }    
                    #endregion
                }
                
                timer.Stop();
                int count = ht.Count;
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }
    }

我的这段程序顶多只能跑到 155ms, 求坛子里的各路大神帮帮忙,小弟感激涕零!

[解决办法]
你的程序不对：

1）ht 应该每次重建，或清空。
2）最多只能四位数？

[解决办法]
到底是五千个还是五万个.
循环部分可以这样避免不断new char[] { '\0', '\0', '\0', '\0' };提高一点速度

[code=C#]
            for (int i = 0; i < 50000; i++)
            {
                string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";
                int start = 0;
                fixed (char* c = apps)
                {
                    for (int j = 0; j < apps.Length; j++)
                    {
                        if (c[j] == ',')
                        {
                            string s = new string(c, start, j - start);
                            if (!ht.Contains(s))
                            {
                                ht.Add(s);
                            }
                            start = j + 1;
                        }
                    }
                }
/code]

查看更多 下一篇