七爪源码：JavaScript 算法入门

avaScript 算法基础第 1 部分：什么是算法？解决特定问题时必须遵循的一组规则。

让我们从关于算法的非常基本的问题开始。

什么是算法？

解决特定问题时必须遵循的一组规则。

这是您在 Google 上搜索“算法”时会看到的基本定义。让我们理解它，这里的“规则集”是指解决特定问题必须遵循的一系列指令。这意味着，如果我们对一个问题遵循相同的规则集和相同的输入，那么它总是会导致相同的解决方案。这就是算法背后的核心思想。

作为程序员，我们编写的任何程序都被视为算法，因为它遵循上述相同的基本规则。例如，如果我们创建一个函数来将一个数字与另一个数字相加，那么我们在那里也有一个算法。而且，作为程序员，我们的目标是找到最有效的问题解决方案。这意味着我们将始终寻求解决特定问题的最佳可用解决方案，因为将有多种方法来解决它。现在我们遇到的问题是，我们如何找到最佳的可用解决方案？

如何找到最好的算法？

当我们谈论找到给定问题的最佳解决方案时，我们可以考虑以下几点：

它是消耗最少内存的算法吗？
是代码量最少的算法吗？
是花费最少时间的算法吗？

最好的解决方案很可能取决于我们工作的条件。但通常它会是执行时间最少的那个。因此，我们应该寻找执行时间最少的算法。但是，我们如何衡量算法的时间呢？

测量算法的时间复杂度（使用时间差）

让我们用一个例子来看看我们如何测量算法的时间复杂度。

示例问题

编写一个函数，将数字作为输入，然后返回所有数字的总和。

功能：此功能可以在 JavaScript 中实现如下。

const n=[1, 2, 3, 4, 5];    // Inputfunction sum(n) {
  let total=0;
  for (let index=0; index < n.length; index++) {
    total +=n[index];
  }
  return total;
}console.log(sum(n));         // 15

上面的函数接受一个数字数组作为参数，用 0 初始化总数，然后在 for 循环中我们遍历数组中的所有数字，添加到总数中，最后返回总数。

例如，如果我们使用数组作为 [1, 2, 3, 4, 5] 调用函数，那么我们得到的结果为 15（即 1 + 2 + 3 + 4 + 5）。所以这是我们解决上述问题的第一个算法。

现在，让我们看看如何衡量它所花费的时间。

为此，一种简单的方法是通过计算函数的开始时间和结束时间之间的差异来测量时间。这可以在 JavaScript 中如下所示完成。

let startTime=0;
let endTime=0;
let timeToExecute=0;startTime=performance.now();
sum([1, 2, 3, 4, 5]);
endTime=performance.now();
timeToExecute=endTime - startTime;

timeToExecute 将为我们提供函数的执行时间。让我们尝试找出具有几个不同参数的函数所花费的时间。我们将在两个不同的设备上执行此操作，一个在较慢的设备上，另一个在较快的设备上。

在较慢的设备上执行上述功能：

sum([1,2,3,4,5,6,7,8,9,10]);
// 0.19999980926513672 -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
// 0.2999999523162842  -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]);    
// 0.40000009536743164  -> Time

在更快的设备上执行上述功能：

sum([1,2,3,4,5,6,7,8,9,10]);  
// 0  -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30]);
// 0  -> Timesum([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40]);
// 0  -> Time

现在，如果我们在较慢的设备和较快的设备上查看结果输出，您会发现时间并不总是相同的。在慢速设备上，它会随着阵列大小的增加而逐渐增加。但是，在速度更快的设备上，它是恒定的。

同样，假设我们对同一问题有另一种解决方案，我们认为它比上述实现更快，但结果相同，即在更快的设备上为 0，那么我们很难在两者中找出最佳解决方案.因此，根据这些具体数字来测量时间并不是正确的方法。因为它有很多与我们的算法无关的影响因素。例如，我们正在运行的设备硬件很重要。

正如我们在上面看到的，在旧设备上，我们看到不同的数字。可能还有其他影响因素，比如后台运行的进程数、可用内存量较少等。那么，我们应该如何衡量函数时间呢？

测量算法的时间复杂度（使用模式）

答案在于我们在不同输入下看到的模式，我们将在此处参考较慢设备的结果，其中对于数组中传递的更多数字往往需要更长的时间。

一般来说，我们可以说的是，数组中的数字越多，所需的时间就越长。而且，模式中似乎很常见的一件事是时间随着数组大小的增加而增加。事实上，这就是我们应该如何看待它。

我们不应该太在意具体数字，因为这些取决于上面看到的环境中的许多因素。但我们应该始终寻找这种和类似的一般模式。所以对于这个函数，如果你想画一个图形，它大概是这样的。

这是一个线性图，因为我们在上述函数中看到的模式是线性的。我们看到函数所花费的时间随着数组大小的增加而增加。而且，时间的增加与数组大小的增加成正比。所以我们可以说增长是线性的，因此我们在这里有一个线性增长函数。

我们增加输入的因子，在我们的例子中（n）（即数组中的数字）是时间函数增加的因子。

这就是我们在谈论算法时判断性能的方式。我们查看时间的函数，即我们看到的模式，而不是实际时间，以便能够通过算法对输入的反应时间来评估算法的性能。而且，我们也称其为时间复杂度。在这种情况下，我们可以说求和函数和算法具有线性时间复杂度。

上述问题的另一种解决方案（线性时间与恒定时间）

在 JavaScript 中，并非所有算法都需要线性时间。有时我们的算法需要固定的时间。在这种情况下，输入的数量不会影响该算法所花费的时间。我们可以通过修改前面的示例来看到这一点，如下所示，以接受数字作为不同的参数而不是数组。

function sum(n1, n2, n3, n4, n5) {
  return n1 + n2 + n3 +n4 +n5;
}sum(1, 2, 3, 4, 5)   // 15

在这种情况下，该函数接受五个参数并返回所有参数的总和。这也是解决上述问题的另一种方法，我同意这不是最佳解决方案，因为参数的数量是固定的，如果我们需要更多的数字来传递参数，那么我们将不得不为它。

但是，它仍然解决了问题，即计算所有通过的数字的总和。但是，当我们比较这两个函数时，需要注意一个重要的区别。修改后的函数没有循环，而是只有一个数学公式。

现在，如果我们尝试通过使用与循环应用到前一个函数相同的参数来执行上述函数来测量时间，你会看到这里的结果是恒定的。

sum(1,2,3,4,5,6,7,8,9,10);
// 0  -> Timesum(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30);
// 0  -> Timesum(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40);
// 0  -> Time

而且，无论我们传递多少参数，它都保持不变。我们在这里也没有任何模式，因为我们以前有不同的数组大小。我们可以将其视为恒定时间的示例。具有恒定时间复杂度的图看起来像这样。

因此，通过比较上述两种算法的时间复杂度，即循环的函数（指较慢设备的结果）和数学公式的函数，我们可以说一个具有线性时间复杂度，另一个具有恒定时间复杂。

模式方法可靠吗？

然而，这里有一个问题，如果我们在一个速度非常快的设备上执行这两个函数，结果是恒定的时间值怎么办？我们在这里做什么？因为我们刚刚遵循的模式方法无法应用，因为那里没有模式，因为结果是恒定的。

在这种情况下，我们可能会做出错误的判断，并将两个函数的时间复杂度视为常数，而我们刚刚在较慢的设备示例中看到的情况并非如此。因此，即使这种通过基于时间识别模式来识别函数时间复杂度的技术也是不可靠的，因为它受到很多因素的影响。但是，我们确实有一种可靠的方法来评估算法，我们将在以后的帖子中对其进行研究。

感谢您的阅读。

关注七爪网，获取更多APP/小程序/网站源码资源！

雯发自凹非寺
量子位报道 | 公众号 QbitAI

5月中旬刚刚结束的Pycon US 2021上，Python之父Guido van Rossum提出要在未来四年内将CPython速度提升5倍。

而这一“Shannon计划”的参与者除了Guido本人之外，还有任职微软的CPython核心开发人员Eric Snow，以及Semmle的研究工程师Mark Shannon。

但在此之前，Guido可并不认为提升CPython的速度有多关键，因为“有其他方法可以获得更好的性能”，比如JIT编译的PyPy，或使用C语言编写扩展。

为什么要加速？

Python真的慢吗？

不见得，开发效率和执行速度本就难以兼得。

而且发展到今天，Python已经是一个胶水语言的定位，主要用来快速构建系统的逻辑控制流，再把对性能要求高的部分丢给C/C++来实现。

不过如果只看标准版的语言实现本身的话……它的性能确实不怎么样。

动态语言的特性决定了Python会在C语言代码运行（runtime）上花费大量的时间，且难以使用JIT（Just-In-Time）进行优化。

在接受英国技术新闻网站The Register的采访时，对于“为什么开始关注CPython性能？”的问题，Shannon表示：

过去几年里，Python在机器学习领域的使用率大大提升，可用资源也越来越多。这意味着我们可以不用担心破坏其可靠性，而是专注在性能上。

并且，Shannon之前参与的HotPy项目中所开发的解释器，比目前CPython解释器的纯Python代码快三倍。这证明了对CPython优化的可行性。

而在去年10月份的时候，耐不住退休寂寞的Guido又加入了微软：

再加上疫情的家里蹲buff，拥有了更多时间的大佬们一拍即合，决定Make Python Great Again。

加速之前的挑战

Shannon坦言，向下兼容是加速Python的最大挑战。

其实不仅是对Python，90年代末libc的那次不兼容更新，直接导致所有应用程序都要重编……

而现在已经凉凉的Pyston，官方文章里提到的Dropbox放弃Pyston项目的几大因素中，第一个也是：

这就是所有既试图兼容CPython，又想大幅提升性能的Python都会遇到的严峻问题。

因为Python的执行类似于HTML渲染：更多是对运行时应如何执行C库的描述，而非单步执行命令。

所以，Python性能提升的源头来自于这些C扩展模块。而CPython又有着超过400k的loc，这意味着要从底层去做优化是一项非常庞大的工程。

特别是对于过于动态的Python语言来说，语言的语义对优化的影响就更大了。

而现在加速的过程中，像是CPython的工具、调试器、配置文件，NumPy包，以及Cython这样的编译器，又会有多少涉及到CPython内部和底层的行为？

因此Shannon表示：

要改变是困难的……与CPython用户间的隐形协议并没有很好地定义什么能改，什么不能改。

可能是五年前从Python2.x迁移到3的痛苦经历实在是有些刻骨铭心，Guido专门发推表示这次的迁移会更加平和。

而他也在Python峰会中承诺：不破坏stable ABI兼容性；不破坏limited API兼容性；不破坏或减缓extreme cases。

“总之，代码的可维护性才是第一要务。”

Python的5倍速之路

按照已在GitHub上发布的faster-cpython，Shannon计划具体分为四个阶段：

Python 3.10

预计在今年10月发布，主要添加一个自适应、专业化的解释器（interpreter）。

解释器将不在运行时生成代码，而是利用程序中的类型稳定性，在执行过程中适应类型和数值。

Python 3.11

Guido提出要在3.11版本实现至少2倍的提速，为此，他已经和几位Python开发人员提出了一份增强功能的提案PEP 659。

这一提案中表示要增加适应性的字节码解释器，并且实施更有效的异常处理。

除此之外，还提出了优化帧堆栈、改变函数调用的方式、增加优化以加快启动时间，以及修改 .pyc 字节码缓存文件格式等工作。

Python 3.12

这一阶段使用针对小区域的JIT解释器，在运行代码时简单、快速地对小区域的专门代码进行编译。

Python 3.13

同样在代码运行时对扩展区域进行编译，增强编译器，以完成5倍的超级加速。

Guido表示此次围绕性能展开的 Python 变更，将主要服务于运行CPU密集型纯Python代码的开发者，以及内置Python网站的用户。

而在C语言代码（如 NumPy和TensorFlow）、I/O 绑定代码、多线程代码以及算法代码上，提升效果将会比较有限。

微软回馈Python

其实，微软长期以来一直以多种方式为Python项目提供助力，包括在Azure云AI服务教程里发布免费的Python课程，以及通过VS Code Python扩展在Win10及以上版本支持Python。

自 2006 年起，微软还成为了Python软件基金会（PSF）的赞助商，并在今年出资15 万美元进行资助。

目前已有五位Python开发者社区的核心人员在微软任职，包括去年年底加入的Python之父，和这次Shannon计划里的三人之一Eric Snow。

Guido也在这次峰会里特地cue了一下微软，提出微软资助了一支小型Python团队“负责语言解释层面的性能改进工作”，以使他能携手微软同事持续对Python进行开发。

当然，对于3.11版本的短期目标，Guido还是在ppt中给自己兜了个底。

△“乐观一点，好奇一点总没错”

而对于那个四年五倍速的最终目标，Guido则表示“我们必须保持旺盛的创造力。”

参考链接：
[1]https://www.theregister.com/2021/05/19/faster_python_mark_shannon_author/
[2]https://pyfound.blogspot.com/2021/05/the-2021-python-language-summit-pep-654.html
[3]https://www.python.org/dev/peps/pep-0654/

Python version 3.11.0 alpha 0：
https://github.com/faster-cpython/ideas
“A faster CPython”计划简介：
https://github.com/markshannon/faster-cpython

— 完 —

量子位 QbitAI · 头条号签约

关注我们，第一时间获知前沿科技动态

言

最近在自己的群里遇到一道关于使用Javascript解决算法问题的讨论，最终答案的代码很简洁，我自己也进行了整理，这里和大家分享下。

Javascript

题目

题目的内容是这样的：一个人投篮12次,命中8球,命中编号1,未命中编号0,那么1次投篮的可能性我们可以编码为000011111000，那么这个人连续投中4个球及以上的概率有多大?

这里我选择了其中一种穷举法，因为它实现的方法很巧妙。注意：这种方法不是最优方法。

分析

既然选择穷举法，必定要列举出所有可能的情况，然后判断满足条件的情况。整个分析过程我们分为4步。

第一步-获取数组

一个人投12次篮，投中为1，未投中为0，那么每次投篮都会有2种情况，总的情况就是2*2*2...*2=4096种情况，实际从二进制上看就是000000000000-111111111111中所有二进制值的个数。

这样的话我们可以定义一个数组，里面包含所有可能的情况值。

但是这个数组我们怎么获取呢？这是算法的第一步。

这里有个很巧妙的方法就是利用数组索引，我们定义一个长度为4096的空数组，那么数组的索引就是从0-4095了。

这里我们就可以得到第一步的代码。

第一步

其中0xfff表示的是16进制的数fff，表示的是4095，再加上1，就是整个数组的长度4096，然后将其用扩展运算符展开成数组。

map方法就是专门输出索引值，上述代码运行后得到的结果是[0,1,2,3...4095]。

第二步-过滤其中包含8个1的值

第二步就是过滤出投中8次篮的值，即二进制编码中包含8个1的值。

这里我们需要定义一个过滤函数isContainEightOne，判断其中是否包含8个1。

判断的方法也很简单，首先将十进制值转化为二进制，再将二进制数的每一位进行相加，如果等于8则代表符合条件，不等于8则代表不符合。

因此可以得到以下方法。

因为Javascript中数组的语法是支持链式调用的，我们可以继续在第一步的后面补充如下filter方法。

第二步

第三步-过滤连续4个1及以上

过滤出连续投中4次及以上的值，即包含连续4个1或者更多的值。

首先将索引数字转化为二进制数，然后通过正则表达式去匹配'1111'，只要匹配到了就表示符合条件，这里也包括连续5个1，连续6个1等的情况。

我们可以得出下列代码。

第三步

第四步-计算概率

第二个filter方法后得到的就是满足条件的值，获取到其长度后，就是所有可能的情况，然后除以总数即可。

第四步

最终代码

将上述代码进行整合，得到最终完整形态的代码。

完整代码

结束语

今天这道Javascript实现的关于概率方面的算法题，虽然在效率上并不是最优的，但是其短巧精妙的代码却很吸引我，这也是我专门写这篇文章的原因。

后续如果看到了类似的巧妙代码解决的问题，我还会将它整理出来。

在线咨询

上一篇：前端必备：自适应所有分辨率的神技
下一篇：JavaScript中的Callbacks

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

整合营销服务商