2 Replies - 626 Views - Last Post: 23 October 2013 - 02:16 AM Rate Topic: -----

#1 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Queue ADT

Posted 17 October 2013 - 05:07 AM

All the ruby tutorials point to arrays when you need queue functionality. << gives you the functionality of enqueue, shift gives you dequeue. It couldn't be simpler.

My question is about performance. I'm dealing with a large number of objects and am worrying about shift degrading to O(N), or O(N^2) to empty the queue.

Do ruby arrays have some hidden magic that keeps it at O(1) or do they behave the same way as Java arrays.

Is This A Good Question/Topic? 0
  • +

Replies To: Queue ADT

#2 Lemur  Icon User is offline

  • Pragmatism over Dogma
  • member icon


Reputation: 1383
  • View blog
  • Posts: 3,514
  • Joined: 28-November 09

Re: Queue ADT

Posted 22 October 2013 - 07:57 PM

Really, we can take a look through the source to see what we can find. Ruby Docs has it as a toggle for any function.

http://ruby-doc.org/...#method-i-3C-3C

That being said it's substantially faster for string concatenation, but as far as queues I'm not entirely sure.
Was This Post Helpful? 2
  • +
  • -

#3 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2069
  • View blog
  • Posts: 4,307
  • Joined: 11-December 07

Re: Queue ADT

Posted 23 October 2013 - 02:16 AM

Yeah, I had a look at the source but still wasn't sure. From what I can infer (from a second look), it might be a circular array which would give appending and prepending the same performance. I was just asking in case anybody knew for sure. For what it's worth, I've been using an array as a queue and haven't noticed any performance problems.

Thanks for the answer in any case. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1