[Ruby] Ruby: array intersperse, efficiency

2009-06-10T11:00:18-07:00

Intersperse is a method of the array class

Intersperse takes an object o, and returns the array ( self ), with o inserted between each element of self.

class Array

   # insert i between each element in the array

   # this is O( 2n ) ( I think! Is it? ) as the length of the list is not needed, but we need to initially make a copy of the list
     def intersperse( v )
      tail = [ ].replace self # we need a shallow copy
      first_elem = tail.first
      second_elem = tail[ 1 ]
      arr = [ ]
      while first_elem
         arr.push first_elem
         if second_elem
            arr.push v
            tail = tail.drop 1
            first_elem = tail.first
            second_elem = tail[ 1 ]
         else
            break
         end
      end
      arr
   end

  # this is faster, but I worry that for large arrays, storing i in memory will makes this slower
  # Bearing that in mind, since the speed at which this goes is determined by the length of the list as well as the length of the list stored in memory ( i ) is O( n^2 ) ( again, please correct me )
  def intersperse( v )
     arr = [ ]
     i = 0
     j = 0
     inc_jay = lambda { j = j + 1 }
     while i < length
        arr[ j ] = self[ i ]
        inc_jay.call
        if self[ i + 1 ]
           arr[ j ] = v
           inc_jay.call
        end
        i = i + 1
     end
     arr
  end
end

spoonerism.myopenid.com

[Ruby] Ruby: array intersperse, efficiency