Solved

Is there a proper/best java structure to do 'last n things'

Posted on 2014-01-25
9
174 Views
Last Modified: 2014-05-10
For a particular task I am working on, I want to keep track of the 'last 5 things' , where a thing is added when triggered.  Then, I will be comparing a difference between the 1st and last thing, as well as averaging something from each of the 5 things.

I would really love if there was a structure that let me just add a thing, and remove the first thing, so that the 6th thing added, then first removed, becomes an ordered arrangement of 5 things, a sliding window...


My existing solution looks like this, where i have an Array of "mythings".  I'm not interested in examining a difference if there are fewer than 5 things listed, just in pushing the old things out of the list as new ones are added once there are 5.

Is there a better structure to pull off this job, or better code (obviously a loop to shift the array items would be better than what is listed, anything else better?)   This same approach will be used elsewhere for looking at 'the last 30 things' and 'the last 100 things' at some point, so a solution that scales that way is desirable.

I dont believe that I nailed this one on my first shot at it, and would like to think some structure works better than a simple array with this code:

		public void addToListy(Thingy thing){
		int j
		if (listy.length <4){
			j=listy.length;
			listy[j]=thing;
		} else {
			listy[0]=listy[1];
			listy[1]=listy[2];
			listy[2]=listy[3];
			listy[3]=listy[4];
			listy[4]=thing;
		}

Open in new window

0
Comment
Question by:GPrentice00
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 4
  • 4
9 Comments
 
LVL 28

Expert Comment

by:dpearson
ID: 39808987
A Deque (or double ended queue) might meet your needs:
http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

Deque<Thingy> listy = new ArrayDeque<Thingy>() ;

Then the code becomes:

int keep = 5 ;
listy.addFirst(thing) ;

if (listy.size() > keep)
    listy.removeLast() ;

Doug
0
 
LVL 86

Expert Comment

by:CEHJ
ID: 39809018
Sounds more like you need a circular List or Queue
0
 
LVL 6

Author Comment

by:GPrentice00
ID: 39809192
I think your size>keep part of the pseudocode idea might be backwards, if i understand what im reading elsewhere on Deque... If I understand this correctly, I would still be responsible for deleting the one end after adding to the other, but in using an array, does this mean that after thousands and thousands of calls, my actual indexes would be ie 5300 to 5304.  Or would it reinternalize to 0-n after deleting the first?  I dont actually need the indexes for doing a first-last comparison using the getfirst/getlast concepts, and i imagine an interator would be the way to traverse it to average the one set of data from the things...  but is an iterator faster or better than being able to for-loop from 0 to 4 every time ?? Could i hit a point where the actual indices grow to a out of control scenario and overflow regardless of choosing an indexless iterator process, just the underlaying structure itself not supporting adding one to the index anymore..



I tried to look at circular lists just now, but I dont see a connection to my example after a few minutes of hitting pages, or rather, they appear very involved codewise to keep track of the structure and im not sure i see how to make it a fixed size to otherwise just keep going around in otherwise some self-attending way of having an add(thing) that would just overwrite existing.   I will try looking some more, as it does seem possible to throw out an index incriment issue that might be in the deque array.  But thinking to a future application of this similar structure, I would at one point require the 'middle' element of an odd-number sized set.  With the arrays, I can jump to the middle directly if i new the endpoints - currently, by shuffling the array over, it would always be index 2 for me... or index 24 or index 49 etc...  but to find the middle would require traversing half of the list if I understand correctly.  and yes, thats not a qualification I wrote in the question, but, its a releated tie-to to help me try to connect an understanding to the structures, even though im still not really seeing a circular list example I can follow all the way with certainty...
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 28

Expert Comment

by:dpearson
ID: 39809328
I don't think the test is backwards.  It says "Once the deque has more than 5 members, drop the last one".

The indexes of the items in the queue won't grow.  In fact a queue is designed so you usually only get the items from the front or the back.

If you want to walk through all of the items you may be better off with just an ArrayList, which would be pretty similar code:

List<Thingy> listy = new ArrayList<Thingy>() ;

Then the code becomes:

int keep = 5 ;
listy.add(0, thing) ;   // Add to front of the list

if (listy.size() > keep)
    listy.remove(keep) ; // Remove the 5th item if the list gets too big

Then you can do things like:

Thingy first = listy.get(0) ;

or

// Iterate through the whole list - however long it currently is
for (Thingy thing : listy) {
    System.out.println(thing) ;
}

or

// More old school iterating by index
for (int i = 0 ;  i < listy.size() ; i++) {
     System.out.println(listy.get(i)) ;
}

Doug
0
 
LVL 6

Author Comment

by:GPrentice00
ID: 39809341
Perhaps our definition of first and last changes...

My definition of last is the new customer who walks into the bank and stands in line.  The first customer in line moves to the open teller.  The next customer in the bank becomes the new 'last'

I want to track the 5 "last" customers who walk through the door.
0
 
LVL 6

Author Comment

by:GPrentice00
ID: 39809342
thats why this is an issue, otherwise, a simple array would just work and keep replacing #5 for me, I would figure.  How is this dfiferent
0
 
LVL 28

Accepted Solution

by:
dpearson earned 500 total points
ID: 39809350
It's quite different from an array where you replace the 5th element.

Let's make this concrete.  Let's assume it's a list of strings and they come in order A,B,C,D,E,F,G,H,I,J,K,L,M, etc.

With the array list the algorithm is
"add to the front of the list"
"if list too big, remove end of list"

So we get:
{ A }
{ B, A }            <-- added to front, so rest of list automatically "moves down"
{ C, B, A }
{ D, C, B, A }
{ E, D, C, B, A }
{ F, E, D, C, B }  <-- last 5 customers once F enters
{ G, F, E, D, C } <-- last 5 customers once G enters

If instead we just used an array and replace the 5th element we get:
{ A }
{ A, B }
{ A, B, C }
{ A, B, C, D }
{ A, B, C, D, E }
{ A, B, C, D, F } <-- Not the last 5 customers at all
{ A, B, C, D, G }

Is this making better sense now?

Doug
0
 
LVL 6

Author Comment

by:GPrentice00
ID: 39809359
I see - if i pretend up is down, and left is right, then what is really last, would be the first.

I will try to shift my perspective and code this, see if it works.
0
 
LVL 28

Expert Comment

by:dpearson
ID: 39809392
Haha - yes the list is always showing "last 5 most recently seen in order" - which indeed means the most recent is first in the list, not last.
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
In this post we will learn how to make Android Gesture Tutorial and give different functionality whenever a user Touch or Scroll android screen.
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …

717 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question