So Tired !_! 逆水行舟, 不进则退!

用geohash字符串实现附近地点搜索

可以考虑使用geohash算法。

http://code.google.com/p/python-geohash/

geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串。比如，北海公园的编码是wx4g0ec1。

geohash有以下几个特点：

首先，geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 （例如MySQL 4之前的版本，Google App Engine的数据层等），利用geohash，只需在一列上应用索引即可。

其次，geohash表示的并不是一个点，而是一个矩形区域。比如编码wx4g0ec19，它表示的是一个矩形区域。 使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。

第三，编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash（例如wx4g0ec1）然后取其前缀进行查询 （SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'），即可查询附近的所有地点。

geohash的算法

下面以(39.92324, 116.3906)为例，介绍一下geohash的编码算法。首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)， 如果目标纬度位于前一个区间，则编码为0，否则编码为1。由于39.92324属于(0, 90)，所以取编码为1。然后再将(0, 90)分成 (0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，得到纬度编码为1011 1000 1100 0111 1001。

纬度范围	划分区间0	划分区间1	39.92324所属区间
(-90, 90)	(-90, 0.0)	(0.0, 90)	1
(0.0, 90)	(0.0, 45.0)	(45.0, 90)	0
(0.0, 45.0)	(0.0, 22.5)	(22.5, 45.0)	1
(22.5, 45.0)	(22.5, 33.75)	(33.75, 45.0)	1
(33.75, 45.0)	(33.75, 39.375)	(39.375, 45.0)	1
(39.375, 45.0)	(39.375, 42.1875)	(42.1875, 45.0)	0
(39.375, 42.1875)	(39.375, 40.7812)	(40.7812, 42.1875)	0
(39.375, 40.7812)	(39.375, 40.0781)	(40.0781, 40.7812)	0
(39.375, 40.0781)	(39.375, 39.7265)	(39.7265, 40.0781)	1
(39.7265, 40.0781)	(39.7265, 39.9023)	(39.9023, 40.0781)	1
(39.9023, 40.0781)	(39.9023, 39.9902)	(39.9902, 40.0781)	0
(39.9023, 39.9902)	(39.9023, 39.9462)	(39.9462, 39.9902)	0
(39.9023, 39.9462)	(39.9023, 39.9243)	(39.9243, 39.9462)	0
(39.9023, 39.9243)	(39.9023, 39.9133)	(39.9133, 39.9243)	1
(39.9133, 39.9243)	(39.9133, 39.9188)	(39.9188, 39.9243)	1
(39.9188, 39.9243)	(39.9188, 39.9215)	(39.9215, 39.9243)	1

经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。

经度范围	划分区间0	划分区间1	116.3906所属区间
(-180, 180)	(-180, 0.0)	(0.0, 180)	1
(0.0, 180)	(0.0, 90.0)	(90.0, 180)	1
(90.0, 180)	(90.0, 135.0)	(135.0, 180)	0
(90.0, 135.0)	(90.0, 112.5)	(112.5, 135.0)	1
(112.5, 135.0)	(112.5, 123.75)	(123.75, 135.0)	0
(112.5, 123.75)	(112.5, 118.125)	(118.125, 123.75)	0
(112.5, 118.125)	(112.5, 115.312)	(115.312, 118.125)	1
(115.312, 118.125)	(115.312, 116.718)	(116.718, 118.125)	0
(115.312, 116.718)	(115.312, 116.015)	(116.015, 116.718)	1
(116.015, 116.718)	(116.015, 116.367)	(116.367, 116.718)	1
(116.367, 116.718)	(116.367, 116.542)	(116.542, 116.718)	0
(116.367, 116.542)	(116.367, 116.455)	(116.455, 116.542)	0
(116.367, 116.455)	(116.367, 116.411)	(116.411, 116.455)	0
(116.367, 116.411)	(116.367, 116.389)	(116.389, 116.411)	1
(116.389, 116.411)	(116.389, 116.400)	(116.400, 116.411)	0
(116.389, 116.400)	(116.389, 116.394)	(116.394, 116.400)	0

接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。

最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。

十进制	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
base32	0	1	2	3	4	5	6	7	8	9	b	c	d	e	f	g
十进制	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
base32	h	j	k	m	n	p	q	r	s	t	u	v	w	x	y	z

解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可，这里不再赘述。 不过由于geohash表示的是区间，编码越长越精确，但不可能解码出完全一致的地址。

geohash的应用：附近地址搜索

geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点， 虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。

以geohash的python库为例，相关的geohash操作如下：

>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5)  # 编码，5表示编码长度
'wx4g0'
>>> geohash.expand('wx4g0')                # 求wx4g0格子及周围8个格子的编码
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']

最后，我们来看看本文开头提出的两个问题：速度慢，缓存命中率低。使用geohash查询附近地点，用的是字符串前缀匹配：

SELECT * FROM place WHERE geohash LIKE 'wx4g0%';

而前缀匹配可以利用geohash列上的索引，因此查询速度不会太慢。另外，即使用户坐标发生微小的变化， 也能编码成相同的geohash，这就保证了每次执行相同的SQL语句，使得缓存命中率大大提高。

使用 SQLObject 连接数据库与 Python

通过提供用于操作数据库表的类和对象，对象关系映射工具有助于提高生产率。Python 最好的对象关系映射工具是 SQLObject —— 一个开放源码项目，它几乎完成编程数据库所需的所有操作。sqlobject支持数据库类型有sqlite3，mysql，PostgreSQL等等

1、安装和设置 SQLObject
SQLObject 具有一个 setup.py 文件，安装方式与其他任何 Python 包一样。直接python setup.py即可，当然你也可以进一步使用setup tools即可：easyinstall.exe sqlobject即可，呵呵，十分简单方便哦。

2、数据库准备（本文使用mysql为例）
要实际使用 SQLObject，需要设置数据库包以及这种数据库的 Python 接口。SQLObject 连接多种数据库，其中包括三个大的开放源码产品：MySQL、PostgreSQL 和无服务器 SQLite。
——————————-
mysql> use mysql;
Database changed
mysql> create database sqlobject_demo;
Query OK, 1 row affected (0.00 sec)
mysql> grant all privileges on sqlobject_demo to ‘dbuser’@'localhost’
identified by ‘dbpassword’;
Query OK, 0 rows affected (0.00 sec)
mysql> flush privileges;
Query OK, 0 rows affected (0.00 sec)
——————————-

3、连接数据库
如果想让应用程序使用 SQLite 数据库，则需要将数据库文件的路径写入位于sqlobject.sqlite 包的 SQLite 连接构建器中。如果数据库文件不存在，QLObject 将告诉 SQLite 创建一个，代码如下：
——————————-
import sqlobject
from sqlobject.sqlite import builder
conn = builder()(‘sqlobject_demo.db’)
——————————-
如果使用的是 MySQL 或带有服务器的其他数据库，则将数据库连接信息传递到连接构建器中。上面提供了在上一节创建的 MySQL 数据库的示例。
——————————-
import sqlobject
from sqlobject.mysql import builder
conn = builder()(user=’dbuser’, passwd=’dbpassword’,
host=’localhost’, db=’sqlobject_demo’)
——————————-
不管连接哪种数据库，连接代码都应该放置在一个名称类似 Connection.py 的文件中，且该文件存储在一些通常可访问的位置中。这样，可以导入您定义的所有类，并使用已经构建的conn 对象。conn 变量将包含所有与数据库相关的详细信息。
注意：SQLObject 的一些特性不可用于 SQLite 或 MySQL。

4、定义模式
SQLObject 使得操作数据库表变得容易。看第一个简单的例子，考虑一个电话簿应用程序的由单个表组成的数据库模式，如下所示。
字段    类型    说明
id        Int        主键
number    String    “(###) ###-####”字符串格式；应该惟一
owner    String    这是谁的号码？
last_call    Date    用户最后一次呼叫该号码是什么时候？

该表的 SQL 类似如下：
CREATE TABLE phone_number (
id INT PRIMARY KEY AUTO_INCREMENT,
number VARCHAR(14) UNIQUE,
owner VARCHAR(255),
last_call DATETIME,
notes TEXT
)
使用 SQLObject，不需要编写该 SQL 代码。通过定义 Python 类来定义该数据表。该代码将进入名为 PhoneNumber.py 的文件中。
——————————-
import sqlobject
from Connection import conn

class PhoneNumber(sqlobject.SQLObject):
_connection = conn
number = sqlobject.StringCol(length=14, unique=True)
owner = sqlobject.StringCol(length=255)
lastCall = sqlobject.DateTimeCol(default=None)
PhoneNumber.createTable(ifNotExists=True)
——————————-

定义表的类还有一组定义表字段的成员。SQLObject 提供了 StringCol、BoolCol 等等 —— 一个类对应一种数据库字段类型。
createTable() 方法第一次运行时，SQLObject 将创建一个名为 phone_number 的表。然后，它将只使用该表，因为您将 ifNotExists 设置为 True 来调用该方法。

最后注意，无需在 PhoneNumber 中为 id 字段创建字段对象。因为 SQLObject 总是需要该字段对象，所以它总会创建一个。

5、处理CRUD
著名的缩写词 CRUD 代表对数据库行进行的四种操作：Create、Read、Update 和 Delete。定义了与数据库表对应的类之后，SQLObject 将对表行的操作表示为对类及其实例的操作。

创建
要创建数据库行，需创建对应类的实例，代码如下：
——————————-
>>> from PhoneNumber import PhoneNumber
>>> myPhone = PhoneNumber(number=’(415) 555-1212′,
owner=’Leonard Richardson’)
——————————-
现在 phone_number 表有一个存储我的姓名的行。PhoneNumber 构造函数将表列的值作为关键字参数。它使用您提供的数据创建一行 phone_number。如果由于某种原因，数据不能进入数据库，则构造函数抛出一个异常。当电话号码无效时，会发生如下情况：
——————————-
>>> badPhone = PhoneNumber()
Traceback (most recent call last):
File "<stdin>", line 1, in ?
…
TypeError: PhoneNumber() did not get expected keyword argument number
如果电话号码已经在数据库中，将会看到：
——————————-
>>> duplicatePhone = PhoneNumber(number="(415) 555-1212")
Traceback (most recent call last):
File "<stdin>", line 1, in ?
…
TypeError: PhoneNumber() did not get expected keyword argument owner

读取（和查询）
SQLObject 类的实例的所有字段可用作成员。这与其他一些将数据库行当作字典的数据库映射工具相反。因此，对于数据库行中的每个字段，PhoneNumber 对象都具有一个成员。
——————————-
>>> myPhone.id
1
>>> myPhone.owner
‘Leonard Richardson’
>>> myPhone.number
‘(415) 555-1212′
>>> myPhone.lastCall == None
True
但如何检索数据库中已经存在的 PhoneNumber 对象呢？需要对数据库执行查询来获取。这就是 SQLObject 的查询构造工具包（该软件包最有趣的特性之一）发挥作用的地方。它允许将 SQL 查询表示为 Python 对象链。如果您熟悉 Java™ 编程语言的对象关系包的话，它与可以对 Torque 中 Criteria 对象执行的操作一样。
您定义的每个 SQLObject 类都有一个 select() 方法。该方法接受一个定义查询的对象，返回与该查询匹配的项列表。例如，下面这个方法调用返回包含数据库中第一个电话号码的列表：
——————————-
>>> PhoneNumber.select(PhoneNumber.q.id==1)
<sqlobject.main.SelectResults object at 0xb7b76cac>
>>> PhoneNumber.select(PhoneNumber.q.id==1)[0]
<PhoneNumber 1 number=’(415) 555-1212′ lastCall=None
owner=’Leonard Richardson’>
——————————-
PhoneNumber.q.id 指明想要对 phone_number 表的 id 字段运行查询。SQLObject 过载比较操作符（==、!=、<、>= 等等）来执行除布尔表达式之外的查询。表达式PhoneNumber.q.id==1 是与 id 字段值为 1 的每行相匹配的查询。
——————————-
>>> PhoneNumber.select(PhoneNumber.q.id < 100)[0]
<PhoneNumber 1 number=’(415) 555-1212′ lastCall=None
owner=’Leonard Richardson’>
>>> PhoneNumber.select(PhoneNumber.q.owner==’Leonard Richardson’).count()
1
>>> PhoneNumber.select(PhoneNumber.q.number.startswith(‘(415)’)).count()
1
——————————-
可以使用 SQLObject 的 AND 和 OR 函数来组合查询子句：
——————————-
>>> from sqlobject import AND, OR
>>> PhoneNumber.select(AND(PhoneNumber.q.number.startswith(‘(415)’),
>>>                        PhoneNumber.q.lastCall==None)).count()
1
——————————-
下列查询获取一年中呼叫过的所有人以及从未呼叫过的所有人：
——————————-
>>> import datetime
>>> oneYearAgo = datetime.datetime.now() – datetime.timedelta(days=365)
>>> PhoneNumber.select(OR(PhoneNumber.q.lastCall==None,
…                       PhoneNumber.q.lastCall < oneYearAgo)).count()
1
——————————-

更新
如果更改 PhoneNumber 对象的一个成员，则该更改被自动镜像映射至数据库：
——————————-
>>> print myPhone.owner
Leonard Richardson
>>> print myPhone.lastCall
None
>>> myPhone.owner = "Someone else"
>>> myPhone.lastCall = datetime.datetime.now()
>>> #Fetch the object fresh from the database.
>>> newPhone = PhoneNumber.select(PhoneNumber.q.id==1)[0]
>>> print newPhone.owner
Someone else
>>> print newPhone.lastCall
2005-05-22 21:20:24.630120

注意：SQLObject 不允许更改对象的主键。通常最好是让 SQLObject 来管理表的 id 字段，即使是您不使用 SQLObject 时碰巧用另一个字段作为主键。

删除

删除特定行对象的方法是将其 ID 传递到其类的 delete() 方法中：
——————————-
>>> query = PhoneNumber.q.id==1
>>> print "Before:", PhoneNumber.select(query).count()
Before: 1
>>> PhoneNumber.delete(myPhone.id)
>>> print "After:", PhoneNumber.select(query).count()
After: 0
——————————-

6、验证和转换数据
SQLObject 通过允许定义验证和转换入站数据的钩子方法来解决这个问题。可以为表中的每个字段定义一个方法。字段的钩子方法命名为 _set_[field name]()，不管是作为 create 操作还是 update 操作的一部分，每当要为该字段设置一个值时，都会调用该方法。钩子方法应（可选）将入站值转换为可接受格式，然后设置该值。否则，它应抛出异常。要实际设置一个值，该方法需要调用 SQLObject 方法 _SO_set_(field name)。
【PhoneNumber 的 _set_number() 方法。如果电话号码完全没有格式化，比如 4155551212，则该方法将该数字格式化为 (415) 555-1212。否则，如果数字格式不正确，该方法会抛出 ValueError。正确格式化的电话号码 —— 或者是转换为正确格式的电话号码 —— 被正确传递给 SQLObject 的 _SO_set_number() 方法。】
——————————-
import re
def _set_number(self, value):
if not re.match(‘\([0-9]{3}\) [0-9]{3}-[0-9]{4}’, value):
#It’s not in the format we expect.
if re.match(‘[0-9]{10}’, value):
#It’s totally unformatted; add the formatting.
value = "(%s) %s-%s" % (value[:3], value[3:6], value[6:])
else:
raise ValueError, ‘Not a phone number: %s’ % value
self._SO_set_number(value)
——————————-

7、定义表之间的关系
真正的数据库应用程序通常具有多个相关表,SQLObject 允许将表之间的关系定义为外键。作为演示，我们将一个小的数据库规范化（normalization）应用于上一示例，将 PhoneNumber 的 owner 字段分割到单独的 person 表中。清单 14 所示的代码保存在名为 PhoneNumberII.py 的文件中。
——————————-
import sqlobject
from Connection import conn
class PhoneNumber(sqlobject.SQLObject):
_connection = conn
number = sqlobject.StringCol(length=14, unique=True)
owner = sqlobject.ForeignKey(‘Person’)
lastCall = sqlobject.DateTimeCol(default=None)

class Person(sqlobject.SQLObject):
_idName=’fooID’
_connection = conn
name = sqlobject.StringCol(length=255)
#The SQLObject-defined name for the "owner" field of PhoneNumber
#is "owner_id" since it’s a reference to another table’s primary
#key.
numbers = sqlobject.MultipleJoin(‘PhoneNumber’, joinColumn=’owner_id’)

Person.createTable(ifNotExists=True)
PhoneNumber.createTable(ifNotExists=True)
——————————-

该 PhoneNumber 类具有与旧类相同的成员，但它的 owner 成员是对 person 表的主键的引用，而不是对 phone_number 表中字符串列的引用。这使得表示具有两个电话号码的个人成为可能：
——————————-
>>> from PhoneNumberII import PhoneNumber, Person
>>> me = Person(name=’Leonard Richardson’)
>>> work = PhoneNumber(number="(650) 555-1212", owner=me)
>>> cell = PhoneNumber(number="(415) 555-1212", owner=me)
——————————-

Person 的 numbers 成员，一个 SQLObject MultipleJoin，使得基于 person 到 phone_number 的连接进行查询变得容易：
——————————-
>>> for phone in me.phoneNumbers:
…     print phone.number
…
(650) 555-1212
(415) 555-1212
——————————-

同样，SQLObject 允许使用 MultipleJoin 类进行多对多连接的查询。

8、将 SQLObject 用于现有表
SQLObject 的一个常见用途是为另一个应用程序创建的数据库提供 Python 接口。SQLObject 有多个特性可用于实现这一点。

数据库内省
如果正在使用数据库中已经存在的表，则不需要在 Python 中定义列。SQLObject 可以通过数据库内省来提取它需要的信息。例如，清单 17 中的代码保存在 PhoneNumberIII.py 中。
——————————-
import sqlobject
from Connection import conn
class PhoneNumber(sqlobject.SQLObject):
_connection = conn
_fromDatabase = True
——————————-
该类将使用现有 phone_number 数据表的属性。您可以与它交互，就好像已经手动定义了该类及其所有列一样，如前面的示例所示。使用 SQLObject，只需要编写表定义一次 —— 用 SQL 还是用 Python 编写就取决于您了。

但是，该特性又带来了数据库的选择问题。例如，该特性完全不能用于 SQLite。它基本上能用于 MySQL，但不能提取外键关系。如果使用的是 MySQL，而且想要为表定义外键，则需要在从数据库中加载模式之后，编写代码定义这些字段。

命名约定
上一部分中的代码假设现有表符合 SQLObject 的命名约定（例如，表的主键字段名为 id，且列名中的词用下划线分隔）。表的命名约定在 Style 类中定义。

SQLObject 提供了一些与常见数据库命名约定对应的 Style 类。例如，如果列名类似 likeThis 而非 like_this，则可以使用 MixedCaseStyle：
——————————-
import sqlobject
from sqlobject.styles import MixedCaseStyle
from Connection import conn
class PhoneNumber(sqlobject.SQLObject):
_connection = conn
_fromDatabase = True
_style = MixedCaseStyle
——————————-

如果没有预包装的 Style 类符合您的需要，那么您可以定义 Style 基类的子类，并定义自己的命名约定。在最坏的情况下，如果表的字段名分配得毫无道理，则可以逐个命名每个字段。

关于 SQLObject 限制
SQLObject 想让您用面向对象的方式而非关系方式进行思考。这有利于您的理解和您的编程生产率，但不利于性能。毕竟，数据库仍是关系型的。如何标记呼叫过的每个电话号码？使用 SQL，您将使用单个 UPDATE 命令。使用 SQLObject，您需要迭代通过整个结果集，并修改每个对象的 last_call 成员，这是非常低效的。

SQLObject 为开发人员时间牺牲了处理器时间。这通常是好的交易，但甚至在简单的应用程序中，您也可能需要下降一个级别到达 Python 数据库接口，为一些关键路径的操作编写原始 SQL。