About
RSS

Bit Focus

对象炼金术 - 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()

Posted at Mar 12 2012 - 08:31:04

Permanent Link: /p/486 Load full text

Post tags:

 SQLAlchemy
 Python
 ORM
 Tutorial

对象炼金术 - 体验 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))

Posted at Mar 09 2012 - 13:46:26

Permanent Link: /p/485 Load full text

Post tags:

 ORM
 SQLAlchemy
 Python
 Tutorial

基于 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 本身由谁在什么时机来调用

Posted at Mar 08 2012 - 08:08:42

Permanent Link: /p/484 Load full text

Post tags:

 Sanguosha
 Boarder game
 Game development
 Python

基于 B/S 的桌游设计 - 协议

前言

    虽然我觉得国内桌游的始祖可能国粹麻将什么的, 不过貌似这个词在三国杀风靡之后才被正式使用. 这系列文章中, 我也打算使用三国杀来做样例项目, 分析 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,
}
    此时服务器返回的可能是如下格式的列表

Posted at Mar 02 2012 - 13:34:47

Permanent Link: /p/483 Load full text

Post tags:

 Game development
 Sanguosha
 Boarder game
 Python

还是低调地给博客写个应用文档

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 ==> a2x2+a1x+a0=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
row 2...
row 333333333333333333333333333333...

Posted at Feb 22 2012 - 15:28:54

Permanent Link: /p/482 Load full text

Post tags:

 Google AppEngine
 NijiPress
 Markdown

万能巧械 - 二叉检索树 [壹]

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

    从二叉检索树中删除一个元素分多个步骤:
  • 找到节点
  • 将节点移动到容易删除的位置
  • 删除节点
    找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 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 表示待删除节点的父节点)

Posted at Jan 24 2012 - 05:42:01

Permanent Link: /p/481 Load full text

Post tags:

 Algorithm
 Generic Programming
 Order Statistic
 B-tree
 Data Structure
 Template
 C++
 Binary Search Tree

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

Posted at Jan 23 2012 - 07:17:09

Permanent Link: /p/480 Load full text

Post tags:

 Web Server
 Google AppEngine
 Tutorial
 Python

万能巧械 - 二叉检索树 [零]

    堆在维护固定的顺序统计量有先天优势, 但在面对如下需求的时候又极其手短
  • 按键索引 - 给定一个元素的键, 在数据集合中找到与该键相同 (或较小, 较大) 的元素
  • 随机索引 - 在堆建立时, 可以给定一个固定的数值 K, 让堆维护第 K 大的元素, 但毕竟这个 K 是建堆时固定的
  • 多键索引 - 堆中的元素的排序索引是唯一的, 如果想要其它的索引, 则需要借助额外的数据结构
    前两个手短指的是时间复杂度, 要完成这些功能, 跟直接到未排序数组里面去暴力解决是一回事. 而后面一个则是堆的硬伤. 严格来说, 堆并不是一种数据结构, 说穿了堆只有数据而没有结构 (是的, 即使是数组也是数据结构, 因此严格来讲应该说成, 它没有自身独特的结构, 还记得 STL 中优先队列的模板定义吧, 它的底层存储结构是可以通过模板参数替换的), 其精髓在于算法. 由于不具备结构, 也就是说没有实质上的数据与数据的关系, 因而不方便弄出多个不同的键. 这个现在空谈就像白切鸡一样没什么味道, 以后有机会再加上油盐详述.

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

    首先还是把二叉树的架子给搭出来
template <typename T>
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);
};

Posted at Jan 23 2012 - 05:04:23

Permanent Link: /p/479 Load full text

Post tags:

 C++
 Generic Programming
 Data Structure
 Binary Search Tree
 Algorithm
 Order Statistic
 Template

GAE 速成简易博客 - 更多数据库操作

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

现在首页能显示文章列表了, 但是
  • 文章的顺序貌似是乱的, 而一般来说, 博客系统会按照发布的时间先后顺序来放置
  • 构造一个页面, 看指定的某一篇文章的内容
那么, 现在就开始修改数据库吧.

为文章加上 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')

Posted at Jan 20 2012 - 11:43:58

Permanent Link: /p/478 Load full text

Post tags:

 Web Server
 Python
 Tutorial
 Google AppEngine

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

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

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

添加文章

入口

    虽然添加文章这种事情可以直接通过后台暴力搞数据库来做, 但既然要写的是 Web 应用, 那么写个页面提供添加文章的入口也是理所当然的事情.
    页面嘛, 肯定得有个 HTML 模板撑着, 来建个文件, templates/add_post.html
<html>
<head><title>Add Post</title></head>
<body>
<form>
<table>
<tr><td>Title</td><td><input type='text' name='title'></td></tr>
<tr><td style='vertical-align: top;'>Content</td>
    <td><textarea name='content'></textarea></td></tr>
<tr><td><input type='submit'/></td></tr>
</table>
</form>
    接下来得增加一个 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')

Posted at Jan 19 2012 - 03:31:17

Permanent Link: /p/477 Load full text

Post tags:

 Web Server
 Tutorial
 Google AppEngine
 Python

GAE 速成简易博客 - 开张

前期准备

目前 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 文件, 内容是
<html>
<head><title>My Blog</title></head>
<body>
{% for post in posts %}
<h1>{{ post.title }}</h1>
<p>{{ post.content }}</p>
{% endfor %}
    在 GAE 中, HTML 模板文件使用的是 django 的模板语法. 上面文件中, {% for ... %} 到 {% endfor %} 是对传入模板的参数 posts 的迭代. {{ post.title }} 则是对 post 对象的 title 的引用, 而 {{ post.content }} 则是引用 content.
    简而言之 {% xxx %} 是模板中的控制语句, 而 {{ xxx }} 则是引用值. 在 django 官方网站可以看到详细文档, 鄙博客之前也对 django 有过简介.

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

视图源文件

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

Posted at Jan 19 2012 - 03:30:27

Permanent Link: /p/476 Load full text

Post tags:

 Tutorial
 Web Server
 Template
 Python
 Google AppEngine

单链表 给我翻过来

下面是一个简单的单链表节点结构
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 <stdio.h>

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;
}

Posted at Dec 21 2011 - 04:59:53

Permanent Link: /p/475 Load full text

Post tags:

 C
 Algorithm
 Data Structure

天净沙 – 神社 入夜

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

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

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

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

Posted at Dec 21 2011 - 02:58:10

Permanent Link: /p/464 Load full text

Post tags:

 Tou-hou
 Tian-jing-sha

位运算的优先级

    在现代计算机程序设计语言中, 每一种成熟的语言都支持许多算符. 对于除了像 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 的语言这么承袭的. 哎, 你们这么折腾到底图个啥啊.

Posted at Oct 23 2011 - 08:29:11

Permanent Link: /p/454 Load full text

Post tags:

 Javascript
 Python
 C
 Operator Precedence

元気娘美紗緒参上

Posted at Oct 23 2011 - 08:21:21

Permanent Link: /p/449 Load full text

Post tags:

 Lucky Star
 ASCII Art

日常的数据结构 - 堆的实现与第 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 <typename _T, typename _Less>
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();
};

Posted at Oct 07 2011 - 09:23:13

Permanent Link: /p/441 Load full text

Post tags:

 C++
 Algorithm
 Template
 Heap
 Order Statistic
 Generic Programming
 Data Structure

对空结构体求 sizeof

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 <stdio.h>

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

Posted at Oct 07 2011 - 09:15:26

Permanent Link: /p/438 Load full text

Post tags:

 sizeof
 C
 C++

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

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

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

    而如果一棵二叉树满足
  • 除了最后一层, 其余层构成一棵满二叉树
  • 最后一层从右起缺少 0 个或多个连续的节点
那么它就是一棵完全二叉树. 更直观一些, 将一个满二叉树的节点按照广度优先 (即逐层向下) 遍历的方式顺序编号, 编号从 1 开始 (而不是从 0 开始), 如

Posted at Oct 03 2011 - 13:01:06

Permanent Link: /p/434 Load full text

Post tags:

 Data Structure
 Heap
 Algorithm
 Order Statistic

正确重载 operator=

    以一个整数数组类型为例, 下面的写法
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 到配置文件.

Posted at Sep 30 2011 - 11:25:19

Permanent Link: /p/430 Load full text

Post tags:

 Operator Overload
 C++
 RAII

日常的算法 - 顺序统计

    顺序统计指的是在一坨并没有排序的数据上找出跟顺序量有关的元素. 典型的顺序统计包括找最小值或最大值算法, 这两个算法可以说没有任何技巧而言, 暴力地遍历一次数据集合就行了, 如找最小值算法的实现 (以 C++ 面向迭代器的程序设计描述, 不考虑集合为空的情形. 以后的例子相同)
template <typename _Iterator>
_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 次循环判断结束的比较. 之所以这么计较比较的次数, 因为目前计算机体系结构和分支语句非常不友好, 太多分支 (意味着大量的预测失败) 的程序会因为无法充分利用流水线而显著地降低实际执行效率.
    下面是实现的例子

Posted at Sep 30 2011 - 09:20:03

Permanent Link: /p/426 Load full text

Post tags:

 Generic Programming
 STL
 C++
 Order Statistic
 Algorithm
 Template

Angel Beats! & SSS

          ____                           __  _____                     __            __
         /   |__ _____  _____ _    ___   | | |  _ `.    ___      ___ _ | |_   _____  | |
        / _  || ' __  \/  __ Y | ,'   `. | | | | \ |  ,'   `.  ,' _ ` ||  _| / ___ `.| |
       / / | || r'  | || |  `. |;  ,-.  || | | |_/ / ;  ,-.  |/ ,' `. || |  | /   `-'| |
      / /__| || |   | || |   | || `---` || | |  __ \ | `---` || |   | || |  | `----. | |
     / ____  || |   | || |   | || .-----'| | | |  \ || .-----'| |   ; || |   `----. \| |
    / /    | || |   | || '---' |: `.__,-:| | | |__/ |: `.__,-:| `._'  || |_ .-.___; ||_|
   / /     |_||_|   |_|\_____  | `.____.'|_| |_____//\`.____.' `.__,|_||__/ `._____.'(_)
--' /------------------,-----' |-------------------'  \,----------------------------------
---'-------------------\______/---------------------'\  ,---------------------------------
                                                      \/

猛击这里查看动画版.

Posted at Sep 15 2011 - 16:17:44

Permanent Link: /p/414 Load full text

Post tags:

 ASCII Art
 AngelBeats!

Pipeline: 我所希望的列表处理方法

    本文仅表现个人从事程序设计以来的感受和想法, 带有主观色彩, 可以认为结论式的句子均省略了 "我认为" 这样的字眼.

    编程语言中最基本的事情就是数据变换, 比如基本的四则运算, 或是求正弦, 或是将字符串拼接起来, 前面这三种都是针对数据个体的, 而且在不同语言中实现得大同小异. 而对于数据集体的操作, 比如对一个列表进行变换, 各种编程语言会有各自独特的方法, 甚至同一种语言在语言特性升级前后都会有不同, 比如在 C++ 中, 一直以来采用 for 来迭代, 在 C++11 新标准引入了 lambda 之后, std::for_each 就咸鱼翻身变得流行起来; 又比如在 Python 中, 列表迭代采用 for element in list 的方式, 而在引入 yield 之后的版本中, 转为了 for element in generator. 虽然语法没有变, 但是整体思想改变了不少.

    而在这些眼花缭乱迭代方式当中, 程序员究竟想要得到什么? 解决实际问题的过程中, 最常见的操作应当是
  • 映射: 给出一个函数 f 和集合 {x}, 得到新的集合 {f(x)}
  • 过滤: 给出一个函数 g 和集合 {x}, 得到新的集合 {x 当且仅当 g(x) 为真}

    将这些需求提出来之后, 最让我感到有趣的莫过于 Shell 的管道. 比如这样一句
find -type f | awk '{ print "mv", $1, "/tmp/" }'
相当与进行了一次映射, 集合为 find -type f 给出的文件列表, 函数 f 就是 awk 程序. 而这个例子
find -type f | grep wav$
则是一个过滤.
    上面的例子中, 并没有任何迭代的过程, 可以说 Shell 的管道完全抽象了集合迭代, 让对集合的操作变为了对元素个体的操作. 在语言层面上将迭代过程本身封装起来, 这确实是一件很实在的事情. 因此, 我很乐意将这个特性引进到了 Stekin 程序设计语言中.

    在当前的 dev 分支上, Stekin 实现了类似管道的列表操作方式. 具体的语法类似
  • 列表 | return 表达式
  • 列表 | if 布尔表达式
分别表示映射和过滤.
    在 awk 中, 使用 $1 等表示该行的第一个词, 而 $2 表示第二个, 等等. 而在 Stekin 中并没有这个困扰, 因为迭代的列表中元素类型是确定的, 因此直接使用 $element 来表示元素, 如下面的代码
list: [0, 1, 2, 3, 4]
sqr_list: list | return $element * $element
将每一个元素 $element 映射到其平方 $element * $element, 得到的 sqr_list 将是 [0, 1, 4, 9, 16].
    除了在管道中可以使用 $element 引用元素之外, 还可以使用 $index 引用当前元素的索引 (从 0 开始). 不过这种表示法仍然有待商榷, 我曾想过使用如 $$, $@ 这样看起来很 Shell 很 Makefile 的符号, 但那样实在太不直观, 于是使用了 $element 这样直接写单词的方法. 如果你有什么想法或建议, 欢迎在回复中提出来.

    而过滤操作则除了将管道符号 | 之后的 return 关键字换成 if 之外, 它要求接下来的表达式是布尔类型的. 当且仅当这个表达式的值为真时, 则该元素将被添加到结果列表中去, 如
list: [0, 1, 2, 3, 4]
new_list: list | if $element % 3 != 0

Posted at Aug 31 2011 - 07:43:35

Permanent Link: /p/408 Load full text

Post tags:

 Stekin
 List Processing
 Pipeline

头文件禁区: C++ 中的 ABI

    在上一篇文章中写到了 C 的 ABI (application binary interface) 有关的内容. 而 C++ 这货也采用 header / cpp 分离的方式来组织代码, 并在编译时将头文件直接在 cpp 中插入, 这种暴力方法已经不能简单说是为了兼容 C 的各种编译期行为, 完全就是彻头彻尾地重蹈覆辙, 甚至有过之而无不及.

    首先, C++ 也会遇到 "如果直接用了动态库中修改过签名的函数怎么办" 这个全静态语言的千古难题. 而且比起 C 语言更要命的是, C++ 的类是不能进行前置声明来回避对象内存布局耦合: 前置声明就没有引用成员函数了, 那还怎么面向坑爹的对象呢? 不仅仅对象成员布局有此问题, 连同 C++ 藉由实现多态的虚函数亦面临着同样的窘境. 试想动态库中虚函数表都改得面目全非时, 使用该对象的代码却还用原来的方式访问, 那还不是各种鸡飞狗跳.
    对于如此恶劣环境下仍然想保持 ABI 兼容性的 C++ 程序员来说, 倒也不是完全无路可走. 具体的方案就不在这篇文章中赘述了, 请转到陈硕老师的 C++ 工程实践: 二进制兼容性和 C++ 工程实践: 避免使用虚函数作为库的接口. 两篇文章都写得非常详细.

    撇开这些跟 C 语言有关的孽缘不谈, C++ 本身也提供了一些机制来帮助程序员养成编码恶习, 比如一些函数实现可以直接写进头文件中, 而无须担忧任何链接错误. 首当这个批评的就是成员函数, 包括静态或非静态, 虚或非虚. inline 函数或者 template 函数实现要写头文件这点可以理解可以忍, 但成员函数来凑什么热闹? 成员函数的不往头文件里面写, 可以避免一些 ABI 耦合, 比如
class Date {
    int month;
    int day;
public:
    int getDay() const;
    int getMonth() const;
};
    这种情况下, 在使用
Date* date /* initialize */;
date->getDay();
不必担心内存布局耦合, 因为作为非虚的成员函数, Date::getDay() const 这样的函数签名正如 getday(Date const*) 一样, 这就回到了上一篇文章最后提到的解决方法了. 但是如果用得不恰当, 比如头脑发热认为 inline 一下能提高效率什么的, 而活生生地写成
class Date {
    int month;
    int day;
public:
    inline int getDay() const
    {
        return day;
    }

    inline int getMonth() const
    {
        return month;
    }
};

Posted at Aug 31 2011 - 06:52:02

Permanent Link: /p/404 Load full text

Post tags:

 C++
 Template
 ABI
 STL
 inline

struct 禁区: 内存布局耦合与 C 语言 ABI 基础

    假如现在有个某复杂系统需要存放人员信息. 人员类型定义类似:
struct person_t {
    name_t name;
    age_t age;
};
    这个系统的人员添加功能由两个部分通过动态库集成到一起, 后端的部分只负责拿到人物信息并做诸如存入数据库, 数据统计等工作, 它向前端提供了两种风格的接口, 分别是
void add_person_0(name_t name, age_t age);
void add_person_1(struct person_t const* person);
    两种看上去没有太多区别. 对于前一种接口, 使用该接口的代码很可能写成这样子
add_person_0("hideyosi", 16);
而对于后一种接口, 代码很可能这样写
struct person_t person = { "hideyosi", 16 };
add_person_1(&person);
    现在考察一次扩展性, 而且来最坏的情况: 接口提供方先行更新了动态库, 而使用方在一段时间内并不知情. 更新的内容包括, 在 name 和 age 之间插入一项 gender (当然前一种人员添加接口也有变动):
struct person_t {
    name_t name;
    gender_t gender;
    age_t age;
};

void add_person_0(name_t name, gender_t gender, age_t age);
void add_person_1(struct person_t const* person);
    这时会怎么样呢?

    显然两种情况都好不到那里去.
    对于 add_person_0 这个接口, 由于参数个数都改变了, 签名对不上号, 那么使用该接口的一方在通过动态库访问此函数时会少压入一个参数, 并且压入的第二个参数 age 对上的还是 gender 这个参数的位置. (在 C++ 中, 由于允许函数重载, 动态库中的函数名会因签名不同而被 name-mangling 成不同的函数, 因此会导致函数找不到错误. 当然这并不意味着 C 和 C++ 孰优孰劣, 因为这本来就是两个不同的语言, 只是在这一个问题上有不同的死法罢了.) 这样一调用函数程序立马崩掉不客气.
    而对于第二种使用, 因为使用方在初始化 person_t 时, 仍然按照旧的逻辑, 即在偏移为 0 的地方放上 name, 在偏移为 sizeof(name_t) 的地方放上 age, 然后将这样初始化的 person 结构体传递给接口提供方; 而此时提供方对这一片内存区的解释有很大不同, 至少它认为的 sizeof(person_t) 都比使用方给出的要多出一个 sizeof(gender_t). 使用这样的 person 就像拿着三年前的武汉市地图到今天的洪山广场游玩结果掉进工地不明不白地挂掉了一样.

    那么有没有什么无痛的方法能够在这种不同模块分离更新的环境下让程序仍然, 至少在新来的人可能都缺少性别的情况下, 能够继续像模像样地跑呢?
    要找到这个方案, 自然应该先看看问题出在什么地方. 这里问题的核心围绕着内存布局, 即双方在 person_t 这一结构体到底包含了什么数据需要达成一致, 换句话说就是因为 person_t, 双方紧耦合了.

    解决方案很自然的就是, 把所有跟 person_t 内存布局相关的代码全部移到一个模块 (当然是接口提供方那边) 里去, 并提供一套操作接口 (为了彻底不让使用方知道 person_t 的内存布局, 干脆只给个前置声明好了)

Posted at Aug 08 2011 - 09:07:25

Permanent Link: /p/390 Load full text

Post tags:

 C
 ABI

C++ inline 坑爹真相

    准备两个文件 a.cpp b.cpp, 内容如下
/* a.cpp */

#include <iostream>

void b();

inline void echo()
{
    std::cout << 0 << std::endl;
}

int main()
{
    echo();
    b();
    return 0;
}

/* b.cpp */

#include <iostream>

inline void echo()
{
    std::cout << 1 << std::endl;
}

void b()
{
    echo();
}
    然后执行
$ c++ a.cpp b.cpp -o a.out && ./a.out
    也许会出现两个 0, 或者两个 1, 但是不会出现 0 1 这样的组合, 更不会链接冲突了. 如果有任何跳过生成目标文件直接到生成可执行文件的顾虑, 尝试下面的方法结果是一样的
$ c++ -c a.cpp
$ c++ -c b.cpp
$ c++ -o a.out a.o b.o
$ ./a.out
    甚至最直接地, 如果查看两个中间文件的符号
$ nm a.o
$ nm b.o
    会在两次结果中都看到一条名为 _Z4echov 的记录, 这就是 echo 函数被 name-mangling 之后的标识.

    C++ 文档和标准中过度赞扬 inline 这个关键字, 然而一笔带过的是, 编译器可以选择忽略 inline 标记, 至于忽略了会有什么后果, 如何链接等细节都一字不提. 如果这是一个封装行非常良好的编译器特性, 那也就没什么. 但实际上这里敷衍了一些重要事实, 既然 0) 有的函数即使程序员写了 inline, 编译器可以不进行 inline, 则 1) 很有可能出现这样的函数, 并在编译后被生成到目标文件中去, 而且 2) 由于 inline 函数一般实现在头文件中, 那么 3) 编译器在编译每一个包含了这个头文件的 cpp 文件时, 都会将该函数符号生成到对应目标文件中去, 而若要 4) 链接这多个目标文件不发生链接冲突, 只好由 5) 编译器或者链接器耍一些手段来保证, 可是 6) 耍了手段, 却有可能造成上面的问题发生.

    与 inline 失败的函数有关的真相是, 编译器会为 inline 函数做上标记, 链接器根据这个标记, 从目标文件中找到这个函数的多处实现, 不负任何责任地选取其中一个作为正身, 并抛弃其它的实现, 无论这些实现是否相同 (链接器也无从判断是否相同).
    开头的例子非常猎奇, 但是也不排除这样日常的情况: 0) lib 作者因为各种原因, 让 inline 失败的函数编入 lib; 1) 这个函数没有在文档中被提及, 头文件也隐藏得很好; 2) 引用 lib 的程序员定义了一个同 namespace 且同名的 inline 函数 (当然最有可能在全局名字空间这么干了). 于是就悲催了.

    现在再回头看一下 inline 的描述
  • 要想 inline, 得先 inline
  • 若是 inline, 未必 inline
    这是不是有种在看葵花宝典开头的感觉?

Posted at Jul 24 2011 - 04:24:52

Permanent Link: /p/379 Load full text

Post tags:

 inline
 C++

ArchLinux 64 位重装记

    本本上一直是 Win7 Home 和 32 位 ArchLinux (下称 arch) 双系统. 不过, 吐槽一下, Win7 跟 WinXP 之间巨大的操作差异让我真心戒掉了 Windows, 就像 Gnome3 的巨大变化让我转投了 Xfce 一样. 另, 要与时代接轨 (虽然刚才好像我对新东西都很抵触) 想尝试一下 64 位系统, 所以决定: wipe out & reintall. 这里记录一下自己重装的过程, 让以后的折腾有所参考.

前期准备

    其实最重要的就是前期准备了. 准备好了后面装系统改配置都是轻松加愉快啊.

备份配置

    备份必要的配置文件当然是必须的.
    首先告诉大家一个好消息, 最让人纠结的 xorg.conf (一般放在 /etc/X11/xorg.conf) 不需要. 貌似现在 arch 启动 X 并不需要这个文件了 :D
    如 pacman.conf 这样的文件可以备份一下, 我实在不太记得住 archlinuxfr 的网址. 此外, arch 现在还启动了 multilib 计划, 可以把下面这个加入 pacman.conf
[multilib]
Include = /etc/pacman.d/mirrorlist
    其它的还有 /etc/locale.gen 以及 /etc/host* 这些文件.
    如果有修改 /etc/bash_aliases 或 /etc/vimrc 等等, 不过这些一般也没谁去改吧, 盯好自己的 ~/.bashrc ~/.bash_profile ~/.vimrc 就好了.
    如果你跟我一样使用 compiz 来卖萌, 记得可以使用 ccsm 将 compiz 的设置导出到文件哦.
    个人目录下其它值得备份的文件还有 .bash_history .fonts .mplayer 等等, 看各自的需求了.
    当然别忘了其它重要的文件比如小电影什么的.

已安装的软件包

    接下来一件比较重要的事情就是看看系统现在装着哪些软件, 装好新系统后立刻把它们都装上, 在 arch 下通过
$ pacman -Q
来查询安装的所有软件, 包括 aur. 导出这个列表
$ pacman -Q | awk 'BEGIN { print "echo -n \"pacman\" -S"} { print "echo -n \" " $1 "\"" }' | sh > install-packages
    最后, 准备安装镜像.
    再看一眼旧的系统, 马上就要说再见了哦.

安装

    用 ArchLinux 安装镜像启动后, 会进入这样一个 shell 交互环境
root@archiso ~ #
之后就是全手动安装了. 这么坑的设定, 萌生退意也是理所当然的了...

格式化磁盘

    如果没有必要重新格式化磁盘, 请跳过这个步骤.
    首先要搞清楚硬盘在挂在哪个地方, 一般是 /dev/sda, 使用 U 盘安装的用户将还会看到 /dev/sdb, 或者 sda 是 U 盘而 sdb 才是磁盘. 对应地请小心行事, 不要误删数据了.
    如果不想退的话, 先从格式化分区开始吧. 下面是用 parted 进行分区 (以在 /dev/sda 上安装为例, 高亮的部分是输入, 其它是 shell 或 parted 回显)

Posted at Jul 24 2011 - 03:29:55

Permanent Link: /p/376 Load full text

Post tags:

 ArchLinux

Google & Baidu 图片识别搜索测评之二次元

Posted at Jul 01 2011 - 13:14:45

Permanent Link: /p/368 Load full text

Post tags:

C++ 对象构造时的异常与 RAII 的救赎

    在上一篇文章中简单介绍了一下 RAII 的原理, 举了个读文件的例子. 这个例子稍微单薄了一些, 它只封装了一个需要 RAII 机制管理的资源 (FILE*). 软件工程中流行的观念是, 不具备扩展性, 经不起追加功能的东西注定会悲剧. 现在假如需要给这货增加个缓冲区, 也许这样是可以的
struct File {
    File(char const* filename, int buffer_size)
        : file(fopen(filename, "r"))
        , buffer(new char[buffer_size])
    {
        if (NULL == file) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    ~File()
    {
        fclose(file);
        delete[] buffer;
    }
private:
    FILE* file;
    char* buffer;

/* other members */
};
    在 buffer 分配失败时, 一般会抛出 std::bad_alloc.
    这个类型的破绽相当多, 稍不注意就有可能漏资源. 首先是刚刚提到的 buffer 分配失败抛异常, 那么假如这个时候 file 已经打开成功了, 它会被关闭么? 其次, 假设 buffer 成功分配, 但这时 file 打开失败, 那么 buffer 是否会被释放呢?
    很不幸的, 两者的答案都是否. 还是那句话, 因为 File 的构造函数没有走完, 这时抛出异常, 那么析构函数不会被执行. 因此, 不要尝试构造控制多于一个资源的类型. 而遇到这种需求, 应该拆分资源, 然后将这些单元类型进行聚合, 如
struct File {
    explicit File(char const* filename)
        : file(fopen(filename, "r"))
    {
        if (NULL == file) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    ~File()
    {
        fclose(file);
    }
private:
    FILE* file;

/* other members */
};

struct Buffer {
    explicit Buffer(int buffer_size)
        : buffer(new char[buffer_size])
    {}

    ~Buffer()
    {
        delete[] buffer;
    }
private:
    char* buffer;

/* other members */
};

struct BufferedFile {
    BufferedFile(char const* filename, int buffer_size)
        : file(filename)
        , buffer(buffer_size)
    {}

    File file;
    Buffer buffer;

/* other members */
};

Posted at Jun 21 2011 - 13:27:55

Permanent Link: /p/363 Load full text

Post tags:

 RAII
 Exception Handling
 C++

从 Python 的 with 到 RAII

    在上一篇文章中提到了 Python 的 with 结构, 其背后的思想正是 RAII. 在 C++ 中, RAII 的样子看起来跟 Python 中的会非常不一样, 还是以打开读取文件为例子
#include <cstdio>
#include <stdexcept>
#include <iostream>

struct File {
    explicit File(char const* filename)
        : f(fopen(filename, "r"))
    {
        if (NULL == f) {
            throw std::runtime_error(std::string("fail to open ") + filename);
        }
    }

    std::string readLine()
    {
        char buffer[256] = { 0 }; // just for demo
        if (NULL == fgets(buffer, 256, f)) {
            if (!feof(f)) {
                throw std::runtime_error("error occurs while reading file");
            }
            throw std::out_of_range("end of file")
        }
        return buffer;
    }

    ~File()
    {
        fclose(f);
    }
private:
    FILE* const f;
};

int main()
{
    try {
        File file("litsu");
        while (true) {
            std::cout << file.readLine();
        }
    } catch (std::runtime_error e) {
        std::cerr << e.what() << std::endl;
    } catch (std::out_of_range) {}
    return 0;
}
    注意看 try 块中间的语句, 看起来流程很清晰, 完全不像 Python 里面那样, 还要弄个 with 块, 多一级缩进. 都说 C++ 代码没 Python 的精神, 然而在这种小地方 C++ 反而超过了 Python 呢.

    其实, Python 的 with 块更像个语法糖, 上篇文章中有提到, 双层 try 在 Python 中能等效地解决这个问题, 只是看起来丑很多. 这个问题的根本在于, Python 这样不具备 RAII 特性的语言没能处理好对象从不可用状态切换到可用状态的状态过渡. 回顾一下双层 try 结构的处理方式
def readFile():
    try:
        f = open('sawako', 'r')
        pass
        try:
            process(f.readlines())
        except:
            print 'error occurs while reading file'
        finally:
            f.close()
    except:
        print 'error occurs while reading file'

Posted at Jun 20 2011 - 08:43:07

Permanent Link: /p/358 Load full text

Post tags:

 Exception Handling
 C++
 RAII
 Python

码中萌

Source

Qt

Q_Q
Q_D
这两个真的是 Qt 中定义的宏来的.

C

int V = 0, _ = 1, U = 2, o = 3;
int ___ = , l_l = 0;
assert('_');
assert(V^_^V);
assert(-_-U);
assert((o, o));
assert(U>_<U);

assert((
___,  ___
 |  _  |  U
 | l_l |  o
));

Lisp

(define < 0)
(define o 0)
(> o <)

注释

HTML

<!--...-->

Shell 注释

#= o=

C

/* _ */

Posted at Jun 12 2011 - 14:42:09

Permanent Link: /p/349 Load full text

Post tags:

 C
 Shell
 Lisp
 ASCII Art
 Qt

Python: try finally with 简介

    用 Python 做一件很平常的事情: 打开文件, 逐行读入, 最后关掉文件; 进一步的需求是, 这也许是程序中一个可选的功能, 如果有任何问题, 比如文件无法打开, 或是读取出错, 那么在函数内需要捕获所有异常, 输出一行警告并退出. 代码可能一开始看起来是这样的
def read_file():
    try:
        f = open('yui', 'r')
        print ''.join(f.readlines())
    except:
        print 'error occurs while reading file'
    finally:
        f.close()
    不过这显然无法运作, 因为 f 是在 try 块中定义的, 而在 finally 中无法引用.

    如果将 f 提取到 try 块外部, 如
def read_file():
    f = open('azusa', 'r')
    try:
        print ''.join(f.readlines())
    except:
        print 'error occurs while reading file'
    finally:
        f.close()
那么, 问题在于当打开文件失败, 抛出异常将不会被捕获.

    挫一点的方法自然是, 再套一层 try 吧
def read_file():
    try:
        f = open('sawako', 'r')
        try:
            print ''.join(f.readlines())
        except:
            print 'error occurs while reading file'
        finally:
            f.close()
    except:
        print 'error occurs while reading file'
    当然这不仅仅是多一层缩进挫了, 连警告输出都白白多一次呢.

    正规一点的方式是, 使用 Python 引入的 with 结构来解决, 如
def readFile():
    try:
        with open('mio', 'r') as f:
            print ''.join(f.readlines())
    except:
        print 'error occurs while reading file'
    当文件打开失败时, 异常自然会被 except 到; 否则, 在 with 块结束之后, 打开的文件将自动关闭.

    除了打开文件, 还有其它这样可以用于 with 的东西么? 或者说, 怎么自定义一个什么东西, 让它能用于 with 呢?
    直接回答后一个问题吧, 秘密在于 Python 虚拟机在 with 块退出时会去寻找对象的 __exit__ 方法并调用它, 把释放资源的动作放在这个 __exit__ 函数中就可以了; 另外, 对象还需要一个 __enter__ 函数, 当进入 with 块时, 这个函数被调用, 而它的返回值将作为 as 后引用的值. 一个简单的例子是

Posted at Jun 12 2011 - 11:18:54

Permanent Link: /p/328 Load full text

Post tags:

 Exception Handling
 Python
 RAII

归

归

Posted at May 28 2011 - 09:00:58

Permanent Link: /p/318 Load full text

Post tags:

 Story
 Tian-jing-sha

0 1 2 3 4 Page 5 6 7 8 9 10 11 12

. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site