best way to interleaf arrays?
David Alan Black
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.
By the way, my curiosity about this stems from some tinkering with
hashes -- specifically, trying to populate a hash from two arrays. A
related problem, which I'll throw in here too, is how best to create a
hash which simply sets each value to "true" (or 1, or whatever). The
best I've come up with for that is:
h = Hash[*arr.map { |x| [x,true] } .flatten ]
which feels awfully roundabout for this purpose. Intervention
is welcome.
Thanks --
David
--
David Alan Black
home: dbl...@candle.superlink.net
work: blac...@shu.edu
Web: http://pirate.shu.edu/~blackdav
Brian F. Feldman
> 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.
irb(main):004:0> ["ichi", "ni", "san"] | ["san", "yon", "go"]
["ichi", "ni", "san", "yon", "go"]
Which you can also do with (A + B).uniq, or destructively with
A.join(B).uniq!.
If you mean that you want to actually want to interleave the elements, I can
think of a bunch of ways, but no actual idiom. One would be:
irb(main):042:0> class Array
irb(main):043:1> def interleave(ary2)
irb(main):044:2> ary1 = self.reverse
irb(main):045:2> ary2 = ary2.reverse
irb(main):046:2> nary = []
irb(main):047:2> flipflop = true
irb(main):048:2> while !ary1.empty? && !ary2.empty?
irb(main):049:3> nary.push((flipflop ? ary1 : ary2).pop)
irb(main):050:3> flipflop = !flipflop
irb(main):051:3> end
irb(main):052:2> nary.concat((ary2.empty? ? ary1 : ary2).reverse)
irb(main):053:2> return nary
irb(main):054:2> end
irb(main):055:1> end
nil
irb(main):056:0> [1, 3, 5, 7, 8, 9].interleave([2, 3, 4, 6])
[1, 2, 3, 3, 5, 4, 7, 6, 8, 9]
irb(main):057:0> [1, 3, 5, 7, 8, 9].interleave([2, 4, 6])
[1, 2, 3, 4, 5, 6, 7, 8, 9]
> By the way, my curiosity about this stems from some tinkering with
> hashes -- specifically, trying to populate a hash from two arrays. A
> related problem, which I'll throw in here too, is how best to create a
> hash which simply sets each value to "true" (or 1, or whatever). The
> best I've come up with for that is:
>
> h = Hash[*arr.map { |x| [x,true] } .flatten ]
>
> which feels awfully roundabout for this purpose. Intervention
> is welcome.
You can always do it as:
h = Hash.new(false)
(array1 + array2).each {|x| h[x] = true}
This version seems slightly less "functional", but it should be more
efficient, and it's less convoluted. In this case, I'd be inclined to
believe that using the or operator | instead of + would be a bit slower.
I suppose if I _really_ cared about making it totally functional, I could
do something evil ;):
[Hash.new(false)].each {|h| (array1 + array2).each {|x| h[x] = true}}
> Thanks --
>
>
> David
Hope this helps.
--
Brian Fundakowski Feldman \ FreeBSD: The Power to Serve! /
gr...@FreeBSD.org `------------------------------'
David Alan Black
On Mon, 27 Nov 2000, Brian F. Feldman wrote:
> David Alan Black <dbl...@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.
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 :-)
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).
Dave Thomas
> 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.
Matz has a technique for simulating external iterators using threads,
which would do it.
You could also do it the boring way:
def interleave(a1, a2)
n = a1.size
n = a2.size if a2.size < n
(0...n).collect {|i| [a1[i], a2[i]]}.flatten + a1[n..-1] + a2[n..-1]
end
On the Hash front, I'm starting to think it would be useful to have
Hash.from_array(ary, value)
which was equivalent to
def Hash.from_array(ary, value = 1)
h = {}
if block_given?
ary.each {|k| h[k] = yield(k,value) }
else
ary.each {|k| h[k] = value }
end
h
end
Regards
Dave
Mike T. Miller
Or maybe something like this:
res = []
bigger = if a1.size > a2.size then a1 else a2
bigger.each_index { |n| res << [a1[n], a2[n]] }
res = res.flatten.compact
Of course, that only works if 'nil' is not a normal value in your
arrays.
--
Mike T. Miller
Senior Java Architect
Sun Microsystems, Switzerland
+41 1 812 04 51
Brian F. Feldman
> Hello --
>
> On Mon, 27 Nov 2000, Brian F. Feldman wrote:
>
> > David Alan Black <dbl...@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
David Alan Black
> 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
Except... you haven't (un)reversed what's left of a1 and a2. So, for
example:
a1 = [1, 2, 3, 4]
a2 = %w{ one two }
p a1.interleave(a2) # => [1, "one", 2, "two", 4, 3]
So:
res.concat n.reverse unless n.empty?
though dropping the whole 'for' construct and replacing the final
'res' with this:
res + (a1 + a2).reverse
(snagging the '+' instead of concat approach from Dave's iterator
version) runs a little faster. To save some space (I assume, since +
creates a new array):
res.concat (a1 + a2).reverse
And other permutations, yet unborn.... :-)
Cullen J O'neill
: 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
A somewhat different approach I thought of is:
class Array
def intereach(arr)
length.times { |n| yield(at(n), arr.at(n)) }
end
end
card = [1,2,3,4]
ord = ['first','second','third','fourth']
hs = []
card.intereach(ord) { |n, m| hs << n << m }
hs # => [1, "first", 2, "second", 3, "third", 4, "fourth"]
Which gets the desired result.
: which is about as fast as I can get it (non-destructively :-)
I have no idea how fast it is, but hopefully it's at least worth investigating.
--
Cullen J O'Neill
--
cj...@engin.umich.edu
David Alan Black
On Mon, 27 Nov 2000, Dave Thomas wrote:
> On the Hash front, I'm starting to think it would be useful to have
>
> Hash.from_array(ary, value)
>
> which was equivalent to
>
> def Hash.from_array(ary, value = 1)
> h = {}
> if block_given?
> ary.each {|k| h[k] = yield(k,value) }
> else
> ary.each {|k| h[k] = value }
> end
> h
> end
What about a to_h method for arrays? I mention this mainly for the
sake of symmetry with other to_* methods. Then again, such a method
may violate some principle of design: it does seem slightly wrong for
Array to "know" how to generate a hash (whereas not strange for Hash
to know how to create itself from an array).
Dave Thomas
> What about a to_h method for arrays? I mention this mainly for the
> sake of symmetry with other to_* methods. Then again, such a method
> may violate some principle of design: it does seem slightly wrong for
> Array to "know" how to generate a hash (whereas not strange for Hash
> to know how to create itself from an array).
That was my thinking (if you can call it that ;-) It seems reasonable
for a more complex class to know about a more primitive one, but not
the other way around.
An alternative might be Kernel::Hash, along the lines of
Kernel::Integer, which does the business depending on the type of its
argument.
Regards
Dave
David Alan Black
> David Alan Black <dbl...@candle.superlink.net> writes:
>
> > What about a to_h method for arrays? I mention this mainly for the
> > sake of symmetry with other to_* methods. Then again, such a method
> > may violate some principle of design: it does seem slightly wrong for
> > Array to "know" how to generate a hash (whereas not strange for Hash
> > to know how to create itself from an array).
>
> That was my thinking (if you can call it that ;-) It seems reasonable
> for a more complex class to know about a more primitive one, but not
> the other way around.
Although.... what about the cases where two types have to_* methods
for each other? (Array#to_s, String#to_a, for example) Are all such
types considered lateral to each other, on the scale of complexity?
Or maybe the difference is that a-to-s/s-to-a don't introduce new
data, whereas hashing an array against a bunch of 1's adds a bunch
of 1's.
There's another way to look at it, though -- somewhat Devil's
advocate, but anyway. Arrays and hashes are both indexed collections
of elements, with the one singularity that the indices of arrays are
integers. From that perspective, a case could be made that changing
an array to a hash really wouldn't involve anything that wasn't part
of the array already. But this would depend on doing it, not as we've
been discussing so far, but like this:
class Array
def to_h
h = {}
each_index { |i| h[i] = at i }
h
end
end
%w{ list of words }.to_h # => {0=>"list", 1=>"of", 2=>"words"}
One could then invert the hash to get at least one version of the
original effect -- namely, the original array elements as hash keys
and all the values true. (Even zero!)
In short: just as a string knows enough to break itself down into an
array, an array could perhaps reasonably know enough to present itself
as a hash, if all that's involved is lining up the indices and the
elements and letting them be called something else (i.e., without
interpolating anything new).
Well, that's about the best case I can make for this. I'm not as
unconvinced by it as I thought I would be :-) Comments encouraged.
Dave Thomas
> class Array
> def to_h
> h = {}
> each_index { |i| h[i] = at i }
> h
> end
> end
>
> %w{ list of words }.to_h # => {0=>"list", 1=>"of", 2=>"words"}
>
> One could then invert the hash to get at least one version of the
> original effect -- namely, the original array elements as hash keys
> and all the values true. (Even zero!)
I'm convinced by this, particular if we added the block form too.
Regards
Dave
David Alan Black
I was wondering about a block form. I'm not sure exactly what it
would do -- specifically, whether the results of the block would
pertain to the keys or the values of the new hash. In other words,
would it be this:
each_with_index { |e,i| h[i] = yield(i, e) }
or this:
each_with_index { |e,i| h[yield(i, e)] = e }
or something else? Or might it be better for to_h to be blockless,
since the new hash could in any case simply be processed with all the
familiar iterators?
Another question on the hypothetical to_h subject: would there be any
reason for to_h not to be part of Enumerable, rather than Array?
Dave Thomas
> I was wondering about a block form. I'm not sure exactly what it
> would do -- specifically, whether the results of the block would
> pertain to the keys or the values of the new hash. In other words,
> would it be this:
>
> each_with_index { |e,i| h[i] = yield(i, e) }
>
> or this:
>
> each_with_index { |e,i| h[yield(i, e)] = e }
>
or
module Enumerable
def to_h(value = 1)
h = {}
if block_given?
each_with_index {|e,i| hk,hv = yield(e,i); h[hk] = hv }
else
each {|hv| h[hv] = value }
end
h
end
end
ary = %w{one two three}
ary.to_h #=> {"one"=>1, "three"=>1, "two"=>1}
ary.to_h false #=> {"one"=>false, "three"=>false, "two"=>false}
ary.to_h { |word, index| [index, word]}
#=> {0=>"one", 1=>"two", 2=>"three"}
ary.to_h { |word, index| [word, index]}
#=> {"one"=>0, "three"=>2, "two"=>1}
ary.to_h { |word,| [word.upcase, true]}
#=> {"ONE"=>true, "THREE"=>true, "TWO"=>true}
> Another question on the hypothetical to_h subject: would there be any
> reason for to_h not to be part of Enumerable, rather than Array?
Sounds reasonable to me.
Dave
David Alan Black
> David Alan Black <dbl...@candle.superlink.net> writes:
>
> > I was wondering about a block form. I'm not sure exactly what it
> > would do -- specifically, whether the results of the block would
> > pertain to the keys or the values of the new hash. In other words,
> > would it be this:
> >
> > each_with_index { |e,i| h[i] = yield(i, e) }
> >
> > or this:
> >
> > each_with_index { |e,i| h[yield(i, e)] = e }
> >
>
> or
> module Enumerable
> def to_h(value = 1)
> h = {}
> if block_given?
> each_with_index {|e,i| hk,hv = yield(e,i); h[hk] = hv }
> else
> each {|hv| h[hv] = value }
> end
> h
> end
> end
Oh, ok :-)
For what it's worth, here are the results of an attempt on my part to
chart a path, method by method, from a very simple to_h approach to
the more complex, useful ones (including use of blocks). The idea is
to be as incremental as possible, defining later methods largely in
terms of earlier ones (including an interleave method). My goal was
to see how the principle of the array not "knowing" too much holds up,
as things move beyond the level of an array just allowing itself to be
interpreted as a hash and onto the level of things like accepting a
value to set all the hash values to. (I couldn't see how that could
*not* represent an array knowing too much, until I worked it through
as shown below.)
This stuff is not optimized or debugged, nor is it meant as a
practical way of organizing or naming methods. It's more a sort of
exploded/implemented model of this train of thought.
module Enumerable
# For convenience, adapted from the latest ruby-talk consensus
def interleave(enum2)
e1, e2, res = to_a.reverse, enum2.to_a.reverse, []
res.push e1.pop, e2.pop until e1.empty? or e2.empty?
res + (e1 + e2) .reverse
end
# The simplest to_h: array elements are taken two at a time.
# (Not even indices -- just elements.)
def to_h_raw
a = dup
h = {}
h[a.shift] = a.shift || nil until a.empty?
h
end
# Now, building on that:
# Indices as keys
def to_h_ikeys
(0...size) .interleave(self) .to_h_raw
end
# Elements as keys
def to_h_ekeys
to_h_ikeys .invert
end
# Elements as keys, values all set to value
def to_h_v(value)
interleave([].fill(value, 0...size)) .to_h_raw
end
# Block version
def to_h_b
(0...size) .map { |i| yield(at(i),i) } .flatten .to_h_raw
end
end
ary = %w{one two three}
ary.to_h_raw # => {"one"=>"two", "three"=>nil}
ary.to_h_ikeys # => {0=>"one", 1=>"two", 2=>"three"}
ary.to_h_ekeys # => {"one"=>0, "three"=>2, "two"=>1}
ary.to_h_v true # => {"one"=>true, "three"=>true, "two"=>true}
ary.to_h_b { |e,|
[e.upcase, true]
} # => {"ONE"=>true, "THREE"=>true, "TWO"=>true}
__END__