Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

How to create a two dimensional queue in Perl

by meena (Novice)
on Aug 04, 2013 at 07:39 UTC ( [id://1047772]=perlquestion: print w/replies, xml ) Need Help??

meena has asked for the wisdom of the Perl Monks concerning the following question:

How to create a two dimensional queue in Perl

Replies are listed 'Best First'.
Re: How to create a two dimensional queue in Perl
by BrowserUk (Patriarch) on Aug 04, 2013 at 10:11 UTC

    A 2-dimensional queue? That would be "a crowd".

    If you create a crowd, we'll probably need to send in riot control.


    With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      My head is flooding with visions of MCP in TRON, but I can't find the right way to present the joke. So I feed you this protoplasmic goo and hope the joke carries.

      /me needs sleep
      or coffee.

Re: How to create a two dimensional queue in Perl
by Laurent_R (Canon) on Aug 04, 2013 at 08:37 UTC

    A simple queue can just be an array in which you add new items at the end of the array with the push operator, and remove oldest elements from the front with the shift operator (you could also use pop and unshift, but it seems less natural and it is probably slower).

    For a "two dimensional queue", although your description seems to be far from clear in my eyes at least (you don't specify how the items should be managed), you could in principle use an array of arrays (AoA). Or maybe what you really need is just several queues working in parallel (with different types of items). Or, if you really think of a queue within the queue, then you should probably just flatten the whole thing into a single queue, which will work just the same way.

    But the very idea of a two dimensional queue seems to somewhat defeat or contradict the essential idea of a queue, i.e. a FIFO data structure in which the oldest element is removed first.

    This tends to sound as a case of XY Problem. Please state what you are actually trying to do, rather than asking how to implement what you think is the solution to your problem.

      I want to write a state machine using queues Meaning :Each state has two or more operations After each operation is there that operation from the given state should be removed ;and only after all operations are done ,the state should be dequeued from the queuue and we should move forward to the next state

        Assuming your question is not related to threads (since nothing of what you said in this ... thread relates to threads), my understanding is that you need a queue of items, in which each item is itself a list of successive actions to be performed together one after the other when a certain state is reached. This is not really a queue of queues, but rather a queue of lists.

        If such is the case, then an AoA is probably what you need. Something like this:

        my @queue = ( [$action1, $action2, $action3], [$action4, $action1, $ac +tion3], ...); # or possibly; my @queue = ( [1, 2, 3], [4, 1, 3]); # where [1, 2, 3] is a reference to an array of subscripts on an array + of actions defined somewhere else.

        To add an item to the queue:

        push @queue, [7, 3, 0, 9];

        Which results in the following data structure:

        0 ARRAY(0x80359f90) 0 1 1 2 2 3 1 ARRAY(0x8035a050) 0 4 1 1 2 3 2 ARRAY(0x803561e8) 0 7 1 3 2 0 3 9

        To retrieve and remove a list of actions from the queue:

        my $action_ref = shift @queue;

        Now, $action_ref is [1, 2, 3], i.e. a reference to an anonymous array containing (1, 2, 3). You can now retrieve the actions one after the other from that anonymous array. For example, if you want to list the actions you've just dequeued:

         print $_, " - " foreach @$action_ref; # prints: 1 - 2 - 3 -

        Is this what you need?

        Sounds like you want to just use Thread::Queue objects inside a Thread::Queue, dequeue from the parent, then work on the child. A potential problem with this is that you can't modify the child queue in place (except by peeking) and would potentially have to keep a reference to it separate from the parent queue.

        Alternatively you could use an actual state machine implementation from CPAN.
        I want to write a state machine using queues Meaning :Each state has two or more operations After each operation is there that operation from the given state should be removed ;and only after all operations are done ,the state should be dequeued from the queuue and we should move forward to the next state

        Let's visualise that:

        [ state1: [ op1; op2; op3 ] ] [ state2: [ op1; op2; op3; op4 ] ] [ state3: [ op1; op2; op3; op4; op5; op6 ] ] [ state4: [ op1; op2; op3; op4; op5 ] ] [ state5: [ op1; op2 ] ] [ state6: [ op1; op2; op3; op4 ] ] [ state7: [ op1; op2; op3 ] ] [ state8: [ op1; op2; op3; op4 ] ] [ state9: [ op1; op2 ] ]

        Will all of state1 (or state9) operations be completed before any of state2 (state8)?

        If so, just enqueue() a bunch of Thread::Queue objects onto a Thread::Queue. Dequeue() them one at a time and dequeue() each operation one at a time and process it. But that isn't a state machine, it's just a pre-serialised series of operations.

        If however, it is your intention that the first operation of any of states 1 thru 9 can be processed in any order -- which would make it a state machine -- then you aren't using a queue for the outer level; you are using a random access data structure. Ie. an array.

        So, use an array of queues rather than abusing a queue of queues.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
        I think maybe we should step back one more step than that. What precisely is the state machine meant to do? Perhaps some sample input and output would help us understand better. As BrowserUK says, your description seems to imply just an ordered series of actions, and I think that's not what you mean.

        Do the state transitions add more items to the queues or something like that? Otherwise I can't see why a...oh, WAIT.

        Is the idea to have a top-level set of states (the "top"), with each state having a "queue" (actually a set) of possible "next" states, and this needs to possibly be variable - or each state is set up to have multiple actions, to be used one-by-one? So the real idea is to have a list of possible current states, with each possible next state linked to it, and one or more actions per each state? More like the right idea?

        Ah, that makes sense.

        How to "dimensionalize" your queue greatly depends on how the queue is implemented.

        A simple queue can be a normal array -- that is to say, an array of scalars:

        #!/usr/bin/perl -w use strict; my @MyQueue = (); { # Add items to queue push @MyQueue, 'First Entry'; push @MyQueue, 'Second Entry'; # Consume from queue (FIFO) my $nextEntry = shift @MyQueue; }

        To dimensionalize this, you could make each entry in the queue an array instead of a scalar -- look up "Array Of Arrays" or AoA. Thought I saw links already embedded in other answers on this thread.

        If the queue is a hash instead of an array, syntax for use of the queue is simpler, but now you have to manage the hash keys to ensure uniqueness and sequence (presumably FIFO).

        I suppose you could just use a two-dimensional array, but I think doing so you'd lose the very attractive simplicity of push/shift. I'd probably just use a hash at that point.

        If I had the privilege of building the two-dimensional queue manager from scratch, the question I'd find most pertinent is whether or not the calling program would benefit from receiving its state steps in an array.

        If yes, I'd do the extra work to use AoA.
        If no, I'd go with a hash and manage the keys myself.
        Reason:I find reading the hash syntax easier.
        (Yes, all things considered, that's fairly arbitrary.)

        Good luck!

Re: How to create a two dimensional queue in Perl
by Corion (Patriarch) on Aug 04, 2013 at 07:41 UTC

    What is a two-dimensional queue?

    Also see Thread::Queue for a one-dimensional queue. Maybe if you use enough of them, you can get a two-dimensional queue.

      Each queue element should have two elements which can individually be dequeued Like a queue within a queue
        Each queue element should have two elements which can individually be dequeued Like a queue within a queue

        If "each queue element contains 2 elements that can be individually dequeued"; what is the difference between a your 2D-queue containing one, two-element element; and a normal queue containing two, single-element elements pushed by the same producer at the same time?


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
        I'm assuming that these aren't priority queues - just items in whatever order they've been added into the queues. So here's how to go about it.
        # Start with an empty master queue. my @master; # Build a sub queue. Note that this is a array *reference*. my $subqueue = [ 1, 2, 3, 4]; # add it to the queue. push() puts it at the tail of the queue. push @master, $subqueue; # Now let's create a couple more sub queues and add them. push @master, [5, 6, 7]; # Some high-priority-items we'll stick at the front of the master: unshift @master, [-1, 0]; # Now let's run the queue. We look at the master. If there are no item +s remaining, # the queue is empty. Otherwise, process the leading sub queue. while (@master) { # If the leading sub queue is empty, discard it, and start over with + the rest of # the (now possibly empty) master queue. while ( @{ $master[0] } ) { my $item = shift @{ $master[0] }; print $item, " "; } # We arrive here when the sub queue is empty. Discard the empty sub +queue. shift @master; # Move to the next line so we can see we switched sub queues. print "\n" } print "\n";
        The output will be
        -1 0 1 2 3 4 5 6 7
        Obviously this is a toy program, but it serves to demonstrate the basic array operations and tests that are needed to manage a queue of queues. More complex operations (like priority queuing, etc.) are left as an exercise. (I'd probably switch the plain scalar values for anonymous hashes, one item of which is a 'priority' field that you can sort the array of hashes on, and the other a 'value' which will be either the scalar value you want in the node (on the sub queues) or a reference to a subqueue (for the master).)

        And of course this isn't a class; that'd be a nice thing to do as well.

Re: How to create a two dimensional queue in Perl
by rjt (Curate) on Aug 04, 2013 at 09:53 UTC

    Based on your previous questions1, you are probably talking about threads. As Corion pointed out, Thread::Queue provides queue functionality to threads. According to its documentation (reformatted for brevity):

    Any data types supported by threads::shared can be passed via queues: a) Ordinary scalars, b) Array refs, c) Hash refs, d) Scalar refs, e) Objects based on the above. Ordinary scalars are added to queues as they are.

    If not already thread-shared, the other complex data types will be cloned (recursively, if needed, …

    Your question here is very vague (please read How do I post a question effectively?), but taking your meaning of "two dimensional queues" as literally as I can, I believe a simple anonymous array ref (constructed with  [ ... ]) would work for you. Something like this:

    use Thread::Queue; my $q = Thread::Queue->new; # Later, in producer thread(s) ($first and $second # represent the 2 dimensional tuple you wish to enqueue) $q->enqueue( [ $first, $second ] ); # Anonymous array ref # Later still, to signal the end of all elements: $q->enqueue(undef); # In the consumer thread(s): while (defined (my $ref = $q->dequeue)) { my ($first, $second) = @$ref; # Dereference array # ... Process $first and $second }

    That's pretty much the pattern. You should be able to easily adapt it to your needs. If not, write up a better description of what you need, and we'll help you from there.

    ____________
    1. meena's recent threads: Create your own signal in Perl, Alarm In Perl

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1047772]
Approved by moritz
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others browsing the Monastery: (3)
As of 2024-03-19 04:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found