From: "Brian F. Feldman" <green@...>
Date: 2000-11-27T11:26:13+09:00
Subject: [ruby-talk:6587] Re: best way to interleaf arrays?

David Alan Black <dblack@candle.superlink.net> wrote:
> Hello --
> 
> On Mon, 27 Nov 2000, Brian F. Feldman wrote:
> 
> > David Alan Black <dblack@candle.superlink.net> wrote:
> > > Hello --
> > > 
> > > Is there a nice Ruby idiom for interleafing arrays?  It's not hard to
> > > write a method that will do it, but I'd be interested in knowing how
> > > it's been done in the past.
> > 
> > What do you mean by interleave?  Normally I'd take this to mean that you'd 
> > want the even number of elements from the first array and the odd numbered 
> > elements to come from the second array, but it seems you're implying you 
> > just want the logical union of the two.  e.g.
> 
> Hmmmm.... I'm not sure what I said that implied that.  Maybe throwing
> in the hash thing was confusing.  Anyway, except for my misspelling
> the word (an old mental glitch), my reference was indeed to
> interleaving.

Yes, that would be the confusing part :)

> My current best shot at an interleave method is:
> 
> class Array
> 
>   def interleave(ary2)
>     a1, a2, res = self.dup, ary2.dup, []
>     res.push a1.shift, a2.shift until a1.empty? or a2.empty?
>     for n in [a1, a2]
>       res.concat n unless n.empty?
>     end
>     res
>   end
> 
> end
> 
> which is about as fast as I can get it (non-destructively :-)  

Ah, hm!  I thought that shift would be slower because every single shift 
requires a memory copy operation...  It seems it is, but I pessimized things 
in a couple ways.  "until" is faster than "while" in this case because the
two "not" operations take more cycles than the one extra "not" in the C code.
Then there's the speed hit in doing it with pop because the reverses mean 
that an optimized memcpy() cannot be called.

The flip-flop between the two arrays was clearly unnecessary because it 
would only happen an even number of times anyway, *L*.  The speed gain was 
when you use pop instead of shift; shift involves a bunch of memcpy()s, but 
pop (often) involves just shrinking the array by decrementing the size. It's 
pretty interesting to see how code gets faster and why :)  The final, fastest
version I know of is:

class Array

  def interleave(ary2)
    a1, a2, res = self.reverse, ary2.reverse, []
    res.push a1.pop, a2.pop until a1.empty? or a2.empty?
    for n in [a1, a2]
      res.concat n unless n.empty?
    end
    res
  end

end


> On the hash matter:
> 
> > You can always do it as:
> > 
> > h = Hash.new(false)
> > (array1 + array2).each {|x| h[x] = true}
> 
> Yes, I think that's where the union confusion was.  My hash topic was
> actually separate.  I was working on a whole cluster of problems, the
> connections among which were probably less clear than I'd thought.
> The problem in the middle, so to speak, was populating a hash from two
> arrays, in this sense:
> 
>   h = Hash[*a1.interleave(a2)]
> 
> which set me on the road to interleaving, and also got me wondering
> about what else could be done between those square brackets (e.g.,
> setting values to true for an array of keys).

Ah, now I see where this all fits in!  How about this, not as fun but it is 
useful.  Yeah, it's just not the same, but it works nicely :)

module Enumerable
    def hash_with(en2, *harg, &hblock)
        h = Hash.new(*harg, &hblock)
        self.each_with_index {|e, i| h[e] = en2[i]}
        h
    end
end


--
 Brian Fundakowski Feldman           \  FreeBSD: The Power to Serve!  /
 green@FreeBSD.org                    `------------------------------'