Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Object iterations and string comparisons  RSS feed

 
Steve Wood
Ranch Hand
Posts: 137
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi (me again),

Are their any good techniques I should be aware of for iterating through objects?

Basically, this is what we're doing:
1. We have a list containing a number of objects
2. Each object has a unique identifier - which is a string
3. We want to iterate through the list of objects to find the one with a particular identifier

So, it looks something like this:

for (Iterator i = myObjects.iterator(); i.hasNext()
{
MyObject myObject = (MyObject)i.next();

if (myObject.getID().equals(myID))
{
return myObject;
}
}

Any help is much appreciated.

Cheers,

Steve
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That'a about it for items in a List. In Java 5, you can write this as



But note that if there's no actual need for your MyObjects to be kept in a particular order, then a List isn't necessarily the best collection type to use. If you don't actually need them in order, but often need to find them by Id, then you should consider keeping them in a Map using the Id as the key; then this code reduces (in Java 5, where you can omit the cast) to

return myObjects.get(myId);

and it's considerably faster.
 
Steve Wood
Ranch Hand
Posts: 137
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Ernest,

We're sticking to 1.4 compatibility at the moment, though the idea of putting everything in a Map is tempting. I've had a quick look around, and I think the major issue is that we need to extract different properties from the object depending on which method is looking - so it's not just the string identifier as I previously indicated.

So, in the iterator, we might test the ID and also test another property to check it's correct.

We could perhaps switch between Maps and Lists depending on the purpose of the look-up, but that makes my head hurt!

Cheers,

Steve
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Steve - if there's more than one property you want to look things up by, you may want to simply use multiple Maps - each one using a different type key. Whenever you add a new entry, you need to add it to all the Maps (using the appropriate key). Same for any removals. If this requires too much memory, or if it becomes too complicated, then you may instead want to use a database and use SQL for the different types of queries you need.
 
Ilja Preuss
author
Sheriff
Posts: 14112
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Or you just stay with the "iterating over the list" solution - it's straightforward and should give acceptable performance for collections of up to a few thousand objects or something.

If your logic for deciding whether you've found the right object becomes more complicated, you might want to use the Interpreter pattern.
 
Virag Saksena
Ranch Hand
Posts: 71
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Your list iteration is O(n), so it is going to become a bottleneck as the number of objects in the list increase.

Few suggestions ...
#1. Use hashmaps -- they are an implementation of map available in 1.4
#2. The same object will store your multiple properties, and once you have retrieved the object using

you can extract the property you need from the object, and you don't need multiple hash maps.
#3. I hope your properties are not serialized in a string, but stored as fields in the object

Of course if you have a significantly large amount of data, storing it in database will be better, as an index lookup using the database should not be more than a few ms, and it at O(log n) it scales quite well.
 
Steve Wood
Ranch Hand
Posts: 137
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks guys,

That's really helpful - a number of strategies to explore then!

Cheers,

Steve
 
Pratik Lohia
Ranch Hand
Posts: 88
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Try and avoid using Iterators... The hasNext() method has a cost associated with it.
Use for loop instead to iterate through your list. For larger data in the list, the performance with for loop is much faster and as the data grows, the difference becomes more noticable
 
Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by PRATIK LOHIA:
Try and avoid using Iterators... The hasNext() method has a cost associated with it.
Use for loop instead to iterate through your list. For larger data in the list, the performance with for loop is much faster and as the data grows, the difference becomes more noticable


The overhead of just calling a method is negligible; let's not spread that sort of groundless fear.

The cost associated with calling "hasNext" depends, of course, on the implementation of the particular list. But for an ArrayList, it compares two integer member variables. For LinkedList, it looks at a member variable in one object reference and compares it to null. In both cases, this cost is vanishingly small -- and, of course, is not proportional to the size of the list, as your message seems to imply it is.

Finally, as has been discussed many times on the Ranch, using List.get() in a for loop can either be very slightly faster (for an ArrayList) or vastly slower (for a LinkedList) than using Iterator. You most certainly should not "avoid using Iterators." What you should do is understand the issues associated with using different kinds of List, and do the appropriate thing in each case. In the general case, your best performance bet is, actually, to use Iterator.
 
u johansson
Ranch Hand
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
To be a successful programmer you need to know the basic data structures. A list isn't a tree isn't a hash table etcetera.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!