有趣的小实验：五种语言搞定“超超超难”剑桥面试数学题

2024-01-09 22:10
文章标签 语言 面试 实验 五种 搞定 有趣 数学题 剑桥 超超 超难

本文主要是介绍有趣的小实验：五种语言搞定“超超超难”剑桥面试数学题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

概览

如上图所示，这是一道貌似“超超超难”（作者用了 4 个 Super）的数学题，出自剑桥大学的面试环节。

说实话，现在的我已“不可能”通过纸笔计算得出这个问题的解了。

不过，如果剑桥面试官允许我们带电脑入场的话，解决它是分分钟的事（确切的说应该是毫毫秒的事…）。

在本篇博文中，我们将用 5 种语言（x64汇编、C、ruby、Python 和 Swift）来搞定它，并比较它们性能的优劣。

测试主机为我快被淘汰的爱机： MacBookPro（2016年） 2.9 GHz 双核Intel Core i5，8GB内存，测试系统为 macOS Monterey（12.6.6）。

废话少叙，Let‘s workout it！！！😉

审题

题目意思很简单：

  • 如果 a + b + c + d = 63；
  • 求 ab + bc + cd 的最大值；
  • 其中 a、b、c、d 都为自然数；

那么问题来了，零是否属于自然数？

关于这个问题的答案知乎上有一篇文章做了回答：

各方有两个观点：第一，不包括；第二，包括。


我的观点是自然数(Natural numbers)不包括0，因为在国外的学术界，自然数是从数(shu三声)实物开始，或者数(shu三声)数（Counting Numbers{1，2，3，…}）,数(shu三声)物体是从1开始数(shu三声)的。所以自然数不包括0.


给正在学习的学生两个建议:


1.如果你一直在国内读书，从小学（小学数学课本有规定自然数包括0）一直读到大学或者研究生或者博士，那么你一定要知道自然数是包括0的，自然数集N（从0开始，中国教科书的规定），N+(N的右下角是“+”)或者N*（表示从1开始的正整数集）。因为会贯穿国内的数学考试，所以记住0是自然数。


2.如果你在国际学校或者国外读书，请记住自然数不包括0，原因如上（我的观点）。如果你中途出国留学，请记住国内和国外的标准就好了。

原文在此：自然数到底是否包括0？

这里，我们采用 零不是自然数的观点 ，在 swift 的解决方案中，我们将会看到如果选择 零是自然数的观点，结果会有怎样的不同。

另外需要注意的是：对于这些语言生成的可执行文件，我们都使用 time 命令多次运行（估算耗时平均值）的方式来确保计时相对准确，但无法保证非常严谨的绝对准确，毕竟只是“趣味实验”而已。

ruby

ruby 的代码很直截了当：

#!/usr/bin/rubymax = 0
r = 1..63
for a in r dofor b in r dofor c in r dofor d in r doif a + b + c + d == 63rlt = a*b + b*c + c*dif rlt >= max max = rltendendendendend
endprint("max is #{max}\n")

将以上代码保存至 test.rb 文件中，再用 chmod 指令赋予它可执行权限：

chmod u+x test.rb

运行可以看到，ruby 平均耗时大约在 1.28秒左右：

% time ./test.rb
max is 991
./test.rb  1.22s user 0.04s system 98% cpu 1.272 total
% time ./test.rb
max is 991
./test.rb  1.23s user 0.04s system 98% cpu 1.286 total
% time ./test.rb
max is 991
./test.rb  1.24s user 0.04s system 98% cpu 1.295 total

我们还可以换一种算法：

r = (1..63).to_a
all = r.product(r,r,r)all.map do |g|a,b,c,d = g[0], g[1], g[2], g[3]if a + b + c + d == 63rlt = a*b + b*c + c*dif rlt >= max max = rltendend
endprint("max is #{max}\n")

这种算法会先创建所有 a、b、c、d 数的组合，然后再做计算，所以非常慢，花了 11 秒之多：

% time ./test.rb
max is 991
./test.rb  10.58s user 0.95s system 97% cpu 11.831 total

Python

Python 的实现和 ruby 非常相似：

#!/usr/bin/python3max = 0
r = range(1,64)
for a in r:for b in r:for c in r:for d in r:if a + b + c + d == 63:rlt = a*b + b*c + c*dif rlt > max:max = rltprint("max is", max)

如上代码所示，这样一看 Python 省略的结束语句可以节省一大片空间呢！

下面是运行结果：

time ./test.py
max is 991
./test.py  1.05s user 0.02s system 97% cpu 1.090 total
time ./test.py
max is 991
./test.py  1.16s user 0.01s system 99% cpu 1.186 total
time ./test.py
max is 991
./test.py  0.99s user 0.01s system 99% cpu 1.013 total

可以看到 Python 的确要比 ruby 快那么一丢丢呢。

swift

再来看看 Swift 语言的表现。

为了确保计时准确，我们不在 Playground 中测试；而是使用 Xcode 新创建一个 Command Line Tool 类型的项目，将如下代码放入 main.swift 文件中：

import Foundationtypealias GroupNumbers = (a: Int, b: Int, c: Int, d: Int, rlt: Int)@inline(__always) func value(_ g: GroupNumbers) -> Int {g.a * g.b + g.b * g.c + g.c * g.d
}var max = 0
let r = 1...63
for a in r {for b in r {for c in r {for d in r {if a + b + c + d == 63 {let v = (a: a, b: b, c: c, d: d, rlt: 0)let rlt = value(v)if rlt >= max {max = rlt}}}}}
}print("max is \(max)")

使用 Xcode 编译链接生成 test 可以执行文件，运行测试发现耗时要将近 7 秒多：

% time ./test
max is 991
./test  7.20s user 0.04s system 83% cpu 8.671 total
% time ./test
max is 991
./test  7.22s user 0.04s system 99% cpu 7.317 total
% time ./test
max is 991
./test  7.28s user 0.05s system 98% cpu 7.435 total

现在填之前挖的坑：如果零算自然数的话 ，结果会有怎样的不同呢？

改变上面代码中 r 的值为：

let r = 0...63

再次运行可以发现此时 max 值为 992，比之前的值大 1：

% time ./test
max is 992
./test  7.73s user 0.05s system 99% cpu 7.859 total

swift 语言咋这么不给力呢？别急，往下看！

c

c 代码看起来就很 beautiful 了：

#include <stdio.h>int main() {int start = 1;int end = 63;int max = 0;for (int a = start; a <= end; a++) {for (int b = start; b <= end; b++) {for (int c = start; c <= end; c++) {for (int d = start; d < end; d++) {if(a + b + c + d == 63) {int rlt = a*b + b*c + c*d;if(rlt >= max) {max = rlt;}}}}}}printf("max is %d\n", max);return 0;
}

使用 clang 生成可执行文件 test：

clang -o test test.c

运行看一下结果：

% time ./test
max is 991
./test  0.04s user 0.00s system 93% cpu 0.050 total
% time ./test
max is 991
./test  0.04s user 0.00s system 94% cpu 0.047 total
% time ./test
max is 991
./test  0.04s user 0.00s system 95% cpu 0.049 total

c 果然名不虚传，结果是碾压式的胜利，只需 0.05 秒左右。

x64 asm

最后，我们来看看 macOS 中低调的 x64 汇编语言。

关于新 Apple Silicon 芯片上 ARM64 汇编的测试代码，请移步如下链接观赏：

  • 搞定“超超超难”剑桥面试数学题番外篇：ARM64汇编

为了进一步追求性能，我们将所有临时变量都放在寄存器中（x64模式下新增了 8 个 64 位通用寄存器：r8 - r15，管够！ ），以减少内存操作带来的性能影响：

    .data
string: .asciz  "max is %ld\n".text.globl      _main.p2align    4, 0x90
_main:push    %rbpmov     %rsp,%rbppushq   %rbxpushq   %rdxmov     $1,%raxmov     %rax,%rbxmov     %rax,%rcxmov     %rax,%rdxxor     %r11,%r11
start_a_loop:cmpq    $63,%raxjg      end_a_loop
start_b_loop: cmpq    $63,%rbxjg      end_b_loop
start_c_loop:cmpq    $63,%rcxjg      end_c_loop
start_d_loop:cmpq    $63,%rdxjg      end_d_loop# if a + b + c + d == 63xorq    %r8,%r8add     %rax,%r8add     %rbx,%r8add     %rcx,%r8add     %rdx,%r8cmpq    $63,%r8jne     not_equ_63# == 63, 计算 a*b + b*c + c*d 放到 r8 中mov     %rax,%r8imul    %rbx,%r8mov     %r8,%r9mov     %rbx,%r8imul    %rcx,%r8mov     %r8,%r10mov     %rcx,%r8imul    %rdx,%r8addq    %r9,%r8addq    %r10,%r8cmpq    %r11,%r8jl      not_equ_63# 更新 max 值mov     %r8,%r11
not_equ_63:incq    %rdxjmp     start_d_loop
end_d_loop:xor     %rdx,%rdxincq    %rcxjmp     start_c_loop
end_c_loop:xor     %rcx,%rcxincq    %rbxjmp     start_b_loop
end_b_loop:xor     %rbx,%rbxincq    %raxjmp     start_a_loop
end_a_loop:lea     string(%rip),%rdimov     %r11,%rsicallq   _printfpopq    %rdxpopq    %rbxpopq    %rbpxor     %rax,%raxret

注意：在上面代码中我们使用 imul 指令处理乘法操作，这里还可以优化。

因为 imul 是相当慢的指令，我们可以进一步使用 SSE 或 移位指令来提高性能。

不过，这里点到为止，别影响“趣味性”哦。

在 macOS 系统中，我们使用如下命令编译和链接汇编代码：

as test.s -o test.o
ld test.o -lSystem -L `xcrun --show-sdk-path -sdk macosx`/usr/lib -o test

使用汇编果然不同凡响，我们成功的把计算耗时降低至 < 0.03 秒：

% time ./x64
max is 992
./x64  0.02s user 0.00s system 89% cpu 0.027 total
% time ./x64
max is 992
./x64  0.02s user 0.00s system 89% cpu 0.029 total
% time ./x64
max is 992
./x64  0.02s user 0.00s system 89% cpu 0.028 total

所以综上所述：为了达到极致性能，我们不得不回归 c 代码，甚至写一些让人“头大”的汇编指令才行吗？

大错特错！！！

另一个故事

ruby 语言咱就不说了，毕竟它是 真·“出了名的慢”。

不过，对于 swift 和 c 语言，我们好像还没开启优化哦？（说好的20倍界王拳呢？说好的超级赛亚人呢？）

首先看 c 语言，我们之前在编译源代码时并没有使用任何优化选项，现在我们要发力了：

clang -O2 -o test test.c

在使用 O2 优化选项后，我们再来看看 c 代码的表现：

% time ./test
max is 991
./test  0.02s user 0.00s system 86% cpu 0.025 total
% time ./test
max is 991
./test  0.02s user 0.00s system 89% cpu 0.025 total
% time ./test
max is 991
./test  0.02s user 0.00s system 91% cpu 0.029 total

看到了吗？几乎和汇编版本不分上下，甚至略微胜出。

再来看看 swift 语言。在 Xcode 中将项目的 Scheme 切换至 Release 模式，并确保 clang 对应的优化选项为如下等级：

在这里插入图片描述

编译并运行可以看到，优化后 swift 语言代码的速度已妥妥的超过汇编了：

% time ./test
max is 992
./test  0.01s user 0.00s system 82% cpu 0.019 total
% time ./test
max is 992
./test  0.01s user 0.00s system 85% cpu 0.021 total
% time ./test
max is 992
./test  0.01s user 0.01s system 86% cpu 0.021 total

感兴趣的童鞋可以使用 otool 工具来查看一下优化后 c 和 swift 可执行文件的汇编代码。

所以，不要低估编译器优化的威力，也不要高估自己汇编语言的水平。T_T

当然，上面汇编代码也是可以再优化的，耗时小于 swift 优化后的代码也不是梦想，不过这真是另一个故事了…

在 超详细：实现 Swift 与 汇编（Asm）代码混编并在真机或模拟器上运行 这篇博文中，我们将会在真机（iPhone 14 Pro Max）上测试上述 ARM64 汇编代码，这次汇编终于赢了 C 和 Swift！！！

有兴趣的小伙伴不妨移步观看哦。

看到这里，大家是不是觉得很有意思呢？

时刻保留一颗童心，保持一颗初心，祝天下所有程序员小伙伴们 6.1 儿童节快乐！！！🚀💯

题目的标准答案

以防小伙伴们挡不住的好奇心：这道题目的标准答案以及数学解题思路到底是什么呢？

下面是百度知道的解答：

a、b、c、d加起来是63 ab+bc+cd的最大值是多少？

这里还有 stackexchange 上国外网友的回答：

If a,b,c,d are positive integers with a sum of 63, what is the maximum value of ab + bc + cd ? (By using calculus to solve it))

最后，还有一个详细的视频解题教程，大家可以参考下：

视频：若abcd是正整数，和是63，求ab+bc+cd的最大值

总结

在本篇博文中，我们用 5 种语言（x64汇编、c、swift、Python 和 ruby）解决了一道“超超超难”的剑桥数学题，并讨论了这些语言的实现性能，你绝猜不到最快的是谁！

感谢观赏，再会 😎

这篇关于有趣的小实验：五种语言搞定“超超超难”剑桥面试数学题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/588611。

相关文章

C语言中联合体union的使用

C语言中联合体union的使用

本文编辑整理自： http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=179471 一、前言 “联合体”(union）与“结构体”(struct)有一些相似之处。但两者有本质上的不同。在结构体中,各成员有各自的内存空间, 一个结构变量的总长度是各成员长度之和。而在“联合”中,各成员共享一段内存空间, 一个联合变量
阅读更多...
Java面试八股之怎么通过Java程序判断JVM是32位还是64位

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

怎么通过Java程序判断JVM是32位还是64位 可以通过Java程序内部检查系统属性来判断当前运行的JVM是32位还是64位。以下是一个简单的方法： public class JvmBitCheck {public static void main(String[] args) {String arch = System.getProperty("os.arch");String dataM
阅读更多...
大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
人工和AI大语言模型成本对比 ai语音模型

人工和AI大语言模型成本对比 ai语音模型

这里既有AI，又有生活大道理，无数渺小的思考填满了一生。 上一专题搭建了一套GMM-HMM系统，来识别连续0123456789的英文语音。 但若不是仅针对数字，而是所有普通词汇，可能达到十几万个词，解码过程将非常复杂，识别结果组合太多，识别结果不会理想。因此只有声学模型是完全不够的，需要引入语言模型来约束识别结果。让“今天天气很好”的概率高于“今天天汽很好”的概率，得到声学模型概率高，又符合表达
阅读更多...
C++面试八股文：std::deque用过吗？

C++面试八股文：std::deque用过吗？

100编程书屋_孔夫子旧书网 某日二师兄参加XXX科技公司的C++工程师开发岗位第26面： 面试官：deque用过吗？ 二师兄：说实话，很少用，基本没用过。 面试官：为什么？ 二师兄：因为使用它的场景很少，大部分需要性能、且需要自动扩容的时候使用vector，需要随机插入和删除的时候可以使用list。 面试官：那你知道STL中的stack是如何实现的吗？ 二师兄：默认情况下，stack使
阅读更多...
C语言 将“China”译成密码

C语言 将“China”译成密码

将“China”译成密码，密码规律是：用原来的字母后面的第4个字母代替原来的字母。例如，字母“A”后面的第4个字母是“E”，用“E”代替“A”。因此，“China”应译为“Glmre”。编译程序用付赋初值的方法使c1，c2，c3，c4，c5这五个变量的值分别为“C”，“h”，“i”，“n”，“a”，经过运算，使c1，c2，c3，c4，c5分别变成“G”，“l”，“m”，“r”，“e”。分别用put
阅读更多...
C语言入门系列：探秘二级指针与多级指针的奇妙世界

C语言入门系列：探秘二级指针与多级指针的奇妙世界

文章目录 一，指针的回忆杀1，指针的概念2，指针的声明和赋值3，指针的使用3.1 直接给指针变量赋值3.2 通过*运算符读写指针指向的内存3.2.1 读3.2.2 写 二，二级指针详解1，定义2，示例说明3，二级指针与一级指针、普通变量的关系3.1，与一级指针的关系3.2，与普通变量的关系,示例说明 4，二级指针的常见用途5，二级指针扩展到多级指针 小结 C语言的学习之旅中，二级
阅读更多...
Java面试八股之JVM参数-XX:+UseCompressedOops的作用

Java面试八股之JVM参数-XX:+UseCompressedOops的作用

JVM参数-XX:+UseCompressedOops的作用 JVM参数-XX:+UseCompressedOops的作用是启用对象指针压缩（Ordinary Object Pointers compression）。这一特性主要应用于64位的Java虚拟机中，目的是为了减少内存使用。在传统的64位系统中，对象引用（即指针）通常占用8字节（64位），而大部分应用程序实际上并不需要如此大的地址空间
阅读更多...
华为某员工爆料：偷偷跑出去面试，被面试官鄙视了。第一句话就问：华为淘汰的吧，35岁了，这个年龄在华为能混得下去吗？身体没啥毛病吧

华为某员工爆料：偷偷跑出去面试，被面试官鄙视了。第一句话就问：华为淘汰的吧，35岁了，这个年龄在华为能混得下去吗？身体没啥毛病吧

“你都35岁了，难不成是被华为淘汰的？在华为混不下去了吧？身体没啥毛病吧，我们这体检可是很严的。” 近日，一位华为员工在朋友圈爆料，自己在面试时遭到了面试官的无理取闹和人身攻击，原因仅仅是因为他35岁了，曾经在华为工作过。 这番话，充满了傲慢与偏见，让人听了义愤填膺。这位面试官的言行，不仅是对求职者的不尊重，更是对职场规则的践踏。 面试本应是双向选择的过程，企业和求职者在相互了解的基
阅读更多...
【LinuxC语言】select轮询

【LinuxC语言】select轮询

文章目录 前言select函数详解selectfd_set类型一个小问题select函数使用步骤改进服务器代码select服务器示例代码 总结 前言 在Linux C语言编程中，我们经常需要处理多个I/O操作。然而，如果我们为每个I/O操作创建一个线程，那么当I/O操作数量增加时，线程管理将变得复杂且效率低下。这就是我们需要select轮询的地方。select是一种高效的I/
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2