一个从四秒到10毫秒 花了1年的算法问题？
发布时间：2025-06-27 点击：15
特别注意：本文的算法问题对很多专业计算机的人来说，很简单，但是注意看文章的人物背景。
五一后的第一周，由于搬家腰扭伤了，没注意导致压迫神经，躺在床上休息了好几天。所以没事就挂 qq，一个网友突然问了我一个算法问题。所以有了这篇文章。感触很深，所以特发此文，以纪念和写给新朋友，以及那些热爱编程的非专业人事。本人可能技术含量很低，但都很真实。虽然我只花了很少的时间，但解决了这个网友困惑了1年的问题，这个网友倒是特别感激，而我倒是感觉特别心塞。那大家喝杯茶，看看这个过程吧。
1.人物背景
这个网友我也是后来聊天才了解到他的情况。他是1个1977年出生的湖北网民，为了分析相关数据，自学了vb.net，这个年龄的人还学了这个，真的不容易，而且能够用vb.net开发比较复杂的数据分析界面。其实后来了解到这些，自愧不如啊。所以对算法问题，这个朋友遇到困难，也可以理解。
其实这个朋友很早就是我的qq好友，也知道都是做数据分析，所有我有新的算法方面的文章会发给他看，偶尔聊一下，但没有问过我问题。上个月发表了一篇文章：机器学习之pagerank算法应用与c#实现(1)算法介绍，发表之后，他看到后，才问我这个问题。
我：其实我也是个半吊子，对算法也不精通，只是业余研究感兴趣而已。。说实话你要我写个二分搜索，我一时半会还搞不定，但我看看论文和资料，可以写个马尔可夫链或者贝叶斯之类的。。。这个东西怎么说呢，在很多问题中，空间效率和时间效率，特别是在硬件条件如此富裕的情况下，可以考虑得更少一点。。当然这里绝对不是说算法是没有用的，只是对很多非常普通的人来说，研究的规模太小，而且由于经验和特殊原因，没有算法和数据结构基础，只能不考虑了，以解决实际问题为主吧。
2.原始问题
该网友的原始问题是这样的，我从qq聊天记录里直接copy过来：
有两组随机生成的（0～99999）int32数据a和b，将a按顺序判断在b中是否存在并记录在boolean型的c中，我分别尝试了array与list（of t),在vs2010下以我的破电脑的速度array大概需要4秒，而list（of t）则要24秒，以下是我用array和list(of t）的代码，请高手指点， 顺便问下有无秒杀的方法。（注：他的vb代码我就不贴了，思路知道就可以了）
帮我看看用什么方法解决，谢谢
有人说用哈希，可惜我不会，也没百度到
他的开发环境是vs2010 vb.net
我收到他的消息的时候是正在用手机qq上的，他还贴了段vb的代码，我是比较反感直接贴代码的人。不过当时躺在床上，也没啥事，好奇嘛，就仔细看了一下这个问题，代码真的没看。
3.解决问题的过程
由于是手机上的，所以也没开电脑敲代码。就想了一下。
网友的原始代码中的比较都是使用array.indexof，可以想象7万的数组，速度慢也正常 。
1.首先我是把哈希给否定了的。其实后来想起来，是我错了，我以为他说的哈希是把每个元素求哈希值后对比，这不是多此一举么。。本来计算哈希就要时间，还是要比较。。。那何必呢。。。后来我才想到，他说的可能是“哈希表”，这是后话，不提了，哈希表这个方法怎么样不知道，应该也还可以吧；但还是先看看我的方法。
2.我当时先给了他一个初步的方案，解决问题有时候不是一步到位的，先试试看咯。我的想法是使用indexof查找会浪费很多时间。所以，你先把b排序，或者b在实际构造过程中就可以进行排序存储，然后a依次对比的时候，采用二分法搜索，甚至有条件，a也可以先排序，然后搜索的时候记录起点，二分法搜索，这样可以节省不少时间。a和b排序的问题，其实根据他的情况，是可以在实际过程中就排序好的，而不是生成后排序，这样就更费时间了。
这个网友也很迅速，过了大概1个小时，测试出来说：“我用的随机数测试了下，速度提升相当明显，比array.indexof要快多了”
3.上面手机沟通不方便，也就随便说了一下，没想到他很快做出来了。虽然快了很多，但具体时间我也没问。然后我洗澡的时候，感觉这个问题不是那么回事，我以前貌似也做过类似的，应该还有更快的方法。然后洗澡过程中，思考了若干秒。。。一个思路也有了，虽然这个想法我感觉很土，但我想实际效果应该很好，所以洗完澡，马上开电脑，跟网友说了一下思路，考虑到他有可能无法理解算法的伪代码或者比较严格的表述(实际上我也不知道该怎么严格表述)，所以就直接打了一个比方，在这里为了方便大家理解，我先大概写了个思路，应该会看得懂吧。至于问题中的记录在c中，我具体没问他怎么记录，其实这和问题关系不大，核心在前面如何确定是否包括：
我给那位网友是这么打比方的(原始有点乱，我写博客的时候稍微整理了下)，不知道大家有没有歧义，感觉还是上面的伪代码容易理解，但是开心的是，这个网友还是理解了 ：
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 = ne
网站无法打开一直载入中……
云虚拟主机是什么?
阿里云服务器两个网站
美国vps多ip
聚美优品回购股票 股价大涨近15%
重庆ecs云服务器异常任务限制
电脑中CAD尺寸标注的箭头和尺寸显示不了怎么办
我本地固定地址访问打不开
五一后的第一周，由于搬家腰扭伤了，没注意导致压迫神经，躺在床上休息了好几天。所以没事就挂 qq，一个网友突然问了我一个算法问题。所以有了这篇文章。感触很深，所以特发此文，以纪念和写给新朋友，以及那些热爱编程的非专业人事。本人可能技术含量很低，但都很真实。虽然我只花了很少的时间，但解决了这个网友困惑了1年的问题，这个网友倒是特别感激，而我倒是感觉特别心塞。那大家喝杯茶，看看这个过程吧。
1.人物背景
这个网友我也是后来聊天才了解到他的情况。他是1个1977年出生的湖北网民，为了分析相关数据，自学了vb.net，这个年龄的人还学了这个，真的不容易，而且能够用vb.net开发比较复杂的数据分析界面。其实后来了解到这些，自愧不如啊。所以对算法问题，这个朋友遇到困难，也可以理解。
其实这个朋友很早就是我的qq好友，也知道都是做数据分析，所有我有新的算法方面的文章会发给他看，偶尔聊一下，但没有问过我问题。上个月发表了一篇文章：机器学习之pagerank算法应用与c#实现(1)算法介绍，发表之后，他看到后，才问我这个问题。
我：其实我也是个半吊子，对算法也不精通，只是业余研究感兴趣而已。。说实话你要我写个二分搜索，我一时半会还搞不定，但我看看论文和资料，可以写个马尔可夫链或者贝叶斯之类的。。。这个东西怎么说呢，在很多问题中，空间效率和时间效率，特别是在硬件条件如此富裕的情况下，可以考虑得更少一点。。当然这里绝对不是说算法是没有用的，只是对很多非常普通的人来说，研究的规模太小，而且由于经验和特殊原因，没有算法和数据结构基础，只能不考虑了，以解决实际问题为主吧。
2.原始问题
该网友的原始问题是这样的，我从qq聊天记录里直接copy过来：
有两组随机生成的（0～99999）int32数据a和b，将a按顺序判断在b中是否存在并记录在boolean型的c中，我分别尝试了array与list（of t),在vs2010下以我的破电脑的速度array大概需要4秒，而list（of t）则要24秒，以下是我用array和list(of t）的代码，请高手指点， 顺便问下有无秒杀的方法。（注：他的vb代码我就不贴了，思路知道就可以了）
帮我看看用什么方法解决，谢谢
有人说用哈希，可惜我不会，也没百度到
他的开发环境是vs2010 vb.net
我收到他的消息的时候是正在用手机qq上的，他还贴了段vb的代码，我是比较反感直接贴代码的人。不过当时躺在床上，也没啥事，好奇嘛，就仔细看了一下这个问题，代码真的没看。
3.解决问题的过程
由于是手机上的，所以也没开电脑敲代码。就想了一下。
网友的原始代码中的比较都是使用array.indexof，可以想象7万的数组，速度慢也正常 。
1.首先我是把哈希给否定了的。其实后来想起来，是我错了，我以为他说的哈希是把每个元素求哈希值后对比，这不是多此一举么。。本来计算哈希就要时间，还是要比较。。。那何必呢。。。后来我才想到，他说的可能是“哈希表”，这是后话，不提了，哈希表这个方法怎么样不知道，应该也还可以吧；但还是先看看我的方法。
2.我当时先给了他一个初步的方案，解决问题有时候不是一步到位的，先试试看咯。我的想法是使用indexof查找会浪费很多时间。所以，你先把b排序，或者b在实际构造过程中就可以进行排序存储，然后a依次对比的时候，采用二分法搜索，甚至有条件，a也可以先排序，然后搜索的时候记录起点，二分法搜索，这样可以节省不少时间。a和b排序的问题，其实根据他的情况，是可以在实际过程中就排序好的，而不是生成后排序，这样就更费时间了。
这个网友也很迅速，过了大概1个小时，测试出来说：“我用的随机数测试了下，速度提升相当明显，比array.indexof要快多了”
3.上面手机沟通不方便，也就随便说了一下，没想到他很快做出来了。虽然快了很多，但具体时间我也没问。然后我洗澡的时候，感觉这个问题不是那么回事，我以前貌似也做过类似的，应该还有更快的方法。然后洗澡过程中，思考了若干秒。。。一个思路也有了，虽然这个想法我感觉很土，但我想实际效果应该很好，所以洗完澡，马上开电脑，跟网友说了一下思路，考虑到他有可能无法理解算法的伪代码或者比较严格的表述(实际上我也不知道该怎么严格表述)，所以就直接打了一个比方，在这里为了方便大家理解，我先大概写了个思路，应该会看得懂吧。至于问题中的记录在c中，我具体没问他怎么记录，其实这和问题关系不大，核心在前面如何确定是否包括：
我给那位网友是这么打比方的(原始有点乱，我写博客的时候稍微整理了下)，不知道大家有没有歧义，感觉还是上面的伪代码容易理解，但是开心的是，这个网友还是理解了 ：
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 = ne
网站无法打开一直载入中……
云虚拟主机是什么?
阿里云服务器两个网站
美国vps多ip
聚美优品回购股票 股价大涨近15%
重庆ecs云服务器异常任务限制
电脑中CAD尺寸标注的箭头和尺寸显示不了怎么办
我本地固定地址访问打不开