在内存中维护表格数据的数据结构？

Question

我的情况是这样的：我有一张数据表（字段不多，行数不到一百），在我的程序中经常使用这张表。我还需要这些数据能够保存下来，所以我把它存成CSV文件，并在启动时加载。我选择不使用数据库，因为任何数据库（即使是SQLite）对我来说都太复杂了（而且我希望能简单地离线编辑这些值，而没有什么比记事本更简单的了）。

假设我的数据看起来是这样的（在文件中是用逗号分隔的，没有标题，这里只是个示例）：

 Row  | Name     | Year   | Priority
------------------------------------
 1    | Cat      | 1998   | 1
 2    | Fish     | 1998   | 2
 3    | Dog      | 1999   | 1 
 4    | Aardvark | 2000   | 1
 5    | Wallaby  | 2000   | 1
 6    | Zebra    | 2001   | 3

注意事项：

1. 行可能是写入文件的“真实”值，也可能只是一个自动生成的值，表示行号。无论哪种情况，它在内存中都是存在的。
2. 名字是唯一的。

我对这些数据做的事情：

1. 根据ID（循环遍历）或名字（直接访问）查找某一行。
2. 根据多个字段以不同的顺序显示表格：比如我需要先按优先级排序，然后按年份，或者先按年份再按优先级，等等。
3. 我需要根据一组参数来计数，比如有多少行的年份在1997到2002之间，或者有多少行在1998年且优先级大于2，等等。

我知道这“很需要”SQL...

我在想，什么样的数据结构最合适。以下是我看到的几种选择：

行列表的列表：

a = []
a.append( [1, "Cat", 1998, 1] )
a.append( [2, "Fish", 1998, 2] )
a.append( [3, "Dog", 1999, 1] )
...

列列表的列表（显然会有一个API来添加行等）：

a = []
a.append( [1, 2, 3, 4, 5, 6] )
a.append( ["Cat", "Fish", "Dog", "Aardvark", "Wallaby", "Zebra"] )
a.append( [1998, 1998, 1999, 2000, 2000, 2001] )
a.append( [1, 2, 1, 1, 1, 3] )

列列表的字典（可以创建常量来替换字符串键）：

a = {}
a['ID'] = [1, 2, 3, 4, 5, 6]
a['Name'] = ["Cat", "Fish", "Dog", "Aardvark", "Wallaby", "Zebra"] 
a['Year'] = [1998, 1998, 1999, 2000, 2000, 2001] 
a['Priority'] = [1, 2, 1, 1, 1, 3] 

字典，键是（行，字段）的元组：

Create constants to avoid string searching
NAME=1
YEAR=2
PRIORITY=3

a={}
a[(1, NAME)] = "Cat"
a[(1, YEAR)] = 1998
a[(1, PRIORITY)] = 1
a[(2, NAME)] = "Fish"
a[(2, YEAR)] = 1998
a[(2, PRIORITY)] = 2
...

我相信还有其他方法...不过每种方法在满足我的需求（复杂的排序和计数）时都有缺点。

有什么推荐的做法吗？

编辑：

为了澄清，性能对我来说不是主要问题。因为表格很小，我相信几乎每个操作都在毫秒级别，这对我的应用程序来说并不是个问题。

Answer 1

我个人会选择用一个包含多个列表的列表。因为每一行的数据总是按照相同的顺序排列，所以你可以很方便地通过访问每个列表中的特定元素来对任何一列进行排序。你也可以轻松地根据某一列的内容进行计数和搜索。总的来说，这种方式和二维数组非常相似。

其实唯一的缺点就是你需要知道数据的顺序，如果你改变了这个顺序，就得相应地调整你的搜索和排序方法。

另外，你还可以使用一个字典的列表。

rows = []
rows.append({"ID":"1", "name":"Cat", "year":"1998", "priority":"1"})

这样就不需要知道参数的顺序了，你可以直接查看列表中的每个“年份”字段。

Answer 2

我知道这是个很老的问题，但...

在这里，使用 pandas 的 DataFrame 似乎是个理想的选择。

http://pandas.pydata.org/pandas-docs/version/0.13.1/generated/pandas.DataFrame.html

根据介绍

DataFrame 是一种二维的、可以改变大小的数据结构，适合存放不同类型的数据，像一个带标签的表格（有行和列）。在进行数学运算时，它会根据行和列的标签来对齐数据。可以把它看作是一个像字典一样的容器，用来存放 Series 对象。它是 pandas 的主要数据结构。

http://pandas.pydata.org/

Answer 3

在内存中有一个需要查找、排序和任意聚合的“表”，这确实很适合用SQL来处理。你提到你试过SQLite，但你知道SQLite可以只在内存中使用数据库吗？

connection = sqlite3.connect(':memory:')

这样你就可以在内存中创建、删除、查询和更新表，享受SQLite的所有功能，而且完成后不会留下任何文件。从Python 2.5开始，sqlite3已经包含在标准库里，所以我觉得这并不是“过度使用”。

下面是一个如何创建和填充数据库的示例：

import csv
import sqlite3

db = sqlite3.connect(':memory:')

def init_db(cur):
    cur.execute('''CREATE TABLE foo (
        Row INTEGER,
        Name TEXT,
        Year INTEGER,
        Priority INTEGER)''')

def populate_db(cur, csv_fp):
    rdr = csv.reader(csv_fp)
    cur.executemany('''
        INSERT INTO foo (Row, Name, Year, Priority)
        VALUES (?,?,?,?)''', rdr)

cur = db.cursor()
init_db(cur)
populate_db(cur, open('my_csv_input_file.csv'))
db.commit()

如果你真的不想使用SQL，可能可以考虑使用字典列表：

lod = [ ] # "list of dicts"

def populate_lod(lod, csv_fp):
    rdr = csv.DictReader(csv_fp, ['Row', 'Name', 'Year', 'Priority'])
    lod.extend(rdr)

def query_lod(lod, filter=None, sort_keys=None):
    if filter is not None:
        lod = (r for r in lod if filter(r))
    if sort_keys is not None:
        lod = sorted(lod, key=lambda r:[r[k] for k in sort_keys])
    else:
        lod = list(lod)
    return lod

def lookup_lod(lod, **kw):
    for row in lod:
        for k,v in kw.iteritems():
            if row[k] != str(v): break
        else:
            return row
    return None

测试的结果是：

>>> lod = []
>>> populate_lod(lod, csv_fp)
>>> 
>>> pprint(lookup_lod(lod, Row=1))
{'Name': 'Cat', 'Priority': '1', 'Row': '1', 'Year': '1998'}
>>> pprint(lookup_lod(lod, Name='Aardvark'))
{'Name': 'Aardvark', 'Priority': '1', 'Row': '4', 'Year': '2000'}
>>> pprint(query_lod(lod, sort_keys=('Priority', 'Year')))
[{'Name': 'Cat', 'Priority': '1', 'Row': '1', 'Year': '1998'},
 {'Name': 'Dog', 'Priority': '1', 'Row': '3', 'Year': '1999'},
 {'Name': 'Aardvark', 'Priority': '1', 'Row': '4', 'Year': '2000'},
 {'Name': 'Wallaby', 'Priority': '1', 'Row': '5', 'Year': '2000'},
 {'Name': 'Fish', 'Priority': '2', 'Row': '2', 'Year': '1998'},
 {'Name': 'Zebra', 'Priority': '3', 'Row': '6', 'Year': '2001'}]
>>> pprint(query_lod(lod, sort_keys=('Year', 'Priority')))
[{'Name': 'Cat', 'Priority': '1', 'Row': '1', 'Year': '1998'},
 {'Name': 'Fish', 'Priority': '2', 'Row': '2', 'Year': '1998'},
 {'Name': 'Dog', 'Priority': '1', 'Row': '3', 'Year': '1999'},
 {'Name': 'Aardvark', 'Priority': '1', 'Row': '4', 'Year': '2000'},
 {'Name': 'Wallaby', 'Priority': '1', 'Row': '5', 'Year': '2000'},
 {'Name': 'Zebra', 'Priority': '3', 'Row': '6', 'Year': '2001'}]
>>> print len(query_lod(lod, lambda r:1997 <= int(r['Year']) <= 2002))
6
>>> print len(query_lod(lod, lambda r:int(r['Year'])==1998 and int(r['Priority']) > 2))
0

就我个人而言，我更喜欢SQLite的版本，因为它能更好地保留你的数据类型（在Python中不需要额外的转换代码），而且可以轻松扩展以满足未来的需求。不过，我对SQL比较熟悉，所以你的体验可能会有所不同。