CODEWITHSUNDEEP
javajava-8java-streamtime-complexityintersection
codemaster001
codemaster001

Reputation: 313

Finding Intersection of two list in O(n) java8 stream

I have two lists, Resources and TableResources. I want to find the intersection of the two lists based on a condition i.e subscriberId+"_"+tableName for the both the list is same. I am able to achieve this in O(N^2) time. I want to do the same using Java8 stream in O(N) time. 

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class intersectionStream {
    private static class Resource {
        String subscriberId;
        String tableName;
        List<String> buyers;

        public Resource(String subscriberId, String tableName) {
            this.subscriberId = subscriberId;
            this.tableName = tableName;
        }

        @Override
        public String toString() {
            return "TableResource{" +
                    "subscriberId='" + subscriberId + '\'' +
                    ", tableName='" + tableName + '\'' +
                    ", buyers=" + buyers +
                    '}';
        }

        public String getResourceString() {
            return this.subscriberId + "_" + this.tableName;
        }

    }

    private static class TableResource {
        String subscriberId;
        String tableName;

        public TableResource(String subscriberId, String tableName) {
            this.subscriberId = subscriberId;
            this.tableName = tableName;
        }

        public String getTableResource() {
            return this.subscriberId + "_" + this.tableName;
        }

        @Override
        public String toString() {
            return "GlobalTableResource{" +
                    "subscriberId='" + subscriberId + '\'' +
                    ", tableName='" + tableName + '\'' +
                    '}';
        }
    }

    public static void main(String[] args) {
        List<Resource> resources = new ArrayList<>();
        List<TableResource> tableResources = new ArrayList<>();
        HashSet<String> commonResources = new HashSet<>();

        resources.add(new Resource("1", "table1"));
        resources.add(new Resource("2", "table2"));
        resources.add(new Resource("3", "table3"));
        resources.add(new Resource("3", "table4"));
        resources.add(new Resource("3", "table5"));


        tableResources.add(new TableResource("2", "table2"));
        tableResources.add(new TableResource("3", "table3"));
        tableResources.add(new TableResource("5", "table5"));
        tableResources.add(new TableResource("6", "table6"));

        for(Resource resource : resources) {
            for(TableResource tableResource : tableResources) {
                if(tableResource.getTableResource().equals(resource.getResourceString())) {
                    commonResources.add(tableResource.getTableResource());
                }
            }

        }

        System.out.println("Hashset is : " + commonResources);
    }
}

Desired output is : Hashset is : [2_table2, 3_table3]

Upvotes: 2

Views: 238

Answers (2)

ETO
ETO

Reputation: 7279

Try this:

Set<String> resourceStrings = resources.stream()
                                       .map(Resource::getResourceString)
                                       .collect(toCollection(HashSet::new));

Set<String> commonResources = tableResources.stream()
                                            .map(TableResource::getTableResource)
                                            .filter(resourceStrings::contains)
                                            .collect(toSet());

Explanation:

Collecting into a HashSet takes linear time O(n), while HashSet::contains takes constant O(1) time. So once you have a HashSet, you can simply iterate over the second collection in O(n) time. Overall complexity os O(n + n) or O(2n). The constant factors are suppressed by big O notation. Thus the resulting complexity is considered O(n).

Upvotes: 1

Vikas
Vikas

Reputation: 7165

You can try as below,

Set<String> tableResourcesSet = tableResources.stream()
                .map(TableResource::getTableResource)
                .collect(Collectors.toSet());

resources.stream()
        .map(Resource::getResourceString)
        .filter(tableResourcesSet::contains)
        .collect(Collectors.toSet());

Upvotes: 2

Related Questions