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

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] )
...

列列表列表(显然有一个add_row等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

在内存中有一个需要查找,排序和任意聚合的"表"确实会调用SQL.你说你试过SQLite,但是你是否意识到SQLite可以使用仅内存数据库？

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

然后,您可以使用SQLite的所有功能在内存中创建/删除/查询/更新表,并在完成后不留下任何文件.从Python 2.5开始,sqlite3它就在标准库中,所以它并不是真的"过度杀伤"IMO.

以下是如何创建和填充数据库的示例:

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很满意,所以YMMV.

Answer 2

我知道一个非常古老的问题,但......

大熊猫DataFrame似乎是这里的理想选择.

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

从模糊

具有标记轴(行和列)的二维大小可变,可能异构的表格数据结构.算术运算在行标签和列标签上对齐.可以被认为是Series对象的类似dict的容器.主要的pandas数据结构

http://pandas.pydata.org/

Answer 3

我个人会使用行列表列表.由于每行的数据始终采用相同的顺序,因此只需访问每个列表中的元素,即可轻松按任意列进行排序.您还可以根据每个列表中的特定列轻松进行计数,并进行搜索.它基本上与二维阵列一样接近.

这里唯一的缺点是你必须知道数据的顺序,如果你改变了这个顺序,你将不得不改变你的搜索/排序例程来匹配.

你可以做的另一件事是有一个词典列表.

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

这将避免需要知道参数的顺序,因此您可以查看列表中的每个"年"字段.

Answer 4

有一个Table类,其行是dict或更好的行对象的列表

在表中不直接添加行,但有一个更新少量查找映射的方法,例如,如果你没有按顺序添加行,或者id不是连续的,你也可以拥有idMap,例如:

class Table(object):
    def __init__(self):
        self.rows =  []# list of row objects, we assume if order of id
        self.nameMap = {} # for faster direct lookup for row by name

    def addRow(self, row):
        self.rows.append(row)
        self.nameMap[row['name']] = row

    def getRow(self, name):
        return self.nameMap[name]


table = Table()
table.addRow({'ID':1,'name':'a'})

Answer 5

首先,鉴于您有一个复杂的数据检索场景,您确定甚至SQLite都是矫枉过正吗？

你最终会得到一个临时的,非正式指定的,错误缠身的,缓慢执行一半的SQLite,解释Greenspun的第十条规则.

也就是说,您选择单个数据结构会影响搜索,排序或计数中的一个或多个,这是非常正确的.因此,如果性能至关重要且数据不变,您可以考虑为不同目的使用多个结构.

最重要的是,衡量哪些操作将更为常见,并决定哪种结构最终会降低成本.