专栏首页奇点大数据算法之旅(1)——认识算法

算法之旅(1)——认识算法

从今天开始,我将用100期的内容讲解各种计算机领域常用的算法和思路,以及优化方法,主要覆盖图论、模式匹配、快速查找、概率统计、聚/分类、神经网络、分布式算法等。这些内容会有部分概念有重叠,不过总体来说不会漏下重要的内容。今天我们先讲第一讲,认识算法。

算法在很多程序员朋友眼里显得非常神秘,总觉得这种东西很高深,都是要数学大牛才能掌握的东西,其实不然,算法是就是指计算的逻辑和步骤,我们现在说到的算法其实主要是指电子计算机的计算逻辑。我们研究算法的目的也非常简单,那就是希望通过高效率,高准确率的运算逻辑让计算机代替我们人类进行数据处理。

在大量的高级语言和工程框架成型后,我们现在使用成型的算法非常简单。

String a = s.trim();

只要我们用这样一个语句,就可以把s这个字符串左右两端所有的空格都去掉,至于怎么做的,效率高不高我们一般也不会去关心,除非我们发现它在工作中给我们带来了执行效率方面的困扰。

面向对象的封装确实已经屏蔽掉了很多的计算细节,这给我们带来了使用的方便,但是同时也在一定程度上扼杀了高效率程序诞生的环境——当然了,现在的CPU资源一般来说还是足够让我们霍霍的。

对于现在的计算机来说,不管是RISC还是CISC指令集,他们在数据处理上都还是图灵机的模型,那就是存储和指令。或者我们只认为计算机只做两件事,一个就是把某个地址的数据放到哪里去,一个就是把某个地址的数据进行计算,真的就这么简单。关于这个过程,我还是要做一些简单的讲解。

1、进制

我们都知道电子计算机里面的计数都是使用二进制的,这也是没办法的事情,因为第一代电子计算机都是使用二稳态器件来做介质的——真空管,正向导通反向截止,也就是说,每一个计算机最小的技术单位只有两个状态,不是0,就是1。不够怎么办,那就再来一个真空管,再多表示一位喽,以此类推。

人类用十进制原因就是因为人类有10根手指,如果当初人类诞生的时候就是两只手,一手一根手指,那么现在很庆幸,计算机和人类有了统一的进制——二进制,而且毫无违和感。

2、存储

学过汇编语言的同学可能不会陌生,汇编语言都是型如这种

mov 35, 10000000b

这种就几乎是计算机最简单的一个动作了,把一个地方的数据搬移到另一个地方去,比如从CPU寄存器到内存。再小的单位恐怕已没有任何计算层面的意义。

如果再搬移一次,那就还要重新对CPU发一次指令。这样的一次不可再分的指令就是我们粗略地度量计算成本的最小单位。

例如同样一个算法,有的人写出来需要10亿个单位,有的人写出来需要3000万个单位,显然后者效率要高得多。

3、计算

计算机里的计算是一种非常接近人类运算认知的计算方式,什么意思呢——人类首先认识加法,用加法定义减法,用加法定义乘法,用减法定义除法,在用这些去定义乘方开方,微分积分等复杂运算。除非在一些特殊领域,计算单元经过了特殊的优化,可能会有其它的实现方式,否则通用计算机是没有捷径可走的。

使用与、或、与非、或非这些计算单元的计算机,也是用二稳态原件的性质来模拟在二进制状态下的加减进位退位过程完成最简单的加法器,然后再在高层计算机语言中封装成为更为复杂的运算,这就是现在计算机计算的基本原理。不管计算多复杂,请记住,底层肯定还是这些小的与、或单元在那里做电源小铡刀似的开闭动作来做一次一次的加法叠加实现的。

4、I/O

说到I/O,理论上只要是从CPU进行数据出入都应该算I/O操作,只不过现在计算机运算速度很快了,在大多数情况下这种I/O都会被忽略不计。而我们平时说的I/O太大影响效率通常指的是磁盘I/O。

现在主流的机械磁盘在有缓存的情况下和内存的存储效率还是要差至少2到3个数量级,所以一旦由于算法写得不够考究,触发了不必要的磁盘I/O操作,那就会让计算效率大打折扣。这些技巧在我们未来的分享中也会逐渐系统性地进行讲解。

5、算法

最后我们总结一下,说一说算法。

我们所说的算法,就是指一种计算逻辑和步骤,我们通过程序告诉计算机应该定义什么样的存储单元,通过什么逻辑和步骤进行相应的计算最后得到结果,这个就是算法的全部。在这其一我们要考虑的是逻辑正确性;其二考虑的是“时间复杂度”——其中也包括随着数据量增加产生的I/O边界效应。

本文分享自微信公众号 - 奇点(qddata),作者:高扬

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2016-06-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 深入了解Google的第一个Tensor Processing Unit(TPU)

    作者: Kaz Sato(谷歌云Staff Developer Advocate) Cliff Young(谷歌大脑软件工程师) David Patterson...

    刀刀老高
  • 什么是算法

    算法这个名称大家应该通常不陌生,如果你是一个信息相关专业的本科学生,至少在本科一年级或者二年级就接触过不少算法了。随便打开一个人力资源网站去搜搜看“算法工程师”...

    刀刀老高
  • 机器学习算法在自动驾驶汽车中扮演怎样的角色

    随着电子控制单元传感器数据处理这项技术的继续发展,人们也越来越期待运用更优化的机器学习,来完成更多新挑战。未来的潜在应用场景包括:通过内外部传感器(包括激光雷达...

    刀刀老高
  • Flink 常见问题定位指南

    流计算作业通常运行时间长,数据吞吐量大,且对时延较为敏感。但实际运行中,Flink 作业可能因为各种原因出现吞吐量抖动、延迟高、快照失败等突发情况,甚至发生崩溃...

    KyleMeow
  • Flink 常见问题定位指南

    流计算作业通常运行时间长,数据吞吐量大,且对时延较为敏感。但实际运行中,Flink 作业可能因为各种原因出现吞吐量抖动、延迟高、快照失败等突发情况,甚至发生崩溃...

    腾讯云大数据团队
  • 最短路算法实现与分析:Dijkstra算法,Floyed,Bellman-Ford, SPFA算法;

    最短路算法:最短路径算法是图论研究中,一个经典算法问题;旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

    xuyaowen
  • 基于图像的场景三维建模

    三月已过半旬,已是春暖花开的季节,也是我们科研爱好者最繁忙的一段时间。春天的到来,意味着新一届的学子即将离开学校,走向自己人生的第二段道路,也意味着您年伊始,所...

    计算机视觉研究院
  • 每个程序员都应该知道的GitHub Repos

    GitHub是领先的Git存储库托管服务,其中包含许多代码存储库,库等的源代码。

    硬核编程
  • 干货|饿了么推荐算法演进及在线学习实践

    ...

    fishexpert
  • 最短路问题与标号算法(label setting algorithm)研究(1) - 开篇介绍

    本系列推文重在从算法基本原理、复杂度分析、优缺点、代码实现、算法扩展等方面科普Label Correcting Algorithm(最短路算法重要分支),同时给...

    用户1621951

扫码关注云+社区

领取腾讯云代金券