如何在 Python 代码中表示二维网格

介绍

这篇博文探讨了 Python 列表和字典可用于表示二维数据结构的不同方式。 我还写了一些测试程序来衡量每个数据结构的性能。

二维或 2D 网格用于各种应用。 想想棋盘、自上而下的视频游戏、电子表格、康威的生命游戏模拟都是存储在二维网格中的数据示例。 我们可以使用笛卡尔坐标系为网格中的每个项目创建唯一的“地址”。 x坐标是水平地址，y坐标是垂直地址。

编程中的笛卡尔坐标系与您可能在数学课上学到的坐标系不同。 原点（即 (0, 0) 坐标）位于屏幕的左上角，而 x 坐标在数学中向右增加，而 y 坐标向下增加而不是向上增加. 在像 Excel 这样的电子表格程序中，x 坐标可能用字母而不是数字表示，但我们将使用数字表示 x 和 y 坐标。 当一起列出时，x 坐标排在第一位。 在坐标(2,-5)中，2为x坐标，-5为y坐标。

顺便说一句，这里有一个使用 2D 数据结构的 Python 项目列表，它们来自我的免费书籍 The Big Book of Small Python Projects：

项目#13 – 康威的生命游戏项目#23 – 蚀刻抽屉项目#37 – 饥饿的机器人项目#39 – 兰顿的蚂蚁项目#44 – 迷宫赛跑者 2D 项目#73 – 数独游戏项目#79 – 2048

二维数据结构

“二维数据结构”是指包含其他值的数据结构，就像列表和字典包含其他值一样。 虽然列表中的数据可以通过整数索引访问，字典中的数据可以通过键值访问，但我们的二维数据结构中的数据将通过两个整数访问：x 和 y 坐标。

我将在这篇博文中比较三种不同的数据结构：

“一维列表”，其中数据存储在 Python 列表中。 坐标 (x, y) 处的数据存储在索引处 grid[y * WIDTH + x]. “二维列表”，其中数据存储在列表的 Python 列表中。 坐标 (x, y) 处的数据存储在 grid[x][y]. 一个字典，数据存储在……一个 Python dictioanry。 坐标 (x, y) 处的数据存储在 grid[(x, y)]. （我们可以指定 grid[x, y] Python 会自动将其解释为包含的元组 x 和 y.)

我可以从头顶看到一些优点和缺点：

一维列表和二维列表必须具有固定的宽度和高度。 字典可以在任意坐标存储数据。 1D 列表和 2d 列表使用相同的完整内存量，无论它们有多空或多满。 字典只使用与其包含数据一样多的内存。 使用 2D 列表可能会很棘手，尤其是将 x 和 y 坐标相互混合时。 这是推测，但我认为随着字典变满，它会比一维或二维列表占用更多的内存。 这是推测，但我认为字典在访问和存储数据方面可能比列表慢。

性能测试

无需深入了解 Big O 算法分析的细节（您可以在我的免费书籍 Beyond the Basic Stuff with Python 的第 13 章中了解），访问和存储数据是列表、列表的列表和字典的常量时间操作. 这意味着当列表或字典填满数据时，访问或存储数据通常不会花费更长的时间。

但是，我更感兴趣的是这些的具体性能指标以及内存使用情况。 我将编写测试来衡量这三种不同的网格数据存储方法。 您可以自己在计算机上下载并运行这些测试。 我在运行 Windows 10 的 T480s Thinkpad 笔记本电脑上使用 Python 3.10.0 运行它们。

我使用 Python 的 timeit 模块来衡量测试代码的性能。 您还可以在 Beyond the Basic Stuff with Python 中了解此模块。

这是我编写的 gridtest.py 程序，用于测量这三种 2D 网格数据结构的运行速度和内存使用情况。 我把我得到的输出放在各自的旁边 print() 称呼：

import timeit from sys import getsizeof, stderr from itertools import chain from collections import deque # 这些常量是测试中使用的网格的大小： WIDTH = 150 HEIGHT = 50 # 确定内存使用情况的函数 来自 https://code.activestate .com/recipes/577504-compute-memory-footprint-of-an-object-and-its-cont/?in=user-178123 def memoryUsage(o, handlers={}, verbose=False): dict_handler = lambda d : chain.from_iterable(d.items()) all_handlers = {tuple: iter, list: iter, deque: iter, dict: dict_handler, set: iter, frozenset: iter, } all_handlers.update(handlers) # 用户处理器优先seen = set() # 跟踪哪些对象 id 已经被看到 default_size = getsizeof(0) # 在没有 __sizeof__ 的情况下估计对象的大小 def sizeof(o): if id(o) in seen: # 不要重复计算同一个对象 return 0 seen.add(id(o)) s = getsizeof(o, default_size) for typ, handler in all_handlers.items(): if isinstance(o, typ): s += sum(map(sizeof, handler(o)) ) break return s 返回大小 eof(o) def createAndFillDict(): # 使用字典从头开始创建一个二维网格，并用数据完全填充它。 dictGrid = {} for x in range(WIDTH): for y in range(HEIGHT): dictGrid[(x, y)] = ‘A’ return dictGrid def createAndFillDictComp(): # 使用字典理解从头开始创建一个二维网格，并用数据完全填充它。 return {(x, y): ‘A’ for x in range(WIDTH) for y in range(HEIGHT)} def createAndFill1DList(): # 使用列表从头开始创建一个二维网格，并用数据完全填充它。 list1DGrid = []
for i in range(WIDTH * HEIGHT): list1DGrid.append(‘A’) return list1DGrid def createAndFill1DListComp(): # 使用列表理解从头开始创建一个二维网格，并用数据完全填充它。 返回 [‘A’ for i in range(WIDTH * HEIGHT)]

def createAndFill2DList(): # 使用列表列表从头开始创建一个二维网格，并用数据完全填充它。 list2DGrid = []
对于范围内的 x（宽度）：list2DGrid.append([]) 对于范围内的 y(高度): list2DGrid[-1].append(‘A’) return list2DGrid def createAndFill2DListComp(): # 使用列表推导式的列表推导式从头开始创建一个二维网格，并用数据完全填充它。 list2DGrid = [[‘A’ for y in range(HEIGHT)] for x in range(WIDTH)]return list2DGrid def read1DList(grid): # 读取列表 2D 网格中的每个坐标。 对于范围内的 x（宽度）：对于范围内的 y（高度）：数据 = 网格[y * WIDTH + x]

def read2DList(grid): # 读取 lists 2D grid 列表中的每个坐标。 对于范围内的 x（宽度）：对于范围内的 y（高度）：数据 = 网格[x][y]

def readDict(grid): # 读取字典 2D 网格中的每个坐标。 对于范围内的 x（宽度）：对于范围内的 y（高度）：数据 = 网格[x, y]

def write1DList(grid): # 写入列表 2D 网格中的每个坐标。 对于范围内的 x（宽度）：对于范围内的 y（高度）：网格[y * WIDTH + x] = ‘A’ def write2DList(grid): # 写入列表中的每个坐标以列出二维网格。 对于范围内的 x（宽度）：对于范围内的 y（高度）：网格[x][y] = ‘A’ def writeDict(grid): # 写入字典 2D 网格中的每个坐标。 对于范围内的 x（宽度）：对于范围内的 y（高度）：网格[x, y] = ‘A’ print(‘比较一维列表和一维列表理解创建：’) print(timeit.timeit(‘createAndFill1DList()’, number=10000, globals=globals())) # 5.796480499964673 print(timeit.timeit( ‘createAndFill1DListComp()’, number=10000, globals=globals())) # 3.3725536999991164 # 结论：使用列表理解创建列表比 for 循环更快。 print(‘比较二维列表和二维列表理解创建：’) print(timeit.timeit(‘createAndFill2DList()’, number=10000, globals=globals())) # 7.913099199999124 print(timeit.timeit(‘createAndFill2DListComp() ‘, number=10000, globals=globals())) # 3.83729699999094 # 结论：使用列表理解创建二维列表比嵌套 for 循环更快。 print(‘比较词典和词典理解的创作：’) print(timeit.timeit(‘createAndFillDict()’, number=10000, globals=globals())) # 9.804479899990838 print(timeit.timeit(‘createAndFillDictComp()’, number=10000, globals=globals())) # 10.132151499972679 # 结论：通过反复试验，没有显着差异。 print(‘比较一维列表、二维列表和字典创建：’) print(timeit.timeit(‘createAndFill1DListComp()’, number=10000, globals=globals())) # 3.2536532999947667 print(timeit.timeit(‘createAndFill2DListComp()’, number=10000, globals=globals())) ()’, number=10000, globals=globals())) # 3.1561911000171676 print(timeit.timeit(‘createAndFillDict()’, number=10000, globals=globals())) # 9.759650700027123 # 结论：字典最慢创建，一维和二维列表差不多。 print(‘比较三种方法中每一种方法的完整网格的内存使用情况：’) print(memoryUsage(createAndFill1DListComp())) # 67274 print(memoryUsage(createAndFill2DListComp())) # 72282 print(memoryUsage(createAndFillDict()) ) # 719246 # 结论：一维和二维列表使用的数量大致相同，一维列表更少。 虽然字典使用了 10 倍的内存。 print(‘比较读取网格数据的速度：’) list1dGrid = createAndFill1DListComp() list2dGrid = createAndFill2DListComp() dictGrid = createAndFillDict() print(timeit.timeit(‘read1DList(list1dGrid)’, number=10000, globals=globals() )) # 8.444686400005594 print(timeit.timeit(‘read2DList(list2dGrid)’, number=10000, globals=globals())) # 3.76759669999592 print(timeit.timeit(‘readDict(dictGrid)’, number=10000, globals=globals ())) # 7.19706789997872 # 结论：二维列表读取数据的速度是其他列表的两倍。 一维列表比字典慢。 print(‘比较写入网格数据的速度：’) print(timeit.timeit(‘write1DList(list1dGrid)’, number=10000, globals=globals())) # 8.487390499969479 print(timeit.timeit(‘write2DList(list2dGrid) ‘, number=10000, globals=globals())) # 4.278829399961978 print(timeit.timeit(‘writeDict(dictGrid)’, number=10000, globals=globals())) # 7.716881500033196 # 结论：与读取测试一样，二维列表的速度是其他列表的两倍。 一维列表比字典慢。

结论

二维列表方法最快，字典方法最慢，使用的内存是一维和二维列表的 10 倍。 但是字典方法为您提供了无限网格的灵活性，而一维和二维列表具有固定的宽度和高度。 一维列表计算索引的要求实际上使它比字典慢。

因此，如果您需要一个 2D 网格数据结构，请使用列表列表方法，除非您需要一个无界网格。 在那种情况下，字典方法要慢得多，但提供了这种灵活性。 或者，如果性能不重要，则字典方法的实现最简单。

在我个人看来，易于实施和可调试性是最重要的因素，而且我的用例往往不会达到性能差异显着的足够大的规模。 我会采用字典方法。

阅读更多