回文质数数组创建器 [速度问题] RUBY
Palindromic Prime numbers array creator [Speed Issues] RUBY
我想创建第 n 个回文质数数组。
我写了下面的代码：
# Enter your code here. Read input from STDIN. Print output to STDOUT
require 'prime'
number = gets
power_array = -> (array_size) do
1.upto(Float::INFINITY).lazy.select { |x|
Prime.prime?(x)&&x.to_s==x.to_s.reverse }.first(array_size)
end
print power_array.(number.to_i)
但它 运行 太慢了。所以我找到了这个 运行 更快的解决方案：
# Enter your code here. Read input from STDIN. Print output to STDOUT
require 'prime'
p Prime.each.lazy.select{|x| x.to_s == x.to_s.reverse}.first(gets.to_i)
为什么上面的代码 运行 比我原来的代码快？关于 big-O 和我的代码效率，我没有得到什么？
TL;DR
首先，确保这不是过早的优化或 X/Y 问题；寻找大素数或大量素数 很慢，这就是为什么在许多现代密码算法中如此依赖素数的原因。
您有一些难以解析的代码，逻辑可能未针对您的 Ruby 版本或引擎进行优化。从算法的角度来看，您还插入了一些我会尝试减少或消除的额外步骤，但在比较此特定代码的 modest 重构时，这显然不是一个重要问题。相反，我会假设您需要不同的 Ruby 引擎来提高速度，不同的算法或架构设计来解决您的问题，或者如果 Ruby 无法满足您的任何要求，则可能需要不同的语言或工具非功能性速度要求是。
然而，根据我的测试，我觉得 Ruby 对于这个问题域很容易使用，并且对于我个人处理过的大多数实际需求来说“足够快”。您的问题域可能不同，在这种情况下，请参阅下面的各个部分（尤其是末尾的摘要）以获取更多想法。
上下文
如评论中所述，我不确定您为什么认为您的代码应该“更快”，或者为什么它对于您将其用于的任何目的都不够快。两者都有些主观，缺乏上下文。
不过，您正在做一些本质上至少会减慢您速度的事情。这些内容包括：
- 在块中使用像
1.upto 这样的迭代器（无论是否有惰性）。
- 在 lambda 中创建迭代块。这至少会产生一些开销，尽管它可能不是您真正的问题所在。
- 您重复将相同的值转换为字符串和整数。一些往返可能是不可避免的，但你做了很多次。
总的来说，这些事情都会增加一些开销，但我没有看到您似乎正在经历的大规模减速。我还在我的基准测试（见下文）中发现，尝试优化字符串分配实际上进一步减慢了速度，这可能是由于垃圾收集、范围和我的 IRB 测试中缺少冻结字符串的组合。有关此的一些其他想法，请参阅底部的摘要。
如果你真的想知道你的代码在哪里“太慢”（不管这对你意味着什么）那么你需要 运行 一个调试器，执行一些基准测试，或者（为了 Big-O 目的）检查 AST 以查看每个变体在 Ruby 中进行了多少次操作。对于 Ruby 在 C 级完成的操作，您可能还需要做类似的事情；无论您如何优化 Ruby 代码，大部分工作仍由 Ruby 解释器调用的 C 代码完成。
备选方案
根据您的原始代码，我不知道“足够快”对您意味着什么，但我会减少 数量 的操作以提高您的性能。使用 Ruby 3.1.0 的一个示例可能是：
require 'prime'
SINGLE_DIGIT_PRIMES = [2, 3, 5, 7].size
# plan on dropping SINGLE_DIGIT_PRIMES from the result set
print "Max size of array: "
max_values = Integer(gets) + 4
pp(
Prime.each.lazy.select do
_1 if 1.to_s == _1.to_s.reverse
end.first(max_values)[SINGLE_DIGIT_PRIMES..]
)
基准
话虽如此，要提高性能，您应该减少步骤，即使在提供了稍微快一点的替代方案之后，基准测试也并没有真正表明使用适度的数组大小或迭代来榨汁是值得的。为提高可读性稍作重构，这里有一些代码比较表明它在 Ruby 3.1.0 中似乎并没有太大的区别。 GraalVM 上的 TruffleRuby 在整体执行时间上明显更快，但在排练后再次没有显示出显着的性能差异。代码未重构以在 JRuby 9.3.2.0 下工作，目前不支持块位置变量，因为引擎版本为 2.6.8，但如果结果有很大不同，我会感到惊讶。
标准 Ruby v3.1.0
require 'prime'
require 'benchmark'
@array_size = 100
@iterations = 1_000
@max_values = @array_size + 4
def op_code
power_array = ->(arr_size) do
1.upto(Float::INFINITY).lazy.select do |x|
Prime.prime?(x) && (x.to_s == x.to_s.reverse).
first(@array_size)
end
end
power_array(@array_size.to_i)
end
def alt_code
Prime.each.lazy.select do
_1 if _1.to_s == _1.to_s.reverse!
end.first(@max_values)[4..]
end
Benchmark.bmbm do
_1.report("OP's code" ) do
@iterations.times { op_code }
end
_1.report("alternative code" ) do
@iterations.times { alt_code }
end
end
即使步数略有减少，我也看不到这两种方法的挂钟时间差异超过十分之一秒。
Rehearsal ----------------------------------------------------
OP's code 4.802338 0.032414 4.834752 ( 4.863002)
alternative code 4.673423 0.021997 4.695420 ( 4.710023)
------------------------------------------- total: 9.530172sec
user system total real
OP's code 4.651271 0.017978 4.669249 ( 4.679910)
alternative code 4.567764 0.012506 4.580270 ( 4.583526)
如果我将 @max_values 调整为 100 并删除删除个位数素数的代码，则替代代码的速度会提高大约在 OP 的代码上又多了 2-3 百分之一秒，但这在测试范围内似乎还不够重要，不足以保证发布更多代码或基准。
TruffleRuby 在 GraalVM 下
但是，使用 truffleruby-graalvm-21.3.0，您可以看到原始性能明显更好，尽管报告“实时”少于总时间的事实显然是某些软件的错误排序。
Rehearsal ----------------------------------------------------
OP's code 5.090858 0.106818 5.197676 ( 1.737905)
alternative code 2.890313 0.046035 2.936348 ( 1.629434)
------------------------------------------- total: 8.134024sec
user system total real
OP's code 2.523286 0.033869 2.557155 ( 1.902949)
alternative code 2.623208 0.038211 2.661419 ( 1.733567)
总结
给定任何一种方法，TruffleRuby 对此 activity 表现更好。但是，由于您可能正在处理更大的数组或其他复杂性，您可能只想考虑替代算法或方法，例如 map/reduce，将问题 space 拆分到多个核心以提高并发性，甚至可能重新设计代码以更有效地处理字符串分配，因为我怀疑（但实际上没有测量）该过程的字符串管理方面可能是除了对素数的实际迭代之外最昂贵的一组操作。
简而言之，虽然出于各种原因我会以不同的方式编写您的代码，但大幅提高速度并不在其中。但是，即使是十分之一秒也会在更大的数组或迭代中加起来，因此您可能应该考虑一下速度优化是否真的有必要。如果是，您可能想确定您在这方面的真正非功能性需求，然后确定是否不同的设计甚至不同的工具或语言可能不能更好地满足您的特定需求。
我想创建第 n 个回文质数数组。
我写了下面的代码：
# Enter your code here. Read input from STDIN. Print output to STDOUT
require 'prime'
number = gets
power_array = -> (array_size) do
1.upto(Float::INFINITY).lazy.select { |x|
Prime.prime?(x)&&x.to_s==x.to_s.reverse }.first(array_size)
end
print power_array.(number.to_i)
但它 运行 太慢了。所以我找到了这个 运行 更快的解决方案：
# Enter your code here. Read input from STDIN. Print output to STDOUT
require 'prime'
p Prime.each.lazy.select{|x| x.to_s == x.to_s.reverse}.first(gets.to_i)
为什么上面的代码 运行 比我原来的代码快？关于 big-O 和我的代码效率，我没有得到什么？
TL;DR
首先，确保这不是过早的优化或 X/Y 问题；寻找大素数或大量素数 很慢，这就是为什么在许多现代密码算法中如此依赖素数的原因。
您有一些难以解析的代码，逻辑可能未针对您的 Ruby 版本或引擎进行优化。从算法的角度来看，您还插入了一些我会尝试减少或消除的额外步骤，但在比较此特定代码的 modest 重构时，这显然不是一个重要问题。相反，我会假设您需要不同的 Ruby 引擎来提高速度，不同的算法或架构设计来解决您的问题，或者如果 Ruby 无法满足您的任何要求，则可能需要不同的语言或工具非功能性速度要求是。
然而，根据我的测试，我觉得 Ruby 对于这个问题域很容易使用，并且对于我个人处理过的大多数实际需求来说“足够快”。您的问题域可能不同，在这种情况下，请参阅下面的各个部分（尤其是末尾的摘要）以获取更多想法。
上下文
如评论中所述，我不确定您为什么认为您的代码应该“更快”，或者为什么它对于您将其用于的任何目的都不够快。两者都有些主观，缺乏上下文。
不过，您正在做一些本质上至少会减慢您速度的事情。这些内容包括：
- 在块中使用像
1.upto这样的迭代器（无论是否有惰性）。 - 在 lambda 中创建迭代块。这至少会产生一些开销，尽管它可能不是您真正的问题所在。
- 您重复将相同的值转换为字符串和整数。一些往返可能是不可避免的，但你做了很多次。
总的来说，这些事情都会增加一些开销，但我没有看到您似乎正在经历的大规模减速。我还在我的基准测试（见下文）中发现，尝试优化字符串分配实际上进一步减慢了速度，这可能是由于垃圾收集、范围和我的 IRB 测试中缺少冻结字符串的组合。有关此的一些其他想法，请参阅底部的摘要。
如果你真的想知道你的代码在哪里“太慢”（不管这对你意味着什么）那么你需要 运行 一个调试器，执行一些基准测试，或者（为了 Big-O 目的）检查 AST 以查看每个变体在 Ruby 中进行了多少次操作。对于 Ruby 在 C 级完成的操作，您可能还需要做类似的事情；无论您如何优化 Ruby 代码，大部分工作仍由 Ruby 解释器调用的 C 代码完成。
备选方案
根据您的原始代码，我不知道“足够快”对您意味着什么，但我会减少 数量 的操作以提高您的性能。使用 Ruby 3.1.0 的一个示例可能是：
require 'prime'
SINGLE_DIGIT_PRIMES = [2, 3, 5, 7].size
# plan on dropping SINGLE_DIGIT_PRIMES from the result set
print "Max size of array: "
max_values = Integer(gets) + 4
pp(
Prime.each.lazy.select do
_1 if 1.to_s == _1.to_s.reverse
end.first(max_values)[SINGLE_DIGIT_PRIMES..]
)
基准
话虽如此，要提高性能，您应该减少步骤，即使在提供了稍微快一点的替代方案之后，基准测试也并没有真正表明使用适度的数组大小或迭代来榨汁是值得的。为提高可读性稍作重构，这里有一些代码比较表明它在 Ruby 3.1.0 中似乎并没有太大的区别。 GraalVM 上的 TruffleRuby 在整体执行时间上明显更快，但在排练后再次没有显示出显着的性能差异。代码未重构以在 JRuby 9.3.2.0 下工作，目前不支持块位置变量，因为引擎版本为 2.6.8，但如果结果有很大不同，我会感到惊讶。
标准 Ruby v3.1.0
require 'prime'
require 'benchmark'
@array_size = 100
@iterations = 1_000
@max_values = @array_size + 4
def op_code
power_array = ->(arr_size) do
1.upto(Float::INFINITY).lazy.select do |x|
Prime.prime?(x) && (x.to_s == x.to_s.reverse).
first(@array_size)
end
end
power_array(@array_size.to_i)
end
def alt_code
Prime.each.lazy.select do
_1 if _1.to_s == _1.to_s.reverse!
end.first(@max_values)[4..]
end
Benchmark.bmbm do
_1.report("OP's code" ) do
@iterations.times { op_code }
end
_1.report("alternative code" ) do
@iterations.times { alt_code }
end
end
即使步数略有减少，我也看不到这两种方法的挂钟时间差异超过十分之一秒。
Rehearsal ----------------------------------------------------
OP's code 4.802338 0.032414 4.834752 ( 4.863002)
alternative code 4.673423 0.021997 4.695420 ( 4.710023)
------------------------------------------- total: 9.530172sec
user system total real
OP's code 4.651271 0.017978 4.669249 ( 4.679910)
alternative code 4.567764 0.012506 4.580270 ( 4.583526)
如果我将 @max_values 调整为 100 并删除删除个位数素数的代码，则替代代码的速度会提高大约在 OP 的代码上又多了 2-3 百分之一秒，但这在测试范围内似乎还不够重要，不足以保证发布更多代码或基准。
TruffleRuby 在 GraalVM 下
但是，使用 truffleruby-graalvm-21.3.0，您可以看到原始性能明显更好，尽管报告“实时”少于总时间的事实显然是某些软件的错误排序。
Rehearsal ----------------------------------------------------
OP's code 5.090858 0.106818 5.197676 ( 1.737905)
alternative code 2.890313 0.046035 2.936348 ( 1.629434)
------------------------------------------- total: 8.134024sec
user system total real
OP's code 2.523286 0.033869 2.557155 ( 1.902949)
alternative code 2.623208 0.038211 2.661419 ( 1.733567)
总结
给定任何一种方法，TruffleRuby 对此 activity 表现更好。但是，由于您可能正在处理更大的数组或其他复杂性，您可能只想考虑替代算法或方法，例如 map/reduce，将问题 space 拆分到多个核心以提高并发性，甚至可能重新设计代码以更有效地处理字符串分配，因为我怀疑（但实际上没有测量）该过程的字符串管理方面可能是除了对素数的实际迭代之外最昂贵的一组操作。
简而言之，虽然出于各种原因我会以不同的方式编写您的代码，但大幅提高速度并不在其中。但是，即使是十分之一秒也会在更大的数组或迭代中加起来，因此您可能应该考虑一下速度优化是否真的有必要。如果是，您可能想确定您在这方面的真正非功能性需求，然后确定是否不同的设计甚至不同的工具或语言可能不能更好地满足您的特定需求。