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

  • 时间:
  • 浏览:31

一阵一阵注意:本文的算法难题对过后专业计算机的人来说,很简单,过后注意看文章的人物背景。

五一后的第一周,因为搬家腰扭伤了,没注意因为压迫神经,躺在床上休息了好几天。过后没事就挂 QQ,一两个前网友视频见面总爱问了我一两个算法难题。过后有了这篇文章。感触太深了,过后特发此文,以纪念和写给新大伙,以及你這個热爱编程的非专业人事。另一方因为技术含量很低,但都很真实。我人太好我只花了很少的时间,但处置了你這個前网友视频见面困惑了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,都可否 想象20万的数组,速率慢也正常 。

1.首先我是把哈希给否定了的。我我人太好过后 想起来,是我错了,我以为是我不好的哈希是把每个元素求哈希值后对比,这完全后要多此一举么。。从前 计算哈希就要时间,还是要比较。。。那太多呢。。。过后 我才想到,是我不好的因为是“哈希表”,这是后话,不提了,哈希表你這個土土妙招为何会 样谁能谁能告诉我,应该也还都可否 吧;但还是先看看我的土土妙招。

2.我歌词 当时先给了他一两个初步的方案,处置难题有以前完全后要一步到位的,先试试看咯。我的想法是使用IndexOf查找会浪费过后时间。过后,你先把B排序,因为B在实际构造过程中就都可否 进行排序存储,过后A依次对比的以前,采用二分法搜索,甚至有条件,A也都可否 先排序,过后搜索的以前记录起点,二分法搜索,从前 都可否 节省不少时间。A和B排序的难题,我我人太好根据他的状况,是都可否 在实际过程中就排序好的,而完全后要生成后排序,从前 就更费时间了。

你這個前网友视频见面也很好快,过了最少一两个小时,测试出来说:“我用的随机数测试了下,速率提升相当明显,比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毫秒左右,他把数据扩大到20万,速率也挺快的。

4.后记与C#实现

处置他的难题后,第4天 大伙又聊了一会,他表示很感谢,说你這個土土妙招速率非常快。说这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 = 150000;
//元素最大值,是一两个假定值
    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);
}

测试了下,我机器是X500+T9500,3G内存。加带数据初始化总共时间是4.3秒,过后实际的时间是4秒左右,和前网友视频见面的结论是差太多的。看看我下面的土土妙招:

4.2 C#代码实现上述算法

使用第3节提出的土土妙招,我测试一下时间:

static void ValidateArrayElement()
{
    Stopwatch sp = new Stopwatch();
    sp.Start();
    Random rand = new Random();
    Int32 maxValue = 150000;
//元素最大值,是一两个假定值
    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<int>();
//随机初始化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,比文章的土土妙招稍微慢了你這個,但也非常快了,在一两个数量级水平吧。因为哈希表对你這個错综复杂的例如数据因为大数据量更管用。不过无所谓了,完全后要土土妙招,都能处置难题,太多纠结你這個细节。