This week's book giveaway is in the Clojure forum.
We're giving away four copies of Clojure in Action and have Amit Rathore and Francis Avila on-line!
See this thread for details.
Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Approach to validate objects in list

 
Sachin Jai
Greenhorn
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 10336
Eclipse IDE Hibernate Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"techie techi" please check your private messages.
 
Rajkamal Pillai
Ranch Hand
Posts: 445
1
Java Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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%.
 
Rajkamal Pillai
Ranch Hand
Posts: 445
1
Java Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 14112
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24204
34
Chrome Eclipse IDE Mac OS X
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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).
 
William Brogden
Author and all-around good cowpoke
Rancher
Posts: 13048
6
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The OP mentioned a set of rules. Using a single sorting algorithm would only work for one rule.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 33697
316
Eclipse IDE Java VI Editor
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!
 
Sachin Jai
Greenhorn
Posts: 7
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 14112
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic