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

Question

本帖最后由 ChargeForward 于 2011-04-16 13:34:15 编辑

Answer 1

1)ht是用来记录结果的,怎么能清空?
2)我的疏忽,那些数字最多只是千位以内数字,所以4位char数组就可以了
请给出您的解决方案 谢谢!

Answer 2

你 50000 次循环只是为了测试速度，内部每次应该是一样的。应该加一个for (int i = 0; i <= 50000; i++)
{
   ht.Clear();
   ...
}                {

Answer 3

这位大神 我觉得您可能对我的需求描述有一点点误解,  
我有50000个value可能不同字符串,  我的那个程序里是假定这50000全部相同,而实际业务需求是这个50000个字符串几乎不可能相同  ht.Clear(); 我已经说过了 ,ht是保存结果的容器,如果Clear了 结果就都没了...

Answer 4

        Hashtable hashTable = new Hashtable();
        string strValue ="112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";
        string[] strList = strValue.Split(new char[] { ',' }, StringSplitOptions.None);
        for (int i = 0; i < 5000; i++)
        { 
            for(int j=0;j<strList.Length;j++)
            {
                if (strList[j] == "")
                    continue;
                if(!hashTable.Contains(strList[j]))
                    hashTable.Add(strList[j], strList[j]);
            }
        }

Answer 5

这50000个字符串是不同的, 而且具体环境不允许使用linq

Answer 6

我知道啊同样的用Split()截取啦数据都添加到Hashtable里面。。

Answer 7

哥哥 你测测性能好不好?  用split都快到400ms了!  我的要求是50ms

Answer 8

到底是五千个还是五万个.
循环部分可以这样避免不断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]

Answer 9

            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;
                        }
                    }
                }

Answer 10

另外,似乎不需要判断contains，看这个hashset源代码    int hashCode = this.InternalGetHashCode(value);
    int index = hashCode % this.m_buckets.Length;
    for (int i = this.m_buckets[hashCode % this.m_buckets.Length] - 1; i >= 0; i = this.m_slots[i].next)
    {
        if ((this.m_slots[i].hashCode == hashCode) && this.m_comparer.Equals(this.m_slots[i].value, value))
        {
            return false;
        }
    }
在add时本身会进行一次判断，如果有相同的就不会添加。

Answer 11

我用你的代码和unsafe都测试过，有提升（本来从道理上推断也是如此），但是不能根本解决50毫秒这个问题。包括后面的不判断contains，实际都不能解决，全部都是不起决定意义的改进。

Answer 12

这是我修改后的程序  最快跑到137ms        static void Act()
        {
            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,";
                    
                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    int startIndex = 0;                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            string s = new string(appCharArr, startIndex, j - startIndex);
                           
                            ht.Add(s);
                         
                            startIndex = j + 1;
                        }
                    }
                    #endregion
                }
                timer.Stop();
                int count = ht.Count;
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }

Answer 13

我觉得就这个思路来说，怎么改进也都是这样了。
每次都是同一个string，比起真正不同的string来速度本身会快很多。
不知道你们的需求是什么样，如果可以改成多线程，或者数据是一次性到达的，就先放到一个大的缓冲区或许能根本解决。

Answer 14

千位以内的用bool[10000]保存就行

Answer 15

index的类型转换会使整个程序更慢To：楼主，性能的损失部分在于拆分字符串和add()这里系统函数调用排它带来的，不知道lz的审题是否有误解。至少这个思路下去没什么作用。阁下觉得呢。

Answer 16

这样行不？                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,";
                    
                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    //int startIndex = 0;                    foreach (char c in appCharArr) 
                    {
                        if (c == ',')
                        {                           
                            ht.Add(c.ToString());
                        }
                    }
                    #endregion
                }

Answer 17

        static void Main(string[] args)
        {
            while (true)
            {
                Stopwatch timer = new Stopwatch();
                timer.Reset();
                bool[] array = new bool[9999];
                timer.Start();
                int count = 0;
                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,";
                    array.Initialize();
                    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 == ',')
                        {
                            int temp = ConvertCharArrayToInt(tempcharArr);
                            if (!array[temp])
                            {
                                count++;
                                array[temp] = true;
                            }
                            startIndex = 0;
                            for (int k = 0; k < 4; k++)
                                tempcharArr[k] = '\0';
                        }
                        else
                        {
                            tempcharArr[startIndex] = c;
                            startIndex++;
                        }
                    }
                    #endregion
                }
                timer.Stop();
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }        static int ConvertCharArrayToInt(char[] array)
        {
            int result = 0;
            int temp = 0;
            int j = 0;
            for (int i = 3; i >= 0; i--)
            {
                if (array[i] != '\0')
                {
                    j = array[i] - 48;
                    switch (temp)
                    {
                        case 0:
                            result += j;
                            break;
                        case 1:
                            result += (j << 4) - (j << 2) - (j << 1);
                            break;
                        case 2:
                            result += (j << 7) - (j << 4) - (j << 2) - (j << 2) - (j << 2);
                            break;
                        case 3:
                            result += (j << 10) - (j << 4) - (j << 2) - (j << 2);
                            break;
                    }
                    temp++;
                }
            }
            return result;
        }

Answer 18

下面这个程序用我那破机器最终跑出了55ms 差不多就这样吧  基本没有优化的空间了  再次谢谢大家提供的思路!       static void Act()
        {
            while (true)
            {
                Stopwatch timer = new Stopwatch();
                timer.Reset();
                HashSet<int> ht = new HashSet<int>();
                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,";
                    
                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    int startIndex = 0;
                    int appInt = 0;
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            ht.Add(appInt);
                            appInt = 0;
                        }
                        else
                        {
                            appInt = appInt * 100 + (int)c;
                        }
                    }
                    #endregion
                }
                timer.Stop();
                int count = ht.Count;
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }

Answer 19

ojlovecd 您好像是叫天行健吧  呵呵  大神啊   不过您这段程序没有35楼的快...
all the same  还是非常感谢您的代码, 我学到了很多知识!

Answer 20

你想知道你得到结果是什么样的么
while (true)
            {
                Stopwatch timer = new Stopwatch();
                timer.Reset();
                HashSet<int> ht = new HashSet<int>();
                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,";                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    int startIndex = 0;
                    int appInt = 0;
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            ht.Add(appInt);
                            appInt = 0;
                        }
                        else
                        {
                            appInt = appInt * 100 + (int)c;
                        }
                    }
                    #endregion
                }
                timer.Stop();
                int count = ht.Count;
                foreach (var i in ht)
                {
                    Console.WriteLine(i);
                }
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }

Answer 21

appInt = appInt * 100 + (int)c; =》
appInt = appInt * 10 + c - '0';

Answer 22

没有人反思数据结构？字符串是好的介质吗？
四位数用一个short就可以表示了，固定2个字节，还不需要分割符号。

Answer 23

如果已经是short[]数组还要再"切"吗？
如果是文件，那么：byte[] raws = File.ReadAllBytes("...");
short[] vals = new short[raws.Length/2];
Buffer.BlockCopy(raws, 0, vals, 0, vals.Length*2);

Answer 24

static void Main(string[] args)
        {
            Stopwatch timer = new Stopwatch();
            timer.Reset();
            
            HashSet<int> big = new HashSet<int>();
            bool[] small = new bool[100];            timer.Start();            for (int i = 0; i <= 500000; i++)
            {
                string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";                int number = 0;
                
                for (int j = 0; j < apps.Length; j++)
                {
                    char c = apps[j];
                    
                    if (c == ',')
                    {
                        if (number < 100)
                        {
                            small[number] = true;
                        }
                        else
                        {
                            big.Add(number);
                        }                        number = 0;
                    }
                    else
                    {
                        number = number * 10 + (int) (c - '0');
                    }
                }
            }
            
            timer.Stop();            for (int i = 0; i < small.Length; i++)
            {
                if (small[i])
                {
                    Console.WriteLine(i);
                }
            }            foreach (var i in big)
            {
                Console.WriteLine(i);
            }
            
            Console.WriteLine("{0} ms", timer.Elapsed.TotalMilliseconds / 10);
        }
    }

Answer 25

就对这些数据，把35楼的 HashSet 改为 List，用时最少 21ms。仅仅是对35楼的程序啊，实际的数据处理情况就不知道了。

Answer 26

我的想法基本和35楼一样，但是大家忽略了一点，可以把ht.count打出来看，发现只有18，事实上真正做ht.add操作的只有18次，猜想ht.add应该自带contain检测。这样的话最后测得的时间略有偏差，如果在每次循环开头加上ht.clear的话，我的机器跑出来需要100ms

Answer 27

HashSet存放的数据都是不重复的
HashSet.Add(T)会返回bool操作结果，这里LZ好像不需要关心这个
如果只是想取总长度，在外面弄个变量累计数字也可以，ht.Clear()就也没必要了
Mark!

Answer 28

试了一下 bool[10000] 快不少class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Random random = new Random();
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 50000; i++)
                {
                    sb.Append(random.Next(10000));
                    sb.Append(",");
                }
                Act1(sb.ToString());
                Act2(sb.ToString());
                Console.ReadLine();
            }
        }
        static void Act1(string apps)
        {
            Stopwatch timer = new Stopwatch();
            timer.Reset();
            HashSet<int> ht = new HashSet<int>();
            timer.Start();            char[] appCharArr = apps.ToCharArray();
            int length = appCharArr.Length;
            int appInt = 0;
            for (int j = 0; j < length; j++)
            {
                char c = appCharArr[j];
                if (c == ',')
                {
                    ht.Add(appInt);
                    appInt = 0;
                }
                else
                {
                    appInt = appInt * 100 + (int)c;
                }
            }            timer.Stop();
            int count = ht.Count;
            Console.WriteLine(count);
            Console.WriteLine(timer.Elapsed.ToString());
        }
        static void Act2(string apps)
        {            Stopwatch timer = new Stopwatch();
            timer.Reset();
            MySet set = new MySet();
            timer.Start();
            char[] appCharArr = apps.ToCharArray();
            int length = appCharArr.Length;
            for (int j = 0; j < length; j++)
            {
                char c = appCharArr[j];
                if (c == ',')
                {
                    set.Set();
                }
                else
                {
                    set.Local(c);
                }
            }
            timer.Stop();
            int count = set.Count;
            Console.WriteLine(count);
            Console.WriteLine(timer.Elapsed.ToString());
        }
    } 
    public class MySet
    {
        bool[] set = new bool[10000];
        private int index = 0;
        private int count = 0;        public void Local(char c)
        {
            index = index * 10 + (c - 48);
        }        public void Set()
        {
            if (!set[index])
            {
                count++;
            }
            set[index] = true;
            index = 0;
        }        public int Count { get { return count; } }
    }

Answer 29

用bool[]
这些数字输出也很方便
 public IEnumerable<int> Numbers
        {
            get
            {
                for (int i = 0; i < 100000; i++)
                {
                    if (set[i])
                    {
                        yield return i;
                    }
                }
            }
        }

Answer 30

我最新的程序是将35楼中hashset换成了int【】 intArr=new int【1000000】；
50000次循环完了之后 用linq的distinct去除重复， 最后我那破机器跑到了32ms
我现在在网吧， 回公司后再验证袁锋的那段程序有没有我的快， 下  先Dota  哈哈

Answer 31

54楼MySet换成这个位运算版本的，内存只有原来的 1/32 速度也能快一点点。 public class MySet
    {
        int[] set = new int[3125];
        private int index = 0;
        private int count = 0;
        public void Local(char c)
        {
            index = index * 10 + (c - 48);
        }
        public void Set()
        {
            int a = index / 32;
            int b = index % 32;
            if ((set[a] & (1 << b)) == 0)
            {
                count++;
                set[a] |= (1 << b);
            }
            index = 0;
        }
        public int Count { get { return count; } }
    }

Answer 32

TotalMilliseconds 就是毫秒数, 不知道您为什么要除以10?
您的程序在我的机器上的结果为:
 Console.WriteLine("{0}", timer.Elapsed.ToString());
00:00:00.4147369
这好像是414毫秒吧...    纠结中...

Answer 33

54楼方案1，最短2ms,方案2最短3ms58楼更省空间

Answer 34

不能用unsafe的话,借楼主的程序改一下
        private static void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                List<int> ht = new List<int>();
                timer.Start();
                bool[] isValue = new bool[10000];                for (int i = 50000; i >= 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    int appInt = 0;
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            if (!isValue[appInt])
                            {
                                ht.Add(appInt);
                                isValue[appInt] = true;
                            }
                            appInt = 0;
                        }
                        else
                        {
                            appInt <<= 1;
                            appInt += appInt << 2;
                            appInt += c - '0';
                        }
                    }
                    #endregion
                }
                timer.Stop();
                int count = ht.Count;
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }

Answer 35

机器配置：一代酷rui,1.8G 
测试结果 ：串长为5万时，时间11ms, 串的数量为5万时，时间49ms.
 private void button2_Click(object sender, EventArgs e) {            //这是生成测试用的数据的            StringBuilder builder = new StringBuilder(50000);
            int k = 0;
            for (int i = 0; i < 50000; i++) {
                k = i % 10000;
                builder.Append("," + k.ToString());               // if (builder.Length > 50000) break;
            }            Test(builder );
        }
        
        //这是函数
        void Test(StringBuilder appCharArr) {
            DateTime dt0 = DateTime.Now;            List<int> lst = new List<int>(50000);            string sub = "";
            int iMax = appCharArr.Length;
            for (int i = 0; i < iMax; i++) {
                char c = appCharArr[i];                if (char.IsDigit(c)) {
                    sub += c;
                }
                else if (c.Equals(',')) {
                    if (sub.Length > 0) {
                        lst.Add(Convert.ToInt32(sub));
                    }                    sub = "";
                }
            }            //-0------------------------------------
            List<int> lstResult = new List<int>(50000);            lst.Sort();
            if (lst.Count == 0) return;            //-0--------compare----------------
            int iOld = lst[0];
            lstResult.Add(iOld);
            foreach (int each in lst) {
                if (each == iOld) continue;
                lstResult.Add(each);
                iOld = each;
            }            TimeSpan span = DateTime.Now - dt0;
            MessageBox.Show("总时间(ms)：" + span.TotalMilliseconds.ToString());        }

Answer 36

如果只计数就没必要Add了，直接用个++count

Answer 37

用 HashSet 相比直接用 内存数组，还是要慢比较多！

Answer 38

用unsafe只计数
        private static unsafe void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                timer.Start();
                int count = 0;
                byte[] isValue = new byte[10000];                for (int i = 50000; i >= 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";                    #region
                    fixed (byte* isValueStart = isValue)
                    {
                        fixed (char* appStart = apps)
                        {
                            int value, high, appInt = count = 0;
                            int* next = (int*)appStart;
                            for (int* end = next + (apps.Length >> 1); next != end; ++next)
                            {
                                high = value = *next;
                                value &= 0xffff;
                                high >>= 16;
                                if (value != ',')
                                {
                                    appInt <<= 1;
                                    appInt += appInt << 2;
                                    appInt += (value -= '0');
                                    if (high != ',')
                                    {
                                        appInt <<= 1;
                                        appInt += appInt << 2;
                                        appInt += (high -= '0');
                                    }
                                    else
                                    {
                                        count += isValueStart[appInt] ^ 1;
                                        appInt = 0;
                                        isValueStart[appInt] = 1;
                                    }
                                }
                                else
                                {
                                    count += isValueStart[appInt] ^ 1;
                                    appInt = (high -= '0');
                                    isValueStart[appInt] = 1;
                                }
                            }
                            count += apps.Length & 1 & (isValueStart[appInt] ^ 1);
                        }
                    }
                    #endregion
                }
                timer.Stop();
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }

Answer 39

用unsafe获取列表
        private static unsafe void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                List<int> ht = new List<int>();
                timer.Start();
                byte[] isValue = new byte[10000];                for (int i = 50000; i >= 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20,";                    #region
                    fixed (byte* isValueStart = isValue)
                    {
                        fixed (char* appStart = apps)
                        {
                            int value, high, appInt = 0;
                            int* next = (int*)appStart;
                            for (int* end = next + (apps.Length >> 1); next != end; ++next)
                            {
                                high = value = *next;
                                value &= 0xffff;
                                high >>= 16;
                                if (value != ',')
                                {
                                    appInt <<= 1;
                                    appInt += appInt << 2;
                                    appInt += (value -= '0');
                                    if (high != ',')
                                    {
                                        appInt <<= 1;
                                        appInt += appInt << 2;
                                        appInt += (high -= '0');
                                    }
                                    else
                                    {
                                        if (isValueStart[appInt] == 0)
                                        {
                                            ht.Add(appInt);
                                            isValueStart[appInt] = 1;
                                        }
                                        appInt = 0;
                                    }
                                }
                                else
                                {
                                    if (isValueStart[appInt] == 0)
                                    {
                                        ht.Add(appInt);
                                        isValueStart[appInt] = 1;
                                    }
                                    appInt = (high -= '0');
                                }
                            }
                            if ((apps.Length & 1 & (isValueStart[appInt] ^ 1)) != 0)
                            {
                                ht.Add(appInt);
                            }
                        }
                    }
                    #endregion
                }
                timer.Stop();
                int count = ht.Count;
                Console.WriteLine(timer.Elapsed.ToString());
                Console.ReadLine();
            }
        }

Answer 40

54楼没有理解我的需求  应该将你程序中50000换成2500000才相当于我的需求
目前最快的一个        static void Act()
        {
            while (true)
            {
                Stopwatch timer = new Stopwatch();
                timer.Reset();
                HashSet<int> ht = new HashSet<int>();                
                timer.Start();
                //int[] list = new int[10000000];
                bool[] small = new bool[300];
                int[] result = new int[300];
                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";
                    
                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    
                    int appInt = 0;
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            //list[startIndex] = appInt;
                            small[appInt] = true;
                            appInt = 0;                       
                        }
                        else
                        {
                            appInt = appInt * 10 + (int)(c-'0');
                        }
                    }
                    #endregion
                }
                var intApps = GetIntArr(small);                               timer.Stop();
                int count = 0;
                count = intApps.Count();
                List<int> lll = intApps.ToList();
                Console.WriteLine(timer.Elapsed.ToString() + "    Count:" + count);
                Console.ReadLine();
            }
        }
        static IEnumerable<int> GetIntArr(bool[] small)
        {
            for (int i = 0; i < small.Length; i++)
            {
                if (small[i])
                {
                    yield return i;
                }
            }
        }

Answer 41

[Quote=引用 69 楼 chargeforward 的回复:]
54楼没有理解我的需求 应该将你程序中50000换成2500000才相当于我的需求
目前最快的一个
sorry,没有看你的代码，只看了前边的说明，理解有误，在此深表歉意！

Answer 42

将数据灌入到c#的dataset里面的datatable, 利用它进行sql语句操作,速度很快的。

Answer 43

恩，反正算法是都是这样的。
就是29楼litaoye提到的 bool[]
内存数组本来就是一种特殊的哈希表。只不过哈希函数比较简单index直接对应位置。
不过要求数字比较集中，而且都是整数，才能直接用数组代替哈希表

Answer 44

> TotalMilliseconds 就是毫秒数, 不知道您为什么要除以10?我循环次数增加了 10 倍。

Answer 45

我修改了一个上面的实现，可以测试一下bool[]比HashSet快多少。注释了一部分，是重置bool数组的。using System;
using System.Collections.Generic;
using System.Diagnostics;namespace CsdnTest
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch timer = new Stopwatch();
            timer.Reset();
            bool[] flag = new bool[10000];
            List<int> rseult = new List<int>();
            timer.Start();            for (int i = 0; i <= 500000; 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;
                //rseult.Clear();
                int appInt = 0;                for (int j = 0; j < length; j++)
                {
                    if (appCharArr[j] == ',')
                    {
                        if (!flag[appInt])
                        {
                            flag[appInt] = true;
                            rseult.Add(appInt);
                        }                        appInt = 0;
                    }
                    else
                        appInt = appInt * 10 + appCharArr[j] - '0';
                }                //foreach (int index in rseult)
                //    flag[index] = false;
            }            timer.Stop();            foreach (int index in rseult)
                Console.WriteLine(index);            Console.WriteLine(timer.Elapsed.ToString());
            Console.ReadLine();
        }
    }
}

Answer 46

楼主的程序有做弊行为
var intApps = GetIntArr(small);               
应该放在循环里面

Answer 47

static IEnumerable<int> GetIntArr(bool[] small)
        {
            for (int i = 0; i < small.Length; i++)
            {
                if (small[i])
                {
                    yield return i;
                }
            }
        }这一段代码的代价是很高的，直接用个循环生成数组比这个快几倍。

Answer 48

再借楼主的程序改一下
        private static void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                timer.Start();
                int count = 0;
                int[] small = new int[300];
                int[] result = new int[300];
                for (int i = 50000; i != 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20";                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    int appInt = count = 0;
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            if (small[appInt] != i)
                            {
                                result[count++] = appInt;
                                small[appInt] = i;
                            }
                            appInt = 0;
                        }
                        else
                        {
                            appInt = appInt * 10 + (int)(c - '0');
                        }
                    }
                    if (appCharArr[length - 1] != ',') result[count++] = appInt;
                    #endregion
                }                timer.Stop();
                Console.WriteLine(timer.Elapsed.ToString() + "    Count:" + count);
                Console.ReadLine();
            }
        }

Answer 49

好像是yield 的代价很高的  不过small的length很小  这里只是把结果计算出来 用哪种都行

Answer 50

前面的循环都没有得到最终结果，只有最后一个循环之后才求出最后一个结果，还不如直接改成for (int i = 0; i <= 1; i++)

Answer 51

if (small[appInt] != i) 单凭这一句 好像就已经偏离了我的需求了
 

Answer 52

建议你再仔细看看我的需求描述   然后循环内部不使用i 试试 
还是不能理解 留下你的QQ  我们细细讨论

Answer 53

真是服了你了，不用你的i,我自已加个变量总行了吧
        private static void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                timer.Start();
                int count = 0, index = 0;
                int[] small = new int[300];
                int[] result = new int[300];
                for (int i = 50000; i != 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20";                    #region
                    char[] appCharArr = apps.ToCharArray();
                    int length = appCharArr.Length;
                    int appInt = count = 0;
                    ++index;
                    for (int j = 0; j < length; j++)
                    {
                        char c = appCharArr[j];
                        if (c == ',')
                        {
                            if (small[appInt] != index)
                            {
                                result[count++] = appInt;
                                small[appInt] = index;
                            }
                            appInt = 0;
                        }
                        else
                        {
                            appInt *= 10;
                            appInt += c;
                            appInt -= '0';
                        }
                    }
                    if (appCharArr[length - 1] != ',') result[count++] = appInt;
                    #endregion
                }                timer.Stop();
                Console.WriteLine(timer.Elapsed.ToString() + "    Count:" + count);
                Console.ReadLine();
            }
        }

Answer 54

这个不难理解，那个i是记录某一次比较的，主要是在下一次比较中不用重置Hash表。
而且连List都没用，自己用数组维护，稍微有点麻烦，但性能会有略微的提高。

Answer 55

发贴以后也看到了，改成unsafe效率要高一倍，因为数组没有越界判断了        private static unsafe void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                timer.Start();
                int count = 0;
                int[] small = new int[300];
                int[] result = new int[300];
                for (int i = 50000; i != 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20";                    #region
                    fixed (int* smallStart = small, resultStart = result)
                    {
                        fixed (char* appStart = apps)
                        {
                            int length = apps.Length, appInt = count = 0, low, high;
                            int* start = (int*)appStart;
                            for (int* end = start + (length >> 1); start != end; ++start)
                            {
                                high = low = *start;
                                low &= 0xffff;
                                high >>= 16;
                                if (low != ',')
                                {
                                    appInt *= 10;
                                    appInt += low;
                                    appInt -= '0';
                                    if (high != ',')
                                    {
                                        appInt *= 10;
                                        appInt += high;
                                        appInt -= '0';
                                    }
                                    else
                                    {
                                        if (smallStart[appInt] != i)
                                        {
                                            resultStart[count++] = appInt;
                                            smallStart[appInt] = i;
                                        }
                                        appInt = 0;
                                    }
                                }
                                else
                                {
                                    if (smallStart[appInt] != i)
                                    {
                                        resultStart[count++] = appInt;
                                        smallStart[appInt] = i;
                                    }
                                    appInt = high;
                                    appInt -= '0';
                                }
                            }
                            if ((length & 1) == 0)
                            {
                                if (appStart[length - 1] != ',') resultStart[count++] = appInt;
                            }
                            else if ((low = *(char*)start) != ',')
                            {
                                appInt *= 10;
                                appInt += low;
                                appInt -= '0';
                                resultStart[count++] = appInt;
                            }
                            else if (smallStart[appInt] != i)
                            {
                                resultStart[count++] = appInt;
                                smallStart[appInt] = i;
                            }
                        }
                    }
                    #endregion
                }                timer.Stop();
                Console.WriteLine(timer.Elapsed.ToString() + "    Count:" + count);
                Console.ReadLine();
            }
        }

Answer 56

问题是 改成unsafe代码  我在本地编译后 放到服务器上运行 会不会报错啊？

Answer 57

还有一个原因是每次读取一个int比只读取一个char快，如果改成读char的话，比读int要慢，但是程序简单        private static unsafe void Act()
        {
            while (true)
            {
                System.Diagnostics.Stopwatch timer = new System.Diagnostics.Stopwatch();
                timer.Reset();
                timer.Start();
                int count = 0;
                int[] small = new int[300];
                int[] result = new int[300];
                for (int i = 50000; i != 0; --i)
                {
                    string apps = "112,2,3,4,5,6,7,8,9,10,112,12,13,14,15,16,17,18,19,20";                    #region
                    fixed (int* smallStart = small, resultStart = result)
                    {
                        fixed (char* appStart = apps)
                        {
                            int length = apps.Length, appInt = count = 0, low;
                            for(char* start = appStart, end = start + length; start != end; ++start)
                            {
                                low = *start;
                                if (low != ',')
                                {
                                    appInt *= 10;
                                    appInt += low;
                                    appInt -= '0';
                                }
                                else
                                {
                                    if (smallStart[appInt] != i)
                                    {
                                        resultStart[count++] = appInt;
                                        smallStart[appInt] = i;
                                    }
                                    appInt = 0;
                                }
                            }
                            if (appStart[length - 1] != ',') resultStart[count++] = appInt;
                        }
                    }
                    #endregion
                }                timer.Stop();
                Console.WriteLine(timer.Elapsed.ToString() + "    Count:" + count);
                Console.ReadLine();
            }
        }

Answer 58

有一个问题，你要保证你的字符串中的数字最大只有299，参数apps也不能为null，否则会引发不可预料的后果。

Answer 59

哈哈 你担心的这些都不会发生  最开始的时候 我会将数据准备好的 谢谢 all the same
不知道可否留下联系方式啊？ 

Answer 60

class Program
{
    static void Main(string[] args)
    {
        while (true)
        {
            Random random = new Random();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 50000; i++)
            {
                sb.Append(random.Next(10000));
                sb.Append(",");
            }
            Splits1(sb.ToString());
            Act2(sb.ToString());
            Console.ReadLine();
        }
    }
    static void Splits1(string apps)
    {
        Stopwatch timer = new Stopwatch();
        timer.Reset();
        timer.Start();
        var f = GetIntArr(apps).GetEnumerator();
        timer.Stop();
        Console.WriteLine(timer.Elapsed.ToString());
        
    }
    static IEnumerable<int> GetIntArr(string apps)
    {
        int appInt = 0;
        int resint = 0;
        char[] small = apps.ToCharArray();
        for (int i = 0; i < small.Length; i++)
        {
            if (small[i] != ',')
            {
                appInt = appInt * 10 + (int)(small[i] - '0');
            }
            else
            {
                resint = appInt;
                appInt = 0;
                yield return resint;
            }
        }
    }
    
    static void Act2(string apps)
    {        Stopwatch timer = new Stopwatch();
        timer.Reset();
        bool[] small = new bool[10000];
        timer.Start();
        char[] appCharArr = apps.ToCharArray();
        int length = appCharArr.Length; int appInt = 0;
        for (int j = 0; j < length; j++)
        {
            char c = appCharArr[j];
            if (c == ',')
            {
                small[appInt] = true;
                appInt = 0;
            }
            else
            {
                appInt = appInt * 10 + (int)(c - '0');
            }
        }
        timer.Stop();
        Console.WriteLine(timer.Elapsed.ToString());
    }
}

Answer 61

 static IEnumerable<int> GetIntArr(string apps)
    {
        int appInt = 0;
        int resint = 0;
        char[] small = apps.ToCharArray();
        for (int i = 0; i < small.Length; i++)
        {
            if (small[i] != ',')
            {
                appInt = appInt * 10 + (int)(small[i] - '0');
            }
            else
            {
                resint = appInt;
                appInt = 0;
                yield return resint;
            }
        }
    }
效率提高不少