刘汝佳教材体系的一个补丁

18 views
Skip to first unread message

LTaoist

unread,
Aug 24, 2019, 8:02:50 PM8/24/19
to 广州 GNU/Linux 用户组
算法艺术与信息学竞赛是国内影响了许多信息学竞赛选手的一个经典作品、某种事实上的教材,虽然如果按照“年龄”来看,这本书其实还是一本十分年轻的作品。

没有刘汝佳先生的这本书,我估计很多信息学竞赛的选手是不会那么早“开窍”的。

书中有一个观点是“时间和空间的互换“,这种观点在竞赛中,某种程度上是普遍有效的。但是其实作为一个严肃的批评,教材的体例有一种”世界消失在时间和空间之中“的倾向。

我在这里提出一个修正:时间、空间、功能的关系应该整体考虑。

情况是这样子的:问题从来没有止步于空间和时间。

更详细地说,我归结为如下:

* 时间、空间、功能,是可以相互转换的。

* 时间换空间,空间换时间。

* 时间换功能,功能换时间。

* 空间换功能,功能换空间。

* 特别地,业务世界许多的是时间换功能,空间换功能。

难以找到刘老师的联系方式,在此记录做一个说明。

莫宇诚

2019.8.25

==================


例子:

时间换功能的例子:

irc中有一个uptime的指令。具体来说,每次机器启动就会开始一个计时器,而uptime指令总是返回已经发生了多久。

这里的问题并不在抽掉了时间和空间的”输入输出“”数据结构“”时间空间“,这里的问题正在于计时器的第一步的有效性(跟现实时间的反应力,并且在后续中能够保持这种反应的正确)。

这里唯一的解释只能是时间换功能。

功能换时间的例子:

通常来说,在旧的体系里,功能有时候是时间,有时候则是空间。从这个角度来说,新的算法就已经是新的功能,虽然在输出输入和运行效率的约束上没变。

例如用表记录了的递归。从单个程序来说,似乎改变不大。但从修改和维护来看,用表记录的递归跟”保存到外部设备“是可以直接衔接的。

功能换时间主要是两重意义上的:(1)改变了的功能带来不一样的时间效率,通常是更快的时间效率;(2)通过功能的改变,来实现不一样的时间形态,这其实是许多新型、功能不一样的数据结构被发明的”一半“(另一半是这种数据结构的空间形式)

空间换功能例子:

从程序和意义的角度来说,空间比时间重要的多。例如GUI程序,大量的算法,实际上是因为新的空间的设想,并且固定了这种空间性的设想,功能才成为可能。

空间换功能有两个方向:闲置空间转换为新的功能,这涉及到新的概念、设计和想象等等;已经支配了的空间的重新分配和安排,进而实现非线性的功能变革。

我们看,状态机在旧体系中通常被认为是系统的一个环节,在这种思维中,状态机是算法的某个环节。但是我们看面向对象整的思路,就是在使系统在空间上完全地状态机化,进而实现了许多的诸如反射、封装这样子的设计。

我们看如果我们不记录GUI程序的”皮肤“,GUI程序就没有”皮肤“,也就无所谓”界面“的实现。如果我们记录了GUI程序的”皮肤,GUI程序的”界面“,作为要求,作为对空间的要求,他们就是新的GUI的功能。

功能换空间例子:

功能为什么能够换空间呢?因为实际上,计算空间某种程度上又的确是于计算时间有关系的,这就有点类似于数据和程序的关系 —— 程序同时也是数据。

例如软的”缓存“。在硬件的意义上,软的缓存并不创造新的物理地址,然而软的缓存创造了新的隔离以及格式化了的对内存的布局或对内存的布局的定义。这实际上是功能模拟着空间。

一个想法的看法是否定性的。这提现为对空间的禁止。例如提供了权限表和按权限的空间使用。这里为什么也换了空间了呢?不难想到,限制是为了使用,直观来看,限制了一个地方而总量不变,实际上就为别的地方扩大了可用的空间。

开源软件中的例子:

在linux,libreoffice这些程序中,到处都是”时间换功能,空间换功能“的例子​​​​

LTaoist

unread,
Aug 24, 2019, 8:13:18 PM8/24/19
to 广州 GNU/Linux 用户组
而且似乎有理由修改复杂度理论:

* 时间复杂度
* 空间复杂度
* 编程复杂度
* 维护复杂度
* 衔接复杂度

编程复杂度和维护复杂度在许多地方可以说已经成为一种“广受注目的灾难”。

衔接复杂度跟编程复杂度、维护复杂度是不同的。有的地方衔接容易,但是编程复杂;有的地方,维护和衔接根本简直已经是两个问题。前者如简单的平台迁移到复杂的平台,衔接可能不难,但是编程可能复杂得多了(编程复杂度不一定是坏事,甚至是某种商业手段);后者如第一次迁移的所必要的衔接的成本,和以后的维护成本。

迁移复杂度实际上并不总能化为衔接复杂度和维护复杂度,例如我们对迁移后的了解并不透彻的话。而衔接复杂度某种程度上是比迁移更为低级的问题(因而可能是更重要的)。


在 2019年8月25日星期日 UTC+8上午8:02:50,LTaoist写道:

LTaoist

unread,
Aug 24, 2019, 8:14:57 PM8/24/19
to 广州 GNU/Linux 用户组
衔接复杂度是一个很重要的问题。


在 2019年8月25日星期日 UTC+8上午8:02:50,LTaoist写道:
算法艺术与信息学竞赛是国内影响了许多信息学竞赛选手的一个经典作品、某种事实上的教材,虽然如果按照“年龄”来看,这本书其实还是一本十分年轻的作品。
Reply all
Reply to author
Forward
0 new messages