如何高效存储大量键值对？

Question

我正在编写一个 ML 项目，我需要在其中获取大量位置及其最终结果（跳棋游戏）。位置表示为 0 到 4（包括在内）f 之间的 32 个整数的元组。 e:

pos = (0, 4, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 3, 0, 0, 1, 1, 0, 0, 2, 0, 0, 0, 2, 2, 2, 2, 0, 2, 0, 0)

对于我要存储的每个位置：

result = white_wins - black_wins
num_games # total number of games

因为职位总数太多了（我什至不确定它是否可以管理）。当然，它从上方受到 2.3 x 10^22 左右的限制，实际上不同（可能在游戏中出现）位置的总数要小得多，甚至可能是 10^19 或更少的数量级。在一个 site 我发现游戏可以采用 5 x 10^20 种可能的游戏（移动顺序），这表明独特位置的数量大大减少，但我不确定我是否使用了相同的集合规则等等

值得注意的是，首先进行游戏，然后根据移动记录循环添加每个位置。

从这里我尝试了不同的方法：

1.在 python dict 中存储数据为：

dict = {pos1: [result1, num_games1], ...}

并添加每个位置：

def add_pos(dict, pos, who_won): # who_won = 1 if white wins and -1 if black 0 if draw
    if pos in dict.keys():
        dict[pos][0] += who_won
        dict[pos][1] += 1
    else:
        dict[pos] = [who_won, 1]

然后使用 pytorch 将其存储到 .pth 文件中：

torch.save(dict, f'saves/pos_dict.pth', pickle_protocol=HIGHEST_PROTOCOL)

2。存储在sqlite3数据库

创建于：

self.cur.execute(""" CREATE TABLE IF NOT EXISTS pos_table (
                            pos TEXT PRIMARY KEY ,
                            result INTEGER NOT NULL,
                            num_games INTEGER NOT NULL,
                            eval REAL NOT NULL );""")

添加职位：

def add_pos(cur, pos, who_won):
    pos_str = str(pos)
    cur.execute("SELECT rowid FROM pos_table WHERE pos=?;",(temp,))
    row = self.cur.fetchone()

    if row is None:
        tuple_to_insert = (pos_str, who_won, 1, who_won)
        cur.execute("INSERT INTO pos_table VALUES (?, ?, ?, ?);", tuple_to_insert)
    else:
        cur.execute("""UPDATE pos_table 
                       SET result=result+(?),
                           num_games = num_games+1,
                           eval = result/CAST(num_games AS REAL)
                           WHERE pos LIKE ?;""", (who_won, pos_str))

主要问题：

在这两种情况下，我很乐意摆脱“位置已经在数据库检查中”或以某种方式将其概括为 f.e。合并到字典，但我无法想出任何更快的算法。

第一种方法的问题是，虽然它相当快，但它会占用大量 RAM，而且保存和加载它到文件的速度也会非常慢，因为唯一位置的数量约为 5 000 000。

我发现 SQL 的唯一问题是它变得非常慢非常快（大约 500 000 - 700 000 个唯一位置）这使得它在 1 000 000 行或更多行时变得无用

修复：

简单且可能是必要的修复是选择位置 f.e 的一些特征。兵、皇后等的数量，因此减少了可区分位置的数量。

我听说过 shelves，虽然因为不太可能解决我的问题而拒绝了（没有测试）

因此我有几个问题：

有没有办法改进数据存储系统以增加可以存储的唯一位置的数量？
大约有多少个可区分的位置（在减少到一组特征之后）我能够有效地处理？ - 非常重要的是，查找与键关联的值不会花费很多时间
有没有办法改进“插入算法”？

Answer 1

对于 SQLite，提高性能的一些技巧：

由于您的主键不是 INTEGER，请将其设为 WITHOUT ROWID table。这将减少在数据库中检索与键关联的值所需的查找次数，从 2（首先在索引中找到相应的 rowid，然后在 table 本身）到 1（直接在 table).

self.cur.execute(""" CREATE TABLE IF NOT EXISTS pos_table (
                            pos TEXT PRIMARY KEY NOT NULL,
                            result INTEGER NOT NULL,
                            num_games INTEGER NOT NULL,
                            eval REAL NOT NULL ) WITHOUT ROWID;""")

使用 UPSERT 语法只需要一个查询来插入或更新。

def add_pos(cur, pos, who_won):
    pos_str = str(pos)
    cur.execute("""INSERT INTO pos_table(pos, result, num_games, eval)
                   VALUES (?1, ?2, 1, ?2)
                   ON CONFLICT(pos) DO UPDATE
                   SET result = result + ?2,
                       num_games = num_games + 1,
                       eval = result/CAST(num_games AS REAL);""", (pos_str, who_won))

您还可以以比字符串化元组更紧凑的形式存储位置以节省 space，方法是在字节数组中每个元素使用 3 位（32 个元素总共 12 个字节）。 bitstruct 模块让这一切变得简单。

将 pos 列的类型更改为 BLOB，类似

import bitstruct
# ...
# Pack the positions into bytes
pos_str = bitstruct.pack("u3" * len(pos), *pos)
# Unpack back into a tuple
pos_tuple = bitstruct.unpack("u3" * 32, pos_str)

您可能探索的一个 non-sqlite 替代方案是 shelve 模块，它提供 key-value 对的持久存储：

import shelve
shelfdb=shelve.open("positions")

def add_pos(shelf, pos, who_won)
    pos_str=str(pos)
    if pos_str in shelf:
        tmp = shelf[pos_str]
        tmp[0] += who_won
        tmp[1] += 1
        shelf[pos_str] = tmp
    else:
        shelf[pos_str] = [who_won, 1]

# Close before exiting!
shelfdb.close()

如何高效存储大量键值对？

How to store large amount of key value pairs efficently?

python

sqlite

python-3.x