From: Brian Candler <B.Candler@...>
Date: 2003-02-23T05:35:30+09:00
Subject: Re: optimization question


--82I3+IH0IqGh5yIs
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

On Sun, Feb 23, 2003 at 03:45:43AM +0900, Martin DeMello wrote:
> Yes, but Ruby is nowhere near as wedded to unix as some other languages
> are. One interesting idea might be to subclass Array, adding a status
> flag where you can set various bits to clean or dirty everytime you make
> or break an invariant. That way, uniqc could optimise for a sorted list
> when the sorted? bit was clean, and sort first otherwise.

For uniqc, is the output going to be a hash anyway? In that case you don't
need to do anything clever. Just count adjacent elements which are
identical, then add that count to the appropriate hash slot (which may or
may not already have a value). Then it works whether it's sorted or not, but
it runs faster if sorted. Moonwolf's Hash#succ could easily be tweaked to
do that.

Or, do you think the output of uniqc should be
   [[value,count], [value,count], ... ]

with the values in the order they were first seen in the source, as
Array#uniq gives?

Just as a first attempt at extending ruby, I wrote an Array#uniqc which
gives a hash output with the above optimisation. [BEWARE: My first attempt
at writing an extension! Run this code at your own risk!!]

  require 'array_uniqc'
  a=['hello','bye']
  a.uniqc                    => {"bye"=>1, "hello"=>1}
  a<<'hello'       
  a                          => ["hello", "bye", "hello"]
  a.uniqc                    => {"bye"=>1, "hello"=>2}
  1000.times { a<<'hello' }
  a.uniqc                    => {"bye"=>1, "hello"=>1002}

Timings for a million Fixnum elements:

  require 'array_uniqc'

  a=[]
  1000.times { |x| 1000.times { |y| a << y } }  # unsorted
  b=[]
  1000.times { |x| 1000.times { |y| b << x } }  # sorted

  start = Time.now.to_f
  a.uniqc
  puts Time.now.to_f - start       #>> 1.220 secs [P233MMX]

  start = Time.now.to_f
  b.uniqc
  puts Time.now.to_f - start       #>> 0.106 secs

Having done that, I still think Moonwolf's model is better - i.e. make it a
method of Hash not Array - because you may have an existing hash of counts
which you wish to add values to.

Regards,

Brian.

--82I3+IH0IqGh5yIs
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="extconf.rb"

require 'mkmf'
create_makefile('array_uniqc')

--82I3+IH0IqGh5yIs
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="arrayuniqc.c"

#include "ruby.h"
#include "st.h"
 
VALUE
array_uniqc(ary)
    VALUE ary;
{
    long i;
    long n = 0;
    VALUE last = Qnil;
    VALUE hash = rb_hash_new();
    VALUE val;
    
    RHASH(hash)->ifnone = INT2FIX(0);
    
    for (i=0; i<RARRAY(ary)->len; i++) {
        VALUE elem = RARRAY(ary)->ptr[i];
        if (elem == last) {
          n++;
          continue;
        }
        if (n == 0) {
          /* do nothing */
        } else if (st_lookup(RHASH(hash)->tbl, last, &val)) {
          st_insert(RHASH(hash)->tbl, last, LONG2FIX( FIX2LONG(val) + n ));
        } else {
          rb_hash_aset(hash, last, LONG2FIX(n));
        }
        last = elem;
        n = 1;
    }

    if (n == 0) {
      /* do nothing */
    } else if (st_lookup(RHASH(hash)->tbl, last, &val)) {
      st_insert(RHASH(hash)->tbl, last, LONG2FIX( FIX2LONG(val) + n ));
    } else {
      rb_hash_aset(hash, last, LONG2FIX(n));
    }
    return hash;
}

void
Init_array_uniqc()
{
  rb_define_method(rb_cArray, "uniqc", array_uniqc, 0);
}

--82I3+IH0IqGh5yIs--