正文

如何在 scala 中为 collatz 链改进 tailrec 函数的执行时间

 2023-04-13  256

关键词：

【中文标题】如何在 scala 中为 collatz 链改进 tailrec 函数的执行时间【英文标题】：how can I improve the execution time of my tailrec function in scala for collatz chain 【发布时间】：2021-08-02 02:47:02 【问题描述】：

 def collatzChainLength(n:Int):Int=
      @tailrec
      def collatz(n:Int,acc:Int):Int=
         if(n==1) acc+1
         else if (n%2==0) collatz(n/2,acc+1)
         else collatz(3*n+1,acc+1)
      collatz(n,0)

我在 100000 次迭代中得到了几乎即时的结果，但之后它会变得无穷大

 println( (1 to 100000).map(x=> 
(x,collatzChainLength(x))).foldLeft((0,0))((m,y)=> 
if(y._2>m._2) y else m))
 println( (100001 to 200000).map(x=> 
(x,collatzChainLength(x))).foldLeft((0,0))((m,y)=> 
if(y._2>m._2) y else m))

【问题讨论】：

【参考方案1】：

虽然您可以进行一些小的改进，但这里真正的问题是您的Int 值溢出。尽管200000 是一个舒适的Int 值，但请记住n 可以在多次迭代过程中增长和缩小。

进行此更改...

def collatzChainLength(n: Long): Int =

...以及所有以下用于协调编译器的小模块，您就可以开始了。

【讨论】：

【参考方案2】：

您最好对偶数进行尾递归缩减，因为奇数情况给出了偶数。（否定 if）

或者：

  else collatz((3*n + 1)/2, acc +2)

但实际的解决方案是在最后打一个电话。

  if (n == 1) acc + 1
  else collatz(n & 1 == 0? n/2 : 3*n + 1, acc + 1)

当达到 2³¹ 的三分之一时也使用 Long。

【讨论】：

谢谢你，通过上述修改获得最佳效果

如何在 Scala 中为未来添加截止日期？

】如何在Scala中为未来添加截止日期？【英文标题】：HowtoaddadeadlinetoafutureinScala?【发布时间】：2021-07-0604:39:15【问题描述】：假设我有一个函数fab:A=>Future[B]并希望它返回一个在截止日期之前完成的新未来。所以我正在写一... 查看详情

Erlang中的Collatz序列

】Erlang中的Collatz序列【英文标题】：CollatzsequenceinErlang【发布时间】：2021-05-1916:05:35【问题描述】：我要解决的问题如下：编写一个名为collatz的Erlang函数，它接受一个参数N。您可以假设N是整数1或更大。该函数应打印... 查看详情

如何在 spark scala 中为单列创建数据框

】如何在sparkscala中为单列创建数据框【英文标题】：HowtoCreateDataframeinsparkscalaforsinglecoumn【发布时间】：2017-05-1816:14:51【问题描述】：我是sparkscala的新手。我有包含10列的数据框，但我想为该数据框再添加一列，该列是日期格式... 查看详情

如何在scala中为like运算符添加switch case？

】如何在scala中为like运算符添加switchcase？【英文标题】：Howtoaddswitchcaseforlikeoperatorinscala?【发布时间】：2018-10-0421:25:42【问题描述】：我有一个包含(A,B)列的数据框，其中B列是免费测试，我将其转换为类型（NOT_FOUND、TOO_LOW_PURCHAS... 查看详情

如何在 WPF 中为装饰器设置 Z 顺序索引

】如何在WPF中为装饰器设置Z顺序索引【英文标题】：HowtosettheZorderindexforadornerinWPF【发布时间】：2014-04-2409:36:43【问题描述】：我正在尝试为装饰器设置Z顺序索引，目前装饰器位于最顶层，我想将其更改为它正在装饰的控件的索... 查看详情

如何在scala akka（spray）中为rest服务编写测试用例

】如何在scalaakka（spray）中为rest服务编写测试用例【英文标题】：howtowritetestcaseforrestserviceinscalaakka(spray)【发布时间】：2016-04-2416:38:22【问题描述】：如何模拟HttpRespose？我正在使用scalla、akka和spray来调用以json响应的rest服务，我... 查看详情

如何在 Spark SQL 中为每个组创建 z 分数

】如何在SparkSQL中为每个组创建z分数【英文标题】：Howtocreateaz-scoreinSparkSQLforeachgroup【发布时间】：2016-04-2307:23:49【问题描述】：我有一个看起来像这样的数据框dScTranAmount1:10002179.642:10002179.643:1000210.164:10002211.655:1000220.366:1000220.47... 查看详情

如何在与 z 索引的本机反应中为淡入淡出设置动画？

】如何在与z索引的本机反应中为淡入淡出设置动画？【英文标题】：Howtoanimatefadeinfadeoutinreactnativewithzindex?【发布时间】：2019-07-1204:49:07【问题描述】：我正在尝试为一条消息设置动画，该消息始终位于具有可滚动视图的屏幕顶... 查看详情

如何在 Scala/Spark 中为数据框中的每一行编写一个 Json 文件并重命名文件

】如何在Scala/Spark中为数据框中的每一行编写一个Json文件并重命名文件【英文标题】：HowtowriteoneJsonfileforeachrowfromthedataframeinScala/Sparkandrenamethefiles【发布时间】：2019-02-0721:24:15【问题描述】：需要为数据框中的每一行创建一个json... 查看详情

在 spark scala 中为 withcolumn 编写通用函数

...帧df。我对其他数据帧也有以下withcolumn条件的相同用法。如何将这些所有withcolumn条件编写为通用函数并在所有数据帧中访问它。valdf 查看详情

最大化 Collatz 猜想程序 Python 的效率

】最大化Collatz猜想程序Python的效率【英文标题】：MaximizingEfficiencyofCollatzConjectureProgramPython【发布时间】：2022-01-1410:36:42【问题描述】：我的问题很简单。我写这个程序纯粹是为了娱乐。它接受一个数字输入并找到每个Collat... 查看详情

在 Eclipse 中为 Scala 配置运行

】在Eclipse中为Scala配置运行【英文标题】：configurerunineclipseforScala【发布时间】：2010-12-0913:26:37【问题描述】：我是Scala的初学者。我在Eclipse中安装了ScalaIDE，现在我想运行我的应用程序。它从不显示“作为Scala应用程序运行”，... 查看详情

在 IntelliJ IDEA 中为 scala 项目附加源

】在IntelliJIDEA中为scala项目附加源【英文标题】：AttachingsourcesinIntelliJIDEAforscalaproject【发布时间】：2012-11-1107:32:01【问题描述】：我有Scala的Playframework2项目（非常小的一个）。它使用ScalaAnorm库。我有这样的代码：packagemodels..impor... 查看详情

在scala中为理解而组成

】在scala中为理解而组成【英文标题】：composedforcomprehensioninscala【发布时间】：2021-11-2013:40:06【问题描述】：我有一个任务列表供理解：defmain=List("en","es","de").foreach(c=>execAll(c))defexecAll(country:String):Future[Unit]=for_<-repo.exec1(countr... 查看详情

java示例代码_在Scala中为枚举添加一个方法

java示例代码_在Scala中为枚举添加一个方法查看详情

在 Play 中为 Scala 实现 Hibernate

】在Play中为Scala实现Hibernate【英文标题】：ImplementingHibernateinPlayforScala【发布时间】：2017-07-2117:58:14【问题描述】：我正在尝试将Hibernate集成到PlayforScala中。我向conf/META-INF添加了一个文件hibernate.cfg.xml，但显然Play没有找到它，因... 查看详情

在 PySpark 中为 Scala 类构造函数初始化 Scala 正则表达式

】在PySpark中为Scala类构造函数初始化Scala正则表达式【英文标题】：InitializingScalaregexinPySparkforScalaclassconstructor【发布时间】：2020-06-1022:21:30【问题描述】：我在Jupyter笔记本采用PySparkv2.3.4运行于Java的8个工作，Python的3.6（与py4j==0.... 查看详情

为啥必须在scala的for循环中为模式匹配定义过滤器？

】为啥必须在scala的for循环中为模式匹配定义过滤器？【英文标题】：whydoesfilterhavetobedefinedforpatternmatchinginaforloopinscala?为什么必须在scala的for循环中为模式匹配定义过滤器？【发布时间】：2011-05-2119:37:26【问题描述】：要创建一... 查看详情

正文

如何在 scala 中为 collat​​z 链改进 tailrec 函数的执行时间