Iterate two lists and find matches
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
1
down vote
favorite
I have 2 lists with varying length. Both lists contain data which has to be matched with entries from the other list. Currently I am iterating both lists with a nested for-loop.
List<MyClass1> list2 = myClass1dao.findUnmatchedEntries();
List<MyClass2> list1 = myClass2dao.findUnmatchedEntries();
for (MyClass2 list1entry : list1)
for (MyClass1 list2entry : list2)
if (list1entry.getName().equals(list2entry.getName())
&& list1entry.getID().equals(list2entry.getID()))
//update entries
myClass2dao.update(list1entry);
myClass1dao.update(list2entry);
break;
I know that this takes exponentially longer the more elements each list has.
So my question is, how can this code be improved?
Note: I am on a java 7 code base so answers to java 7 are preferred, but java 8 is okay as well
java iteration
asked Jan 26 at 7:42
XtremeBaumer
1337
 |Â
show 6 more comments
up vote
1
down vote
favorite
I have 2 lists with varying length. Both lists contain data which has to be matched with entries from the other list. Currently I am iterating both lists with a nested for-loop.
List<MyClass1> list2 = myClass1dao.findUnmatchedEntries();
List<MyClass2> list1 = myClass2dao.findUnmatchedEntries();
for (MyClass2 list1entry : list1)
for (MyClass1 list2entry : list2)
if (list1entry.getName().equals(list2entry.getName())
&& list1entry.getID().equals(list2entry.getID()))
//update entries
myClass2dao.update(list1entry);
myClass1dao.update(list2entry);
break;
I know that this takes exponentially longer the more elements each list has.
So my question is, how can this code be improved?
Note: I am on a java 7 code base so answers to java 7 are preferred, but java 8 is okay as well
java iteration
asked Jan 26 at 7:42
XtremeBaumer
1337
2
What's the nature of the condition? Does it involve both list elements or is it unrelated?
– chatton
Jan 26 at 7:50
It includes elements from both lists
– XtremeBaumer
Jan 26 at 7:51
If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though
– chatton
Jan 26 at 8:05
@chatton This is sadly not an option. I think I have to iterate both lists like this
– XtremeBaumer
Jan 26 at 8:15
As you are dealing with lists the resulting algorithm complexity will beO(n*m). For better performance compose and return maps fromfindUnmatchedEntries()and use them in your names comparison mechanism. Usenamesas map keys and class (MyClass1 and MyClass2) objects as map values.
– user23908
Jan 26 at 11:10
 |Â
show 6 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have 2 lists with varying length. Both lists contain data which has to be matched with entries from the other list. Currently I am iterating both lists with a nested for-loop.
List<MyClass1> list2 = myClass1dao.findUnmatchedEntries();
List<MyClass2> list1 = myClass2dao.findUnmatchedEntries();
for (MyClass2 list1entry : list1)
for (MyClass1 list2entry : list2)
if (list1entry.getName().equals(list2entry.getName())
&& list1entry.getID().equals(list2entry.getID()))
//update entries
myClass2dao.update(list1entry);
myClass1dao.update(list2entry);
break;
I know that this takes exponentially longer the more elements each list has.
So my question is, how can this code be improved?
Note: I am on a java 7 code base so answers to java 7 are preferred, but java 8 is okay as well
java iteration
asked Jan 26 at 7:42
XtremeBaumer
1337
I have 2 lists with varying length. Both lists contain data which has to be matched with entries from the other list. Currently I am iterating both lists with a nested for-loop.
List<MyClass1> list2 = myClass1dao.findUnmatchedEntries();
List<MyClass2> list1 = myClass2dao.findUnmatchedEntries();
for (MyClass2 list1entry : list1)
for (MyClass1 list2entry : list2)
if (list1entry.getName().equals(list2entry.getName())
&& list1entry.getID().equals(list2entry.getID()))
//update entries
myClass2dao.update(list1entry);
myClass1dao.update(list2entry);
break;
I know that this takes exponentially longer the more elements each list has.
So my question is, how can this code be improved?
Note: I am on a java 7 code base so answers to java 7 are preferred, but java 8 is okay as well
java iteration
asked Jan 26 at 7:42
XtremeBaumer
1337
edited Jan 26 at 11:20
asked Jan 26 at 7:42
XtremeBaumer
1337
asked Jan 26 at 7:42
XtremeBaumer
1337
asked Jan 26 at 7:42
XtremeBaumer
1337
1337
2
What's the nature of the condition? Does it involve both list elements or is it unrelated?
– chatton
Jan 26 at 7:50
It includes elements from both lists
– XtremeBaumer
Jan 26 at 7:51
If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though
– chatton
Jan 26 at 8:05
@chatton This is sadly not an option. I think I have to iterate both lists like this
– XtremeBaumer
Jan 26 at 8:15
As you are dealing with lists the resulting algorithm complexity will beO(n*m). For better performance compose and return maps fromfindUnmatchedEntries()and use them in your names comparison mechanism. Usenamesas map keys and class (MyClass1 and MyClass2) objects as map values.
– user23908
Jan 26 at 11:10
 |Â
show 6 more comments
2
What's the nature of the condition? Does it involve both list elements or is it unrelated?
– chatton
Jan 26 at 7:50
It includes elements from both lists
– XtremeBaumer
Jan 26 at 7:51
If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though
– chatton
Jan 26 at 8:05
@chatton This is sadly not an option. I think I have to iterate both lists like this
– XtremeBaumer
Jan 26 at 8:15
As you are dealing with lists the resulting algorithm complexity will beO(n*m). For better performance compose and return maps fromfindUnmatchedEntries()and use them in your names comparison mechanism. Usenamesas map keys and class (MyClass1 and MyClass2) objects as map values.
– user23908
Jan 26 at 11:10
2
2
What's the nature of the condition? Does it involve both list elements or is it unrelated?
– chatton
Jan 26 at 7:50
What's the nature of the condition? Does it involve both list elements or is it unrelated?
– chatton
Jan 26 at 7:50
It includes elements from both lists
– XtremeBaumer
Jan 26 at 7:51
It includes elements from both lists
– XtremeBaumer
Jan 26 at 7:51
If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though
– chatton
Jan 26 at 8:05
If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though
– chatton
Jan 26 at 8:05
@chatton This is sadly not an option. I think I have to iterate both lists like this
– XtremeBaumer
Jan 26 at 8:15
@chatton This is sadly not an option. I think I have to iterate both lists like this
– XtremeBaumer
Jan 26 at 8:15
As you are dealing with lists the resulting algorithm complexity will be
O(n*m). For better performance compose and return maps from findUnmatchedEntries() and use them in your names comparison mechanism. Use names as map keys and class (MyClass1 and MyClass2) objects as map values.– user23908
Jan 26 at 11:10
As you are dealing with lists the resulting algorithm complexity will be
O(n*m). For better performance compose and return maps from findUnmatchedEntries() and use them in your names comparison mechanism. Use names as map keys and class (MyClass1 and MyClass2) objects as map values.– user23908
Jan 26 at 11:10
 |Â
show 6 more comments
2 Answers
2
active
oldest
votes
up vote
1
down vote
I would strongly consider adding a Comparable abstract class with two implementations (one containing a MyClass1, and the other a MyClass2). At that point you can use all the normal collection framework methods to process this. Alternatively you could transform both sets into something like HashMap<String,HashMap<String,List<MyClassX>>>, then just lookup by the name and id.
Additionally, if the lists are sorted, we could do this much more efficiently, by getting two iterators, then simply getting the next element of the one that is behind at each stage.
answered Jun 26 at 7:17
Ian Martin
113
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
add a comment |Â
up vote
0
down vote
I assume both lists contain object of the same type/class, ie MyClass1 and MyClass2 are not two different classes.
In such a case MyClass can override equals method. Once equals is implemented as stated & you have ensured not to have violated the equals and hashcode contract, you can the use a HashMap.
This can reduce your time complexity.
answered Jan 26 at 15:44
Tanvi Jaywant
1122
1
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
I would strongly consider adding a Comparable abstract class with two implementations (one containing a MyClass1, and the other a MyClass2). At that point you can use all the normal collection framework methods to process this. Alternatively you could transform both sets into something like HashMap<String,HashMap<String,List<MyClassX>>>, then just lookup by the name and id.
Additionally, if the lists are sorted, we could do this much more efficiently, by getting two iterators, then simply getting the next element of the one that is behind at each stage.
answered Jun 26 at 7:17
Ian Martin
113
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
add a comment |Â
up vote
1
down vote
I would strongly consider adding a Comparable abstract class with two implementations (one containing a MyClass1, and the other a MyClass2). At that point you can use all the normal collection framework methods to process this. Alternatively you could transform both sets into something like HashMap<String,HashMap<String,List<MyClassX>>>, then just lookup by the name and id.
Additionally, if the lists are sorted, we could do this much more efficiently, by getting two iterators, then simply getting the next element of the one that is behind at each stage.
answered Jun 26 at 7:17
Ian Martin
113
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
add a comment |Â
up vote
1
down vote
up vote
1
down vote
I would strongly consider adding a Comparable abstract class with two implementations (one containing a MyClass1, and the other a MyClass2). At that point you can use all the normal collection framework methods to process this. Alternatively you could transform both sets into something like HashMap<String,HashMap<String,List<MyClassX>>>, then just lookup by the name and id.
Additionally, if the lists are sorted, we could do this much more efficiently, by getting two iterators, then simply getting the next element of the one that is behind at each stage.
answered Jun 26 at 7:17
Ian Martin
113
I would strongly consider adding a Comparable abstract class with two implementations (one containing a MyClass1, and the other a MyClass2). At that point you can use all the normal collection framework methods to process this. Alternatively you could transform both sets into something like HashMap<String,HashMap<String,List<MyClassX>>>, then just lookup by the name and id.
Additionally, if the lists are sorted, we could do this much more efficiently, by getting two iterators, then simply getting the next element of the one that is behind at each stage.
answered Jun 26 at 7:17
Ian Martin
113
edited Jun 27 at 11:43
answered Jun 26 at 7:17
Ian Martin
113
answered Jun 26 at 7:17
Ian Martin
113
answered Jun 26 at 7:17
Ian Martin
113
113
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
add a comment |Â
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
"...we could do this much more efficiently, but getting two iterators, then simply..." - should the word but have actually been by?
– Sam Onela
Jun 26 at 14:54
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
Yup. Thanks for spotting it.
– Ian Martin
Jun 27 at 11:43
add a comment |Â
up vote
0
down vote
I assume both lists contain object of the same type/class, ie MyClass1 and MyClass2 are not two different classes.
In such a case MyClass can override equals method. Once equals is implemented as stated & you have ensured not to have violated the equals and hashcode contract, you can the use a HashMap.
This can reduce your time complexity.
answered Jan 26 at 15:44
Tanvi Jaywant
1122
1
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
add a comment |Â
up vote
0
down vote
I assume both lists contain object of the same type/class, ie MyClass1 and MyClass2 are not two different classes.
In such a case MyClass can override equals method. Once equals is implemented as stated & you have ensured not to have violated the equals and hashcode contract, you can the use a HashMap.
This can reduce your time complexity.
answered Jan 26 at 15:44
Tanvi Jaywant
1122
1
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
add a comment |Â
up vote
0
down vote
up vote
0
down vote
I assume both lists contain object of the same type/class, ie MyClass1 and MyClass2 are not two different classes.
In such a case MyClass can override equals method. Once equals is implemented as stated & you have ensured not to have violated the equals and hashcode contract, you can the use a HashMap.
This can reduce your time complexity.
answered Jan 26 at 15:44
Tanvi Jaywant
1122
I assume both lists contain object of the same type/class, ie MyClass1 and MyClass2 are not two different classes.
In such a case MyClass can override equals method. Once equals is implemented as stated & you have ensured not to have violated the equals and hashcode contract, you can the use a HashMap.
This can reduce your time complexity.
answered Jan 26 at 15:44
Tanvi Jaywant
1122
answered Jan 26 at 15:44
Tanvi Jaywant
1122
answered Jan 26 at 15:44
Tanvi Jaywant
1122
answered Jan 26 at 15:44
Tanvi Jaywant
1122
1122
1
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
add a comment |Â
1
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
1
1
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
The reason i named them differntly here is because htey are different classes
– XtremeBaumer
Jan 26 at 15:49
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
If name+id concatenated can be unique, then create a hashmap<string, string> or Set ?
– Tanvi Jaywant
Jan 26 at 15:52
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f186036%2fiterate-two-lists-and-find-matches%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
What's the nature of the condition? Does it involve both list elements or is it unrelated?
– chatton
Jan 26 at 7:50
It includes elements from both lists
– XtremeBaumer
Jan 26 at 7:51
If your class's equals method returns true if names are equal you could use the built in list.retailAll(list2). This operation would probably be a lot faster if you used sets instead of lists too. The copying of elements to make a set might not be worth it though
– chatton
Jan 26 at 8:05
@chatton This is sadly not an option. I think I have to iterate both lists like this
– XtremeBaumer
Jan 26 at 8:15
As you are dealing with lists the resulting algorithm complexity will be
O(n*m). For better performance compose and return maps fromfindUnmatchedEntries()and use them in your names comparison mechanism. Usenamesas map keys and class (MyClass1 and MyClass2) objects as map values.– user23908
Jan 26 at 11:10