AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

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:012061
用户头像

发布了 427 篇内容, 共 293.7 次阅读, 收获喜欢 664 次。

关注

评论

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

网络协议之HTTP:HTTP 1.1与HTTP 2

程序员架构进阶

HTTP2.0 28天写作 HTTP协议 5月日更

源码解析之Seata项目中的分布式ID生成算法

Coder的技术之路

分布式 分布式ID

限流与Guava RateLimiter原理解析

千珏

Java 微服务 限流算法 Guava 令牌桶

嵌入式程序调用函数的内部过程和机制

不脱发的程序猿

单片机 嵌入式程序 嵌入式设计

你认识镜子里的那个自己吗?

小天同学

原则 认知 5月日更

CampusBulider(模模搭)学习笔记5:创建自定义建筑

ThingJS数字孪生引擎

大前端 可视化 3D 3D可视化 数字孪生

再学习一个 Golang 专栏

escray

学习 极客时间 Go 语言 5月日更

关于组件,你真的了解么?

架构精进之路

组件化 5月日更

Gradle学习笔记

ES_her0

5月日更

Nginx负载均衡配置误区

运维研习社

nginx 负载均衡 5月日更

“云演唱会”也有仪式感!能检票、可转赠,爱奇艺“云票”如何重构线上购票逻辑

爱奇艺技术产品团队

STM32电源框图解析(VDD、VSS、VDDA、VSSA、VREF+、VREF-、VBAT等的区别)

不脱发的程序猿

嵌入式 stm32 单片机 电源框图解析

Spring Cloud Alibaba 生态学习

风翱

spring cloud alibaba 5月日更

人证一体机产品设计

lenka

5月日更

学习笔记:02 | 第一个程序:教你输出彩色的文字

Nydia

学习

华为云PB级数据库GaussDB(for Redis)揭秘第十期:GaussDB(for Redis)迁移系列(上)

华为云开发者联盟

数据仓库 华为云 数据迁移 GaussDB(for Redis) PB级数据库

揭秘 Amazon Go 无人商店是如何炼成的!

亚马逊云科技 (Amazon Web Services)

零基础学习NLP-DAY2

Qien Z.

nlp 5月日更

流量变现业务概论——Linkedmall流量变现业务初步分析及系统设计概要

关贺宇

【LeetCode】子数组异或查询Java题解

Albert

算法 LeetCode 5月日更

anyRTC 六周年 打造全网最低音视频价格

anyRTC开发者

音视频 WebRTC RTC sdk

如何高效地存储与检索大规模的图谱数据?

华为云开发者联盟

存储 知识图谱 检索 图结构 表结构

Amazon Route 53 Resolver 落地中国区,轻松玩转私有域名互访不是梦!| 新服务上线

亚马逊云科技 (Amazon Web Services)

将自媒体玩得风生水起的不一定是前总统,还有可能是艺术家

zhoo299

艺术 自媒体 5月日更

NumPy之:理解广播

程序那些事

Python Numpy 程序那些事

iMazing比iTunes好用在哪些地方

懒得勤快

HuskyLens人工智能摄像头

不脱发的程序猿

人工智能 智能硬件 AIOT HuskyLens 人工智能摄像头

Ansible AD-Hoc

耳东@Erdong

ansible 5月日更

Windows自带的功能这么好用,还装什么第三方软件?

彭宏豪95

windows 5月日更

编程思考路径2条

顿晓

5月日更 思考路径

Amazon Glue 版本 2.0 将作业启动时间缩短了 10 倍,现已全面开放!

亚马逊云科技 (Amazon Web Services)

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