CODEWITHSUNDEEP
javaperformancearraylist
user3700608
user3700608

Reputation: 13

Performance of priority queue using an ArrayList

I'm currently working on a minimum priority queue that keeps itself sorted as items are added. The suggested implementation has new items added to the end of a sorted ArrayList, and then working back through the list to find the items correct location. So it swaps with each previous element in the list until the added item is in order.

The implementation I used before this method was suggested involved comparing through the sorted list, marking the index where the item was to be inserted and then using Java's add(int index, Object O) method instead of just adding to the end.

I'm trying to understand the performance difference between the 2. I understand that if I insert, all of the trailing indexes will have to be corrected (which is taken care of by the class method). But is this really less efficient than swapping back through the list?

Thanks in advance for any explanations

Upvotes: 1

Views: 2449

Answers (1)

awksp
awksp

Reputation: 11867

As stated, the two choices will both run in O(n) time (I think). However, the second option (i.e. your initial implementation) will likely have better constant factors due to the fact that moving a group of elements all at once can be (and probably will be) more efficient than moving elements one at a time, especially if you have to move large groups of elements. So I would say that your initial implementation was more efficient, unless your final insertion point is almost always near the end of the array, at which point the overhead of System.arraycopy() may dominate the time needed to do the actual work -- but not by much.

I suppose you can think of the two situations as approximately comparing a single iteration of bubblesort (suggested implementation) and insertion sort (initial implementation). Both have the same time complexity, but a single iteration of insertion sort will almost always (or maybe always?) run faster due to fewer operations.

Take this for an example (assuming resizable arrays for simplicity):

int[] a = new int[] {1, 2, 4, 5};

and say you want to insert 3.

Your initial implementation would go something like this:

  1. Find the index to insert at. 3 comparisons to find index == 2.
  2. Shift elements at indices > 2. 2 operations: Shift 5 over one place, and shift 4 over one place. (this might be one operation, depending on how System.arraycopy() is implemented). Result is {1, 2, 0, 4, 5}
  3. Insert element. 1 Operation. Final result is {1, 2, 3, 4, 5}.

Total: 3 comparisons, 3 operations.

Your new implementation would go something like this:

  1. Insert element at end. 1 operation. Result is {1, 2, 4, 5, 3}.
  2. Compare to see if need to swap. 1 comparison. Swap needed.
  3. Swap. 3 operations: Assign 5 to temp variable, assign 3 to index 3, assign temp variable to index 4. Result is {1, 2, 4, 3, 5}
  4. Compare to see if need to swap. 1 comparison. Swap needed.
  5. Swap. 3 operations: Assign 4 to temp variable, assign 3 to index 2, assign temp variable to index 3. Result is {1, 2, 3, 4, 5}.
  6. Compare to see if need to swap. 1 comparison. No swap needed. Done.

Total: 3 comparisons, 7 operations.

As a side note, you would probably be better off using binary search to find the insertion point instead of a straight linear search.

Upvotes: 1

Related Questions