我在 Node.js 服务器上有一些性能敏感代码需要计算组合。来自 this SO answer ，我使用这个简单的递归函数来计算 n 选择 k:
function choose(n, k) {
if (k === 0) return 1;
return (n * choose(n-1, k-1)) / k;
}
因为我们都知道迭代几乎总是比递归快，所以我根据 multiplicative formula 编写了这个函数:
function choosei(n,k){
var result = 1;
for(var i=1; i <= k; i++){
result *= (n+1-i)/i;
}
return result;
}
我跑了几个benchmarks在我的机器上。以下是其中一个的结果:
Recursive x 178,836 ops/sec ±7.03% (60 runs sampled)
Iterative x 550,284 ops/sec ±5.10% (51 runs sampled)
Fastest is Iterative
结果一致表明，迭代方法确实比 Node.js 中的递归方法快 3 到 4 倍(至少在我的机器上是这样)。
这可能速度足以满足我的需求，但是有什么方法可以让它更快吗？我的代码必须非常频繁地调用此函数，有时会使用相当大的 n 和 k 值，因此越快越好。
在对 le_m 和 Mike 的解决方案进行了更多测试后，结果表明虽然两者都比我提出的迭代方法快得多，但 Mike 使用 Pascal 三 Angular 形的方法似乎比 le_m 的日志表方法稍快。
Recursive x 189,036 ops/sec ±8.83% (58 runs sampled)
Iterative x 538,655 ops/sec ±6.08% (51 runs sampled)
LogLUT x 14,048,513 ops/sec ±9.03% (50 runs sampled)
PascalsLUT x 26,538,429 ops/sec ±5.83% (62 runs sampled)
Fastest is PascalsLUT
在我的测试中，对数查找方法比迭代方法快大约 26-28 倍，使用帕斯卡三 Angular 形的方法比对数查找方法快大约 1.3 到 1.8 倍。
请注意，我遵循了 le_m 的建议，即使用 mathjs 以更高的精度预先计算对数。 ，然后将它们转换回常规的 JavaScript Number(始终为 double-precision 64 bit floats)。
最佳答案
永远不要计算阶乘，它们增长太快。而是计算您想要的结果。在这种情况下，您需要二项式数，它具有非常简单的几何构造:您可以构建 pascal's triangle ，根据需要，使用简单的算术来完成。
从 [1] 和 [1,1] 开始。下一行的开头是 [1]，中间是 [1+1]，结尾是 [1]:[1,2,1]。下一行:开头的 [1]，点 2 中前两项的总和，点 3 中接下来两项的总和，以及末尾的 [1]:[1,3,3,1]。下一行:[1]，然后是 1+3=4，然后是 3+3=6，然后是 3+1=4，最后是 [1]，依此类推。如您所见，没有阶乘、对数，甚至乘法:只有超快速加法和干净的整数。非常简单，您可以手动构建一个巨大的查找表。
你应该。
永远不要在代码中计算您可以手动计算的内容，而只是将其作为常量包含在内以供立即查找；在这种情况下，写出大约 n=20 的表绝对是微不足道的，然后您可以将其用作“起始 LUT”，甚至可能永远不会访问高行。
但是，如果您确实需要它们，或者更多，那么因为您无法构建一个无限查找表，所以您妥协了:您从一个预先指定的 LUT 开始，以及一个可以将其“填充”到某个术语的函数你需要的还没有:
// step 1: a basic LUT with a few steps of Pascal's triangle
const binomials = [
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1],
[1,5,10,10,5,1],
[1,6,15,20,15,6,1],
[1,7,21,35,35,21,7,1],
[1,8,28,56,70,56,28,8,1],
// ...
];
// step 2: a function that builds out the LUT if it needs to.
module.exports = function binomial(n,k) {
while(n >= binomials.length) {
let s = binomials.length;
let nextRow = [];
nextRow[0] = 1;
for(let i=1, prev=s-1; i<s; i++) {
nextRow[i] = binomials[prev][i-1] + binomials[prev][i];
}
nextRow[s] = 1;
binomials.push(nextRow);
}
return binomials[n][k];
};
由于这是一个整数数组，因此内存占用很小。对于很多涉及二项式的工作，我们实际上每个整数甚至不需要超过两个字节，这使它成为一个极小查找表:我们不需要超过 2 个字节，直到您需要更高的二项式比 n=19，并且直到 n=19 的完整查找表只占用区区 380 个字节。与程序的其余部分相比，这不算什么。即使我们允许 32 位整数，我们也可以在仅 2380 字节的情况下达到 n=35。
所以查找速度很快:对于先前计算的值，要么是 O(constant)，要么是 (n*(n+1))/2 步，如果我们根本没有 LUT(在大 O 表示法中，那将是 O(n² )，但大 O 表示法几乎从来不是正确的复杂性度量)，对于我们需要但尚未在 LUT 中的术语，介于两者之间。为您的应用程序运行一些基准测试，这将告诉您您的初始 LUT 应该有多大，只需硬编码(说真的。这些是常量，它们正是 应该 进行硬编码)，并保留生成器以防万一。
但是，请记住，您是在 JavaScript 领域，并且受到 JavaScript 数字类型的限制:integers only go up to 2^53 ，除此之外，不保证整数属性(每个 n 都有一个不同的 m=n+1 使得 m-n=1)。不过，这几乎不会成为问题:一旦达到该限制，我们就会处理您永远不应该使用的二项式系数。
关于javascript - 在 Node.js 中高效计算 n 选择 k，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37679987/
这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，
状态:我正在构建一个应用程序，其中需要一个可供用户选择颜色的字段，该字段将包含RGB颜色代码字符串。我已经测试了一个看起来很漂亮但效果不佳的。它是“挑剔的颜色”，并托管在此存储库中:https://github.com/Astorsoft/picky-color.在这里我打开一个关于它的一些问题的问题。问题:请建议我在Rails3应用程序中使用一些颜色选择器。 最佳答案 也许页面上的列表jQueryUIDevelopment:ColorPicker为您提供开箱即用的产品。原因是jQuery现在包含在Rails3应用程序中，因此使用基
项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明：前端使用微信微信小程序开发工具：后端使用ssm：VU
我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我
给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true？”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组，其中每个子数组代表一列，然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本，应该在1.8.6上运行，没有任何依赖:arr.transpose.map{|subarr|subarr.in
我完全不是程序员，正在学习使用Ruby和Rails框架进行编程。我目前正在使用Ruby1.8.7和Rails3.0.3，但我想知道我是否应该升级到Ruby1.9，因为我真的没有任何升级的“遗留”成本。缺点是什么？我是否会遇到与普通gem的兼容性问题，或者甚至其他我不太了解甚至无法预料的问题？ 最佳答案 你应该升级。不要坚持从1.8.7开始。如果您发现不支持1.9.2的gem，请避免使用它们(因为它们很可能不被维护)。如果您对gem是否兼容1.9.2有任何疑问，您可以在以下位置查看:http://www.railsplugins.or
我希望用户从一个模型的三个选项中选择一个。即我有一个模型视频，可以被评为正面/负面/未知目前我有三列bool值(pos/neg/unknown)。这是处理这种情况的最佳方式吗？为此，表单应该是什么样的？目前我有类似的东西但显然它允许多项选择，而我试图将它限制为只有一个..怎么办？ 最佳答案 如果要使用字符串列，让我们说rating。然后在你的表单中:#...#...它只允许一个选择编辑完全相同但使用radio_button_tag: 关于ruby-on-rails-Rails单选按钮-模
我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的
我的Rails应用程序中安装了carrierwave。但是，当用户上传多页pdf时，我只希望应用程序获取文档中的第一页并将其转换为jpeg。这可能吗？用什么命令？这是我的uploader。#encoding:utf-8classImageUploader[200,300]##defscale(width,height)##dosomething#end#Createdifferentversionsofyouruploadedfiles:version:thumbdoprocess:resize_to_fill=>[150,210]process:convert=>:jpgdefful
给定两个大小相等的数组，如何找到不考虑位置的匹配元素的数量？例如:[0,0,5]和[0,5,5]将返回2的匹配项，因为有一个0和一个5共同；[1,0,0,3]和[0,0,1,4]将返回3的匹配项，因为0有两场，1有一场；[1,2,2,3]和[1,2,3,4]将返回3的匹配项。我尝试了很多想法，但它们都变得相当粗糙和令人费解。我猜想有一些不错的Ruby习惯用法，或者可能是一个正则表达式，可以很好地回答这个解决方案。 最佳答案 您可以使用count完成它:a.count{|e|index=b.index(e)andb.delete_at