3步设计出更好的数据结构

作为开发人员，在开始编码前，我们能做的最有价值的事情就是弄清楚函数和模块将要操作哪种类型的数据结构。为什么呢？正如下面看到的那样，如果我们使用了正确的数据结构，那么编写操作它们的函数也就变得更容易了，这反过来也能带来乐趣和收益。

本文的目的是通过一个示例来说明如何获得良好的数据结构。我们将通过比较用于存储井字游戏棋盘（Tic Tac Toe）的三种不同数据结构来实现这一点。

让我们先睹为快。你会押注在哪一个上呢?

一个简单真实的例子

首先，先来描述一个之前遇到的问题。我构建了一个 Elixir/Phoenix 应用程序，并用它作为 React 客户端的后端。由于希望 React 应用程序在初始页面加载之后能非常快，我们因此设计了一个 API 端点用来提供大量当前用户的状态。初始 JSON 的 payload 如下所示：

{
  "user": {
    "id": 1,
    "full_name": "Bob Dobolina",
    "email": "bob@dobo.inc",
    "projects": [
      {
        "id": 1,
        "name": "Project 1",
        "proofs": [
          {
            "id": 1, 
            "title": "A design proof",
            "comments": [...]
          }
        ]
      }
    ]
  }
}

在用户的控制面板上，我们显示一个项目列表，使用这种结构很容易实现。但要渲染一个带有 proof 和 proof 注解的页面时，事情就变得棘手。使用这种深度嵌套的数据结构，React 客户端需要遍历树并提取数据才能获得特定的 proof，这将是一件非常痛苦的事情。解决方案是将这个数据结构展平，并使其能够更容易地按 id 进行查询。数据结构必须要对我们在其上执行的主要操作有意义才行，即按 id 查询数据。

三个步骤

下面的例子是用 Elixir 编写的，但这种常规方法适用于任何编程语言。具体方法如下：

1. 列出需要在数据结构上执行的操作
2. 头脑风暴一些数据结构
3. 通过检查需要执行的操作来评估每种数据结构

在这个阶段，你需要了解代码是否易于编写，并且就 CPU 和内存的使用而言，性能是否能满足需求。

如果你在想：“我是为企业开发 Web 应用程序的，能从井字游戏中学到什么呢？”，请耐心地等待下。本文的要点与我们日常工作中需要解决的算法问题是非常相关的。

在棋盘上将要执行哪些操作？

首先，列出将要在数据结构上执行的操作，因为如果不了解这些，我们就无法评估要用的数据结构是好是坏。有很多方法可以表示一个 3x3 棋盘，但哪一种最适合作为井字游戏的棋盘呢？那么，我们需要用井字游戏的棋盘做些什么呢？

• 在给定的坐标上读写值
• 在终端中将棋盘显示为3×3的网格
• 检查表示获胜的8个不同位置
• 了解棋盘是否满了，这样我们就可以检查游戏是否结束了

头脑风暴数据结构并对其进行评估

对于本文的其余部分，我们将从这块棋盘开始：

X _ __ O __ X _

我们尝试一些数据结构，并评估其利弊。

第一次尝试：行和列的嵌套元组（Tuple）

直观地说，当提到一个 3x3 的网格时，你可能就会想到一个矩阵或二维数组。在 Elixir 中实现该功能的方法之一就是使用嵌套元组（Tuple）。

旁注：为什么不在这里使用嵌套列表呢？对于函数型数据结构，建议在值有意义的情况下使用元组。在本例中，外部元组表示行，内部元组表示列。

{  {"X", nil, nil},  {nil, "O", nil},  {nil, "X", nil}}

看起来是个不错的开端。

让我们来看一下操作列表，并感受一下将它们编写成函数是多么容易。

在给定的坐标上读写值

现在轮到第二个玩家了，他们想在第 1 行第 3 列的棋盘上角写一个 O。

为此，我们可以编写一个类似write(board, row: 1, col: 3, move: "O")的函数。

如何实现这个函数呢？

由于 Elixir 中的数据结构是不可变的，这意味着我们必须为第 1 行重新创建元组，并重新创建棋盘元组以返回更新的棋盘。实现并不难，但很笨拙，代码也不太易读。

我们不必把函数写出来就知道它实现起来会很麻烦。

将棋盘显示为 3x3 的网格

这似乎很简单，我们只要将嵌套的元组展平到一个列表中并对每个元素进行遍历即可。

检查表示获胜的 8 个不同位置

得益于 Elixir 的模式匹配，检查棋盘是否有一条获胜线的代码非常易读且易于实现。例如，如果你想检查中间一行是否有获胜线，则可以这样编码。

def find_winner(
  {
    {_, _, _},
    {a, b, c},
    {_, _, _},
  }
) when a == b and b == c and !is_nil?(a), do: a

了解棋盘是否满了

为了检查棋盘是否满了，我们可以计算所有可用的格子，用nil表示可用：

def board_full?(board)
  num_free_tiles = board
    |> Tuple.to_list
    |> Enum.reduce(0, fn(row, free_spots) ->
      free_in_row = row |> Tuple.to_list |> Enum.count(&is_nil/1)
      free_in_row + free_spots
    end)
  num_free_tiles == 0
end

也许这里还能有更好的实现，但是到目前为止，上面的代码看起来并不太易于阅读和维护。

总体而言，这种数据结构的缺点之一似乎是它是嵌套的，访问一个值需要读取两个元组。如果我们想使用那些有趣的Enum函数 ，元组也不易于遍历，因为我们必须要将它们转换成列表。

第二次尝试：以坐标作为键的映射（Map）

在元组数据结构中，最大的问题是如何使其易于访问给定行列的值。我们尝试创建一个键（key）为{row, col}坐标的映射（Map）来简化这一过程。

{
  {1, 1} => "X",
  {1, 2} => nil,
  {1, 3} => nil,
  {2, 1} => nil,
  {2, 2} => "O",
  {2, 3} => nil,
  {3, 1} => nil,
  {3, 2} => "X",
  {3, 3} => nil
}

读写某个位置上的数据

有了这个数据结构，那就更容易了。

要读取第 1 行第 1 列的项，我们可以简单地通过键来进行查找：

%{{1, 1} => val} = board

若要更新第 1 行第 3 列的值，我们可以使用Map.put：

Map.put(board, {1, 3}, "O")

检查表示获胜的 8 个不同位置

我们可以采用与读取单个值相同的策略来读取一组值。例如，如果使用模式匹配来检查第一行是否具有相等的值，可以这样编码：

@doc ~S"""
  接受一个棋盘，如果有赢家或nil，则返回“X”或“O”。
  
  例如
  
  iex> TicTacToe.find_winner(
      {
        {1, 1} => "X", {1, 2} => "O", {1, 3} => nil,
        {2, 1} => nil, {2, 2} => "X", {2, 3} => nil,
        {3, 1} => nil, {3, 2} => "O", {3, 3} => "X"
      }
    )
  "X"
"""
# 检查第一行是否具有相同的值
def find_winner(%{{1, 1} => a, {1, 2} => b, {1, 3} => c})
  when a == b and b == c and !is_nil(a), do: a # check first row
def find_winner(%{{1, 1} => a, {2, 2} => b, {3, 3} => c})
  when a == b and b == c and !is_nil(a), do: a # check \ diagonal
def find_winner(%{{1, 3} => a, {2, 2} => b, {3, 1} => c})
  when a == b and b == c and !is_nil(a), do: a # check / diagonal
# ...其余5种情况依此类推
def find_winner(_board), do: nil

这很容易实现，但在我看来，代码本身并不易读。通过阅读第一个子句，不易看出它的功能是要检查第一行是否具有相同的值。当不得不添加注解来解释这行代码的作用时，我总是觉得代码有点不好。而且，在 doctest 中，棋盘本身的可读性并不强，更不用说在 IEx 中IO.inspect它了，可读性将会更差，因为每个键都将打印在一个新行上。

将棋盘显示为 3x3 的网格

在 Elixir 中，Map虽然看起来像是有序的（因为IEx会按顺序显示它们），实际上并不是。这意味着我们不能只遍历键并打印出值。

为了显示棋盘，我们可以使用行 id 和列 id 的嵌套循环，并以这种方式查找值。

但这并不理想。我们来看看能不能想出更好的办法。

第三次尝试：位置列表（List）

我们不再从行和列的角度考虑棋盘，而是从位置 0 到 8 的角度考虑棋盘呢？

0 1 2
3 4 5
6 7 8

在 Elixir 中，我们可以使用列表（List）来表示。

[
  "X", nil, nil,
  nil, "O", nil,
  nil, "X", nil
]

这个感觉比另外两个更合适！你的直觉是否如蝴蝶般飘动？让我们通过检查操作来再次验证下这种直觉吧。

读写某个位置上的数据

与其说“玩家 1 在第 1 行第 3 列标记了 X”，不如说成“玩家 2 在位置 2 标记了 O”，像这样List.update_at(board, 2, "X")很简单。

要检查位置 2 是否已经被占用，就像Enum.at(board, 2)一样简单，这是一个 O(n) 运算，但我们根本不需要担心这个问题的时间复杂性，因为我们处理的是如此小的数据集。

检查表示获胜的 8 个不同位置

就像嵌套元组的示例一样，检查棋盘上是否有一条获胜线，我们可以使用模式匹配。假设我们要检查第二行是否都有相同的数值：

[
  _, _, _,
  a, b, c,
  _, _, _
] = board

对角线呢？

[
  a, _, _,
  _, b, _,
  _, _, c
] = board

知道棋盘是否满了，展示棋盘

展示棋盘以及检查棋盘是否已经满了，这也是非常容易实现的。

def board_full?(board)
  !Enum.any?(board, &is_nil/1)
end
def display(board)
  board |> 
    Enum.map(&tile_representation/1)
    |> Enum.chunk_every(3)
    |> Enum.join("\n")
    |> IO.puts
end
defp tile_representation(nil): "_ "
defp tile_representation(tile): "#{tile} "

保持数据结构扁平

一般来说，在设计数据结构时，越扁平的结构越容易使用。像元组（Tuple）和映射（Map）棋盘这样的嵌套结构很难更新。由于 Elixir 是不可变的，因此每当我们更新数据结构时，都必须将变更组装成原始结构。数据结构嵌套的越多，实现起来就越难。

想想这三种方法在实现上的区别。你更愿意使用哪种呢？在我看来，列表（List）实现起来更容易。

总结

良好的数据结构可能是干净的、可维护的、无缺陷的代码库与垃圾代码库之间的区别。

希望你能喜欢这篇文章，如果你有任何关于如何储存井字游戏棋盘的想法，请在评论中留言！

原文链接：

https://mochromatic.com/3-steps-to-designing-better-data-structures-in-elixir/