Palindromic Prime numbers array creator [Speed Issues] RUBY

Question

I want to create an array of palindromic prime numbers nth numbers.

I wrote the code below:

# 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)

But it runs too slow. So I found this solution which runs much quicker:

# 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)

Why does the above code run quicker than my original code? What am I not getting with respect to big-O and the efficiency of my code?

Answer 1

TL;DR

First of all, be sure this isn't a premature optimization or an X/Y problem; finding large primes or large numbers of primes is slow, which is why there's so much reliance on prime numbers in many modern cryptographic algorithms.

You have some hard-to-parse code, and the logic may not be optimized for your Ruby version or engine. From an algorithmic standpoint, you are also inserting some extra steps that I would try to reduce or eliminate, but that's not apparently a significant issue when comparing modest refactorings of this particular code. I would instead assume that either you need a different Ruby engine for more speed, a different algorithm or architectural design to solve your problem, or possibly a different language or tool if Ruby can't meet whatever your non-functional speed requirements are.

However, based on my tests, I felt that Ruby was easy to use for this problem domain and "fast enough" for most practical requirements that I've personally dealt with. Your problem domain may be different, in which case please refer to the various sections below (and especially the summary at the end) for additional ideas.

Context

As mentioned in the comments, I'm not sure why you think your code should be "faster," or why it's not fast enough for whatever purpose you're putting it to. Both of those are somewhat subjective, and lack context.

Still, you're doing some things that are inherently slowing you down at least a little bit. Those things include:

1. Using an iterator like 1.upto (lazy or not) inside a block.
2. Creating an iterating block inside a lambda. This will create at least some overhead, although it's probably not where your real issue is.
3. You're repeatedly converting the same values to strings and integers. Some round-tripping is probably inevitable, but you're doing it multiple times.

Collectively, these things all add a bit of overhead, but I'm not seeing the massive slowdowns you seem to be experiencing. I also found in my benchmarking (see below) that trying to optimize for string assignment actually slowed things down further, probably due to a combination of garbage collection, scope, and the lack of frozen strings in my IRB testing. See the summary at the bottom for some additional thoughts about this.

If you really want to know where your code is "too slow" (whatever that means to you) then you need to run a debugger, perform some benchmarking, or (for Big-O purposes) examine the AST to see how many operations each variation takes in Ruby. You might also need to do similar things for the operations being done at the C-level by Ruby; no matter how well you optimize your Ruby code much of the work is still being done by the C code called by the Ruby interpreter.

Alternatives

I have no idea what "fast enough" means to you, based on your original code, but I'd reduce the number of operations to improve your performance. One example using Ruby 3.1.0 could be:

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..]
)

Benchmarks

Having said that to improve performance you should reduce steps, and even after offering a slightly faster alternative, benchmarking doesn't really show that the juice is worth the squeeze with modest array sizes or iterations. Slightly refactored for readability, here are some comparisons of the code that show that it really doesn't seem to make that much difference in Ruby 3.1.0. TruffleRuby on the GraalVM was noticeably faster in overall execution time, but again didn't show a dramatic difference in performance after the rehearsal. The code was not refactored to work under JRuby 9.3.2.0, which currently doesn't support block positional variables because the engine version is 2.6.8, but I'd be surprised if the results were tremendously different.

Standard 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

Even with the modest reduction in steps, I don't really see more than about a tenth of a second's difference in wall-clock time with either approach.

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)

If I adjust @max_values to 100 and strip out the code that removes the single-digit primes, the alternative code speeds up by about another 2-3 hundredths of a second over the OP's code, but that doesn't seem to be significant enough over the test range to warrant posting more code or benchmarks.

TruffleRuby Under GraalVM

With truffleruby-graalvm-21.3.0, though, you can see that the raw performance is significantly better, even though the fact that "real time" is being reported as less than total time is obviously a bug of some sort.

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)

Summing Up

Given either approach, TruffleRuby performs better for this activity. However, since you may be working with much larger arrays or other complexities, you might simply want to consider alternative algorithms or approaches such as map/reduce, splitting the problem space across cores for increased concurrency, or possibly even redesigning the code to handle string assignment more efficiently since I suspect (but didn't actually measure) that the string management aspect of the process is potentially the most expensive set of operations beyond the actual iteration over primes.

In short, while I would have written your code differently for a variety of reasons, massive speed increases aren't among them. However, even tenths of a second add up over larger arrays or iterations, so you should probably think a little bit about whether the speed optimization is truly necessary. If it is, you may want to determine your real non-functional requirements in that regard, and then decide whether a different design or even a different tool or language might not better suit your specific needs.