Solved

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

Posted on 2014-01-25
9
160 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
  • 4
  • 4
9 Comments
 
LVL 26

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
 
LVL 26

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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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 26

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 26

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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
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:
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.

760 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

Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!

Get 1:1 Help Now