草庐IT

javascript - 在 Javascript 中执行(整数)操作的最有效方法是什么？

coder 2024-07-20 原文

我正在用 Javascript 实现一个图灵机(把它想象成一个虚拟机)。我正在研究一个尽可能高效地执行计算的例程(从一开始这不是项目的重点)。

是的，除非遇到性能问题，否则我不应该考虑优化。但是我正在做的事情的性质(大多数非平凡程序的渐近运行时效率非常低)意味着总是可以从优化中获得一些好处。我想尽我所能(合理地)每秒获得尽可能多的指令。

例如，如果我用 C++ 编程，解决方案就很清楚了。做一些计时。 gprof . -O3等等。我将研究我希望运行代码的体系结构，并且可能还会查看正在生成的程序集。

但是，不能用 javascript 做到这一点。我的第一直觉是将内部循环中的操作减少到数组查找。在我看来，如果解释器能够将它转换为一系列(希望是简短的)整数运算，我将能够利用 CPU 缓存性能，这是一个很好的选择。

图灵机非常简单。它实际上是存在的最简单的计算公式(!):它具有有限数量的状态，一个双向无限磁带，一个可以向任一方向移动一个单元的磁头，并且可以读取和写入单个字符到磁带。

一个程序被编码在一个转换函数中，该函数接受一个状态和一个读取的字符，并根据该信息提供要写入的字符、移动头部的方向和新状态。

这是每一步的逻辑:

// states is an array of arrays of triplets and is the transition func
var trans = states[state][alph_index[tape[pos]]]; 
tape[cur_tape_pos] = trans[0]; // write
cur_tape_pos += trans[1]; // move
state = trans[2]; // state update

该过程发生在一个循环中。在我看来很清楚磁带将是一个数组。我想将值存储(附加)到数组的末尾至少是一个使用 Javascript 数组的分摊常量时间操作。不太清楚附加到数组的前面也有很好的性能，所以我可能想使用两个数组，一个向左扩展，一个向右扩展。

问题是，这会在幼稚的实现中在内循环中插入一个条件语句。我不喜欢那样。无论如何必须已经有条件检查来检查状态是否为停止状态。所以也许它不会那么糟糕。

还有一种潜在的优化可以消除对 alph_index 的索引。通过将索引存储在字母表中而不是将字母表值本身存储在磁带上。

但主要的问题是这个。我还能做些什么来让它更快？有没有可能让它更快？我不知道执行的哪个组件将成为瓶颈(CPU 或 I/O，或其他什么？)，我不知道我将如何找到它。使用 Javascript，我也可以使用哈希表，但似乎数组总是更快。

也许我过早地寻求建议。随着我的进步，我会回来编辑性能数据。

作为阅读我的问题的奖励，我将提供一个链接到我的项目的实时工作中版本:http://stevenlu.net/tm.html

到目前为止，它的操作一直是操纵一个 div充满spans它代表磁带。它还对字符串执行大量操作，并且还进行了大量元素的复制，这在图灵机的实际计算中是完全没有必要的。但即便如此，它也取得了不错的性能。我的机器花了大约一分钟来计算 600,000 步左右(5^4 = 625)，即每秒 10,000 步。这还不错，但我知道我可以通过一些较低级别的编程达到每秒超​​过一百万的目标。

看着 benchmark perf here对于上一代 CPU，我看到每个内核大约 10,000 MIPS。因此，我估计，如果我能在运行 50 次 Dhrystone 迭代所需的时间内运行一次我的内部循环(即使我不知道那些合成基准测试实际上做了什么，这似乎很可能用一个简单的 C 实现)，除非内存带宽限制，我在一个线程上每秒进行 2 亿次迭代。我的 600k 步计算将在 3ms 内完成!!

好吧，如果我可以让我的 5^4 计算在没有浏览器向我报告它挂断的情况下运行，我会很高兴......

更新

随着算法更高效的javascript实现完成，9^4 = 6561的计算需要 58202209 步，计算耗时 6173 毫秒。那是每秒 940 万步。比我原来的 DOM 依赖方法增加了近 1,000 倍。

原5^4计算(即使不滚动磁带也需要大约 30 秒)现在在 84 毫秒内完成。

最佳答案

如果您想同时拥有 +ve 和 -ve 整数索引，为什么不使用普通对象呢？您是否使用任何特殊的数组方法？数组方法大多是通用的，因此可以使用其他 native 对象调用(可能不适用于宿主对象，但我认为这不是问题)。

在 javascript 中，数组只是对象，所以我不明白为什么访问 array[i] 应该比 object[i] 更快或更慢(当然它可能在不同的实现中)。您只需要保留自己的长度属性(可能是正长度和负长度)。

如果您提供一些示例代码，无论性能如何，您都可能会得到一些更具体的建议。

关于javascript - 在 Javascript 中执行(整数)操作的最有效方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7748487/

javascriptbrcode的arraysperformanceoptimization

有关javascript - 在 Javascript 中执行(整数)操作的最有效方法是什么？的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  5. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  6. ruby-openid:执行发现时未设置@socket - 2

    我在使用omniauth/openid时遇到了一些麻烦。在尝试进行身份验证时，我在日志中发现了这一点:OpenID::FetchingError:Errorfetchinghttps://www.google.com/accounts/o8/.well-known/host-meta?hd=profiles.google.com%2Fmy_username:undefinedmethod`io'fornil:NilClass重要的是undefinedmethodio'fornil:NilClass来自openid/fetchers.rb，在下面的代码片段中:moduleNetclass

  7. Ruby 方法() 方法 - 2

    我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby​​-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco

  8. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  9. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  10. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

随机推荐