承认或不承认有不可数集这个东西, 倒有点哲学的味道, 而非证明这样数学上的东西. --- 我自己说的.
这篇文章算不得很数学的研讨文章, 用开源许可证里面经常用到的措辞就是它 AS IS.

无限集的数量概念

在离散数学中, 集合论部分中有个证明, 给出了两个不那么跟经验相符的说法

整数跟有理数一样多
实数比有理数多 (自然也就比整数多)

对于无穷数量的比较, 日常的说法就是, 给定无限集合 A 跟 B, 如果每从 A 里面拿出来一个东西, B 里面都相应地能拿出一个东西, 那么至少 B 中元素个数不会比 A 中元素数目少; 如果反过来也成立, 那么 A 跟 B 在元素个数上相同.
按照上面的思路, 前面一个断言的证明多种多样. 首先经验告诉我们有理数集 Q 不会比整数集 Z 中的元素少 (因为 Z 是 Q 的子集); 反过来, 从 Q 中拿出任何一个数 X/Y, 其中 X Y 分别在用二进制表示为

X = ...x_nx_n-1...x₃x₂x₁x₀
Y = ...y_ny_n-1...y₃y₂y₁y₀

那么必然可以在 Z 中找到数

K = ...x_ny_nx_n-1y_n-1...x₁y₁x₀y₀

与之对应, (并且不同表示的有理数对应的整数一定是不同的,) 因此 Z 中元素也不少于 Q. 命题得证.

常见于对角线方法的误解

而为了证明实数集 R 中元素多于 Z, 康托尔引入了称为对角线方法的证明方式. 对于这个证明方法如果叙述不严谨, 容易出现误解. 对角线方法不准确地阐述方式包括如下不准确的步骤

反证法: 假定实数区间 [0, 1) 是可数无限的
将这个区间中的元素按照某种方式排列成一个序列, 它与自然数一一映射
构造一个数 S, 它与这个序列中第 1 个数在小数点后第 1 位不同, 而与第 2 个数在小数点后第 2 位不同, ...
那么 S (很) 可能不是一个有理数, 但一定是一个实数, 并且与列表中任何一个实数的值不同
因此产生矛盾, 假定的条件不成立.

即证: 实数集不是可数的.

上述描述容易导致如下的误解

(S 真的不在列表中吗?) 两个数表现不同, 但它们的值可以是相同的. 比如构造出的 S=0.8999... 而列表中有 0.9000... 存在, 实际上这两个数虽然长得不一样, 值却是相同的.
(要花多久构造这个 S?) 如果让一台图灵机来干这个活计, 当然是 --- 无限久. 一个定理的破证明需要无穷多个步骤, 那还叫证明么? 四色定理的证明都比这强.

看这个看多了, 久而久之当然就不确信对角线方法的靠谱度.

勘误

问题描述

第一个误解是因为每次讲到这货, 书上 (甚至维基百科也如此) 偏偏要拿实数集来搞事. 其实还是回归证明的本质 (证明可数集的幂集的基数严格大于该可数集的基数), 只要设某个可数集 T (不一定是整数集之类的) 的幂集 p(T) 是可数的, 并且可列出一张表, 然后构造出一个 T 的子集不存在于这张表里面, 构造的要点当然也是.
因此, 首先明确要证明的是: 给定一个可数集 T, 如 {t₀, t₁, ... }, 它的幂集中元素的个数严格大于 T 中元素的个数.

证明

第二个误解不过因为大部分凡人数学家将自己限制到无论什么都得眼见为实, 对于搞数学这确实不是个好事情, 不过有些人 (譬如我) 就爱这样搞. 如果不喜欢, 只须谨记: 只要否定皇帝新衣的不可见性, 它就是可见的. 这才是超凡逻辑学家应有的节操.
那么证法变为如下

Created at 2012-09-14 19:05:30

Permanent Link: /p/496/

Post tags:

基本概念与构成

    MIDI 是一种音频格式, 它用来描述声音在什么时间以什么音色多高的音调被发出或终止.
    一个 MIDI 文件中通常包含多个音轨 (track), MIDI 文件可以配置多个音轨以并行方式播放还是串行方式播放, 一般应用上多个音轨当然是同时播放比较好.
    为什么要有多个音轨呢? 这个... 写代码的时候一般也不会把所有代码塞在一个函数里面吧.
    而一个音轨就是一系列事件构成的. 事件包括了演奏或停止直接与发声有关的, 以及换乐器这样的控制指令.

文件内容组成

MIDI 文件全景可以用下面的产生式来描述.

MIDI =>
    文件头部信息 音轨集

# 至少得有一个音轨
音轨集 =>
    音轨 音轨集
    |
    音轨

下面解释其中的细节.

文件头部信息详情

文件头部信息 =>
    "MThd" 0x00000006 音轨类型 音轨数 节拍描述

    任何 MIDI 文件开头都由 "MThd" 四个字母 ASCII 码构成.
    接下来 0x00000006 是一个四字节类似大端码表示的整数 (是 0x00 0x00 0x00 0x06 而不是 0x06 0x00 0x00 0x00), 它的含义是文件头部剩下多少个字节. 本来这东西设计是可变的, 不过实际上后面 "音轨类型" "音轨数" "节拍描述" 每个都是固定的 2 字节, 因此这里直接填 6 就行.

    音轨类型有三种取值

0 : 只有一个音轨
1 : 多个音轨, 同时播放
2 : 多个音轨, 串行播放

一般来说这个就取 1 (同样编码为 0x00 0x01, 而不是 0x01 0x00, 后面的音轨数, 节拍描述同样).

音轨数也是一个 2 字节整数, 表示后面实际含有的音轨数量.
节拍描述是一个 2 字节整数, 表示一个四分音符 tick 数. (本人没学过乐理, 这信息是照搬过来的)

音轨结构详情

音轨 =>
    "MTrk" 音轨内容长度 事件集 0x00ff2f00

类似整个文件的开头, 音轨开头固定由 "MTrk" 四个字符填充. 此外, 音轨以固定的四字节 0x00 0xff 0x2f 0x00 结尾.
音轨内容长度是 4 字节整数, 大端表示. 这个整数指示音轨中事件集的字节数加上末尾的 0x00ff2f00 填充物这 4 个字节.

事件集与事件结构

事件集 =>
    事件 事件集
    |
    ε

事件 => 相对时间 事件类型 事件参数

相对时间是一个整数, 单位是 tick, 指的是该事件相对于上一个事件延迟多久. 如第一个事件发生在 0x08, 第二个事件的相对时间如果是 0x18, 则实际发生时间会是 0x20.
比较麻烦的是, 这个时间并不是固定字节长度的, 它的构成大概如下:

如果这个数在 0~127 之间, 则用 1 字节表示, 否则
最后一个字节存放这个数对 128 的模, 再将这个数地板除 128 得到的商以递归的方式在前面 (较低位置) 表示
除了最后一个字节, 其它字节最高为均为 1 (这样判别何处结束)

Created at 2012-09-05 18:17:39

Permanent Link: /p/495/

Post tags:

MIDI

Android SDK r20 深坑逃脱

    最近有点不淡定, 一方面是看到 Google Nexus 7 还不错的样子, 另一方面听说已经有达人在 Nokia N9 上成功刷了 JB, 还能打电话 (作为外观控表示被 N9 的设计萌得死去活来), 所以无论如何近期是要入一台 Android 设备了 (嗯, N9 刷 Android 是肯定要进行的, 用 Meego 总感觉... 应用不多不靠谱? 或许是心理作用吧)
    言归正传, 就在这个时候, 想到, 嗯, 咱还是继续来一炮 Android 研发吧.
    所以搞了 JDK 搞了 Eclipse 搞了 ADT 准备开始.

    好了, 新建 Android Application, 映入眼帘的是三个小红叉, 看得我一阵浓重的違和感. 这些是什么东西? 跟以前见过的大不相同啊, 然后我的视线飘到小红叉左边的项目, 如下

Application Name:
Project Name:
Package Name:

Created at 2012-08-25 19:30:24

Permanent Link: /p/494/

Post tags:

Android

Configuration Problem

对象炼金术 - SQLAlchemy 使用 Postgres 数据库

安装 Postgres 与基本配置

Postgres, 或者又称为 PostgreSQL (结尾的小写 s 变成了 SQL) 是一个功能强大的数据库.
在 ubuntu 下安装

# apt-get install postgresql

其它发行版应该差不多. Windows 用户请自行解决.

安装完成之后, 系统中会多出一个名为 postgres 的用户, 这个用户用于登录数据库. 但无法直接用该用户在 shell 或 xdm 中登录, 须先用其它用户登录 shell, 然后 su 到该用户. 先为该用户设置一下密码

# passwd postgres

再切换到该用户

me@host:~$ su postgres
Password:
postgres@host:/home/me $

如果当时处在某个用户的 home 目录, 如 /home/me 下, 则命令行会弹出一行错误信息
could not change directory to "/home/me"
因为 postgres 这个用户无法读取当前用户的 home 目录. 觉得讨厌的话可以

$ cd /

此时在命令行输入指令进入 Postgres 交互环境

$ psql
psql (version number)
Type "help" for help.

postgres=# input instructions here

这样会以 postgres 用户身份登录, 如果要输入密码就输入刚才为 postgres 用户设置的密码.

这时 postgres 用户相当于数据库的根用户, 就像 root 用户之于 Linux 系统一样, 直接让应用程序使用 postgres 用户是比较危险的. 下面新建一个用户 "psuser", 密码为 "qwerty"

postgres=# CREATE USER psuser WITH PASSWORD 'qwerty';
CREATE ROLE

当然 Postgres 是不区分大小写的. 不过这里 (包括下文) 中将以全大写标明这些是关键字, 而小写的部分是可替换的. 密码需要用引号包围起来.

然后再建立一个新数据库, 并授权 psuser 这个用户可以使用该数据库

postgres=# CREATE DATABASE mydb;
CREATE DATABASE
postgres=# GRANT ALL PRIVILEGES ON DATABASE mydb TO psuser;
GRANT

这样就差不多好了. 下面开始搞 Python 与 SQLAlchemy 部分.

如果上面每个句子输入之后没回显结果, 并且交互环境开头变为了 postgres-# (注意 # 前是一个减号而非等号), 请查看一下句尾的分号是否漏掉了.

使用 SQLAlchemy 连接 Postgres

有关 SQLAlchemy 的基本使用请见这里.
编写这样一段 Python 代码, 来测试 Postgres 数据库连接是否可用

Created at 2012-07-30 13:04:32

Permanent Link: /p/493/

Post tags:

Postgres

Python

SQLAlchemy

使用 Python 2.7 作为 GAE 运行时

GAE 支持 Python 2.7 也有段时间了, 考虑到 2.7 加入了很多有意思的东西, 其中一些特性是先在 Python 3 里面出现, 然后移到 2.7 里面来的, 如

有序字典 (而非默认的散列字典) 类型, 如 collections.OrderedDict({ 1: 'abc', 2: 'def' })
集合类型字面常量, 如 { 1, 2, 3 } (以前版本写作 set([1, 2, 3]))
字典及集合类型的推导式 (这么翻译准确么? Set / dictionary comprehensions), 如 { x: x * x for x in range(5) }

要简单地将运行时环境切换到 Python 2.7 版本, 需要修改 app.yaml 为如下形式

application: YOUR APP ID
version: YOUR APP VERSION
runtime: python27
threadsafe: false
api_version: 1

此外需要修改应用程序启动代码, 类似如下方式

from google.appengine.ext import webapp
from google.appengine.ext.webapp import template
import wsgiref.handlers
import webapp2

class Index(webapp.RequestHandler):
    def get(self):
        print 'Hello'

if __name__ == '__main__':
    application = webapp2.WSGIApplication([
        ('/', Index),
    ], debug=True)
    wsgiref.handlers.CGIHandler().run(application)

使用 2.7 版本的另一个好处是 GAE 上为 2.7 版本提供了很多库支持, 包括 jinja (这样就可以摆脱 django 模板了 :-). 如果需要引用 jinja2 库最近版本, 需要在 app.yaml 中加入以下内容

application: YOUR APP ID
version: YOUR APP VERSION
runtime: python27
threadsafe: false
api_version: 1

handlers:
- url: /.*
  script: main.py

libraries:
- name: jinja2
  version: latest

libraries 下面还可以附上其它想要使用的库. 在此处可以查看所有 Python 2.7 运行时所支持的库.

Created at 2012-07-30 12:59:13

Permanent Link: /p/492/

Post tags:

Google AppEngine

Python

模板之工 - Mako 上手篇

简介

Mako 是一个 Python 模板程序. 用于给定一个字符串, 或给定一个文件, 使用 Python 对象值动态地替换其中的一部分内容.

可是使用 pip 或 easy_install 安装 Mako 库.

# pip install Mako
# easy_install Mako

使用

基本文本替换

安装完成后, 在交互环境中可以通过下面的代码来测试 Mako

>>> import mako.template
>>> print mako.template.Template('Hello, ${ what }!').render(what='Mako')
Hello, Mako!

上述代码中, 引入 Mako 模板模块, 并使用模板对字符串 Hello, ${ what }! 中的动态内容进行替换. 动态内容是形如 ${ what } 这样的 Mako 标记, 它表示将传递给 render 函数的字典中, what 对应的项的值替换这个标记. 因此上面的 render 结果便是 Hello, Mako!.

替换文件中的动态内容

更多的应用场景是将需要生成的内容写成一个文件模板 (如 HTML 页面), 读取这个页面并生成结果内容. 在当前目录下创建 hello-mako.html 文件, 内容如下




Dear ${ username }, welcome back!

并使用如下的 Python 代码

import mako.template
templ = mako.template.Template(filename='hello-mako.html')
print templ.render(username='Mako')

就能看到输出的结果 HTML 代码了.

使用中文及指定编码

上面的页面模板代码中如果包含中文或其它非 ASCII 字符, 如



你好, ${ username }, 欢迎回来!

那么这一段程序在构造 mako.template.Template 对象时多半会挂掉. 要为 Mako 模板指定输入编码方式才行

import mako.template
templ = mako.template.Template(filename='hello-mako.html', input_encoding='utf-8')
print templ.render(username=u'柑奈')

分支

接下来, 如果这个用户是个管理员用户, 那么希望为这个用户呈现一个后台管理的入口 (当然其它用户就没这个福利了), 那么可以用 Mako 提供的分支来实现

你好, ${ username }, 欢迎回来!

%if is_admin:
    管理页面
%endif

并使用如下语句分别测试

templ = mako.template.Template(filename='hello-mako.html', input_encoding='utf-8')
print templ.render(username=u'柑奈', is_admin=False)
print templ.render(username=u'柑奈', is_admin=True)

%if %endif 之间表示一段分支. 如果确实需要书写一个百分号, 而不是作为 Mako 的指令符号, 那么此处须连续两个百分号 %% 来转义, 通常页面上似乎也不会出现那么多百分号, 所以这个应该还是可以接受的吧.

关于分支, 更详细的例子是

%if condition_a:
    do_a
%elif condition_b:
    do_b
%else:
    do_c
%endif

对象式引用

Created at 2012-07-30 12:37:19

Permanent Link: /p/491/

Post tags:

多态泛型不两全 - 面向对象中的协变与逆变

在面向对象语言中, 子类覆盖父类中的实例成员函数时, 可以酌情修改返回值类型, 使之变得更加具体. 比如在 C++ 中, 下面的代码是可行的.

Code Snippet 0-0

class base {
public:
    virtual base* copy() const
    {
        return new base;
    }
};

class inherit: public base {
    virtual inherit* copy() const
    {
        return new inherit;
    }
};

因为 inherit* 类型可以无压力转换为 base* 类型, 所以这样做并不会破坏多态机制. 这种做法称之为协变 (covariance).

然而协变一方面满足着面向对象设计的种种需求时, 另一方面与泛型的协作却非常糟糕, 比如如果尝试使用自动指针取代上述代码中的返回值类型就不正确了

Code Snippet 0-1

class base {
public:
    virtual std::unique_ptr

 copy() const
    {
        return new base;
    }
};

class inherit: public base {
    virtual std::unique_ptr
 copy() const
    {
        return new inherit;
    }
};

编译这一段代码会得到类似如下的错误

invalid covariant return type for 'virtual std::unique_ptr inherit::copy() const'

简而言之, std::unique_ptr 与 std::unique_ptr 并无实质上的继承关系, 因此无法如此重定义子类函数的返回类型.

这并不是语言层面出现的疵漏, 如果这确实可行, 反而还会引起问题, 举个例子

Code Snippet 0-2

class fruit {};
class apple: public fruit {public: void do_something_as_apple();};
class banana: public fruit {public: void do_something_as_banana();};

int main(void)
{
    std::unique_ptr a(new apple);

    /* 如果子类的自动指针对象是可以为父类的自动指针的引用直接引用
       也就是说下面这一句合法 */
    std::unique_ptr& f = a;

    /* 接下来利用 f 来重置内部的裸指针 */
    f.reset(new banana);

    /* 由于 f 就是 a 的引用, 因此 a 中的裸指针指向了
       与 apple 类型不兼容的 banana 的实例 */
    a->do_something_as_apple(); // 謎の結果
    return 0;
}

因此, 这种利用自动指针绕着弯子来造错误的行为是绝对不被允许的. 此外, 下面的这种赋值方式 (虽然明显看起来很怪异) 也是不被允许的

int main(void)
{
    inherit* i;
    base*& b = i; // 跪
    return 0;
}

在之前的一篇文章也有简单介绍到, 不过当时说的是父类的二级指针不能被子类二级指针所赋值.

除了指针之外, 可以想象数组, 包括 STL 容器也会纷纷中枪, 比如 std::vector 类型的引用是无法引用 std::vector 类型的对象的.

在 Java 语言中, 为了缓解这个问题, 引入了泛型通配符. 这个名字听起来就很语死早, 又是泛又是通配, 不过程序设计世界就是这么充满纠结. 下面是 Java 中的解决方案

Created at 2012-05-15 00:44:54

Permanent Link: /p/490/

Post tags:

C++

Java

面向对象程序设计

风之力 - Tornado 搭建基于 WebSocket 的聊天服务

这年头 Python web 框架是有点泛滥了. 下面要介绍的是 facebook 的开源框架 tornado. 这东西比较简单, 而且自带 WebSocket 支持, 可以用它做个简单的聊天室.
读者最好已具备 Javascript 与 WebSocket 的基础知识.

安装

使用 easy_install 能很方便地爬到 tornado. 或者, 下载源代码, 解包后在源码目录执行

$ python setup.py build
# python setup.py install

即可.

开张

首先还是来个 hello world.

import tornado.web
import tornado.ioloop

class Index(tornado.web.RequestHandler):
    def get(self):
        self.write('
Hello, world!')

if __name__ == '__main__':
    app = tornado.web.Application([
        ('/', Index),
    ])
    app.listen(8000)
    tornado.ioloop.IOLoop.instance().start()

保存为 main.py, 然后执行

$ python main.py

并访问 http://localhost:8000/ 即可看到页面中的 "Hello, world!".

在分支中定义的 app 在构造时接受的一个列表参数

[
    ('/', Index),
]

用来配置 URL 映射, 比如这里访问根路径则映射至 Index 实例去处理, 在 Index 实例中, 定义的 get 方法将会处理请求.

处理 WebSocket 连接

添加请求处理类

接下来就进入 WebSocket 环节. 先修改返回的页面, 让这个页面在加载后连接服务器.

class Index(tornado.web.RequestHandler):
    def get(self):
        self.write('''






        ''')

修改这个类后, 然后在控制台中止服务器 (猛击 Ctrl-C), 并重新启动之.
现在, 访问 http://localhost:8000/ 会遇到 404 错误, 因为 WebSocket 请求的 URL "ws://localhost:8000/soc" 还没有映射任何处理器, 因此这里需要再添加一个, 用于处理 WebSocket 请求的类.

import tornado.websocket

class SocketHandler(tornado.websocket.WebSocketHandler):
    def open(self):
        self.write_message('Welcome to WebSocket')

并为这个类加上 URL 映射

if __name__ == '__main__':
    app = tornado.web.Application([
        ('/', Index),
        ('/soc', SocketHandler),
    ])
    app.listen(8000)
    tornado.ioloop.IOLoop.instance().start()

然后重启服务器, 并访问 http://localhost:8000/ 就可以在页面上看到服务器传来的信息了.

使用模板

Created at 2012-04-23 17:58:27

Permanent Link: /p/489/

Post tags:

对象炼金术 - SQLAlchemy 多外键关联同一实体类

    继续上节 SQLAlchemy 外键的探索.
    假设现在需求改变了, 需要给每个 Album 加个字段表示作词者, 而作词者本身也应是 Artist 的实例 (比如很多演唱者会自己为歌曲作词编曲等等), 这时 Album 会有超过一个关联到 Artist 的外键.
    如果仅仅简单如下处理

class Album(Base):
    __tablename__ = 'album'
    album_id = sqla.Column('id', sqla.Integer, primary_key=True)
    name = sqla.Column('name', sqla.String)
    artist_id = sqla.Column('artist', sqla.ForeignKey('artist.id'))
    artist = sqlorm.relationship(
          Artist,
          backref=sqlorm.backref('albums', cascade='all,delete-orphan'))
    lyricist_id = sqla.Column('lyricist', sqla.ForeignKey('artist.id'))
    lyricist = sqlorm.relationship(
          Artist,
          backref=sqlorm.backref('written_albums', cascade='all,delete-orphan'))

然后添加一点数据进去

def save():
    artist0 = Artist(name='aki misawa')
    artist1 = Artist(name='katou emiri')
    artist2 = Artist(name='yamada hirosi')
    album0 = Album(name='stella musica', artist=artist0, lyricist=artist0)
    album1 = Album(name='hoshikage no ama no hara', artist=artist0,
                   lyricist=artist0)
    album2 = Album(name='jump!', artist=artist1, lyricist=artist2)
    session = Session()
    try:
        session.add(album0)
        session.add(album1)
        session.add(album2)
        session.flush()
        session.commit()
    finally:
        session.close()

if __name__ == '__main__':
    save()

结果运行立即悲剧, SQLAlchemy 会报下面的错误

sqlalchemy.exc.ArgumentError: Could not determine join condition between parent/child tables on relationship Album.artist. Specify a 'primaryjoin' expression.  If 'secondary' is present, 'secondaryjoin' is needed as well.

也许这是 SQLAlchemy 的问题, 明明这么明了的外键关系咋就跪了呢.

好吧, 简单的正确答案是, 手动配置一下外键的 primaryjoin 属性, 如下

Created at 2012-03-14 12:44:02

Permanent Link: /p/488/

Post tags:

对象炼金术 - SQLAlchemy 中关系的级联

在上一节中谈到了如何把有关联的对象一起塞进数据表中, 现在来试试从数据表里面取出一条数据然后删掉.
在之前代码的基础上添加下面的函数

def remove_album(name):
    session = Session()
    try:
        for a in session.query(Album).filter(Album.name == name).all():
            session.delete(a)
        session.flush()
        session.commit()
    finally:
        session.close()

在这个函数中, 查询 Album 类型, 然后调用查询对象的 filter 函数, 指定列 name 的值严格等于该 name 参数. 接下来, 将查询得到的对象逐个删除.
来看看搞起来如何

if __name__ == '__main__':
    save()
    remove_album('stella musica')
    list_all()

嗯, 看起来还不错的样子.

那么, 接下来试试删 Artist

def remove_artist(name):
    session = Session()
    try:
        for a in session.query(Artist).filter(Artist.name == name).all():
            session.delete(a)
        session.flush()
        session.commit()
    finally:
        session.close()

if __name__ == '__main__':
    save()
    remove_artist('katou emiri')
    list_all()

于是乎就悲剧了.
崩盘之前的几行输出似乎是这样子的

= Albums =
stella musica
+ Artist: aki misawa
hoshikage no ama no hara
+ Artist: aki misawa
jump!
+ Artist:

也就是说, remove_artist 确实从数据库中删去了名字为 'katou emiri' 的那个值, 因此名为 'jump!' 的那个 Album 实例的 artist 域成了 None, 悲剧就发生了.

要解决这个问题, 就得在 Album 与 Artist 的关联关系上动动手脚, 加上级联信息.

Created at 2012-03-13 13:44:15

Permanent Link: /p/487/

Post tags:

对象炼金术 - SQLAlchemy 从外键到关系

上节回顾, 使用下面这样的代码保存一个 Artist 与一个 Album, 两条 flush 令人感觉相当不适.

def save():
    artist = Artist(name='aki misawa')
    session = Session()
    try:
        session.add(artist)
        session.flush() # 0
        album = Album(name='stella musica', artist_id=artist.artist_id)
        session.add(album)
        session.flush() # 1
        session.commit()
    finally:
        session.close()

单纯一个外键还不能很直观地解决对象之间的关联关系. 下面就引入 sqlalchemy.orm.relationship 来改善这块代码.

import sqlalchemy as sqla
import sqlalchemy.orm as sqlorm
from sqlalchemy.ext.declarative import declarative_base as sqla_declarative_base

Base = sqla_declarative_base()
# use MEMORY, not a database file.
# and disable SQL echo
engine = sqla.create_engine('sqlite:///:memory:', echo=False)

class Artist(Base):
    __tablename__ = 'artist'
    artist_id = sqla.Column('id', sqla.Integer, primary_key=True)
    name = sqla.Column('name', sqla.String)

class Album(Base):
    __tablename__ = 'album'
    album_id = sqla.Column('id', sqla.Integer, primary_key=True)
    name = sqla.Column('name', sqla.String)
    artist_id = sqla.Column('artist', sqla.ForeignKey('artist.id'))

    artist = sqlorm.relationship(Artist)

在类 Artist 与 Album 定义完成后, 再用 relationship 为 Album 补上一个类成员, 表示它与 Artist 之间的关系.

这样一来, SQLAlchemy 就能根据此 relationship, 从对象关系中产生外键值, 比如之前的 save 函数可以变成这个样子

Session = sqlorm.scoped_session(sqlorm.sessionmaker(bind=engine))

def save():
    artist = Artist(name='aki misawa')
    album = Album(name='stella musica', artist=artist)
    session = Session()
    try:
        session.add(album)
        session.flush()
        session.commit()
    finally:
        session.close()

Created at 2012-03-12 17:31:04

Permanent Link: /p/486/

Post tags:

对象炼金术 - 体验 SQLAlchemy

一直听说 SQLAlchemy 是个神一般的 ORM, 近期终于忍不住打算搞一搞, 还是小有收获的, 写一点出来, 欢迎大家来搞.
本文中的例子都是基于 Python 2.7, SQLAlchemy 0.7 的. 数据库使用 SQLite.

废话少说, 先来一段代码

import sqlalchemy as sqla
import sqlalchemy.orm as sqlorm
from sqlalchemy.ext.declarative import declarative_base as sqla_declarative_base

Base = sqla_declarative_base()
engine = sqla.create_engine('sqlite:///test.db', echo=True)

class Artist(Base):
    __tablename__ = 'artist'
    artist_id = sqla.Column('id', sqla.Integer, primary_key=True)
    name = sqla.Column('name', sqla.String)

Base.metadata.bind = engine
Base.metadata.create_all()

Session = sqlorm.scoped_session(sqlorm.sessionmaker(bind=engine))

def save_artist():
    artist = Artist(name='aki misawa')
    session = Session()
    try:
        session.add(artist)
        session.flush()
        print 'Artist id:', artist.artist_id
        session.commit()
    finally:
        session.close()

if __name__ == '__main__':
    save_artist()

运行这一段代码将会在当前目录创建 test.db 文件作为数据文件, 同时建立一个 Artist 表, 其中有主键字段 artist_id 跟表示名字的字符串列 name. 然后向这个表中插入一个对象, 并输出这个 artist 的 artist_id
在这一行

Base = sqla_declarative_base()

产生了 SQLAlchemy 中用于构造表的基类. 而接下来 create_engine 调用则绑定数据库以及文件, 并设置回显 SQL.

然后重头来了, 声明类型 Artist

class Artist(Base):
    __tablename__ = 'artist'
    artist_id = sqla.Column('id', sqla.Integer, primary_key=True)
    name = sqla.Column('name', sqla.String)

以及类成员 __tablename__ 表示表名, 接着以整数类型声明主键, 以及另一列 name 为字符串类型. 不用 varchar 真心舒畅.

接着两句

Base.metadata.bind = engine
Base.metadata.create_all()

则是在数据库中建立表. 如果已经建立 (譬如第二次运行这个例子), 删去这两句似乎也没问题.
虽然没看 SQLAlchemy 的实现, 但是构建 Base 类, 以及调用 create_all 建表有点多此一举的感觉. 我还是比较喜欢 GAE 存储那种直白的风格.

后面的

Session = sqlorm.scoped_session(sqlorm.sessionmaker(bind=engine))

Created at 2012-03-09 22:46:26

Permanent Link: /p/485/

Post tags:

基于 B/S 的桌游设计 - 游戏状态控制

三国杀结算模型

    考虑在游戏过程中, 某君使用万箭齐发, 对司马懿造成一点伤害, 司马懿发动反馈, 此时游戏暂停, 等待司马懿选择卡牌区域 (手牌或装备). 而在司马懿选择了反馈的卡牌区域后, 后续的玩家需要继续响应万箭齐发. 在万箭齐发结算完毕后, 回到某君的出牌阶段继续出牌或选择弃牌.
    好吧, 仔细看一下, 这就是个栈.
    题外话, 三国杀对延迟锦囊的判定顺序也是个栈, 后来的先判定.
    现在的问题就是怎么来表示这个游戏状态栈.

栈帧

天下的栈大抵都一个样, 关键还是在于其中的帧是个什么样子的. 首先帧必须能够接受玩家的输入, 以推进游戏状态; 其次, 每个帧只能接受特定玩家的输入, 比如司马懿发动反馈时, 其他玩家是不能决定反馈区域的. 那么, 帧的声明可能会像这个样子

class FrameBase:
    def react(self, args):
        pass # response to player's action

    def allowed_players(self):
        return [] # which players are allowed

其中, react 函数的参数 args 就是在之前提到的, 从浏览器端传来的 JSON 解析后的字典数据.
另外, 当浏览器, 也就是客户端程序向服务器请求 hint 时, 服务器应该给出当前栈顶帧所对应的 hint. 因此, 每个帧都必须还能获得 hint 数据

class FrameBase:
    # other functions

    def hint(self, token):
        if token in map(lambda player: player.token, self.allowed_players()):
            return {} # detail info
        return {} # just who are active players

栈

虽然说栈大抵都一样, 不过一些必须的功能还是得手动引进, 很关键的就是帧退栈时的动作, 以及如何使帧和帧之间可以传递信息. 下面是结算栈的架子

class ActionStack:
    def __init__(self):
        self.frames = []

    def call(self, args):
        return self.frames[-1].react(args)

    def allowed_players(self):
        return self.frames[-1].allowed_players()

    def hint(self, token):
        return self.frames[-1].hint(token)

    def push(self, frame):
        self.frames.append(frame)

    def pop(self):
        stack_top = self.frames.pop()
        # pass something from stack_top to current stack top

实现这个 pop 剩余的部分, 需要理清下面的问题

怎么获得之前栈顶的结果
结果怎么被传递给当前栈顶
pop 本身由谁在什么时机来调用

Created at 2012-03-08 17:08:42

Permanent Link: /p/484/

Post tags:

前言

    虽然我觉得国内桌游的始祖可能国粹麻将什么的, 不过貌似这个词在三国杀风靡之后才被正式使用. 这系列文章中, 我也打算使用三国杀来做样例项目, 分析 B/S 结构的桌游设计方式.
    按惯例, 首节内容应该是纯吹水而无码的. 这里就先拔一拔目前比较靠谱的三国杀实现.
    其一是我很敬佩的一个民间 MOD 版本太阳神三国杀, 武将比官网的全, 还有自制武将, 卡牌, 以及各种趣味度爆表的模式. 不过太阳神三国杀是 C/S 一体的, 与我想要设计的并不很搭边.
    另一就是官方的三国杀, 使用 Adobe Flash 制成 (桌面版似乎用的 Adobe Air), 所以也并不能严格算是 B/S 结构. 并且官方版本也不是开源或者开放 API 的, 很难一窥其究竟, 没什么好借鉴的.
    移动终端的三国杀就没怎么实测过了, 我本身也不是智能或智障手机爱好者, 对这方面也不是太有兴趣.
    读者最好知道三国杀的基本规则, 这样一些具体的例子理解起来会更容易.

B/S 架构的游戏

    继续吹一下水. 对于一般的网络应用, 比如 Google Doc 那样的字处理应用, 大部分的逻辑都在浏览器脚本中, 而即使用户去改了浏览器脚本, 导致保存的文档格式有误, 最终受害者也是用户自身. 而多人连线游戏服务器最起码的一点就是要防止用户作弊, 以免破坏游戏状态影响其他玩家, 因此至少服务器端有一份游戏逻辑是必需的.
    现在的问题是, 客户端 (也就是 Browser 端) 是否也复制一分游戏逻辑呢?
    当然可以, 不过假如要重新开发除了浏览器之外, 能够以相同协议与服务器通信的客户端, 或者开放 API, 使得第三方可以自行开发客户端, 那样必然陷入不断重复开发客户端游戏逻辑的无底洞里.
    因此, 除了尽可能将全部游戏逻辑堆在服务器端, 服务器端还应该尽可能指导客户端, 例如告知当前游戏状态, 以及客户端该如何响应.

服务器职责

好, 吹水结束, 现在理一下, 服务器端应该

完善游戏逻辑, 这是必须的
游戏开始后, 维护游戏状态
接受客户端输入, 返回游戏状态 ^a
接受客户端输入, 返回谁现在应该如何去做什么事情, 这也就是上一部分最后提到的对客户端的指示
接受指定客户端输入, 推进游戏进程

注 a: 向客户端提供状态有方式有直接提供当前游戏的完整状态, 或提供从游戏某个时机开始的一系列状态增量. 前一种方式每次传输的信息量多, 负担较大, 所以这里采用后者.

协议格式

B/S 模式下传递信息可以考虑传递 JSON. 而 Python 跟 JS 一样, 是不需要指定变量类型的, 如果发现转出来的值有任何问题就直接认为客户端发送了错误数据就行了, 所以服务器端用 Python 可以省不少事.
通信内容的具体格式可设计为一个字典, 例如向服务端发送如下信息

{
    'token': '10178a67c867b82392f41c9723cf2daae8fd6ab0',
    'previous event id': 4,
}

此时服务器返回的可能是如下格式的列表

Created at 2012-03-02 22:34:47

Permanent Link: /p/483/

Post tags:

NijiPress

你现在就在浏览 (如果不是通过 Reader 之类的查看这篇文章的话) 我自制的, 山寨 WordPress 的, 实际上挂载在 Google AppEngine 上的, 文章格式完全靠 markdown 的 NijiPress 系统上的文章. (即使通过 Reader, 你看到的文章内容版式也是经由 markdown 转换的结果)
这篇文章将谈谈其中的 markdown 语法.

NijiText

NijiPress 的 markdown 内核叫做 NijiText. 不得不说 NijiText 中有些 markdown 语法确实很非主流, 对于下面出现的各种魑魅魍魉, 还请高抬贵槽.

行中转换

超链接

@@ http://example.org/ @Example@@ ==> Example
语法为 @@链接@文字@@.

强调

将文字包入 strong 标签
**需要加粗的文字** ==> 需要加粗的文字

行中代码

将文字包入 tt 标签
``text im+-*/`` ==> text im+-*/
这里的引号为标准键盘主键区数字 1 左边那个.

上下标

将文字包入 sub 或 sup 标签
,,下标,,
^^上标^^
a,,2,,x^^2^^+a,,1,,x+a,,0,,=0 ==> a₂x²+a₁x+a₀=0

删除线

将文字包入 s 标签
--删除线-- ==> ~~删除线~~

斜体

将文字包入 i 标签
///italic/// ==> italic
因为许多编程语言中, 双斜杠 // 表示单行注释, 为了避免纠结的转义, 所以斜体设计为三个斜杠.

转义

将反斜杠放在与 markdown 语法相关的特殊字符前转义该字符

这段文字 *\* 不会被加粗, *\* 反斜杠本身 \\ 转义 ==> 这段文字 ** 不会被加粗 **, 反斜杠本身 \ 转义

Headings

当某一行由 1~3 个等号 (=) 开头, 且等号后加上一个空格, 那么这些符号之后的内容将被转换为标题.

= Heading 1
== Heading 2
=== Heading 3

代码块

用仅 {{{ 和仅 }}} 将多行内容括起来时, 中间的内容将会变为一个代码块
{{{
code line 0
code line 1
}}}
==>

code line 0
code line 1

ASCII Art

如果一行由一个冒号一个空格开头, 这一行将被解析为一行 AA 内容. AA 内容中的转义字符 (\) 和任何行中转义将被忽略. 连续多个这样的行将被合并为一块 AA 内容.

: . | : |\ | : | \| : | `

==>

. | |\ | | \| | `

表格

用仅 [[[ 和仅 ]]] 将多行内容括起来时, 中间的内容将会变为一个表格, 每行内容将被转换成一个 tr. 中间的单元格用 || 分隔. 下面是一些例子
一般表格:

[[[
||单元格||单元格
||第二行||...
]]]
==>

单元格	单元格
第二行	...

更复杂地, 为单元格加上跨行跨列内容对齐等属性:

[[[
||;hcr2;hori-align 为 top 且跨 2 行||cell
||row 2||...
||row 333333333333333333333333333333||...
]]]
==>

hori-align 为 center 且跨 2 行	cell
hori-align 为 center 且跨 2 行	row 2	...
row 333333333333333333333333333333	...

Created at 2012-02-23 00:28:54

Permanent Link: /p/482/

Post tags:

二叉检索树的查询与检索操作看这里

从二叉检索树中删除一个元素分多个步骤:

找到节点
将节点移动到容易删除的位置
删除节点

找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1.
下面是这一部分的实现

void remove_by(key_type const& key)
{
    remove_by_from(key, &root);
}

void remove_at(int position)
{
    remove_at_from(position, &root);
}

static void remove_by_from(key_type const& key, node** parent)
{
    --((*parent)->load);
    if (key < (*parent)->t.key()) {
        remove_by_from(key, &((*parent)->left));
        return;
    }
    if ((*parent)->t.key() < key) {
        remove_by_from(key, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove_at_from(int position, node** parent)
{
    --((*parent)->load);
    int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
    if (position < left_load) {
        remove_at_from(position, &((*parent)->left));
        return;
    }
    if (left_load < position) {
        position = position - left_load - 1;
        remove_at_from(position, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove(node** n);

这些函数都是 class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改.

找到了节点之后将会有下面 3 种情况

节点是叶子
节点只有一侧子树
节点两侧子树健全

前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)

Created at 2012-01-24 14:42:01

Permanent Link: /p/481/

Post tags:

GAE 速成简易博客 - 简化 RequestHandler

上节回顾 - 进阶数据库操作

在 index.py 和 single_post.py 中, 请求处理器 Index 跟 SinglePost 的代码重复的部分还是挺多的

class SinglePost(webapp.RequestHandler):
    def get(self):
        path = os.path.join(os.path.dirname(__file__),
                            'templates/single_post.html')
        posts = db.GqlQuery('SELECT * FROM Post WHERE pid = :1',
                            int(self.request.get('id')))
        self.response.out.write(template.render(path, {
                'post': posts[0],
            }))

class Index(webapp.RequestHandler):
    def get(self):
        path = os.path.join(os.path.dirname(__file__), 'templates/index.html')
        posts = db.GqlQuery('SELECT * FROM Post ORDER BY date DESC')
        self.response.out.write(template.render(path, {
                'posts': posts,
            }))

作为程序员, 应该对这样的重复代码零容忍, 当机立断, 大刀阔斧来改起!

从上面的对比看来, 很明显, 对于日常情况中的请求, 服务器端重要的的响应参数包括

模板文件的相对路径
交给模板的参数

那么很好, 来弄个基类, 新建个 base.py 放进去

from google.appengine.ext import webapp
from google.appengine.ext.webapp import template
import os

class BaseHandler(webapp.RequestHandler):
    def put_page(self, templ_file, templ_args):
        path = os.path.join(os.path.dirname(__file__), templ_file)
        self.response.out.write(template.render(path, templ_args))

开始用新的 BaseHandler 搞起吧.
先来搞 index.py

Created at 2012-01-23 16:17:09

Permanent Link: /p/480/

Post tags:

堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短

按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构

    前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述.

    较之堆更加全能的索引数据结构非二叉检索树 (binary search tree, 缩写为 BST) 莫属了, 一般的二叉检索树可以很轻松地解决按键索引, 而若将子树节点计数器加诸其上, 就能进行快速的随机索引. 不过, 在这篇文章中, 只讨论理想状态下的二叉树, 不考虑那种被精心准备的数据叉成链表的情况.

    首先还是把二叉树的架子给搭出来

template

class binary_search_tree {
    struct node {
        T t;
        node* left;
        node* right;
        int load;

        explicit node(T const& rhs)
            : t(rhs)
            , left(NULL)
            , right(NULL)
            , load(1)
        {}
    };

    node* root;

    typedef typename T::key_type key_type;
public:
    binary_search_tree()
        : root(NULL)
    {}
public:
    void insert(T const& e);

    void remove_by(typename T::key_type const& key);
    void remove_at(int position);

    T& element_by(typename T::key_type const& key);
    T& element_at(int position);
};

Created at 2012-01-23 14:04:23

Permanent Link: /p/479/

Post tags:

上节回顾 - 表单处理与基本的数据库操作

现在首页能显示文章列表了, 但是

文章的顺序貌似是乱的, 而一般来说, 博客系统会按照发布的时间先后顺序来放置
构造一个页面, 看指定的某一篇文章的内容

那么, 现在就开始修改数据库吧.

为文章加上 ID 和日期

添加属性

修改 model.py

class Post(db.Model):
    pid = db.IntegerProperty()
    title = db.StringProperty(multiline=False)
    content = db.TextProperty()
    date = db.DateTimeProperty(auto_now_add=True)

def put_post(title, content):

其中 pid 表示 post id, 是一篇文章的唯一标识; date 是文章的发布时间, 它被设置为对象被存入数据库时自动设置为当前时间 (auto_now_add=True).
在 GAE 存储中, 并没有类似 auto_increment 的设置, 因此 pid 的管理需手动进行. 在数据库中, GAE 也有给每个对象设置一个全局唯一的 id, 可以通过如 post.key().id() 来获取, 但是这样获取的 id 值在发布服务器上没有规律可言, 不具备有序性, 不建议使用.

按 ID 排序查询和自增 ID

刚刚为 Post 添加的两个属性中, date 是会自动添加到数据库中的, 但 pid 并不会, 得手动给加上. 想要实现自增 ID 的功能, 一个简单的思路是, 从数据库中取出 pid 最大的那篇, 在它的基础上 +1 赋值给新文章即可. 那么继续修改 model.py

def next_post_id():
    posts = db.GqlQuery('SELECT * FROM Post ORDER BY pid DESC')
    return 0 if posts.count() == 0 else posts[0].pid + 1

def put_post(title, content):
    post = Post()
    post.pid = next_post_id()
    post.title = title
    post.content = content
    post.put()

这里 GQL 中的 ORDER BY pid DESC 表示按照 pid 排序, 而且是降序排列.

另外, 还得修改 add_post.py 里的 AddPostHandler 不能让它乱来了, 而应该改为调用 put_post

class AddPostHandler(webapp.RequestHandler):
    def post(self):
      # new_post = model.Post()
      # new_post.title = self.request.get('title')
      # new_post.content = self.request.get('content')
      # new_post.put()
        model.put_post(self.request.get('title'), self.request.get('content'))
        self.redirect('/add_post')

Created at 2012-01-20 20:43:58

Permanent Link: /p/478/

Post tags:

GAE 速成简易博客 - 表单处理与数据存取

上节回顾 - 站点基本配置与模板

没有数据滋养的首页还是个半残废, 下面开始折腾数据库.

添加文章

入口

虽然添加文章这种事情可以直接通过后台暴力搞数据库来做, 但既然要写的是 Web 应用, 那么写个页面提供添加文章的入口也是理所当然的事情.
页面嘛, 肯定得有个 HTML 模板撑着, 来建个文件, templates/add_post.html



Add Post



Title
Content

接下来得增加一个 RequestHandler, 新建文件 add_post.py

from google.appengine.ext import webapp
from google.appengine.ext.webapp import template
import os

class AddPostEntry(webapp.RequestHandler):
    def get(self):
        path = os.path.join(os.path.dirname(__file__),
                            'templates/add_post.html')
        self.response.out.write(template.render(path, dict()))

这个文件看起来与 index.py 差不多, 只不过因为 add_post.html 不需要参数, 因此传入 render 的字典是空字典.

最后在 main.py 中新增一项, 将一个 URL 映射到 AddPostEntry

import wsgiref.handlers
from google.appengine.ext import webapp

import index
import add_post

if __name__ == '__main__':
    application = webapp.WSGIApplication([
        ('/', index.Index),
        ('/add_post', add_post.AddPostEntry),
    ], debug=True)
    wsgiref.handlers.CGIHandler().run(application)

现在访问 http://localhost:8080/add_post/, 就可以看到这个入口页面了. 不过因为表单还没有设置处理者, 因此点破提交按钮就没有反应的.

处理表单

还是得添加一个处理请求的类, 修改 add_post.py, 加入这个类

import model

class AddPostHandler(webapp.RequestHandler):
    def post(self):
        new_post = model.Post()
        new_post.title = self.request.get('title')
        new_post.content = self.request.get('content')
        new_post.put()
        self.redirect('/add_post')

Created at 2012-01-19 12:31:17

Permanent Link: /p/477/

Post tags:

前期准备

目前 GAE 官方推荐的 Python 版本是 2.7 (终于脱离了 2.5 的泥潭啊), 实际上 2.6.x 版本也是没问题的 (写个 CMS 这种简易的设备, 应该还用不到太多高端的语言特性).
GAE 当然也是必不可少的. 下载和安装步骤在 Google Code 上都有详细文档. 如果使用 ArchLinux, 还可以通过 AUR 安装. 这里就不废话了.
找个地方, 建立一个目录, 比如叫做 cms-build, 切到这个目录作为工作目录.
下面开始.

数据结构

既然是写博客, 那么最关键的当然要是文章 (post) 了. 先来建立用于定义数据的源文件 model.py

from google.appengine.ext import db

class Post(db.Model):
    title = db.StringProperty(multiline=False)
    content = db.TextProperty()

每篇文章的基本属性有标题 title, 内容 content 和创建时间 date. 其中标题不允许多行; 而内容使用 db.TextProperty 类型而不是 db.StringProperty (根据 GAE 文档, StringProperty 只能存至多 500 字符).

首页

模板

首先, 将首页给弄出来, 建立目录 templates, 并在这个目录下弄一个 index.html 文件, 内容是



My Blog

{% for post in posts %}
{{ post.title }}
{{ post.content }}
{% endfor %}

    在 GAE 中, HTML 模板文件使用的是 django 的模板语法. 上面文件中, {% for ... %} 到 {% endfor %} 是对传入模板的参数 posts 的迭代. {{ post.title }} 则是对 post 对象的 title 的引用, 而 {{ post.content }} 则是引用 content.
    简而言之 {% xxx %} 是模板中的控制语句, 而 {{ xxx }} 则是引用值. 在 django 官方网站可以看到详细文档, 鄙博客之前也对 django 有过简介.

    这个首页是简单了点, 不过呢, 先看看样子.

视图源文件

光有 HTML 模板还不行, 至少, Python 源代码才是核心. 现在添加一个 Python 源文件 index.py

Created at 2012-01-19 12:30:27

Permanent Link: /p/476/

Post tags:

下面是一个简单的单链表节点结构

struct node {
    int value;
    struct node* next;
};

那么如何将这个链表反转过来呢?
void reverse(struct node* head);

下面采用递归的方式实现, 废话少说, 直接上代码

struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}

上面的实现假定传入的 head 不会是空节点. 如果要检测, 可以加入一个判断

void reverse(struct node* head)
{
    if (NULL != head)
        *_reverse(head) = NULL;
}

下面来验证一下吧

#include


struct node {
    int value;
    struct node* next;
};

void reverse(struct node* head);

void print_list(struct node const* head);

int main(void)
{
    struct node a = { 0, NULL },
                b = { 1, &a },
                c = { 2, &b }; // c(2) -> b(1) -> a(0) -> NULL
    print_list(&c);
    reverse(&c); //    changed to a(0) -> b(1) -> c(2) -> NULL
    print_list(&a);
    return 0;
}

void print_list(struct node const* head)
{
    printf("[");
    for (; NULL != head; head = head->next) {
        printf(" %d", head->value);
    }
    printf(" ]\n");
}

struct node** _reverse(struct node* n)
{
    if (NULL != n->next)
        *_reverse(n->next) = n;
    return &(n->next);
}

void reverse(struct node* head)
{
    *_reverse(head) = NULL;
}

Created at 2011-12-21 13:59:53

Permanent Link: /p/475/

Post tags:

Algorithm

Data Structure

天净沙 – 神社入夜

苍穹尽处云燃
茜霞相伴游园
伫立残阳送远
孤身留眷
待清宵月悄悬

遥观烈绽绯霞
若袭辉烨彤纱
簇抱光晕涣洒
晚风萧飒
叶枝摇似涤砂

长空浅印清瞳
帐帷轻掩天宫
暮霭沉沉郁滃
幽幽归梦
眼帘阖意朦胧

卖文艺了 :D
以上, 翻译自三澤秋老师的 Shinto Shrine, 在这里可以看到歌词 (页面中有整个专辑的歌的歌词, 请搜索 Shinto Shrine), 直至 "とばりが落ちる" 一句.

Created at 2011-12-21 11:58:10

Permanent Link: /p/464/

Post tags:

Tian-jing-sha

Tou-hou

位运算的优先级

在现代计算机程序设计语言中, 每一种成熟的语言都支持许多算符. 对于除了像 Lisp 那样表达式本身以中缀式形式书写的语言, 一般语言都会规定表达式的结合顺序, 也就是算符优先级. 由于语言算符数量的庞大, 算符优先级很难整个记下来, 但是通常有迹可循, 比如看到下面的代码
x = y + z
一般会自然地认为 + 将在 = 之前执行, 这是因为很多语言的编译器设计中, 赋值类运算在算术类运算之后进行, 可以认为这是一个常识, 跟乘除在加减之前进行一样自然. 同理下面的代码
x == y and y == z
x == y + z
很自然地能想到, 比较运算 == 会在逻辑运算 and 之前, 而算术运算 + 应该在比较运算之前.

如果要给算符分个类. 以整数运算为例, 日常二元算符分类的大类应该按照运算结果的类型来分类, 也就是

结果类型	算符
整数	`+ - * / % ^ & \| >> <<`
boolean	`== != < > >= <= or and`

    从结果类型上也可以看出一些端倪, 比如
x == y + z
这个算式, 如果先计算 ==, 此时 + 左边是 boolean, 而右边是个整数, 这样根本没法圆场了. 所以一般来说, 算术运算拥有较高的优先级完全是天经地义的.

    现在的问题是, 位运算 (^ & |) 到底算啥?
    从之前的说法来看, 它们也应该是算术运算的一种. 不过优先级还真不好说. 最近在某个项目中我将一个后台功能转移到前台, 需要把一段 Python 代码转换成 Javascript 代码, 这时发生了一个悲剧: Python 对于位运算优先级的实现与我的个人观点非常接近, 认为时至今日, 位运算是日常的算术运算之一, 因此它们的优先级要高于比较运算, 也就是说
x + y == x ^ y
在 Python 中等价于
(x + y) == (x ^ y)
而与之相对的, Javascript 认为位运算的优先级要低, 甚至低过了比较运算, 因此上述代码在 V8 引擎眼中等价于
((x + y) == x) ^ y
    这种槽点爆表的设计真是坑死爹了. 好吧, 我去溯源一下, 谁家的语言设计这么疼. 结果原来 C 语言老大哥是这么个整法的, 什么 Javascript 还有个跟这名字差不多不过没有 script 的语言这么承袭的. 哎, 你们这么折腾到底图个啥啊.

Created at 2011-10-23 17:29:11

Permanent Link: /p/454/

Post tags:

Created at 2011-10-23 17:21:21

Permanent Link: /p/449/

Post tags:

ASCII Art

Lucky Star

日常的数据结构 - 堆的实现与第 K 最小堆

在前一篇文章中纸上谈了堆的性质以及如何在插入元素和弹出最值时保持这些性质. 这篇文章将聊聊实现方式.
从实现的角度来说, 使用完全二叉树作为堆的前提的好处是, 完全二叉树非常容易实现, 甚至可以说是最容易实现的二叉树. 由于完全二叉树的节点编号是连续的, 那么它可以被拉平, 放进一个日常的数组中, 如

+---+ | 4 | +---+ / \ +---+ +---+ | 5 | | 9 | +---+ +---+ / \ +---+ +---+ | 8 | | 5 | +---+ +---+

这样一棵完全二叉树可以被转换成

.----. /--. \ +---+---+---+---+---+---+----- | - | 4 | 5 | 9 | 8 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

其中的线连接节点与它们的子节点. 如果用节点的编号来标识这个数组, 则会是

.----. /--. \ +---+---+---+---+---+---+----- | 0 | 1 | 2 | 3 | 4 | 5 | ... +---+---+---+---+---+---+----- \______/ / \________/

这里有个很奇妙的性质, 索引为 i 的节点, 它的左子节点的索引是 2i, 而右子节点的索引是 2i+1, 其父节点索引则是 floor(i/2) (根节点除外). 如果用 0 号节点而不是 1 号节点存储根节点呢? 如

.----. /--. \ +---+---+---+---+---+---+----- | - | 0 | 1 | 2 | 3 | 4 | ... +---+---+---+---+---+---+----- \______/ / \________/

也能很容易计算, 索引为 i 的节点, 左子节点索引是 2i+1, 右子节点索引是 2i+2, 父节点索引是 floor((i-1)/2). 似乎也没什么太大区别. 不过, 之前那种计算方式的好处在于, 2i, 2i+1, i/2 这样的算式都能换成极快的位运算: 2i 等效于 i << 1, 2i+1 等效于 (i << 1) | 1, floor(i/2) 等效于 i >> 1, 这还能提供一丁点效率优化 (和一部分代码混乱程度加成, 以及大量的极客自豪感上升).
既然堆的逻辑结构是数组, 那么可以采用 std::vector 作为存储数据结构. 此外, 将比较方式以模板形式抽出, 这样可以构造一个抽象的最值堆, 而不是死板的最大堆或者最小堆. 下面是堆的框架

template

class heap {
    std::vector<_T> array;
    _Less const less;
    typedef typename std::vector<_T>::size_type size_type;
public:
    heap()
        : array(1) /* insert a placeholder, array[0] */
        , less(_Less())
    {}

    void push(_T const& value);
    _T pop();
};

向堆中加入元素实现为插入并修正, 修正的过程, 也就是向父节点方向移动, 是递归实现的

Created at 2011-10-07 18:23:13

Permanent Link: /p/441/

Post tags:

C++ 声称完全兼容了 C, 这一点在某些细节上不尽然. 比如对空结构体 --- 没有成员, 不含虚函数, 虽然 C 还生活在没有虚函数的三叠纪 --- 求 sizeof 的结果. 具体地说就是下面这个表达式

Code Snippet 0-0

struct empty {};

sizeof empty; // 值为 0

在 C 和 C++ 中会得到不同的值: C 中其值为 0 (在主流编译器中如此), 而 C++ 中其值为 1. 这个微妙的不同步源于 C 中的一个指针相减问题, 如下代码

Code Snippet 0-1

#include 


struct empty {};

int main()
{
    struct empty x;
    struct empty y;
    printf("%ld", &x - &y);
    return 0;
}

以 C 语言编译并运行, 程序会直接崩溃掉, 因为在 C 中计算表达式 &x - &y 的值等同于 ((char*)&x) - ((char*)&y) / sizeof struct empty. 这个整数除法非常糟糕, 毫无疑问 C 编译器应该了解到危险所在了: 在编译期, 它完全能够发现该除法算式的常数分母是整数 0, 但是它还是义无反顾地生成了代码, 甚至连警告也不给, 将程序推入运行时崩溃的深渊.

本来这种事情应该偷偷改掉拉倒, 可是 C 标准对这个事情讳而不谈, 丢出一张王牌 "对空结构体或联合求 sizeof 将会是*未定义*行为". 对此 C++ 只好吐了个槽, 说*任何对象至少要占用 1 字节空间*. 所以其实 C++ 标准也没有明确说出 "对空结构体或联合求 sizeof 将会是 1" 这样的话, 但是根据前面这个规定, 由编译器厂商演绎出来的结果就是这样的, sizeof 纷纷得到结果 1, 包括下面这样的情况

Code Snippet 0-2

struct empty_base_a {};
struct empty_base_b {};
struct empty_inherit : empty_base_a, empty_base_b {};

sizeof empty_inherit; // 值为 1

即对从空类上 (多重) 继承的空子类求 sizeof 也将得到 1.

这一招看起来很挫, 但还真的管用了, 用 C++ 编译器编译并运行上述程序, 零也不除了, 程序也不会崩了, 还能给出正确地结果.

虽然把两个什么空的东西用继承的方式捏在一起不会产生体积变大, 但是一个数组的什么空的东西则会导致体积累加, 如

struct empty {};

int main()
{
    struct empty x[4];
    printf("%ld", sizeof x); /* 4 */
    return 0;
}

这段 C++ 代码的运行结果将是 4, 也就是 x 占用了 4 个 1 字节. 这又扯到 C++ 另一个核心编程思维 --- 面向迭代器. 例如下面一坨代码

Code Snippet 0-3

struct empty {};

void echo(empty)
{
    std::cout << "echo" << std::endl;
}

int main()
{
    struct empty x[4];
    std::for_each(x, x + 4, echo);
    return 0;
}

如果认为整个数组是一个对象, 打个包求 sizeof 才能得到 1, 而 x[0] 与 x[4] 等等有相同的地址, 那么 std::for_each 中的循环将一次也不被执行. 类似的, 让多个空类对象聚合在一个空类对象中时, 它们占用的空间大小是会累加的, 如

Code Snippet 0-4

struct empty {};
struct twin {
    empty a;
    empty b;
};

sizeof twin; // 2

Created at 2011-10-07 18:15:26

Permanent Link: /p/438/

Post tags:

C++

sizeof

日常的数据结构 - 动态最值统计与堆

    如果设计一个顺序统计系统, 需要动态向集合内添加元素, 又可以随时从集合中取得并丢弃最小值. 由于集合中有集合会被移除, 因此接下来再次取最小值时如果重新扫一次集合, 时间开销会相当大. 在一般情形中, 若为了均衡时间开销, 需要考虑维护一个更复杂的数据结构.
    这个数据结构建立在满二叉树 (full binary tree)和完全二叉树 (complete binary tree)的概念上.
    "满" 这个字眼提示在树的每一层都摆满了节点, 而这恰好又是个充要条件, 即如果一棵二叉树每一层都堆满了节点, 那么它就是满二叉树. 满二叉树的定义干脆就按节点个数来: 一棵二叉树如果深度为 K, 而拥有 2^K-1 个节点, 那么它就是一棵满二叉树. 如下面是 2 层和 3 层满二叉树, 分别拥有 3 个和 7 个节点

+---+ | a | +---+ +---+ | a | .---' `---. +---+ +---+ +---+ / \ | b | | c | +---+ +---+ +---+ +---+ | b | | c | / \ / \ +---+ +---+ +---+ +---+ +---+ +---+ | d | | e | | f | | g | +---+ +---+ +---+ +---+

而如果一棵二叉树满足

除了最后一层, 其余层构成一棵满二叉树
最后一层从右起缺少 0 个或多个连续的节点

那么它就是一棵完全二叉树. 更直观一些, 将一个满二叉树的节点按照广度优先 (即逐层向下) 遍历的方式顺序编号, 编号从 1 开始 (而不是从 0 开始), 如

Created at 2011-10-03 22:01:06

Permanent Link: /p/434/

Post tags:

以一个整数数组类型为例, 下面的写法

class int_array {
    int* array;
    int size;
public:
    int_array& operator=(int_array const& rhs)
    {
        if (this == &rhs) {
            return *this;
        }

        delete[] array;
        array = new int[];
        std::copy(rhs.array, rhs.array + rhs.size, array);
        size = rhs.size;
        return *this;
    }

    /* other members */
};

是完全错误的.
设想在下面这样的上下文中

int_array a /* init */;
int_array b;
try {
    b = a;
} catch (std::bad_alloc) {
}
/* ''b'' is bad now! */

进入 operator= 之后, 先执行了 delete[], 这一句没问题, 如果之后的
array = new int[];
内存分配失败, 这时 b 的成员 array 已经崩坏掉了, 以后再继续使用 b 显然是一件很糟糕的事情.

为了保持对象状态一致性, 很自然地应该将对象状态的切换放入一个尽可能安全的环境中. 一个方法是使用先复制一份对象, 然后利用绝对安全的 std::swap 将副本与当前对象交换. 假如在复制过程中出错, 并不会破坏当前对象的状态一致性.

class int_array {
public:
    int_array& operator=(int_array const& rhs)
    {
        if (this == &rhs) {
            return *this;
        }

        int_array copy(rhs);
        swap(copy);
        return *this;
    }

    void swap(int_array& other)
    {
        std::swap(array, other.array);
        std::swap(size, other.size);
    }

    /* other members */
};

一个与之类似的例子是维护程序配置文件, 当程序在退出或者某个其它时机需要将配置写回文件时, 直接清空原来的文件然后提笔并不是一个好主意, 而应该先写入一个临时文件, 再将临时文件 mv 到配置文件.

Created at 2011-09-30 20:25:19

Permanent Link: /p/430/

Post tags:

顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同)

template

_Iterator find_min(_Iterator begin, _Iterator end)
{
    _Iterator min = begin;
    for (++begin; begin != end; ++begin) {
        if (*begin < *min) {
            min = begin;
        }
    }
    return min;
}

将这两件事情揉合在一起, 即从一个集合中同时找到最小值和最大值, 相比于分头寻找, 能够节省不少时间, 原因不仅仅是两次循环合并成一次循环, 运用一些技巧能显著地减少比较的次数.
在每一次取出剩余元素时, 同时取出两个, 先将这两个比较大小, 然后将较小的元素与当前最小值比较, 而将较大的值与当前最大值比较取出

+-------+-----------+----- | begin | begin + 1 | ... +-------+-----------+----- | | +--( < )--+ / \ / \ +----------+ +-------------+ +-----+ | less one | | greater one |--( < )--| max | +----------+ +-------------+ +-----+ | | +-----+ +-------------------------( < )--| min | +-----+

这样每寻访 2 个元素, 需要 3 次元素比较, 加上判断循环是否结束需要 1 次比较, 而分开查找, 则每 1 个元素需要 2 次元素比较, 加上 1 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率.
下面是实现的例子

Created at 2011-09-30 18:20:03

Permanent Link: /p/426/

Post tags:

1 Page 2 3 4