算法之旅(2)——朴素的存取

上次我们说到算法最基本的处理规则和算法在计算机底层所藉由的工作方式。这次我们来说说计算机中最简单的算法,最朴素的数据存取。

也许有的朋友觉得这种问题太底层,简直没有办法直接把算法转换成大米饭或者房子,但是我还是要说,我们要想深刻理解算法还是要从其处理数据的本质开始看才会有更多思路。

小时候我们可能都学过珠算,即便没有在课堂上学过至少也见过。

每个档位都是一个十进制的计数器,而且有一套天生做加减法的珠算口诀“三下五去二”,“六上一去五进一”——这其实就是珠算中最小的算法单位了。这种珠算口诀的出现是必须由算盘作为搭配承载的,也就是说,这种单档位进退位规则是由于算盘构造而出现的。那计算机中有没有档位呢?有的,上次我们已经说过,就是寄存器的各种逻辑门。

我们把单位放大一点去看——因为从信息论下界的角度来看,1bit的东西在二进制当中只能表示两个不同的信息含义,如果要想表示3或4个,那就需要2bit。8个bit称为一个byte,叫做一个字节,能够表示最多256个不同的信息含义,也是我们平时在高级语言中能够处理的最小单位(不过现在高级语言也很强大的,有很多可以处理底层数据的类也允许你直接对一个bit单位进行操作)。

以内存为例,大量的byte单位连续在一起,就像我们平时看的书橱。

每个小格子都是一个byte,存放着我们要处理的数据。不过别忘了,在内存里,这种小格子有几百万上千万个可不算稀奇。

为了管理这些小格子,我们都要给他们编上序号,在WIN98最盛行的时候我们会不时看到自己的电脑因为各种原因蓝屏。

蓝屏后屏幕会出现这种信息,中间会给出这种0x0000008E的信息,这就是内存地址信息。使用这种16进制来表示内存的地址主要是为了简洁一些,0x0000008E表示第142个内存byte的位置,而0xC0000005则表示第3221225477个byte的内存位置。可以想象一下,0x00000000到0xFFFFFFFF这4294967296个(32位系统寻址的最大单位上限)中,就是有4294967296个连续的小格子来“自由”放置数据。那剩下的发挥空间,都是程序员的。

如果你想存一个数字到一个地方去,那就“MOV 寄存器地址 内存地址”。

如果你想从一个地方把数字取出来,那就“MOV 内存地址 寄存器地址”。

如果你想把内存地址1和内存地址2的数据做加法,那就麻烦点,不过也能很快搞定“MOV 内存地址1 寄存器地址1”,“MOV 内存地址2,寄存器地址2”,“ADD 寄存器地址1, 寄存器地址2”,这样最后寄存器地址1中的值就是内存地址1和内存地址2的加和值了。

计算机每天在做的事情其实只不过是数据写入、数据查找、数据计算,不管数据来源是磁盘、网络、键盘,也不管你是在写作、看电影,还是打游戏,无一例外。

最快的写入方式其实就是直接在已经分配过的内存最后的位置直接写,这样可以在避免覆盖已有数据的安全条件下做写入,这种写入效率一定是最高的,因为除了要记录和移动指向分配地址尾部的内存指针没有任何其它的冗余动作。但是再回来找的时候就麻烦了,具体某个数据的地址在哪里?要每个存储单元挨着查找过去才能找到我们要的数据,具体的效率我们在后面的分享中会量化给出来。

最快的查找读取方式,毫无疑问是直接指定一个地址,因为这同样是没有任何冗余动作就能命中所要数据的方式。但是其实这种方式在我们使用高级语言编程的过程中几乎是没有机会碰到的,因为内存地址对于人来说太难管理,只好让编译器帮我们做一次翻译。关于查找的算法,在后面的分享中同样会把每种算法的效率量化给出来。

计算机中的读和写,算法效率高不高,最底层的实现方式都已经给出来了,这就是计算机自己的珠算口诀。一切算法的实现最终落实下来都是用这样的方式组合而成,自然成本估计也就是用成本叠加的方式去计算。

原文发布于微信公众号 - 奇点(qddata)

原文发表时间:2016-06-15

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技评论

开发 | 如何在 i5 上实现 20 倍的 Python 运行速度?

Intel Distribution for Python 在今年二月进行了更新——英特尔发布了 Update 2 版本。以“加速”为核心的它,相比原生 Pyt...

4126
来自专栏我杨某人的青春满是悔恨

如何提高代码品味

写代码虽然大多数时候是个体力活,但不可否认,也需要一点品位。我曾经觉得代码质量很重要,后来写业务写多了,又觉得如果连代码正确都做不到,又谈何代码质量。后来我又醒...

952

为什么我们从Python切换到Go?

切换到新的编程语言向来是关键一步,尤其是当你的团队只有一位成员有该语言的使用经验时。今年年初,我们将 Stream 的主要编程语言从Python 切换到 Go。...

2602
来自专栏牛客网

多篇面经集合,你不容错过的干货!

  5. 写一个单例模式,答主写的是双检查锁单例,问了为什么用 Volatile,synchronize 移到 方法最外面会怎么样?

1222
来自专栏数据结构与算法

博弈论入门之nim游戏

nim游戏 nim游戏 有两个顶尖聪明的人在玩游戏,游戏规则是这样的: 有n堆石子,两个人可以从任意一堆石子中拿任意多个石子(不能不拿),没法拿的...

8549
来自专栏PPV课数据科学社区

【每日一课】R语言入门教程-1.1 认识R

课程名称:R语言入门教程 第一章:认识R 1.1 认识R 【课程目的】 在大数据时代里,数据分析愈发重要,R语言适合做数据分析,R语言已成为许多数据分析...

3435
来自专栏编程派的专栏

提升 Python 编程效率的十点建议

程序员的时间很宝贵,Python这门语言虽然足够简单、优雅,但并不是说你使用Python编程,效率就一定会高。要想节省时间、提高效率,还是需要注意很多地方的。 ...

1.1K0
来自专栏Golang语言社区

Go 的垃圾回收机制在实践中有哪些需要注意的地方?

之前回答问题的时候Go还处在1.1版本,到了1.2和1.3,Go的GC跟踪命令和GC内部实现已经有一些变化,并且根据评论中的反馈,这边一并做补充说明。 Go ...

4836
来自专栏编程一生

JVM知识在离线数据中的运用

1513
来自专栏机器之心

放弃Python转向Go语言:我们找到了以下9大理由

选自Stream 作者:Thierry Schellenbach 机器之心编译 参与:黄小天、李亚洲 转用一门新语言通常是一项大决策,尤其是当你的团队成员中只有...

57911

扫码关注云+社区