About
RSS

Bit Focus

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:

Posted at Aug 25 2012 - 10:30:24

Permanent Link: /p/494 Load full text

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 数据库连接是否可用

Posted at Jul 30 2012 - 04:04:32

Permanent Link: /p/493 Load full text

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 运行时所支持的库.

Posted at Jul 30 2012 - 03:59:13

Permanent Link: /p/492 Load full text

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 文件, 内容如下
<html>
<body>
Dear ${ username }, welcome back!
并使用如下的 Python 代码
import mako.template
templ = mako.template.Template(filename='hello-mako.html')
print templ.render(username='Mako')
就能看到输出的结果 HTML 代码了.

使用中文及指定编码

上面的页面模板代码中如果包含中文或其它非 ASCII 字符, 如
<html>
<body>
你好, ${ 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:
    <a href='/admin'>管理页面</a>
%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

对象式引用

Posted at Jul 30 2012 - 03:37:19

Permanent Link: /p/491 Load full text

Post tags:

 Python
 Tutorial
 Template
 Mako

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

在面向对象语言中, 子类覆盖父类中的实例成员函数时, 可以酌情修改返回值类型, 使之变得更加具体. 比如在 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<base> copy() const
    {
        return new base;
    }
};

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

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

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

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

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

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<apple> a(new apple);

    /* 如果子类的自动指针对象是可以为父类的自动指针的引用直接引用
       也就是说下面这一句合法 */
    std::unique_ptr<fruit>& 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<base*> 类型的引用是无法引用 std::vector<inherit*> 类型的对象的.

Posted at May 14 2012 - 15:44:54

Permanent Link: /p/490 Load full text

Post tags:

 Java
 C++
 面向对象程序设计

风之力 - 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('<html><body>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('''
<html>
<head>
<script>
var ws = new WebSocket('ws://localhost:8000/soc');
ws.onmessage = function(event) {
    document.getElementById('message').innerHTML = event.data;
};
</script>
</head>
<body>
<p id='message'></p>
        ''')
    修改这个类后, 然后在控制台中止服务器 (猛击 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 映射

Posted at Apr 23 2012 - 08:58:27

Permanent Link: /p/489 Load full text

Post tags:

 Python
 Web Server
 Tornado
 Tutorial

对象炼金术 - 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 属性, 如下

Posted at Mar 14 2012 - 03:44:02

Permanent Link: /p/488 Load full text

Post tags:

 ORM
 SQLAlchemy
 Python
 Tutorial

对象炼金术 - 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 的关联关系上动动手脚, 加上级联信息.

Posted at Mar 13 2012 - 04:44:15

Permanent Link: /p/487 Load full text

Post tags:

 SQLAlchemy
 ORM
 Python
 Tutorial

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

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

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