x/y 坐标稀疏列表的 Python 数据结构

发布于 2024-11-07 20:51:25 字数 417 浏览 0 评论 0原文

考虑 x/y 坐标列表和字节“计数”。 x/y 的范围可能是 0 到 5000，即 2500 万个单元格。

然而，数据将非常稀疏，最多有几千个条目，并且大多数坐标将有零个条目。

该结构偶尔会被查找/添加（例如，如果 x=5 和 y=10 中存在某些内容，则 ++），但更频繁地转换为 x/y/count 列表（排序并不重要）

最快的数据用于查找的结构显然是一个二维数组，但您正在查看 24 MB 左右的内存，并且输出列表的迭代可能会很昂贵。对于磁盘存储，您可以实现 gif 样式压缩，其中 0 字节后跟另一个字节表示 x 个空单元格，其他任何内容都是单元格值 - 但这对内存情况没有帮助。

字典的字典可能会在查找/迭代速度和内存使用之间取得良好的平衡。

我是否应该考虑任何其他合适的数据结构（内置于 Python、现有库或更通用的数据结构？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

居里长安 2024-11-14 20:51:25

以点（即二元组）为键的字典对我来说听起来不错。它的复杂度为 O(1)，类似于数组，而且更加紧凑。只要您不需要进行范围查询或类似的操作，就应该没问题。

# increment
p = (x, y)
counts[p] = counts.get(p, 0) + 1

# list
for (p, count) in counts.iteritems():
    x, y = p
    print x, y, count

A dictionary keyed by a point (ie a 2-tuple) sound good to me. It's O(1) like an array, and significantly more compact. As long as you never need to do range queries or the like, it should be fine.

# increment
p = (x, y)
counts[p] = counts.get(p, 0) + 1

# list
for (p, count) in counts.iteritems():
    x, y = p
    print x, y, count

回复收藏 0 原文

无戏配角 2024-11-14 20:51:25

scipy 有一系列不同的稀疏数组

有七种可用的稀疏矩阵类型：
csc_matrix：压缩稀疏列格式
csr_matrix：压缩稀疏行格式
bsr_matrix：块稀疏行格式
lil_matrix：列表格式的列表
dok_matrix：键格式字典
coo_matrix：坐标格式（又名 IJV，三元组格式）
dia_matrix：对角线格式