从四秒到十毫秒 一个花了1年的算法问题

作者:http://www.kokojia.com/更新于： 2016-01-05 16:29:09

　　课课家给那位网友是这么打比方的(原始有点乱 稍微整理了下)，不知道大家有没有歧义，感觉还是上面的伪代码容易理解，但是开心的是，这个网友还是理解了 ：

　　A数组:不管，随意，也不用排序,

　　B数组：[5，2，4，1],假设最大为5，注意没有3

　　初始化一个长度为5(最大数)的布尔数组:a[1],[2],[3],[4],[5]

　　循环B,将B中值作为a的下标，对应位置标记为true，例如

　　a[5]= true;

　　a[2]= true;

　　a[4]= true;

　　a[1]= true;

　　注意a[3]没有，为false

　　最后循环A，直接对比下标，如果A={2，3},那么：

　　a[2]=true,说明存在，则C[2]=true，到C中标记true

　　a[3]=false，则没有。C中标记为false

　　如果你最大为99999,那么这个数组要这么长你可以直接设置为99999，浪费一点空间;

　　如果你业务中可以直接求出最大值，那是最好的了。自己试一试。

　　这个思路理解了非常简单。这个网友也很快理解了，过了一会就把他的结果告诉我了。

　　下降到10毫秒左右，他把数据扩大到10万，速度也挺快的。

　　4.后记与C#实现

　　解决他的问题后，第二天我们又聊了一会，他表示很感谢，说这个方法速度非常快。说这1年来，他问过很多人，也找过很多计算机方面的人，但效果都不好。。。

　　据说还问过一个拿过什么微软认证的人。。。说他的电脑不行，要去换一下。。。这个有点过份操蛋了。。才几万的数组，能耗多少内存，都是简单的比较计算，需要很好的CPU么。。。

　　后来我也给他分析过说，其他人可能没有完全理解你的问题，都一根筋考虑效率和速度的问题了，所以考虑的东西多了，给你的建议也不一定合适。对这些小问题，牺牲一点空间，何况又不多，而且内存也便宜，现在动不动2G，4G。。换时间也是够划算的。我这里说的空间，是直接初始化数组C的长度包括所有的数字个数，因为我也不了解他实际的数据怎么来的，当然如果能计算最大值，肯定最好了。这样稍微计算一下时间复杂度，循环2遍就能解决问题。至于我第一次提到的排序和二分法的问题，也只是刚开始想到的，没有更深入的思考，因为也是考虑到他的数据是可以在生成的时候就进行排序的，这样也可以省时间，而不是所有的都IndexOf，不慢才怪。

　　4.1 C#代码实现原始方法

　　闲的没事，我用C#实现了一下网友原始的方法，代码如下：

　　static void ValidateArrayElement2()

　　{

　　Stopwatch sp = new Stopwatch();

　　sp.Start();

　　//开始计时

　　Random rand = new Random();

　　Int32 maxValue = 120000;

　　//元素最大值，是一个假定值

　　Int32 length = 70000;

　　// A,B的长度

　　Int32[] A = new Int32[length];

　　Int32[] B = new Int32[length];

　　Boolean[] C = new Boolean[length];

　　//随机初始化A，B数组

　　for (int i = 0; i < length; i++)

　　{

　　A[i] = rand.Next(maxValue);

　　B[i] = rand.Next(maxValue);

　　}

　　//循环A，验证是否存在，将C对应位置标记为true

　　for (int i = 0; i < A.Length; i++) if (B.Contains(A[i])) C[i] = true;

　　sp.Stop();

　　Console.WriteLine(sp.ElapsedMilliseconds);

　　}

　　测试了下，我机器是X200+T9400，3G内存。加上数据初始化总共时间是4.3秒，所以实际的时间是4秒左右，和网友的结论是差不多的。看看我下面的方法：

　　4.2 C#代码实现上述算法

　　使用第3节提出的方法，我测试一下时间：

　　static void ValidateArrayElement()

　　{

　　Stopwatch sp = new Stopwatch();

　　sp.Start();

　　Random rand = new Random();

　　Int32 maxValue = 120000;

　　//元素最大值，是一个假定值

　　Int32 length = 70000;

　　// A,B的长度

　　Int32[] A = new Int32[length];

　　Int32[] B = new Int32[length];

　　Boolean[] C = new Boolean[length];

　　Boolean[] Atemp = new Boolean[maxValue];

　　//临时的辅助变量

　　//随机初始化A，B数组

　　for (int i = 0; i < length; i++)

　　{

　　A[i] = rand.Next(maxValue);

　　B[i] = rand.Next(maxValue);

　　}

　　//循环B，验证元素是否存在

　　foreach (var item in B) Atemp[item] = true;

　　//循环A，验证是否存在，将C对应位置标记为true

　　for (int i = 0; i < A.Length; i++) if (Atemp[A[i]]) C[i] = true;

　　sp.Stop();

　　//停止计时

　　Console.WriteLine(sp.ElapsedMilliseconds);

　　}

　　实际时间只有5ms左右，如果不算数据初始化的时间，基本只有1ms，和网友的10ms有点差别，可能和机器有关吧。总的来说，速度的确是提高了不少。

　　至于所谓的哈希表方法，这里就不实现了，已经够快了。

　　最后感谢那些和我一样，热爱编程的业余人事。。。虽然我们不是正规军，虽然我们没有学过数据结构，也没有系统学习过专业的算法课程，没有接受过专业的编程培训，但只要细心和动脑筋，解决一些小规模的问题，还是可以的。至于那些大量数据的效率问题，算法问题就交给大牛吧。

　　剩下的时间交给网友，这个问题简单吗?你会怎么解决?期待评论有更好更佳的答案。。。如果是喷，说问题简单那就算了吧，没必要，何苦为难我呢。。。

　　4.3 HashSet测试

　　感谢passer.net网友，说用HashSet，这个类以前知道，但很少用，既然提出来了，就测试一下，代码如下：

　　Stopwatch sp = new Stopwatch();

　　sp.Start();

　　Random rand = new Random();

　　Int32 length = 70000;

　　// A,B的长度

　　Int32[] A = new Int32[length];

　　Int32[] B = new Int32[length];

　　Boolean[] C = new Boolean[length];

　　var tmp = new HashSet();

　　//随机初始化A，B数组

　　for (int i = 0; i < length; i++)

　　{

　　A[i] = rand.Next();

　　B[i] = rand.Next();

　　if (!tmp.Contains(B[i]))

　　tmp.Add(B[i]);

　　}

　　//循环A，验证是否存在，将C对应位置标记为true

　　for (int i = 0; i < A.Length; i++) C[i] = tmp.Contains(A[i]);

　　sp.Stop();

　　//停止计时

　　Console.WriteLine(sp.ElapsedMilliseconds);

　　测试了一下，大约17ms,比文章的方法稍微慢了一点，但也非常快了，在一个数量级水平吧。可能哈希表对其他复杂的类似数据或者大数据量更管用。不过无所谓了，都是方法，都能解决问题，不必纠结这些细节。