Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Create a custom stack class with a swap method?

  1. Dec 20, 2015 #1

    rcgldr

    User Avatar
    Homework Helper

    I've written a poly phase merge sort using 3 "stacks" in C++. The key part of the logic is to merge from containers A and B into container C. It's expected for A or B to go empty with lots of data remaining on B or A. To deal with this, when A or B go empty, the empty container is swapped with C and the merge continues, until A and B go empty at the same time, in which case the sort is done. Without the swapping, then I'd have to code for all 6 possible permutations of A, B, C.

    For the C++ program, since in this case the stacks have a maximum size, each stack is simply an array with a stack pointer. Push is *--stack_pointer = value, pop is value = *stack_pointer++. This is quick, when sorting 16 million pseudo random 32 bit integers in 64 bit mode (16 registers) on my system, the poly phase merge sort using 3 "stacks" (a programming challenge) takes 1.6 seconds, versus 1.5 seconds for a 2 way merge sort, 1.4 seconds for a 4 way merge sort, or 1.45 seconds for quick sort.

    The programming challenge here is to emulate poly phase merge sort on 3 tape drives, where data is written forwards and read backwards, which is emulated using stacks (or anything LIFO).

    One alternative would be to use a linked list for the stack, which should work in Java, since a dummy / sentinal node's next pointer could be changed to point to any list, providing a means to swap "pointers" to lists. This would be slower, but Java apparently isn't meant for performance.
     
    Last edited: Dec 21, 2015
  2. jcsd
  3. Dec 20, 2015 #2

    jedishrfu

    Staff: Mentor

    If C is the output of the sort why are you bringing it back into the mix?

    I would think you'd have a test if one queu was empty to return a maximal key so that the other queue would be selected and its elements added to C or a specialized method to take all of the remaining queue and add it to C.

    A linked list strategy would probably speed things up as once one queue is empty the remaining one is simply linked to the end of C.
     
  4. Dec 21, 2015 #3

    rcgldr

    User Avatar
    Homework Helper

    This came up at another forum, asking about implementing an efficient sort using only 3 "stacks" and some local variables, unfortunately in Java for this particular question, although the 3 stack sort question has come up before for other languages.. I don't have Java, so I coded up a few examples in C++, wrongly assuming it had something equivalent to an intelligent swap like C++ std::swap for vectors or containers in general.

    Using a poly phase merge sort only needs to distribute some data from A to B and C at the start, and afterwards, it only merges data, without any copies. It's complicated by the fact that since stacks are used, the merge operations alternate between ascending and desceding, and the runs sizes in A, B, C can either increment or decrement at some point in A or B or C (only one of them will have an increment / decrement point at a time).

    A poly phase merge sort is an "unbalanced" sort. It starts off merging A and B into C, but if A goes empty, it switches to merging B and C into A. Then B should go empty next, in which case it continues merging C and A into B. Wiki article:

    http://en.wikipedia.org/wiki/Polyphase_merge_sort

    For C++, I'm using an array with a stack like pointer into the array. For example an array of size N named A[]. element *Stack_Pointer is initialized to A + N (== &A[N]). As mentioned before, push(value) == *--stack_pointer = value. Pop() returns *stack_pointer++, these are fast operations but this strategy only works when the maximum size of the stack is known in advance. For variable size stack, stack could work from the start of an array, which could then be reallocated if it needed to grow. In this case push(value) = *stack_pointer++ = value. pop returns *--stack_pointer, and peek returns *(stack_pointer - 1).
     
  5. Dec 21, 2015 #4

    Mark44

    Staff: Mentor

    This thread is tagged as being about Java. Is that a mistake?
     
  6. Dec 21, 2015 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I believe he's asking how to implement a swap function in Java. You can't.

    You can come close:
    Code (Java):

    /**
    * Not really a swap function, but when used right, it acts as one.
    * Usage: y = pseudo_swap_function_if_called_correctly (x, x=y);
    */

    <T> pseudo_swap_function_if_called_correctly (T a, T b) {
        return a;
    }
     
    This is massively devious and prone to error. I would never call that function swap because that is not what it does. It simply returns the first argument. The second argument is dropped on the bit floor.
     
  7. Dec 21, 2015 #6

    rcgldr

    User Avatar
    Homework Helper

    The tag is correct, it should be Java. Being new to Java, I didn't realize that Java arrays were handled as references, Java int a[] is similar to C / C++ int *a. Here's an example Java stack class that includes a swap function member:

    Code (Text):

    class fstack{                               // fast fixed size stack
        int []ar;                               // array
        int sz;                                 // size
        int sp;                                 // stack pointer
        public dstack(int sz){                  // constructor with size
            this.ar = new int[sz];
            this.sz = sz;
            this.sp = sz;
        }
        public void push(int d){
            this.ar[--sp] = d;
        }
        public int pop(){
            return this.ar[sp++];
        }
        public int peek(){
            return this.ar[sp];
        }
        public boolean empty(){
            return sp == sz;
        }
        public int size(){
            return sz-sp;
        }
        public void swap(dstack othr){
            int []tempar = othr.ar;
            int tempsz = othr.sz;
            int tempsp = othr.sp;
            othr.ar = this.ar;
            othr.sz = this.sz;
            othr.sp = this.sp;
            this.ar = tempar;
            this.sz = tempsz;
            this.sp = tempsp;
        }
    }
     
     
    Last edited: Dec 23, 2015
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Create a custom stack class with a swap method?
  1. Creating a class (Replies: 2)

Loading...