Day 24 - 资料结构入门理解

前言

今天要来讨论一些更进阶的程序写法,比较偏向效能方面的优化,怎麽写可以让效能变好、扩充容易,而不是讨论如何写出一个 feature,因为我们的目标是「更好」!

但本篇不会触及太多实作,定向为「让初学者有个概念」,可以大概知道为什麽会有资料结构的出现,不会每次看到这四个字就先晕倒。

因此如果你已经有基本概念了,可以简单看过一起讨论指教,或者左转进我的队友系列文,有非常实作的 LeetCode 刷题讲解,完全可以满足高手区的观众唷!

资料结构是什麽?

在电脑科学中,资料结构(Data Structure) 是电脑中储存、组织资料的方式。当资料存在记忆体中的时候,决定资料的存放顺序及存放位置的,就是资料结构。

听起来还是很抽象,所以我们一步一步来,先来看如果没有特别使用资料结构,我们会遇到什麽问题。

资料结构解决了什麽问题?

假如今天一个电商网站要条列出商品与价格:

const product1 = 'TV';
const product2 = 'laptop';
const product3 = 'washing machine';

const price1 = 12000;
const price2 = 25000;
const price3 = 8000;

console.log(`${product1} 的价钱是 ${price1}`);
console.log(`${product2} 的价钱是 ${price2}`);
console.log(`${product3} 的价钱是 ${price3}`);

执行结果

TV 的价钱是 12000
laptop 的价钱是 25000
washing machine 的价钱是 8000

老板:欸那个 Joey 啊!商品太少了没客人啦!多帮我把冷气、电扇、萤幕、空气清净机、除湿机都放上去啊!

於是我就崩溃了,一个变数如果只能储存一个值,我就要从 prodcut1 放到 product99,而且要把每个项目陈列出来的时候,完全就是复制贴上手抽筋。

聪明的你看到上面的案例,会怎麽去优化它呢?

没错,最基本的就是阵列加物件:

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
];

products.forEach(product => console.log(`${product.name} 的价钱是 ${product.price}`));

当我们这样改写,即便老板说要加项目,我也只要在原本的「结构」内,多添加项目即可,不用新增变数,且 forEach 的程序码一个字都不用动:

const products = [
    { name: 'TV', price: 12000 },
    { name: 'laptop', price: 25000 },
    { name: 'washing machine', price: 8000 },
    { name: 'air conditioner', price: 20000 }, // 只加了这两行
    { name: 'electric fan', price: 1000 }, // 只加了这两行
];

products.forEach(product => console.log(`${product.name} 的价钱是 ${product.price}`));

虽然我们现在对於这个优化习以为常,而且信手拈来,很熟的人甚至不需要经过 prodcut1product2 那层思考,可以直接从阵列开始着手。

那你想过阵列到底在背後做了什麽,才能够让我们这麽方便吗?

阵列在记忆体中的储存方式

记得,变数就是用存放数值的地方

当我们宣告了一个字串变数,其实就是电脑在记忆体中抓一个位置,让你存放 'TV' 这个数值,然後再抓一个位置(不一定是连续的位置),用来放 'laptop'

const product1 = 'TV';
const product2 = 'laptop';

而宣告阵列变数时,其实是电脑在记忆体中抓一连串的位置,帮你在第一格存 'TV',第二格存 'laptop',以此类推。

const products = ['TV', 'laptop', 'washing machine'];

所以我们在使用阵列时,才会只需要记住 products 这个变数名称,因为它的记忆体位址是连续的,只要告诉它 index,就可以按图索骥对应到你要的那一格。

阵列在记忆体摆放上,是特别安排过的、有顺序、有结构的,所以我们才可以利用这个特性,使用 forEachfiltermap 等方便的函式,都是基於这个「结构」才有的操作。

这样理解了吗?Array 就是一个大家使用得相当熟练的,其中一种资料结构。

资料结构的种类

比较常见的就有以下几种:

  • 阵列(Array)
  • 堆叠(Stack)
  • 伫列(Queue)
  • 连结串列(Linked List)
  • 树(Tree)
  • 图(Graph)
  • 堆积(Heap)
  • 杂凑表(Hash table)

不同种类的资料结构适合不同种类的应用,部分资料结构甚至是为了解决特定问题而设计出来的。

所以当我们要写某个领域的实作时,通常也不会每个资料结构都拿出来用,而是「针对特定问题使用特定资料结构」。

比如密码学的领域,就经常使用到 hash table;而如果要做 cron server (排程系统),则比较会用到 queue。

非同步核心的资料结构

还记得我们在 Day 14 讨论到非同步核心,下列这些名词还记得吗:

  • Call Stack
  • Memory Heap
  • Callback Queue

有没有某一块拼图突然吻合的感觉!

Call Stack

Call Stack 是用来存放指令的地方,为什麽要用 stack?因为 stack 的特性是 FILO (First-In-Last-Out),就像我的衣橱一样,最早放进去的衣服最晚才发现要穿((误,第一个放进去的指令要最後才执行,而最後放进去的指令则第一个执行。

听起来很不合理吗?看看这个范例,父函式里面有子函式,只要程序跑到子函式,就会等子函式跑完,才把父函式剩余的程序跑完:

const child = () => {
    console.log('child 1');
};
const parent = () => {
    console.log('parent 1');
    child();
    console.log('parent 2');
};

parent();

执行结果

parent 1
child 1
parent 2

是不是正好符合 stack 的特性呢?

Callback Queue

Callback Queue 则更好理解了,queue 的特性是 FIFO (First-In-First-Out),就像排队要吃一兰拉面的民众一样,先来排队的人最先吃。

放在 callback queue 的指令,会等到 call stack 空了,就由 event loop 侦测放到 call stack,早来的先放。

是不是正好符合 queue 的特性呢?

解决不同问题

因为篇幅的关系,就没有要把每个资料结构都介绍一遍,那也不是「入门理解」的范畴了。但透过上述这些范例,有没有更了解为什麽要用资料结构呢?

当然我们可以全都用 Array 暴力解决:Call Array、Memory Array、Callback Array,存资料而已嘛,我怎麽存都没人管得着。

但就像是把衣服放在书柜上,或者把书本放在冰箱一样的道理,不是不能放,只是使用这些资料的效率就降低了。

因此,没有万能的资料结构,只有使用不同资料结构解决不同问题

结语

资料结构是大学资工系基础必修的一环,基本上只要沾到计算机科学的边,都离不开资料结构,因为牵涉到数值怎麽摆放,记忆体如何分配。

虽然听起来很生硬,背後也真的是很硬的一堆知识,但它无疑是迈向「更好」 develop 的一大步,起码 FAANG 这些国际级的软件大公司,处理的都是数百、数千万的资料量,哪个容得下从头到尾都在用 Array 的菜菜?

资料结构的讨论深度与广度,完全可以再开一个 30 天的铁人赛来挑战,但今天的内容,期待可以让许多非本科系,看到资料结构就怕的人,可以有最基础的理解!

崩坏後重建
以全新的姿态
征服鸿沟

参考资料

资料结构 wiki


<<:  Day24 让你的k8s Pod 具备多介面功能 - 实做篇

>>:  DAY24 - 利用 uptime 让你的 Heroku 永不休眠

007 2021线上看

007 2021线上看 世界局势波诡云谲,再度出山的邦德(丹尼尔·克雷格饰)面临有史以来空前的危机。...

Oracle 1Z0-082 Practice Exam 2021

**Actual Oracle 1Z0-082 Practice Exam - Easiest Wa...

Day15 iPhone捷径-媒体Part5

Hello 大家, 今天快速的讲播放这个分类, 播放这分类的功能相当的单纯就如字面上的意思, 接力播...

企划实现(18)

在撰写程序时我发现了一个以前没有遇到过的事情,我原先一直以为是因为环境导致的但是後来我发现跟环境没有...

成员 13 人:狼来了! 狼来了! 狼...... 好乖

一个黑色的房间中,有一个小孩子,聚光灯照着他。 感觉像刑事局的讯问现场,可是却没有任何的压力来源。 ...