如何以更有趣,更轻松的方式学习软件工程的基础知识

2020年12月30日10:51:39 发表评论 36 次浏览

本文概述

本文旨在作为软件工程基础知识的入门指南。

我写这篇文章的前提是, 亲爱的读者, 你可能对该领域的基础知识不太了解, 为什么它们很重要, 以及什么时候应该去学习它们。

我们将深入探讨每个问题, 最后讨论一些建议我学习和处理它们的方法。

对于那些确实熟悉此主题的人, 可能仍然会有一些有趣的新观点, 尤其是在上一节中, 这是加快学习过程的有用方法。

在本文中, 我们将讨论:

  • 是什么让软件工程令我感到恐惧和恐惧, 以及它如何发生变化
  • 我们查看某些代码的原因和度量, 得出的结论是它比另一种方法(计算复杂度)低效率
  • 简单但希望有用的数据结构和算法简介
  • 我个人为了学习软件工程主题而做的事情, 以实现最大的效率和理解
  • 通过添加一些基本测试来衡量算法的正确性和效率来激励你的工作的一种方法

请注意, 我已经尝试按照逻辑上的顺序来组织这篇文章, 其中每个部分(除下一节外, 更多是关于克服对本主题的恐惧的知识)是建立在下一节之上或激发下一节的。

我将一千多个小时的实践和研究浓缩为一篇文章, 并且也尽我所能清楚, 简单地解释了事情。

女电子工程师进行车辆测试

摄影者

这是工程技术

/

不飞溅

问题出在哪里

在有限的正规教育中, 我与数学领域的关系不佳。进而, 这影响了我与大量计算机科学(CS)和软件工程(SEng)的关系。

具体来说, 并不是我数学不好, 但是我数学运算能力很差, 对公式的记忆也很差。

我还发现, 在学校通常教授数学, CS和SEng的方式也不适合我。

迄今为止, 我自己的学习过程主要是由实用主义(强调实践胜于理论知识), 对自然的好奇心以及这些信息如何帮助我谋生-这是我在西方教育中很少强调的三件事。

除了我与主要是数学性质的枯燥乏味的陈述的不安关系外, 我还是一个自学成才的程序员。

明确地说, 我在社区大学上过一门编程课程(大约在2013年), 而我的其余知识则来自于自主学习。在此过程的初期, 我还必须工作各种不同的工作才能支付房租, 这使我几乎没有时间和精力去学习手艺。

最终结果是我选择将大部分时间花在建立个人项目和学习专门针对那些项目的主题上。

这使我非常擅长于编写代码, 学习新技术和解决问题的技能。但是, 如果我确实将CS和SEng中的任何概念应用于所编写的代码, 则很大程度上是偶然的。

总而言之, 我想说的是, 我学习SEng的最大障碍是我对学习它并不十分感兴趣。

我不知道从对算法进行很小的更改就可以获得成就感, 这种算法将其运行时间缩短了数十倍或数百倍。

我不知道根据我要解决的问题的性质来选择数据结构有多重要, 更不用说如何做出决定了。

而且我不知道它与我抛售移动应用程序有什么关系。

因此, 以防万一你在同一条船上, 在我们获取技术细节之前, 我想尝试为你回答其中的一些问题。为了使事情变得不那么乏味, 我将分享一个真实的故事来激发我这个话题, 这个故事改变了我对这个问题的态度。

和大鱼一起游泳

在2019年底之前, 我从学习Android开发中休息了一段时间, 以深入研究UNIX操作系统和C / C ++编程。

我对Android SDK感到很自在, 但是多年的JVM编程使我产生了一种强烈的意识, 即不知道计算机实际上是如何工作的。这困扰了我很多。

我并不是真的在找工作, 但是当时一家大型科技公司的招聘人员向我伸出了我对Android软件工程师职位的兴趣。

尽管在Android平台上工作了数月之久, 但我在第一次采访中还是表现出色(这是我所熟悉的所有Android核心概念), 并收到一封详细说明将来采访中涉及的主题的电子邮件。

这封电子邮件的第一部分详细介绍了Android的特定知识, 内容非常广泛, 但是我至少对大多数主题感到有些熟悉, 但并未感到恐惧。但是, 当我向下滚动到"数据结构和算法"部分时, 突然觉得就像我刚开始编写代码时所做的那样:就像一条没有水的鱼。

并不是我从来没有在代码中应用任何这些概念, 而是我当然没有正式研究过其中任何一个。

尽管我会尽力为你提供有关这些主题的简洁明了的介绍, 但SEng会立即用一句行话来打你, 在阅读完我所拥有的所有DS和Algos清单后, 我的脸比喻非常酸痛和青紫在该电子邮件中学习。

我和我的招聘人员对此非常了解, 他在下一次面试之前给了我四个星期的准备时间。

我知道我不能在四个星期内涵盖所有主题, 但是我确实希望在几个星期内学习一两年的SEng能够显示一些才能和主动性。

我很想告诉你一个多汁的故事, 讲述我是如何失败的, 或者在下一次面试时完全眼花azz乱, 但现实是, 事情甚至在我没有机会之前就崩溃了。

我是加拿大公民, 因此该职位需要搬迁至美国加利福尼亚州或华盛顿州的许多校园之一。

在我第一次深入SEng的两周后, 我收到了我的招聘人员的电子邮件, 内容是他们的移民部门不想赞助我。我怀疑这与在资助一个没有学位的工人方面遇到一些困难有关, 但是正在酝酿中的全球大流行也可能是一个因素。

最后, 即使我希望有机会实时获得成功或失败, 但我很高兴知道自己对在大型科技公司中担任软件工程师所缺乏的知识非常清楚。

在我面前有一条清晰但艰难的道路, 我决心不再让SEng领域吓倒我。我想知道成为软件开发人员与软件工程师的真正含义。

考虑到这一点, 我们将深入探讨SEng中的核心思想, 以及如何使学习它们更容易。不容易-容易。

软件工程中的"三大"主题及其重要性

软件工程的主要主题可以用一堆可怕的大词和短语来概括, 这与计算机科学和数学相关的传统一样。为避免混淆, 我将改用英语和示例进行解释, 这些示例和示例优先考虑清晰度。

我建议你按照本节列出的顺序进行操作, 因为我故意按逻辑顺序进行结构化。

首先-什么是运行时和内存空间?

首先, 我想解释一下我们研究这些主题的原因。

作为物理学迷, 我很高兴得知我们在自然界中看到的时空相互作用也可以在任何类型的计算机中直接观察到。

但是, 在本领域中, 我们将这些品质称为运行和记忆空间.

为了更好地了解什么是运行时, 建议你启动"任务管理器", "活动监视器"或任何可以告诉你系统活动的"进程"的程序。

一个进程只是一个"正在运行的程序", 通过拥有多个"处理器", CPU虚拟化和时间分割的魔力, 看来我们可以同时运行数十个或数百个进程。

我将这些术语称为"专业术语", 以便你对操作系统的工作方式感到好奇时可以查找它们, 但是

这样做没有必要继续本文。

无论如何, 通常可以将流程的运行时视为可以在系统的流程跟踪工具中查看的任何时间点。

我用这个定义指出活动进程不需要用户界面甚至不需要做任何有用的事情即使它可能仍然是占用CPU和内存空间中的运行时间。

说到内存空间, 为了使某些东西能够运行, 它也必须位于某个地方。那是计算机的物理内存空间, 即虚拟化(再次, 抬头虚拟化你可以自行决定, 但本文没有必要), 以使其更加安全且易于使用。

每个进程都分配有自己独特的受保护的虚拟内存空间, 该空间可以根据各种因素增长或缩小到某些边界。

让我们从理论上休息一下

谈论为什么我们应该关心它。

由于运行时和内存空间

可以准确测量

但也

有限

, 如果我们不注意这些限制, 那么像你和我这样的人真的可以搞砸了!

明确地说, 这是我们作为程序员和工程师要关心的两个非常重要的事情:

  • 我们的程序甚至整个系统都会崩溃吗?管理有限的内存空间资源?
  • 我们的程序是否会在一定程度上为我们的用户解决问题?及时有效的方式, 或者它们会挂这么久, 以至于我们的用户决定强迫退出, 要求退款并留下令人讨厌的评论?

这些问题在很大程度上决定了我们计划的成功与否, 无论你是否正式学习它们。幸运的是, 我激励你学习所谓的软件工程三大主题, 我们现在将探讨这三个主题。

我们如何衡量运行时和内存空间

三大主题中的第一个主题用一个可怕的大名词来描述:渐近运行时和空间复杂性.

在已经描述了运行时和内存空间之后, 我认为"复杂性"这个词的一个有用的替代方法是"效率"。渐近性与我们可以在二维笛卡尔图上表示这种效率(或缺乏效率)的事实有关。 , X和ÿ, 跑分上升等等。

如果你不熟悉这些东西, 请不要担心。你只需要对这些事情有非常基本的了解就可以将其应用到代码中。

另外, 请注意图形数据结构, 但该概念与笛卡尔图相去甚远, 而不是我所指的。

由于我们可以表示我们的代码及其相对于笛卡尔图上的运行时或内存空间的行为, 因此必须描述如何绘制图形的函数.

描述这种代码效率的方法是使用" Big O"表示法。

这是我可以为你提供的最简单的介绍, 以帮助你理解该主题。我将在代码示例中使用现代编程语言Kotlin, 这有望为你的Web和本地开发人员提供一个愉快的中间立场。

假设三个函数(有时也称为方法, 算法, 命令或过程):

函数printStatement:

fun printStatement(){
	//print to the system or program’s textual output stream/console
    println("Hello World!")
}

函数printArray:

fun printArray(arr: Array<String>){
    //if 'arr' was {"Hello", "World!"} then the output of this function would be:
    //Hello
    //World!
    arr.forEach { string ->
    	// "string" is a temporary reference given to each element of 'arr'
    	println(string)
    }
}

函数printArraySums:

fun printArraySums(arrOne: Array<Int>, arrTwo: Array<Int>){
    //Prints the sum of every value in both Arrays
    arrOne.forEach { aInt ->
        arrTwo.forEach { bInt ->
        	println(aInt + bInt)
        }
    }
}

为了便于理解, 假设每次println(...)称为"完成"需要100毫秒或平均1秒的时间(实际上, 单个打印命令需要100毫秒, 这非常慢, 但是比微秒或皮秒更容易想象)。

考虑到这一点, 让我们批判性地考虑这些功能的实现方式期望表现不同, 基于他们得到什么输入.

printStatement, 除非系统本身发生灾难性故障, 否则平均需要100毫秒才能完成。

实际上, 尽管Big O表示法非常关注提供给函数的参数的大小(不久之后会更有意义), 但该函数甚至没有任何参数来更改其行为。

因此, 可以说运行时复杂度(完成之前所花费的时间)为常量, 可以由以下数学函数和图形表示:

如何以更有趣,更轻松的方式学习软件工程的基础知识1

运行时(

Ť

)

printStatement

始终平均为100毫秒, 因此

常量

.

在上图中, T表示println(...)我们将其确定为平均100毫秒。我会解释什么ñ指瞬间。

printArray提出了一个新问题。理所当然地, 这需要花费时间printArray完成将是直接成比例到数组的大小, rr, 将其传递给它。

如果Array有四个元素, 则将导致println(...)被调用四次, 总共平均运行时间为400ms。printArray本身。为了更精确地进行数学计算, 我们可以说printArrayis线性的:

如何以更有趣,更轻松的方式学习软件工程的基础知识2

次数

println(...)

被称为直接成比例(即增长

线性地)

关于

n.

printArraySums使事情更进一步你应该关心即使是初级或中级开发人员。的Number给定函数的参数/输入的引用用小n, 使用Big O表示法时。

在我们的第二个函数中, 它专门指数组的大小(即, 尺寸), 但在第三个函数中, 它是指多个参数的集合大小(即, arrone和arrTwo)。

在Big O表示法中, 给定的一段代码实际上具有三种不同的质量, 我们需要注意:

  • 代码的效率如何, 如果ñ很小(最佳情况下的性能)?
  • 代码的效率如何, 如果ñ平均预期大小(平均性能)是多少?
  • 代码的效率如何, 如果ñ是否接近或达到系统的最大允许值(最坏情况下的性能)?

一般而言, 就象土木工程师最关心桥梁可以支持的最大车辆数量一样, 软件工程师通常最关心最坏情况的性能。

通过看printArraySums, 你应该能够推断出我们可以将其表示为最坏情况的运行时复杂度(将调用println(...)的次数)为n * n;其中ñ等于或接近系统中阵列的最大允许大小。

如果不清楚, 我们不只是配对和求和arrone和arrTwo在相同的索引上, 我们实际上将它们的每个值加在一起嵌套循环.

从这里你可以真正理解渐近运行时和空间复杂性的重要性。在最坏的情况下, 运行时间呈二次曲线式增长:

如何以更有趣,更轻松的方式学习软件工程的基础知识3

printArraySums(...)

它的运行时间在

二次的

曲线。对于

Ť

= 100ms,

ñ

甚至不需要太大就可以产生

不良的用户体验

.

关于此主题的最后两点说明:首先, 如果我突然让你对嵌套循环感到有些恐惧(是的, 每个嵌套循环可能会增加另一个因素ñ), 那么我做得很好。

尽管如此, 请理解, 如果你是确定ñ不会超过合理的大小即使在具有指数增长的函数中, 其实不是问题.

如果你想知道如何确定ñ将对性能产生负面影响, 请继续阅读本文的最后一部分。

其次, 你可能已经注意到, 我所有的示例都是关于运行时复杂度, 而不是内存空间复杂度。

原因很简单:我们以完全相同的方式和符号表示空间复杂性。由于我们实际上并没有在临时帧的每个帧中分配一个或两个临时引用以外的任何新内存。forEach {...} 循环渐近地讲, 第二个和第三个函数仍然是线性的O(ñ), 关于内存分配。

数据结构

尽管任何一位老师都会告诉你, 数据结构一词并没有一个单一的定义。

一些教师将强调其抽象性质以及我们如何在数学中表示它们, 一些教师将强调它们在内存空间中的物理排列方式, 而另一些教师则强调在特定语言规范中的实现方式。

我不想告诉你, 但这实际上是计算机科学和工程学中的一个非常普遍的问题:一个单词同时代表很多事情, 很多单词同时代表一件事情。

因此, 与其尝试通过使用过多的技术定义来使来自各种学术或专业背景的各种专家感到高兴, 让我用通俗易懂的英语清楚地解释事情, 让每个人同样感到不安.

就本文而言, 数据结构(DS)是指我们在程序中表示和分组应用程序数据的方式。诸如用户个人资料, 朋友列表, 社交网络, 游戏状态, 高分等等。

当从物理从硬件和操作系统的角度来看, 构建DS的主要方法有两种。两种方式都利用了以下事实:物理内存是离散的(花哨的字表示可数), 因此是可寻址的。

想象这的一种简单方法是考虑街道地址以及如何根据你实际移动的方向(以及你的国家/地区组织街道地址的方式)来增加或减少地址的价值。

物理阵列

第一种方法利用了以下事实:我们可以将数据片段(例如社交媒体应用程序中的朋友列表)分组为一块连续的(物理上彼此相邻)的存储空间。

事实证明, 这是计算机遍历内存空间的一种非常快速有效的方法。而不是给计算机一个ñ每个数据的地址列表大小, 我们为计算机提供一个地址, 该地址表示该DS在物理内存中的开头, 并且大小(即, ñ)作为单个值。

这样做的指令集可以很简单, 就像告诉机器从左向右移动(或任何方向), 减小的值一样简单。ñ每次移动1, 并在该值达到0时停止/返回。

链接列表(地址)

第二种方法要求结构本身中的每个数据片段都必须包含其内部下一个或上一个(也许是两个?)项目的地址。

连续内存空间的主要问题之一是, 它们在增长(添加更多元素)或缩小(这可能会分段内存空间, 我将不解释, 但建议你进行快速Google搜索)。

通过获取每条数据

链接

对于其他部分(通常只是上一个或下一个), 每个部分位于物理内存空间中的位置变得无关紧要。

因此, 我们可以相对轻松地增加或缩小数据结构。你应该能够推断出, 由于结构的每个部分不仅存储其自身的数据, 而且存储下一个(或更多)元素的地址, 因此与连续Array方法相比, 每个块必然需要更多的存储空间。

但是, 它最终是否更有效取决于你要解决的问题。

我所讨论的两种方法通常称为Array和一个链表。几乎没有例外, 我们在DS研究中最关心的是如何将有某种理由分组在一起的数据集合进行分组, 以及如何做到最好。

正如我试图指出的, 在某种情况下使一种结构更好的原因可能会使另一种结构变得更糟。

你应该能够从前几段中得出以下结论:链表通常更适合动态(变化)集合, 而Array通常更适合固定收藏–至少在运行时间和空间效率方面.

但是, 不要误导!并非总是如此, 我们的主要关注点是针对运行时和内存空间选择最有效的DS(或算法)。记住, 如果ñ体积非常小, 然后担心这里的纳秒级或几位内存, 并且不一定像易用性和易读性那么重要。

关于DS, 我想说的最后一件事是, 我发现对于DS与数据类型(DT)之间的区别, 人们缺乏共识。

同样, 我认为这主要是由于不同的专家从不同的背景(数学, 数字电路, 低级编程, 高级别编程)来进行研究的事实, 而且很难对不符合以下条件的人进行口头定义这一事实确实很困难至少部分(或全部)描述另一个。

冒着使情况变得更加混乱的风险, 纯粹实用水平, 我认为数据结构是独立于高级编程语言的类型系统(假设它具有一个)的事物。另一方面, 数据类型由此类系统定义并在其内定义。

但是我知道类型理论本身独立于任何特定的类型系统, 因此你可以希望看到对这两个术语进行具体说明是多么棘手。

演算法

我花了很长时间来解释前面的两个主题, 因为它们使我可以很容易地介绍和激发这个主题。

在继续之前, 我必须非常简短地尝试解开另一种术语。用我自己的方式来解释术语"算法", 实际上非常简单:算法是可由信息处理系统(IPS)理解和执行(作用)的一组指令(命令)。

例如, 如果你要遵循食谱来烹饪某些东西, 那么你将成为IPS, 算法将成为食谱, 而配料和炊具将成为数据输入(参数)。

现在, 根据该定义, 功能, 方法, 过程, 操作, 程序, 脚本, 子例程和算法一词都指向相同的基础概念。

这并非偶然-这些词从根本上讲是同一件事。混乱之处在于, 不同的计算机科学家和语言设计师将以略有不同的方式实现(构建)相同的想法。甚至更令人沮丧的是, 他们将以相同的方式构建它们, 但使用不同的名称。我希望情况并非如此, 但是我能做的就是警告你。

这就是你通常需要了解的所有算法, 因此让我们更具体地了解它们如何帮助我们编写更好的代码。

回想一下, 作为软件工程师, 我们最关心的是编写有限的系统资源方面要保证高效(至少使用户满意)的代码。

还要记得, 我之前曾说过, 某些DS在运行时和内存空间方面比其他DS更好, ñ变大。

算法也是如此。根据你要尝试执行的操作, 不同的算法将比其他算法表现更好。

还值得注意的是, DS将倾向于确定可以将哪些算法应用于该问题, 因此选择正确的DS和正确的算法是正确的 软件工程艺术。

为了完成第三个主要主题, 我们将介绍两种常见但非常不同的解决一个问题的方法:搜索有序数组。所谓有序, 是指它从最小到最大, 从最大到最小, 甚至按字母顺序排列。

同样, 假设给定算法某种目标值作为参数, 这就是我们用来定位特定元素的方法。如果有任何混淆, 在示例中应该清楚这一点。

示例问题如下:我们有一个Users集合(也许是从数​​据库或服务器加载的), 它由一个名为userId的字段(从Integer值开始)从最小到最大排序。

假设此userId来自刚创建新User之前的系统时间(查找Unix Time以获取更多信息)。四舍五入到仍保证没有重复值的最小值。

如果前面的句子没有意义, 那么你只需要知道这是没有重复的排序集合。

编写此算法的一种简单方法是编写我们称为朴素搜索(Naive Search, NS)的内容。在这种情况下, 天真意味着简单, 但方式不好, 这是指我们只是告诉计算机从集合的一端开始, 然后移动到另一端, 直到找到与目标索引匹配的事实。

这通常通过使用某种循环来实现:

函数naiveSearch:

//this function accepts an Integer targetId to match against, // and an Array of User objects as arguments. 
// Assume for simplicity's sake that it is guaranteed to find a User.
fun naiveSearch(targetId: Int, a: Array<User>): User {
    a.forEach { user ->
    	if (targetId == user.userId) return user
    }
}

如果我们恰好在这个集合中只有几百个, 甚至几千个用户, 那么我们可以期望这个函数很快返回相同的结果。

但是, 让我们假设我们正在一个成功的社交媒体技术初创公司中工作, 而我们刚刚吸引了100万用户。

你应该能够推断naiveSearch具有O(ñ)渐进复杂度作为最坏情况的运行时复杂度。简而言之, 原因是如果目标用户恰好位于ñ, 那么我们必须始终遍历整个集合以到达那里。

如果你还不熟悉二进制搜索(BS)算法, 则应该做好准备。

如果我告诉你, 使用BS算法搜索一百万个元素的集合, 你最多只能进行20次比较呢?没错20个比较(NS中为100万个)是最坏的情况.

现在, 我将解释BS的原理, 但是我要做的一项家庭作业是用你喜欢的编程语言来实现它。你选择的语言可能已经从其标准库中获得了BS实现, 但这是一项重要的学习练习!

原则上, 与其搜索下令单向一个接一个地收集, 我们从查看索引处的值开始ñ/ 2。因此, 在具有10个元素的集合中, 我们将检查第五个元素。排序很重要, 因为我们可以然后比较元素ñ/ 2与我们的目标:

  • 如果该元素的值大于目标值, 则我们知道所需元素必须位于集合的更早位置
  • 如果该元素的值小于目标值, 那么我们知道我们想要的元素必须位于集合的更前面
  • 你应该能够猜测如果我们有一场比赛会怎样

现在, 我们的想法是每次迭代将数据集减少一半。假设元素的值ñ/ 2小于我们的目标值。接下来, 我们将选择中间的索引ñ/2和ñ.

从那里开始, 我们的算法将在集合中越来越少的索引范围内使用相同的逻辑来回切片。

这使我们领会到应用于有序集合的BS算法的美妙之处:与其完成线性或指数增长所需的时间, 不如ñ, 它对数增长:

如何以更有趣,更轻松的方式学习软件工程的基础知识4

二进制搜索具有

对数的

运行时复杂度, 这意味着它将处理较大的

ñ

像老板一样(很好)

如果本文确实是你对软件工程主要思想的第一次介绍, 那么请不要指望一切都会立即生效。

虽然我希望我的一些解释会有所帮助, 但我的主要目标是为你提供一些基本的想法供你学习, 并认为这是学习这些想法的一个好顺序。

你的下一步是制定学习此领域的计划, 并对此采取行动。接下来的部分是关于如何做到这一点的。

如何学习软件工程–一些实用建议

现在, 我将讨论一些个人想法和方法, 这些想法和方法使我从动机角度出发, 使学习各种DS和算法的过程更加容易(但不容易!)。

我相信这里至少会有一两个点会有用(假设你自己还没有到达他们), 但是我也想强调一下, 我们的大脑可能会略有不同。拿走有用的东西, 把剩下的扔掉。

作为学习帮助, 你可能还想在youtube上观看我的直播课程, 其中涵盖了该主题。但是, 请不要跳过本文的其余部分。我在这里详细介绍!

我大约在每个星期日早上都在youtube上进行实时问答, 通常在节目开始时有一节课。

遵循基于项目的学习方法

实际上, 这是我告诉任何要求我"最佳方式"学习编码的新程序员的第一件事。我已经多次给出了这种解释的较长版本, 但是我将总结一下总体思路。

在任何编程领域中, 你都会注意到有很多主题需要研究, 并且该领域本身对于学者和行业专业人员都在不断发展。

正如我在导言中提到的, 我不仅没有课程来指导我的学习, 而且学习时间也很有限, 因为我每个月底都有房租。这使我完全没有必要开发和遵循基于项目的学习方法。

本质上, 我建议你做的是避免仅通过逐个主题地研究事物并仅记录每个事物而避免学习DS和算法。

相反, 你将首先选择一个基本主题(例如我之前介绍过的主题), 然后立即编写一个使用该主题的代码片段或小型应用程序。

我创建了一个存储库, 其中包含要学习的每个DS和算法系列的软件包。对于一般算法, 它主要是排序和搜索(气泡排序, 合并排序, 快速排序, 二进制搜索等)。对于链表, 树, 堆, 堆栈等其他更特定的DS, 我既编写了DS本身, 又编写了一些特定于该DS的算法。

现在, 我发现一开始很难理解和实施某些DS。

一个在一段时间内给我带来麻烦的DS家族称为"图表"。一般而言, 该领域充满了一些特别糟糕的术语, 但该特定主题甚至具有误导性的名称(提示:更好的名称是" Networks")。

在转动轮子几周后(尽管公平地说, 我是在一边学习), 我终于对自己承认, 我需要明确的理由在某些应用程序代码中使用此DS。证明和激发了我要花很多时间来学习这个主题的东西。

我之前曾使用可处理二维和一维数组的算法构建过Sudoku游戏, 但我记得在某处读到了可以使用无向彩色图.

这非常有用, 因为我已经熟悉Sudoku的问题领域, 因此我可以集中精力研究DS和算法。

尽管我还需要学习很多东西, 但是当我编写一种算法在450毫秒内生成并解决102个Sudoku难题时, 我无法描述它的满足感。

说到这, 让我谈谈编写更好算法的另一种方法, 这也可能是激励和目标设定的重要来源。

测试你的代码

看, 我知道很多人将测试当作是初学者的噩梦的主题。发生这种情况的原因是, 他们混淆了如何通过一些非常复杂且令人困惑的工具来测试代码这一非常简单的想法可选地用于测试他们的代码。但是这一点很重要, 所以请和我在一起。

回到基础, 甚至不谈Big O表示法, 我们如何知道一种算法是否比另一种算法更有效?当然, 我们必须同时测试它们。

现在, 重要的是要提到基准测试可以给你一个好的(或什至很棒的)总体思路, 但是它们也受到测试系统的强烈影响。

测试需要越精确, 就越需要对测试环境, 设置和准确性进行关注。但是, 对于我通常编写的那种代码, 我只需要一个好的一般想法。

在编写算法时, 有两种测试对实践和生产代码最有用。第一种测试回答了一个非常简单的问题:它有效吗?

以我的Graph Sudoku应用程序为例, 我面临的第一个障碍是为各种大小的Sudokus建立所谓的邻接表(我测试了4, 9、16和25, 这并非偶然, 完美正方形(从数学上来说)。

我无法详细说明什么是邻接表, 但在概念上将其视为节点和线的网络(称为边缘由于某些原因)。实际上, 它形成"图"的虚拟结构。

在数独规则中, 数字的每一列, 每一行或子网格均不得包含任何重复。根据这些规则, 我们可以得出结论, 在9x9的数独中, 必须有81个节点(每个数字一个), 每个节点都应具有21条边(给定的列, 行或子网格中的每个其他节点一个边缘)。

第一步是简单地检查以确保我在构建正确数量的节点:

@Test
fun verifyGraphSize() {
    //note: In Kotlin, brackets following a class name denotes 
    //an assignment statement; it does not use a "new" keyword
    val fourGraph = SudokuPuzzle(4, Difficulty.MEDIUM)
    val nineGraph = SudokuPuzzle(9, Difficulty.MEDIUM)
    val sixteenGraph = SudokuPuzzle(16, Difficulty.MEDIUM)
    assert(fourGraph.graph.size == 16)
    assert(nineGraph.graph.size == 81)
    assert(sixteenGraph.graph.size == 256)
}

该算法确实很容易编写, 但下一个算法要困难一些。

现在, 正如他们在图行话中所说, 我需要构建边缘。这有点棘手, 因为我必须编写一些算法来选择动态大小的行, 列和子网格。同样, 为确认我的工作是正确的, 我编写了另一个测试:

@Test
fun verifyEdgesBuilt() {
    val fourGraph = SudokuPuzzle(4, Difficulty.MEDIUM)
    val nineGraph = SudokuPuzzle(9, Difficulty.MEDIUM)
    val sixteenGraph = SudokuPuzzle(16, Difficulty.MEDIUM)
    fourGraph.graph.forEach {
    	assert(it.value.size == 8)
    }
    nineGraph.graph.forEach {
    	assert(it.value.size == 21)
    }
    sixteenGraph.graph.forEach {
    	assert(it.value.size == 40)
    }
}

有时我遵循测试驱动开发(TDD)方法, 并在算法之前编写测试, 有时在算法之后编写测试。

无论如何, 一旦我能够验证每种算法的正确性, 以至于我生成了一个已解决的, 大小可变的Sudoku拼图, 就该编写一套不同的测试了:基准测试!

这种特定类型的基准测试非常简单, 但这就是我所需要的。为了测试我的算法的效率, 该算法在此阶段可以构建和解决随机生成的数独, 我编写了一个测试, 生成了101个数独难题:

@Test
fun solverBenchmarks() {
    //Run the code once to hopefully warm up the JIT
    SudokuPuzzle(9, Difficulty.EASY).graph.values.forEach {
    	assert(it.first.color != 0)
    }
    //loop 100 times
    (1..100).forEach {
    	SudokuPuzzle(9, Difficulty.EASY)
    }
}

最初, 在生成100个谜题之前和之后, 我有两个对System.nanoTime()的调用, 然后减去该差值得到一个难以理解的数字。

但是, 我的IDE也跟踪完成测试需要花费多长时间(以分钟, 秒和毫秒为单位), 所以我最终还是这么做了。第一组基准(针对9x9拼图)如下:

/**
* First benchmarks (101 puzzles):
* 2.423313576E9 (4 m 3 s 979 ms to completion)
* 2.222165776E9 (3 m 42 s 682 ms to completion)
* 2.002508687E9 (3 m 20 s 624 ms ...)
* ...
*/

尽管我没有太多的参考点, 但我知道生成9x9数独花费的时间超过了一秒钟。非常不好的迹象.

我对如何提前为Graph预先加载一些有效数字感到不满意, 因此我决定在那里重构方法。

自然地, 在想出一种新的方法来做这件事之后, 结果会更糟:

/**
* ...
* Second benchmarks after refactoring seed algorithm:  (101 puzzles)
* 3.526342681E9 (6 m 1 s 89 ms)
* 3.024547185E9 (5 m 4 s 971 ms)
* ...
*/

经过许多基准测试后, 随着时间的推移, 基准测试似乎会稍微变差, 我很沮丧, 并想知道该怎么做。

我有一种非常巧妙的方法, 可以根据将数字放入拼图的确定性来使我的算法多少有些挑剔。但是, 在实践中效果不是很好。

通常, 在我通过代码步进器(调试工具的一部分)进行的第400遍代码中, 我注意到我有一个小错误, 这与我如何调整值有关, 该值决定了我的选择有多严格算法是。

接下来发生的事情使我震惊。

我进行了另一个基准测试, 结果很奇怪:

/**
* ...
* Fifth benchmarks niceValue only adjusted after a 
* fairly comprehensive search (boundary * boundary) 
* for a suitable allocation 101 puzzles:
* 3774511.0 (480 ms)
* ...
*/

我完全不敢相信, 所以我要做的第一件事是撤消我刚刚所做的更改并重新运行测试。 5分钟后, 我停止了测试, 因为这显然是改变游戏规则的区别, 并继续运行另外五个基准测试:

/**
* 3482333.0 (456 ms)
* 3840088.0 (468 ms)
* 3813932.0 (469 ms)
* 3169410.0 (453 ms)
* 3908975.0 (484 ms)
* ...
*/

为了解决这个难题, 我决定尝试构建101个16x16拼图。以前我什至无法构建其中之一(至少在测试运行10分钟后我停止尝试):

/**
* 16x16 (all previous benchmarks were for 9 * 9):
* 9.02626914E8 (1 m 31 s 45 ms)
* 7.75323967E8 (1 m 20 s 155 ms)
* 7.06454975E8 (1 m 11 s 838 ms)
* ...
*/

我要交流的重点是:不仅仅是编写测试使我能够验证我的算法是否有效。他们让我有客观的方法来确定他们的效率。

通过扩展, 这为我提供了一种非常清晰的方法, 可以了解我对算法进行的50种不同调整中的哪些实际上对结果产生了正面或负面的影响。

这对于应用程序的成功非常重要, 但对我自己的动力和心理健康也非常有利。

我还没有提到的是, 我从第一个基准达到第五个基准(快速基准)所花费的时间大约为40小时(每天四小时, 每天10小时)。

第四天我确实很沮丧, 但是当我最终以正确的方式调整事物时, 这是我第一次感到自己像一个真正的软件工程师, 而不是只是一个人为了娱乐而学习。

为了给你留下美好的印象, 在我进行了16x16的测试并看到它们很有希望之后, 我花了整整15分钟的时间在我的农村物业周围跑来跑去, 就像兴奋的黑猩猩一样, 刚好用了肾上腺素。

我的最终建议

我会简短而甜蜜的。当学生无法理解困难和复杂的事物时, 最糟糕的事情就是责备自己。

好的老师和讲解很少见, 对于我们大多数人都觉得相对枯燥乏味的话题尤其如此。

我不得不观看大约四个视频, 阅读了大约五个文章/教科书的章节, 并且盲目地编写一些最初对我来说没有意义的代码, 甚至只是开始使用图表.

这对你来说可能是好消息, 也可能是坏消息, 但是我会很努力地做自己的工作, 而且我很少在自己的领域中找到对我而言自然或轻松的事情。

我写这篇文章的目的从来都不意味着学习软件工程对我来说很容易, 也对你来说并不容易。

所不同的是, 我不时被告知我对事情进行了很好的解释, 而与仅仅反省其他老师所说的人们不同, 我花时间找出对我有用或不可行的东西, 并尝试分享和你在一起

我真的希望本文中的内容对你有用。祝你学习目标顺利, 编码愉快!

你走之前...

如果你喜欢我的作品, 那么你可能会喜欢我的视频内容。我创建了所有内容, 从针对特定主题的专用教程, 每周的现场问答环节到10个小时以上的编程马拉松, 我都会在其中创建一站式整个应用程序.

一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: