Finding whether an object of a list is present in another List
Clash Royale CLAN TAG#URR8PPP
Finding whether an object of a list is present in another List
I have two lists List<AreaOfInterest> and List<AreaOfInterestBean>. The corresponding classes are,
List<AreaOfInterest>
List<AreaOfInterestBean>
@Entity
@Data
@Table( name = "interest_area" )
public class AreaOfInterest
@Id
@GeneratedValue( strategy = GenerationType.AUTO )
@Column( name = "ia_id" )
private Long id;
@Column( name = "ia_value" )
private String value;
@Column( name = "ia_is_active" )
private Boolean isActive;
@Column( name = "ia_created_at" )
private Calendar createdAt;
@Column( name = "ia_is_approved" )
private Boolean isApprovedByAdmin;
@Column( name = "ia_approved_at" )
private Calendar approvedAt;
and,
@Data
public class AreaOfInterestBean
private Long id;
private String value;
private boolean isSelected;
I want to check if the object of List<AreaOfInterest> is present in List<AreaOfInterestBean> and if so, I need to update the corresponding Object of List<AreaOfInterestBean>. Right now, I feel I have to iterate both lists to solve this problem. Is there any efficient way?
List<AreaOfInterest>
List<AreaOfInterestBean>
List<AreaOfInterestBean>
AreaOfInterest
AreaOfInterestBean
@Eugene the field
value– Virat
Aug 10 at 20:06
value
You want to check if each element in one list is in another list? And your goal is to do it more efficiently than iterating over both lists? Not without storing the data in another data structure like a hash set.
– nhouser9
Aug 10 at 20:07
@nhouser9 that would require overriding equals/hashCode, not always an option...
– Eugene
Aug 10 at 20:07
You can indeed avoid O(N²) complexity. An example: turn your
List<AreaOfInterestBean> into a HashSet of ids , then iterate over List<AreaOfInterest> to find occurrences in the set. You still iterate over both lists, but not nested, so complexity falls to O(N)– Joel
Aug 10 at 20:08
List<AreaOfInterestBean>
HashSet
id
List<AreaOfInterest>
2 Answers
2
To be honest I'm not sure of the complexity of this (I'll try to figure it out tomorrow):
Set<String> left = nonBeans.stream()
.map(AreaOfInterest::getValue)
.collect(Collectors.toSet());
beans.stream()
.filter(x -> left.contains(x.getValue()))
.forEach(x -> x.setSelected(true));
In this case the complexity will be O(n).
O(n)
Thank you. I will also try to figure out the complexity
– Virat
Aug 10 at 21:05
Well, this is generally O(n), as Joel pointed out in his comment (
HashSet.contains has O(1) average and O(n) worst-case complexity).– Tomasz Linkowski
Aug 10 at 21:37
HashSet.contains
@TomaszLinkowski right, thank you! better then doing
O(n^2)– Eugene
Aug 10 at 21:44
O(n^2)
@Eugene Definitely! You might also want to update the answer with the complexity info so that I could upvote it :)
– Tomasz Linkowski
Aug 11 at 8:37
@TomaszLinkowski done
– Eugene
Aug 11 at 10:40
Assuming:
List<AreaOfInterest> list = /* ... */
List<AreaOfInterestBean> listOfBeans = /* ... */
Two simple iterations would achieve it easily:
for (int i=0; i<listOfBeans.size(); i++) // Iterate beans
AreaOfInterestBean aoiBean = listOfBeans.get(i); // Get each bean
for (int j=0; j<list.size(); j++) // Iterate entity
AreaOfInterest aoi = list.get(j); // Get each entity
if (aoiBean.getId() == aoi.getId()) // If they have the same ID
aoiBean.setValue(aoi.getValue()); // Update the bean value
break; // Go to the next bean
Example: Having the following simplified data:
AreaOfInterest
id
value
1, "Car"
2, "Bike"
3, "Ship"
AreaOfInterestBeans
id
value
5, "Limo"
2, "Scooter"
7, "Yacht"
The result AreaOfInterestBeans will be with replaced value of id 2: Scooter -> Bike.
AreaOfInterestBeans
2
Scooter
Bike
AreaOfInterestBeans
id
value
5, "Limo"
2, "Bike"
7, "Yacht"
An alternative Stream way:
listOfBeans = listOfBeans.stream()
.peek(aoiBean -> list.stream()
.filter(aoi -> aoi.getId() == aoiBean.getId())
.findFirst()
.ifPresent(i -> aoiBean.setValue(i.getValue())))
.collect(Collectors.toList());
of course yes. But I am looking for a better approach, which do not involve two for loops. Basically to reduce the complexity of
O(n^2) . Thank you– Virat
Aug 10 at 20:23
O(n^2)
This is complexity
O(n^2) - two full iterations always result in this complexity.– Nikolas
Aug 10 at 20:25
O(n^2)
@Nikolas You mean "two nested iterations", right? Two independent iterations would still be O(n).
– Tomasz Linkowski
Aug 11 at 8:39
@TomaszLinkowski: Yes, that's what I mean - an iteration in another one. If these are independent, the complexity would be
O(2n) which is O(n). "Nested" is the right word.– Nikolas
Aug 11 at 13:15
O(2n)
O(n)
@Nikolas or simpler
leftList.size * rightList.size vs leftList.size + rightList.size...– Eugene
Aug 12 at 18:32
leftList.size * rightList.size
leftList.size + rightList.size
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
what is the equality between
AreaOfInterestandAreaOfInterestBean?– Eugene
Aug 10 at 20:05