• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Approach to validate objects in list

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ]
 
Bartender
Posts: 10336
Hibernate Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"techie techi" please check your private messages.
 
Ranch Hand
Posts: 479
1
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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: 479
1
IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
author and iconoclast
Posts: 24207
46
Mac OS X Eclipse IDE Chrome
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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).
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The OP mentioned a set of rules. Using a single sorting algorithm would only work for one rule.
 
author & internet detective
Posts: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
reply
    Bookmark Topic Watch Topic
  • New Topic