写点什么

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

  • 2021-01-06
  • 本文字数:3835 字

    阅读完需:约 13 分钟

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 == 0end
复制代码


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


总体而言,这种数据结构的缺点之一似乎是它是嵌套的,访问一个值需要读取两个元组。如果我们想使用那些有趣的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 rowdef find_winner(%{{1, 1} => a, {2, 2} => b, {3, 3} => c})  when a == b and b == c and !is_nil(a), do: a # check \ diagonaldef 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 23 4 56 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)enddef display(board)  board |>     Enum.map(&tile_representation/1)    |> Enum.chunk_every(3)    |> Enum.join("\n")    |> IO.putsenddefp tile_representation(nil): "_ "defp tile_representation(tile): "#{tile} "
复制代码


保持数据结构扁平


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


想想这三种方法在实现上的区别。你更愿意使用哪种呢?在我看来,列表(List)实现起来更容易。


总结


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


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


原文链接:


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


2021-01-06 12:011741
用户头像

发布了 257 篇内容, 共 147.7 次阅读, 收获喜欢 576 次。

关注

评论

发布
暂无评论
发现更多内容

区块链电子签章平台搭建,区块链电子合同系统

电微13828808271

创业团队组织建设-跨部门沟通

wood

创业 沟通 28天写作

全员客户成功

boshi

随笔杂谈

架构实战营 - 微信业务架构 & 学生管理系统

阿门阿前一颗葡萄树๑

架构实战营 #架构实战营 「架构实战营」

星环科技分布式文件系统TDFS大揭秘(上)

星环科技

大数据 计算与存储

同程旅行 IAST 落地实践

火线安全

DevOps DevSecOps 漏洞扫描 漏洞分析

5.《重学JAVA》--编码规范

杨鹏Geek

Java 25 周年 28天写作 12月日更

AI安全领域的“雨山机车大赛”,改变了什么?

脑极体

2021年度人工智能最佳产品TOP10!百度飞桨EasyDL再获业界认可

百度大脑

人工智能

质量基础设施“一站式”服务信息平台建设,NQI一站式服务平台

电微13828808271

【技术分享】DOSM Web项目优化分析 & 解决方案

云智慧AIOps社区

TypeScript 之映射类型

冴羽

JavaScript typescript 翻译 大前端

IT 好文&好课分享

hackstoic

架构实战营4期-第1周作业

周念

「架构实战营」

实用机器学习笔记五:探索性数据分析

打工人!

机器学习 学习笔记 12月日更 李沐 实用机器学习

从航海贸易到元宇宙,从公司制到DAO

CECBC

数研所已实现在数字人民币中积极探索区块链应用

CECBC

vue单页面和多页面的区别?

CRMEB

Hoo虎符研究院 | 币圈后浪——KBOX

区块链前沿News

虎符 Hoo虎符 Hoo 虎符交易所

Python Qt GUI设计:QTabWidget、QStackedWidget和QDockWidget容器控件类(提升篇—2)

不脱发的程序猿

Python qt PyQt GUI设计 容器控件类

被寄予厚望的区块链在数据交易中能发挥的作用是什么?

CECBC

如何“对抗”听众的短时记忆

将军-技术演讲力教练

流上机器学习,星环科技Sophon Base助力海洋石油富岛工艺监测智能化

星环科技

Python Qt GUI设计:5种事件处理机制(提升篇—3)

不脱发的程序猿

Python qt PyQt GUI设计 事件处理机制

数字人民币生态体系进一步完善 试点场景加速拓展

CECBC

xxxx

guangbao

非专业的系统安全规范

张老蔫

28天写作

智慧社区综合管理平台解决方案,智慧社区一体化管理系统开发

电微13828808271

Hoo虎符研究院 | 区块链简报 20211206 期

区块链前沿News

虎符 Hoo虎符

【AI最前线】精准优质-资讯|分享|热议第43期

百度大脑

人工智能

共享

mtfelix

28天写作

3步设计出更好的数据结构_大数据_monica_InfoQ精选文章