Java: .contains and .equals

Question

Tôi đang cố gắng thực thi một chương trình, để so sánh các phần tử trong hai danh sách liên kết với nhau. một cách, tôi có thể làm điều này là bằng cách thực hiện hai cho vòng lặp và lặp qua cả hai danh sách so sánh từng phần tử trong list1 với list2 sử dụng .equals(). cách khác là, chỉ cần lặp qua danh sách đầu tiên và kiểm tra xem list1.contains (list1.get (i)) .. tài liệu java nói, đó .contains hiện .equals nội bộ. nếu đó là trường hợp, làm thế nào là thời gian chạy của tôi cho cựu là lâu hơn khi so sánh với sau này? Tôi có hiểu sai tài liệu không? Nếu tôi đã làm, làm thế nào chính xác so sánh nội bộ diễn ra khi tôi sử dụng có chứa?

  using equals: 
      for (int i = 0; i < list_one.size(); i++) { 
       for (int j = 0; j < list_one.size(); j++) { 
        if (list_one.get(i).equals(list_two.get(j))) { count++; } 

      using contains: 
      for (int i = 0; i < list_one.size(); i++) { 
       if (list_two.contains(list_one.get(i)) == true) { count++; } 

Answer 1

Tôi nghĩ, nhìn thấy get(i) mà bạn đang sử dụng get(j) trong cả hai vòng. Trong danh sách được liên kết không hiệu quả. for (String s1 : list1) for (String s2 : list2) ... phải có cùng tốc độ là contains.

Ví dụ get (3) sẽ cần phải bắt đầu với phần tử đầu tiên, hãy liên kết đến ba lần tiếp theo. Trong khi đó, for-each sử dụng một trình vòng lặp trỏ tới phần tử tiếp theo.

Answer 2

Việc triển khai contains sẽ ngừng lặp lại khi equals trả về true, vì vậy nó không lặp lại toàn bộ danh sách nếu phần tử bạn đang tìm ở đâu đó ở đầu danh sách. Nếu phiên bản của bạn không làm điều đó, điều đó sẽ giải thích tại sao nó lại chậm hơn.

PS: Dù bằng cách nào thì thời gian chạy vẫn sẽ là bậc hai. Có những cách thông minh hơn để giải quyết vấn đề này không liên quan đến việc lặp qua danh sách thứ hai cho mỗi mục trong danh sách đầu tiên (ví dụ bằng cách sắp xếp hai danh sách trước tiên hoặc sử dụng một bộ).