0

I've been dealing with a problem lately where i have to wait for hours to get the right answer. The problem is this: I have two different lists that have thousands of elements. I want to check if both lists contain the same element and if soo i want to add that element in a separate list. When i try with a small amount of elements in the lists, the program works perfectly fine but when i try with more elements, i have to wait for hours to get the right answer. 

        List<Point> res1 = new LinkedList<>();
        for (Point value : w1) {
            System.out.println("Thread 1");
            Point a = value;
            for (Point point : w2) {
                if (a.equals(point)) {
                    System.out.println(Math.abs(a.x) + Math.abs(a.y));
                    res1.add(a);
                }

            }
        }

What is the fastest way to do this kind of comparing?

Thanks in advance

Fazli Zekiqi
  • 531
  • 2
  • 7
  • 14
  • You can test the different approaches to see which one does better. – SedJ601 Dec 05 '19 at 22:45
  • This works only with small amounts of elements. Thanks. The problem is that this also takes to much time to find the same element. – Fazli Zekiqi Dec 05 '19 at 22:49
  • https://codereview.stackexchange.com – FailingCoder Dec 05 '19 at 22:54
  • 1
    The accepted answer to the linked question will surely help. Checking if something is present in a list has complexity `O(n)`, the same operation for sets is `O(1)`. And please forget `LinkedList`, it's hardly ever the right choice. – maaartinus Dec 06 '19 at 05:13
  • I don't see an accepted answer there and the most upvoted answer would not give a good performance here since - as you pointed out here a `LinkedList` is used and not a HashSet. Performance wise the only acceptable answer from the thread would be the apache commons answer. And performance was not a question there - but is here. So I don't think this is purely a duplicate. – Lutz Dec 06 '19 at 21:37

1 Answers1

2

If you use HashSet you get a very efficient contains method free of charge:

        HashSet hsw1 = new HashSet(w1); // turn first into a hashset
        List<Point> res1 = new LinkedList<>(w2); // load the second into new list
        res1.retainall(hsw1); // retain only values that are in the first as well
Lutz
  • 612
  • 3
  • 8
  • Thank you very much. This worked perfectly. It has accelerated my program thousands of time faster – Fazli Zekiqi Dec 06 '19 at 14:01
  • 1
    if your can use a `HashSet` for w1 to begin with then you could get rid of the first conversion and be a bit faster there - but possibly pay for it by insert performance. Not sure what would outweigh the other for your case. – Lutz Dec 06 '19 at 21:55