0%

序列的最大子序列和问题,说的是:给定一个包含若干整数(正负不限)的序列,寻找其中的一个子序列,使得该子序列元素之和在所有子序列的和中最大。

这一经典的问题,可由动态规划(中的 Kadane 算法)在 $O(n)$ 的时间内解决。

如果我们将给定的序列首尾相连,成为一个环状列表。同样的问题,就变得复杂起来。不过,在巧妙的思路下,问题仍然可以在 $O(n)$ 时间内解决。

下面我们先复习一下 Kadane 算法;然后看看怎样在线性时间内,解决循环列表中的最大子序列和问题。

阅读全文 »

工作中遇到一些需要做集合运算的场景。这种时候,写个 Python 脚本当然是个选择;然而,我却嫌弃太重量级。因此,在 Linux 工具中寻找到了能够胜任这一工作的 sortuniq 两个命令。

阅读全文 »

公认的计算机之父是阿兰·图灵在 1936 年提出了「图灵机」的概念。图灵机是一个抽象的计算模型,它可以形象地表述为:

  1. 有一个向两端无限延伸的带子,可以在上面记录内容
  2. 有一个可以在带子上擦除/写入的读写头,可以在带子上任意移动
  3. 有一个控制器,控制读写头的移动和擦除/写入操作

图灵机的表述看似纸上谈兵,但实际与现在计算机的体系结构有良好的对应,甚至可以说是所有现代计算机背后的灵魂。

  1. 带子对应于内存(当然内存不能无限大,这限制了计算机的处理能力是有上限的)
  2. 读写头可以在带子上任意移动读写对应内存的随机存取(内存的英文名字就是 Random Access Memory)
  3. 控制器对应中央处理器

在内存这条带子上,找到正确的位置以便进行存取的过程,就是所谓的「内存寻址」过程。在图灵机这个思想模型中,我们可以假设读写头可以按照要求立即在带子上找到正确的位置。但是在现实生活中,有效地内存寻址是必须要解决的问题。因此,内存寻址可谓是计算机体系结构的核心问题之一。

这篇文章主要讨论 Intel x86 架构上的内存寻址问题。纯干货,吃到撑。

阅读全文 »

先来个背景音乐。

简介

想必读者对编程中的「变量」、「实例(对象)」不会陌生。

变量和实例对应的,是一些有意义的数据。这些数据,在不同编程语言中,可能有不一样的表现;在不同操作系统中,也可能有不一样的形式。现代计算机应用,不可避免地会涉及到多个模块/程序之间的数据交换、不同语言之间的相互协作、计算机之间的数据交互。如果依着操作系统和编程语言的特性,用不同的形式去实现同样的数据,那整个计算机世界就会乱了套了。

数据的序列化和反序列化,就是为了解决这个问题而诞生的。

序列化是说,将变量和实例这些数据,依照某种约定,转化(通常伴随着压缩)为一种通用的数据格式;转化后的数据,可以用来储存或者传输,以备下次读取使用。其中提到的格式可以是二进制的,也可以是字符串式的。反序列化,就是上述过程的补集:将序列化的数据读入,解析为编程语言可识别的数据结构的过程。

阅读全文 »