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

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

在这里插入图片描述

概览

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

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

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

在本篇博文中,我们将用 4 种语言(x64汇编、C、ruby 和 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

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的最大值

总结

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

感谢观赏,再会 😎

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



http://www.chinasem.cn/article/284471

相关文章

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

Java实现MD5加密的四种方式

《Java实现MD5加密的四种方式》MD5是一种广泛使用的哈希算法,其输出结果是一个128位的二进制数,通常以32位十六进制数的形式表示,MD5的底层实现涉及多个复杂的步骤和算法,本文给大家介绍了Ja... 目录MD5介绍Java 中实现 MD5 加密方式方法一:使用 MessageDigest方法二:使用

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Go语言中最便捷的http请求包resty的使用详解

《Go语言中最便捷的http请求包resty的使用详解》go语言虽然自身就有net/http包,但是说实话用起来没那么好用,resty包是go语言中一个非常受欢迎的http请求处理包,下面我们一起来学... 目录安装一、一个简单的get二、带查询参数三、设置请求头、body四、设置表单数据五、处理响应六、超

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

Java捕获ThreadPoolExecutor内部线程异常的四种方法

《Java捕获ThreadPoolExecutor内部线程异常的四种方法》这篇文章主要为大家详细介绍了Java捕获ThreadPoolExecutor内部线程异常的四种方法,文中的示例代码讲解详细,感... 目录方案 1方案 2方案 3方案 4结论方案 1使用 execute + try-catch 记录