aspose file tools*
The moose likes Performance and the fly likes Approach to validate objects in list Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Approach to validate objects in list" Watch "Approach to validate objects in list" New topic
Author

Approach to validate objects in list

Sachin Jai
Greenhorn

Joined: May 05, 2005
Posts: 7
My problem statment is:

1."n" number of objects are stored in an Array list. We do have some limit for value "n". And these need to be cross validated.
2. There are certain set of rules that makes each object unique.
3. Requirement is to validate the list against such rules and throw some exception if validation fails.

My solution:
1. I take first object from the list and compare it against rest of the objects in the list. If validation passes then I remove first object from the list.
2. Repeat step 1 for second object and follow it untill list is empty. If any validation fails I stop in between and throw exception.

My Issue: It takes way too long to finish this process, almost 20 mins for around 3000 objects in collection.
Any other appraoch/method I could use to do this job very quickly?





TIA... Any suggestion appreciated.
[ June 17, 2008: Message edited by: Sachin Jai ]
Paul Sturrock
Bartender

Joined: Apr 14, 2004
Posts: 10336

"techie techi" please check your private messages.


JavaRanch FAQ HowToAskQuestionsOnJavaRanch
Rajkamal Pillai
Ranch Hand

Joined: Mar 02, 2005
Posts: 443
    
    1

Hi,

Can't you perform the validation mechanism when each object is added to the list? I think that could increase the performance based on your set of validation rules.

Cheers,
Raj.
Sachin Jai
Greenhorn

Joined: May 05, 2005
Posts: 7
I guess we can't do that reason for that is that our data is coming from CSV file through a CSV parser. The CSV parser returns List of objects.
Paul Fairhurst
Greenhorn

Joined: Jun 12, 2008
Posts: 7
You could stream the objects ONCE through a chain of responsibility design pattern: a sequential panel of judging classes, each takes responsibility for one rule and, as necessary, stores previous values or hashes to prove uniqueness. Much of what you decide really has to do with the way the rules can be optimised to suit a single pass approach traded against storing of previous values.

Alternatively, you could use multiple threads. Consider that the objects are unchanging, then two threads can access the list without locking. One from the top doing the top half and one from the bottom doing the bottom half - both performing all combinations of pairs, like you did, like a bubble sort. Very little overlap, and all 'reads'. That should perform better on a multi-core machine, depending on the storage performance, up to say 150%.


<a href="http://www.infoQuanta.com" target="_blank" rel="nofollow">infoQuanta</a> - parallel java programming made simple
Rajkamal Pillai
Ranch Hand

Joined: Mar 02, 2005
Posts: 443
    
    1

Hi,

Are you saying that you don't have control on the objects generated by the CSV parser? I was thinking of having the Objects generated implement the java.util.Comparable interface and using the compareTo() method to implement the rules for your application. Otherwise I am not able to think of anything useful.

Cheers,
Raj.
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Well, for an arbitrary set of rules for uniqueness, it seems to me that you will need to compare every object with each other - there is no way around this. That is, for n objects, you will have O(n^2) comparisons, no matter what exactly your algorithm looks like.

So I see basically two options for you:

- decrease the number of comparisons needed to be made, by making use of some specific properties of the rules you need to use, or

- improve the performance of the comparisons themselve.


The soul is dyed the color of its thoughts. Think only on those things that are in line with your principles and can bear the light of day. The content of your character is your choice. Day by day, what you do is who you become. Your integrity is your destiny - it is the light that guides your way. - Heraclitus
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

Originally posted by Ilja Preuss:
That is, for n objects, you will have O(n^2) comparisons, no matter what exactly your algorithm looks like.


I wouldn't say that; if there's any way to define an ordering consistent with the rules (surely there's some field you can sort on?) then you can sort the list, then just compare each item with its neighbors; that's O(n ln n).


[Jess in Action][AskingGoodQuestions]
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12835
    
    5
Why not create a hashcode() and equals() method for the objects and store them in a Set in addition to the ArrayList? Then the contains() method will let you know if the object is not unique.

Bill
Paul Fairhurst
Greenhorn

Joined: Jun 12, 2008
Posts: 7
The OP mentioned a set of rules. Using a single sorting algorithm would only work for one rule.
Jeanne Boyarsky
author & internet detective
Marshal

Joined: May 26, 2003
Posts: 31079
    
163

Originally posted by Paul Fairhurst:
The OP mentioned a set of rules. Using a single sorting algorithm would only work for one rule.

Right. Luckily Collections.sort allows you to pass in a custom comparator which can use any sorting rules you want!


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Sachin Jai
Greenhorn

Joined: May 05, 2005
Posts: 7
Thanks to all for reply...

I am not too sure that If the sorting could be used for my validation.
My requirement is to compare object against all other objects based on some rules like: if Obj1.val1 == Obj2.val1 then check Obj1.val2 < Obj1.val2
and there are some more rules like this.
[ June 17, 2008: Message edited by: Sachin Jai ]
Ilja Preuss
author
Sheriff

Joined: Jul 11, 2001
Posts: 14112
Originally posted by Ernest Friedman-Hill:

I wouldn't say that; if there's any way to define an ordering consistent with the rules (surely there's some field you can sort on?) then you can sort the list, then just compare each item with its neighbors; that's O(n ln n).


Well, yes - that's exactly one example of "decrease the number of comparisons needed to be made, by making use of some specific properties of the rules you need to use". For an *arbitrary* set of rules, that's just not possible, as far as I can tell.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Approach to validate objects in list