On 23-Oct-07, at 10:37 AM, David A. Black wrote:
alias :enqueue :push
end
This is potentially a troublesome implementation. I believe that the
queue is going to grow and grow. See my other messages about the
behaviour of un/shift.
Cheers,
Bob
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On 23-Oct-07, at 10:52 AM, Jesús Gabriel y Galán wrote:
element in the Array :-). (you could do enqueue → unshift,
Of course I forgot to mention the specific problem for your scheme.
larger and larger.I understand your explanation, but this sounds like a bug to me. I
understand the optimization part of not shifting everything in the
shift method, but if that’s a desired way of working I suppose it
should be warned for the users of Array. In light of this then, the
recommended approach for queue semantics would be to use unshift and
pop?
I just did a quick test. It looks as though Ruby is now handling both
the unshift/pop and push/shift properly. I know when I reported it in
Ruby 1.8.4 there was a discussion about how to deal with this, and it
looks as though 1.8.5 has it working (or I’ve patched my version of
Ruby and have forgotten about it).
So maybe not a problem, or too big of a problem. Just don’t forget
about the cells holding references, that is definitely there in 1.8.5.
Cheers,
Bob
Thanks,
Jesus.
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On 23-Oct-07, at 11:17 AM, Bob H. wrote:
I just did a quick test. It looks as though Ruby is now handling
both the unshift/pop and push/shift properly. I know when I
reported it in Ruby 1.8.4 there was a discussion about how to deal
with this, and it looks as though 1.8.5 has it working (or I’ve
patched my version of Ruby and have forgotten about it).So maybe not a problem, or too big of a problem. Just don’t forget
about the cells holding references, that is definitely there in 1.8.5.
I just wrote a little test script. It looks as though push will
cleanup the empty space left by shift. So your queue should be okay
on average either way you implement it. Though you’ll be growing
the array until push is called (and at the same time there will be
invisible references to objects)… generally working but with
potentially subtle bugginess.
Cheers,
Bob
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://
www.raconteur.info/cms-for-static-content/home/
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On 10/23/07, Bob H. [email protected] wrote:
I just wrote a little test script. It looks as though push will
cleanup the empty space left by shift. So your queue should be okay
on average either way you implement it. Though you’ll be growing
the array until push is called (and at the same time there will be
invisible references to objects)… generally working but with
potentially subtle bugginess.
Thanks, it’s good to know.
Kind regards,
Jesus.
On 23-Oct-07, at 10:52 AM, Jesús Gabriel y Galán wrote:
I understand your explanation, but this sounds like a bug to me. I
understand the optimization part of not shifting everything in the
shift method, but if that’s a desired way of working I suppose it
should be warned for the users of Array. In light of this then, the
recommended approach for queue semantics would be to use unshift and
pop?
unshift/pop seems to me to be a possibility. I think it’ll have to be
tested though. One can easily imagine that ruby does not release
allocated space in an array, as an optimisation. If this is the case
then the queue will continue to grow unbound but after the end of the
array instead before the start.
Maybe a linked list?
Cheers,
Bob
Thanks,
Jesus.
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On Oct 23, 10:32 am, Bob H. [email protected] wrote:
alias :dequeue :shift
end
cms-for-static-content/home/- Hide quoted text -
- Show quoted text -
It was my understanding that unshift was the leaky method. There was a
monkey patch but I have lost the reference to that thread.
On Tuesday 23 October 2007 08:37 am, David A. Black wrote:
Have a look at #shift and #unshift.
Thanks! (I did notice those later.)
Randy K.
On Tue, 23 Oct 2007 20:44:48 +0900, Robert K. wrote:
I always liked that visualization. The problem for me (and I’m not the
OP) is that in Ruby you have to lift all the plates off, put the new
plate on the bottom, and then put all the plates back. (Likewise when
you want to “pop” that plate.)(Because Ruby uses push and pop on
the end of the array instead of the beginning.)I’m not sure what exactly you mean. #push and #pop just work as one
would expect from a LIFO.
Perhaps he means to work with a FIFO?
"Head or tail first
Authors and users of FIFO queue software should consider carefully the
use of the terms “head” and “tail” to refer to the two ends of the
queue.
To many people, items should enter a queue at the tail, remain in the
queue until they reach the head and leave the queue from there. This
point of view is justified by analogy with queues of people waiting for
some kind of service and parallels the use of “front” and “back” in the
above example. Other people, however, believe that you enter a queue at
the head and leave at the tail, in the manner of food passing through a
snake. Queues written in that way appear in places that might be
considered authoritiative, such as the GNU/Linux operating system,
making
the point of view hard to dismiss however repugnant you find the idea of
getting your data from a snake’s rear-end."
http://en.wikipedia.org/wiki/FIFO
-Thufir
On 10/23/07, David A. Black [email protected] wrote:
the array).
No thanks. #shift/#unshift are fine, and certainly I don’t want to
have to figure out what people have aliased enqueue and dequeue to
before I can understand their code.
Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.
Todd
On Tue, 23 Oct 2007 23:32:01 +0900, Bob H. wrote:
Implementing a cache (the uncached stuff was hanging around in memory,
intermittently since unshift will re-use the parts of the array before
the start). I also found (and reported, maybe even supplied a patch for)
a problem in Mongrel’s thread management code that was using shift. How
did I debug it the first time? Don’t ask.
Could this lead to a security problem down the road?
-Thufir
On 10/24/07, Todd B. [email protected] wrote:
Not only that, but enqueue and dequeue return different objects.
Enqueue returns an array, and dequeue returns the object that was
shifted from the stack.Todd
Hmm. I guess shift/unshift are like that too. Sorry for the noise.
I’m surprised, though, that this thread has received so much
attention. I don’t really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven’t experienced
the others in depth yet.
Todd
On 10/24/07, Todd B. [email protected] wrote:
On 10/24/07, Todd B. [email protected] wrote:
I’m surprised, though, that this thread has received so much
attention. I don’t really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven’t experienced
the others in depth yet.
Well, I answered to this thread not because I had any problem with the
terminology, but to comment on the fact that pop/push is stack
semantics, and I would like also queue semantics. After thinking about
what David and I were discussing about how to make this happen, I’m
settled on the following if I ever want queue/stack semantics :
class Queue
def initialize
@buffer = []
end
def enqueue(element)
@buffer.unshift(element)
end
def dequeue
@buffer.pop
end
def empty?
@buffer.empty?
end
end
But, there’s already a Queue implementation in ruby core, so I would
use that, although that class is aimed at synchronizing threads so I
might implement a simple queue like the above at some point if I need
simple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array’s push and pop :-). Or just use an array if the fact of
having more methods than a stack is not a problem :-).
Jesus.
On 24-Oct-07, at 5:03 AM, Thufir wrote:
did I debug it the first time? Don’t ask.
Could this lead to a security problem down the road?
I don’t think so in the cases I mentioned. The objects in front of
the array are not accessible using Ruby. I suppose you could write
some C code easily enough to get at them.
Cheers,
Bob
-Thufir
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On 24-Oct-07, at 6:30 AM, Todd B. wrote:
attention. I don’t really have a problem with the terminology, or the
behavior of the methods pop/push/shift/unshift. In fact, the
shift/unshift methods were two of many things that attracted me to
Ruby. I know they exist in other languages, but I haven’t experienced
the others in depth yet.
I agree with you. I don’t have any problem with the terminology, and
I certainly appreciate the implementation. The only problem I have is
the two specific deficiencies in the optimisation of un/shift. With
some release after 1.8.5 this should be completely resolved, it is
much better in 1.8.5 than in 1.8.4 I think.
Cheers,
Bob
Todd
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On 10/24/07, Jesús Gabriel y Galán [email protected] wrote:
@buffer.popsimple queue semantics.
I would corresponding class for Stack, with push/pop being delegated
to array’s push and pop :-). Or just use an array if the fact of
having more methods than a stack is not a problem :-).Jesus.
You want to – as mentioned elsewhere in this thread – push it in the
front and take it out the back. Interesting. I guess it all comes
down to what direction you want to go. I like to see the procession
moving towards the zeroth position and not to some indexth position.
If I was going to queue, it would be more like…
class Queue
def initialize enum
@list = enum if enum.is_a? Enumerable
end
def enqueue object
@list << object
#haven’t looked at C code, but
#I think this is the same as #push
end
def dequeue
@list.shift
end
def cut_in_line object
@list.unshift object
end
def bouncer_removes_last_guy
@list.pop
end
end
Todd
On 24-Oct-07, at 9:03 AM, Todd B. wrote:
def dequeue
@list.shift
end
Save yourself some grief, do it this way:
def dequeue
tmp = @list[0]
@list[0] = nil
@list.shift
tmp
end
Cheers,
Bob
Bob H. – tumblelog at http://
www.recursive.ca/so/
Recursive Design Inc. – weblog at http://www.recursive.ca/
hutch
http://www.recursive.ca/ – works on http://www.raconteur.info/
cms-for-static-content/home/
On 10/23/07, Randy K. [email protected] wrote:
that in Ruby you have to lift all the plates off, put the new plate on the
bottom, and then put all the plates back. (Likewise when you want to “pop”
that plate.)
instead of the beginning.)
Get on your feet again, no need to stand on your hands all the time ;).
R.
On 10/24/07, Bob H. [email protected] wrote:
tmp = @list[0]
@list[0] = nil
@list.shift
tmp
endCheers,
Bob
Bob, I can only guess that the grief you are talking about has
something to do with memory management, but I don’t see it.
Can someone explain – with the code above – why tmp does in fact
not take on NilClass? I think it would be good info for newbies.
Todd
On 10/24/07, Todd B. [email protected] wrote:
def dequeue
might implement a simple queue like the above at some point if I need
moving towards the zeroth position and not to some indexth position.
The truth is that I don’t mind in which direction to go, because I
only want queue semantics, and that would be part of an implementation
detail. I changed in my example to unshift/pop because of the
recommendations made above in this thread about not using shift, but
other than that I wouldn’t mind.
Jesus.
On 10/24/07, Todd B. [email protected] wrote:
def dequeue
something to do with memory management, but I don’t see it.Can someone explain – with the code above – why tmp does in fact
not take on NilClass? I think it would be good info for newbies.Todd
Okay, I guess I can answer my own question. Binding is resolved when
an operator like ‘=’ is interpreted, especially with immutable objects
(like Fixnum).
a = 1,2,3
puts a[0].id
#output => 3
b = a
puts b.id
#output => 3
a[0] = 7
puts a[0].id
#output => 15
puts b.id
#output => 3
For the newbies out there, keep this in mind. The name b put on
a[0]'s shoes and kept them on. Somebody correct me if I’m wrong.
Todd
This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.
Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs