当前位置:天才代写 > tutorial > 其他教程 > 从四秒到十毫秒 一个花了1年的算法问题

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

2018-05-22 08:00 星期二 所属: 其他教程 浏览:317

从四秒到十毫秒  一个花了1年的算法问题_编程算法_课课家

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

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

  }

#p#分页标题#e#

  实际时间只有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,比文章的方法稍微慢了一点,但也非常快了,在一个数量级水平吧。可能哈希表对其他复杂的类似数据或者大数据量更管用。不过无所谓了,都是方法,都能解决问题,不必纠结这些细节。

 

    关键字:

天才代写-代写联系方式