1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

Discussion in 'Ruby' started by Michael Tan, Jun 21, 2005.

  1. Michael Tan

    Michael Tan Guest

    --0-1157793495-1119383752=:96009
    Content-Type: text/plain; charset=iso-8859-1
    Content-Transfer-Encoding: 8bit

    Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
    1. Ruby result: 101 seconds
    2. Java result:9.8 seconds
    3. Perl result:62 seconds


    Ruby:

    def is_prime(number)
    for i in 2..(number-1)
    if number%i==0 then return false
    end
    end
    return true
    end
    ######### star here:How many primes in 2 to 50000?
    max_number=50000
    start_number=2
    total=0
    time=Time.now.to_i
    for i in start_number..max_number
    if is_prime(i)
    #puts i
    total+=1
    end
    end
    time=Time.now.to_i-time
    puts "There are #{total} primes between #{start_number} and #{max_number}"
    puts "Time taken #{time} seconds"


    Java :
    import java.io.*;
    class prime
    {
    private static boolean isPrime(long i)
    {
    for(long test = 2; test < i; test++)
    {
    if((i%test) == 0)
    {
    return false;
    }
    }
    return true;
    }
    public static void main(String[] args) throws IOException
    {
    long start_time = System.currentTimeMillis();
    long n_loops = 50000;
    long n_primes = 0;
    for(long i = 2; i <= n_loops; i++)
    {
    if(isPrime(i))
    {
    n_primes++;
    }
    }

    long end_time = System.currentTimeMillis();
    System.out.println(n_primes + " primes found");
    System.out.println("Time taken = " + (end_time - start_time)+ "millseconds");
    }
    }


    Perl:

    ######### star here:How many primes in 2 to 50000?

    # start timer

    $start = time();

    $max_number=50000;

    $start_number=2;

    $total=0;

    for ($ii=$start_number;$ii<=$max_number;$ii++){

    if (&is_prime($ii)==1)

    {$total+=1}

    }

    # end timer

    $end = time();

    # report

    print "There are ",$total," primes between ",$start_number," and ",$max_number,"\n";

    print "Time taken was ", ($end - $start), " seconds";

    sub is_prime() {

    my ($number) = $_[0];

    my ($si)=2;

    for ($si;$si<$number;$si++){

    if ($number % $si == 0) {

    return 0;}

    }

    return 1

    }




    ---------------------------------
    Discover Yahoo!
    Find restaurants, movies, travel & more fun for the weekend. Check it out!
    --0-1157793495-1119383752=:96009--
     
    Michael Tan, Jun 21, 2005
    #1
    1. Advertising

  2. On Wed, Jun 22, 2005 at 04:55:58AM +0900, Michael Tan wrote:
    > Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
    > 1. Ruby result: 101 seconds
    > 2. Java result:9.8 seconds
    > 3. Perl result:62 seconds
    >


    Well, Ruby is a scripting language and not compiled, so its
    results in the ballpark of Perl is about right. Only 10x
    as slow as Java JVM? wow, that's pretty good, Ruby rocks!

    Also, for more fun, run your Ruby through YARV and also
    run zenoptimize on it

    Benchmarks are great fun and prove nothing.




    Ralph "PJPizza" Siegler
     
    Ralph \PJPizza\ Siegler, Jun 21, 2005
    #2
    1. Advertising

  3. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    Yeah, Ruby is always going to be slower than java, since java is
    semi-compiled, whereas Ruby is interpreted from scratch. As for your
    algorithm, it is sufficient to change your is_prime methods from:

    for i in 2...number

    to

    for i in 2..Math.sqrt(number).to_i

    Which will significantly reduce the number of tests you will perform.

    David

    Michael Tan wrote:
    > Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
    > 1. Ruby result: 101 seconds
    > 2. Java result:9.8 seconds
    > 3. Perl result:62 seconds
    >
    >
    > Ruby:
    >
    > def is_prime(number)
    > for i in 2..(number-1)
    > if number%i==0 then return false
    > end
    > end
    > return true
    > end
    > ######### star here:How many primes in 2 to 50000?
    > max_number=50000
    > start_number=2
    > total=0
    > time=Time.now.to_i
    > for i in start_number..max_number
    > if is_prime(i)
    > #puts i
    > total+=1
    > end
    > end
    > time=Time.now.to_i-time
    > puts "There are #{total} primes between #{start_number} and #{max_number}"
    > puts "Time taken #{time} seconds"
    >
    >
    > Java :
    > import java.io.*;
    > class prime
    > {
    > private static boolean isPrime(long i)
    > {
    > for(long test = 2; test < i; test++)
    > {
    > if((i%test) == 0)
    > {
    > return false;
    > }
    > }
    > return true;
    > }
    > public static void main(String[] args) throws IOException
    > {
    > long start_time = System.currentTimeMillis();
    > long n_loops = 50000;
    > long n_primes = 0;
    > for(long i = 2; i <= n_loops; i++)
    > {
    > if(isPrime(i))
    > {
    > n_primes++;
    > }
    > }
    >
    > long end_time = System.currentTimeMillis();
    > System.out.println(n_primes + " primes found");
    > System.out.println("Time taken = " + (end_time - start_time)+ "millseconds");
    > }
    > }
    >
    >
    > Perl:
    >
    > ######### star here:How many primes in 2 to 50000?
    >
    > # start timer
    >
    > $start = time();
    >
    > $max_number=50000;
    >
    > $start_number=2;
    >
    > $total=0;
    >
    > for ($ii=$start_number;$ii<=$max_number;$ii++){
    >
    > if (&is_prime($ii)==1)
    >
    > {$total+=1}
    >
    > }
    >
    > # end timer
    >
    > $end = time();
    >
    > # report
    >
    > print "There are ",$total," primes between ",$start_number," and ",$max_number,"\n";
    >
    > print "Time taken was ", ($end - $start), " seconds";
    >
    > sub is_prime() {
    >
    > my ($number) = $_[0];
    >
    > my ($si)=2;
    >
    > for ($si;$si<$number;$si++){
    >
    > if ($number % $si == 0) {
    >
    > return 0;}
    >
    > }
    >
    > return 1
    >
    > }
    >
    >
    >
    >
    > ---------------------------------
    > Discover Yahoo!
    > Find restaurants, movies, travel & more fun for the weekend. Check it out!



    --
    David Mitchell
    Software Engineer
    Telogis
     
    David Mitchell, Jun 21, 2005
    #3
  4. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    Michael Tan wrote:

    >Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
    >
    >

    Your programs aren't the same. The Java and Perl program don't use
    objects, the Ruby version does. Both the Perl and the Java version could
    overflow, if numbers get too big, the Ruby program doesn't suffer from this.

    And look, I just made the Ruby version, faster, smaller and more object
    oriented:

    class Integer
    def prime?
    not (2..Math.sqrt(self).floor).find { |i| self % i == 0 }
    end
    end
    ######### star here:How many primes in 2 to 50000?
    start_number, max_number = 2, 50000
    time = Time.now.to_f
    total = (start_number..max_number).inject(0) { |s,i| s + (i.prime? ? 1 :
    0) }
    time = Time.now.to_f - time
    puts "There are #{total} primes between #{start_number} and #{max_number}"
    puts "Time taken %.3f seconds" % time

    Now do the same in the other two languages...

    --
    Florian Frank
     
    Florian Frank, Jun 21, 2005
    #4
  5. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    Florian Frank wrote:
    [...]

    For correctness, perhaps even:

    > class Integer
    > def prime?


    return false if self < 2

    > not (2..Math.sqrt(self).floor).find { |i| self % i == 0 }
    > end
    > end


    --
    Florian Frank
     
    Florian Frank, Jun 21, 2005
    #5
  6. Michael Tan

    Jim Freeze Guest

    * Florian Frank <> [2005-06-22 05:40:14 +0900]:

    > def prime?
    > not (2..Math.sqrt(self).floor).find { |i| self % i == 0 }
    > end
    > end


    Have you tried skipping even numbers (excluding 2 of course)?
    That should give you a little more speed.

    --
    Jim Freeze
     
    Jim Freeze, Jun 21, 2005
    #6
  7. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    Jim Freeze wrote:

    >Have you tried skipping even numbers (excluding 2 of course)?
    >
    >

    Not me, but some guy did 2500 years ago.

    >That should give you a little more speed.
    >

    It depends on how far you take your idea. It could get really slow on a
    real computer, if you do it with big numbers.

    --
    Florian Frank
     
    Florian Frank, Jun 21, 2005
    #7
  8. Michael Tan

    Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    On Wed, 22 Jun 2005, Michael Tan wrote:

    > --0-1157793495-1119383752=:96009
    > Content-Type: text/plain; charset=iso-8859-1
    > Content-Transfer-Encoding: 8bit
    >
    > Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or it is normal?
    > 1. Ruby result: 101 seconds
    > 2. Java result:9.8 seconds
    > 3. Perl result:62 seconds


    if you just want a fast ruby version:

    harp:~ > cat prime_inline.rb
    def benchmark label, code
    STDOUT.sync = true
    puts "#{ '=' * 16 }\n#{ label }\n#{ '=' * 16 }"
    fork do
    GC.disable
    a = Time::now.to_f
    code.call
    b = Time::now.to_f
    puts " @ #{ b - a }"
    end
    Process::wait
    end

    prime_test = lambda{ (2 ... (2 ** 14)).each{|n| n.prime?} }

    class Fixnum
    def prime?
    (2...self).each{|i| return false if self % i == 0}
    return true
    end
    end
    benchmark 'pure ruby', prime_test

    require 'inline'
    class Fixnum
    inline do |builder|
    builder.c_raw <<-src
    static VALUE
    is_prime_c (int argc, VALUE *argv, VALUE self) {
    long i, n = FIX2LONG (self);
    for (i = 2; i < n; i++) if (n % i == 0) return Qfalse;
    return Qtrue;
    }
    src
    end
    alias prime? is_prime_c
    end
    benchmark 'inline c', prime_test

    harp:~ > ruby prime_inline.rb
    ================
    pure ruby
    ================
    @ 14.9205560684204
    ================
    inline c
    ================
    @ 0.539831876754761


    so that's about two orders of magnitude speed-up for less than 10 extra lines
    of code - and you still get nice things like overflow safety.

    hth.

    -a
    --
    ===============================================================================
    | email :: ara [dot] t [dot] howard [at] noaa [dot] gov
    | phone :: 303.497.6469
    | My religion is very simple. My religion is kindness.
    | --Tenzin Gyatso
    ===============================================================================
     
    , Jun 21, 2005
    #8
  9. Michael Tan

    Ken Kunz Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    Here's a version that skips even numbers:

    class Integer
    def is_prime?
    return false if self < 2
    return false if self % 2 == 0
    max_factor = Math.sqrt(self).to_i
    3.step(max_factor, 2) {|i| return false if self % i == 0 }
    return true
    end
    end

    And here's a benchmark comparison:

    require 'benchmark'

    Benchmark.bm(12) do |x|
    x.report("original:") { 2.upto(50000) {|i| is_prime(i) } }
    x.report("Florian's:") { 2.upto(50000) {|i| i.prime? } }
    x.report("Ken's:") { 2.upto(50000) {|i| i.is_prime? } }
    end

    user system total real
    original: 171.767000 0.020000 171.787000 (174.627000)
    Florian's: 2.804000 0.010000 2.814000 ( 2.814000)
    Ken's: 1.041000 0.000000 1.041000 ( 1.042000)

    What's more important, how fast a program _runs_, or how fast I can
    _write_ it? With Ruby, I can almost always write something that is
    "fast enough", and I can write it a whole lot quicker than in Java or
    C. The above (semi-) optimized version only took 2 minutes to write.
    (And as a side note... it was more fun to write it in Ruby :) )

    And when you need some extra umph... there's always YARV or ruby2c...
    and when you really need it (rarely), manually optimized C.

    Cheers,
    Ken
     
    Ken Kunz, Jun 21, 2005
    #9
  10. Michael Tan

    Isaac Gouy Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    Michael Tan wrote:
    > Just new to Ruby since last week, running my same functional program on the windows XP(Pentium M1.5G), the Ruby version is 10 times slower than the Java version. The program is to find the prime numbers like 2, 3,5, 7, 11, 13...


    Refer to the simple programs on The Great Computer Language Shootout -
    then you can blame those guys for doing meaningless benchmarking rather
    than taking the heat yourself :)

    http://shootout.alioth.debian.org/great/benchmark.php?test=all&lang=ruby&lang2=java&sort=fullcpu
     
    Isaac Gouy, Jun 22, 2005
    #10
  11. Michael Tan

    Jim Freeze Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    * Ken Kunz <> [2005-06-22 07:20:36 +0900]:

    > user system total real
    > original: 171.767000 0.020000 171.787000 (174.627000)
    > Florian's: 2.804000 0.010000 2.814000 ( 2.814000)
    > Ken's: 1.041000 0.000000 1.041000 ( 1.042000)


    That's better than I expected. I'm not sure why Florian thought
    it would be slower.

    --
    Jim Freeze
     
    Jim Freeze, Jun 22, 2005
    #11
  12. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    Jim Freeze wrote:

    >That's better than I expected. I'm not sure why Florian thought
    >it would be slower.
    >
    >

    If you compute a sieve to find out, if a very high number is prime...

    --
    Florian Frank
     
    Florian Frank, Jun 22, 2005
    #12
  13. Michael Tan

    Dee Zsombor Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    How about using a better algorithm than Eratosthenes sieve invented
    thousands of years ago. In late 2003 a new method was published that
    computes the first n primes using binary quadratic forms. This will
    give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).

    For theoretical description see:
    http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf

    And for a sample implementation in C
    http://cr.yp.to/primegen.html

    cheers,
    zsombor
    --
    http://deezsombor.blogspot.com
     
    Dee Zsombor, Jun 22, 2005
    #13
  14. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3.

    irb(main):001:0> require "openssl"
    => true
    irb(main):002:0> include OpenSSL
    => Object
    irb(main):003:0> a=BN.new("103")
    => 103
    irb(main):004:0> a.prime?(10)
    => true
    irb(main):005:0> a.prime?(nil)
    => true
    irb(main):006:0>


    It implements the Miller-Rabin-Test.

    See http://www.hmug.org/man/3/BN_is_prime.php




    Dee Zsombor schrieb:
    > How about using a better algorithm than Eratosthenes sieve invented
    > thousands of years ago. In late 2003 a new method was published that
    > computes the first n primes using binary quadratic forms. This will
    > give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).
    >
    > For theoretical description see:
    > http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf
    >
    > And for a sample implementation in C
    > http://cr.yp.to/primegen.html
    >
    > cheers,
    > zsombor
    > --
    > http://deezsombor.blogspot.com
    >
    >
    >
     
    Roland Schmitt, Jun 22, 2005
    #14
  15. Michael Tan

    Mark Thomas Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    Florian Frank wrote:
    > And look, I just made the Ruby version, faster, smaller and more object
    > oriented:
    > ...
    > Now do the same in the other two languages...


    Okay, here's the Perl version:

    #!/usr/bin/perl -w
    use Math::Big 'primes';
    my $max = 50000;
    my $start = time();
    my $total = primes($max);
    my $time = time() - $start;
    print "There are $total primes below $max.\n";
    print "Time taken was $time\n";

    On my system I get 27 vs. 192 for the original Perl version (which is
    not written very perlishly). Sure, this is cheating. CPAN is like
    institutionalized cheating, and I love it. :) In fact, one of the
    reasons I started lurking in the Ruby group is that I think Ruby (with
    Gems) is closer to developing a CPAN-like system than Python, and thus
    I have decided to learn Ruby instead of Python.

    - Mark.
     
    Mark Thomas, Jun 22, 2005
    #15
  16. Michael Tan

    Ryan Davis Guest

    Re: Ruby result: 101 seconds

    On Jun 21, 2005, at 12:55 PM, Michael Tan wrote:

    > Just new to Ruby since last week, running my same functional
    > program on the windows XP(Pentium M1.5G), the Ruby version is 10
    > times slower than the Java version. The program is to find the
    > prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or
    > it is normal?
    > 1. Ruby result: 101 seconds
    > 2. Java result:9.8 seconds
    > 3. Perl result:62 seconds


    With some very minor modifications to the original code (I did upto
    instead of for and wrapped is_prime in a class), none of which were
    algorithmic improvements (ugh):

    Modified is_prime code:

    class Primer
    def is_prime(number)
    2.upto(number-1) do |i|
    return false if number % i == 0
    end
    return true
    end
    end

    NORMAL:

    % rm -rf ~/.ruby_inline/; ruby primes.rb 50000
    There are 5133 primes between 2 and 50000
    Time taken 237.315160036087 seconds

    (whoa. my laptop is a slowpoke! oh yeah, I'm on battery!)

    ONE EXTRA CMD-LINE TOKEN:

    % rm -rf ~/.ruby_inline/; ruby -rzenoptimize primes.rb 50000
    *** Optimizer threshold tripped!! Optimizing Primer.is_prime
    There are 5133 primes between 2 and 50000
    Time taken 2.81669783592224 seconds

    That said... what did we learn from this thread?

    Yes... benchmarks are dumb (see also, 3 lines down)
    That there is no accounting for taste (ugliest code/
    algorithm ever).
    A good algorithm goes a long way.
    2/3rds of the ppl are going to mis-analyze anyhow.

    ... Nothing really.



    --
    - Seattle.rb - http://www.zenspider.com/
    seattle.rb
    http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c
     
    Ryan Davis, Jun 23, 2005
    #16
  17. Michael Tan

    Ryan Davis Guest

    Ryan Davis, Jun 23, 2005
    #17
  18. Michael Tan

    Dee Zsombor Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    As far as I understood from Miller-Rabin-Test is for determining if a
    number is prime with a _given_ _probability_. It is a very efficient
    algortithm for that.
    The Atkins sieve (binary quadratic forms) is about generating all
    primes less than given number. And that is an entirely different
    problem, even if you woud do MR in a loop you would not get the same
    results as Atkin sieve.
     
    Dee Zsombor, Jun 23, 2005
    #18
  19. Michael Tan

    Dee Zsombor Guest

    Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    As far as I understood from Miller-Rabin-Test is for determining if a
    number is prime with a _given_ _probability_. It is a very efficient
    algortithm for that.
    The Atkins sieve (binary quadratic forms) is about generating all
    primes less than given number. And that is an entirely different
    problem, even if you woud do MR in a loop you would not get the same
    results as Atkin sieve.

    --
    http://deezsombor.blogspot.com
     
    Dee Zsombor, Jun 23, 2005
    #19
  20. Re: 1. Ruby result: 101 seconds , 2. Java result:9.8 seconds, 3. Perl result:62 seconds

    On Wed, Jun 22, 2005 at 10:50:36PM +0900, Mark Thomas wrote:
    > Okay, here's the Perl version:
    >
    > #!/usr/bin/perl -w
    > use Math::Big 'primes';
    > my $max = 50000;
    > my $start = time();
    > my $total = primes($max);
    > my $time = time() - $start;
    > print "There are $total primes below $max.\n";
    > print "Time taken was $time\n";
    >
    > On my system I get 27 vs. 192 for the original Perl version (which is
    > not written very perlishly). Sure, this is cheating. CPAN is like
    > institutionalized cheating, and I love it. :) In fact, one of the
    > reasons I started lurking in the Ruby group is that I think Ruby (with
    > Gems) is closer to developing a CPAN-like system than Python, and thus
    > I have decided to learn Ruby instead of Python.


    It's perhaps worth mentioning that although Ruby is about 1/3rd of the size
    of Perl, it has a far more complete standard library.

    A base Ruby install includes, amongst other things: SSL, base64 encoding/
    decoding, MD5/SHA1 hashing, XML/YAML parsing, HTTP client and server, and
    remote method calls (DRb, SOAP, XMLRPC).

    I think recent version of Perl have accumulated MIME::Base64, but the others
    are still extensions you have to download and install.
     
    Brian Candler, Jun 23, 2005
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Kasu Nai

    Java 101 - Method Calls

    Kasu Nai, Jul 2, 2003, in forum: Java
    Replies:
    1
    Views:
    1,076
    Doug Pardee
    Jul 2, 2003
  2. Ben

    Ruby Threads 101

    Ben, Sep 26, 2005, in forum: Ruby
    Replies:
    11
    Views:
    199
    Robert Klemme
    Sep 27, 2005
  3. Allen Lee

    Ruby 101 Series

    Allen Lee, Nov 4, 2009, in forum: Ruby
    Replies:
    0
    Views:
    96
    Allen Lee
    Nov 4, 2009
  4. Replies:
    0
    Views:
    250
  5. Oliver Soeder
    Replies:
    1
    Views:
    286
Loading...

Share This Page