?
Solved

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

Posted on 2014-01-25
9
Medium Priority
?
178 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
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 2000 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

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!

Question has a verified solution.

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

In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
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 how to read error messages and identify possible mistakes that could cause hours of frustration. Coding is as much about debugging your code as it is about writing it. Define Error Message: Line Numbers: Type of Error: Break Down…
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
Suggested Courses
Course of the Month13 days, 6 hours left to enroll

801 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