Bất kỳ sự khác biệt lớn nào giữa việc sử dụng chứa hoặc lặp qua danh sách?

Question

Hiệu suất khôn ngoan, có thực sự là một sự khác biệt lớn giữa việc sử dụng:

• ArrayList.contains (o) vs foreach | iterator
• LinkedList.contains (o) vs foreach | iterator

Trong số Tất nhiên, đối với vòng lặp foreach | vòng lặp, tôi sẽ phải so sánh rõ ràng các phương thức và trả về true hoặc false cho phù hợp.

Đối tượng tôi so sánh là đối tượng trong đó equals() và hashcode() đều được ghi đè chính xác.

EDIT: Bạn không cần phải biết về containsValue, xin lỗi về điều đó. Và vâng, tôi ngu ngốc ... Tôi nhận ra câu hỏi ngu ngốc của tôi là về containKey vs foreach, không bao giờ nghĩ về điều đó, tôi không biết mình đang nghĩ gì. Tôi về cơ bản muốn biết về những điều trên (chỉnh sửa những người khác).

Answer 1

CHỈNH SỬA:

Với dạng câu hỏi mới không còn bao gồm HashMap và TreeMap, câu trả lời của tôi hoàn toàn khác. Bây giờ tôi nói không.

Tôi chắc chắn rằng những người khác đã trả lời câu hỏi này, nhưng trong cả LinkedList và ArrayList, chứa() chỉ cần gọi indexOf(), nó lặp qua bộ sưu tập.

Có thể có sự khác biệt nhỏ về hiệu suất, giữa LinkedList và ArrayList, và giữa chứa và foreach, không có bất kỳ sự khác biệt lớn nào về số lớn.

Answer 2

Không có điểm chuẩn, nên chứa nhanh hơn hoặc giống nhau trong mọi trường hợp.

Đối với 1 và 2, không cần gọi các phương thức của trình lặp. Nó có thể lặp trong nội bộ. Cả hai ArrayList và LinkedList thực hiện chứa trong indexOf

1. ArrayList - indexOf là kiểu C cho vòng lặp trên mảng sao lưu.
2. LinkedList - indexOf dẫn danh sách được liên kết theo kiểu C cho vòng lặp.

Đối với 3 và 4, bạn phải phân biệt giữa containsKey và containsValue.

3.   HashMap, containsKey là O (1). Nó hoạt động bằng cách băm khóa, lấy thùng liên kết, sau đó đi bộ danh sách liên kết. containsValue là O (n) và hoạt động bằng cách kiểm tra mọi giá trị trong mỗi nhóm trong một vòng lặp lồng nhau.

4.   TreeMap, containsKey là O (log n). Nó kiểm tra xem nó có trong phạm vi không, sau đó tìm kiếm cây đỏ-đen. containsValue, là O (n), sử dụng đi bộ theo trật tự của cây.

Answer 3

Tôi nghĩ việc sử dụng chứa có hiệu quả hơn vì thường việc triển khai thư viện hiệu quả hơn so với triển khai thủ công giống nhau. Kiểm tra nếu bạn có thể trong quá trình xây dựng đối tượng hoặc sau đó vượt qua một phương pháp so sánh mà bạn đã viết mà sẽ chăm sóc của bạn bằng tùy chỉnh và thực hiện hashcode.

Cảm ơn, Krishna

Answer 4

Vượt qua container với foreach/iterator luôn là O (n) thời gian. Tìm kiếm ArrayList/LinkedList cũng là O (n).

HashMap.containsKey() là thời gian O (1) amortized.

TreeMap.containsKey() là thời gian O (log n).

Đối với cả HashMap và TreeMap containsValue() là O (n), nhưng có thể có các triển khai được tối ưu hóa cho containsValue() nhanh bằng hàm containsKey().

Answer 5

ArrayList.contains không

return indexOf(o) >= 0; 

nơi

public int indexOf(Object o) { 
if (o == null) { 
    for (int i = 0; i < size; i++) 
    if (elementData[i]==null) 
     return i; 
} else { 
    for (int i = 0; i < size; i++) 
    if (o.equals(elementData[i])) 
     return i; 
} 
return -1; 
} 

Nó tương tự như đối với LinkedList, chỉ có nó sử dụng .next() để lặp qua các yếu tố, vì vậy không có nhiều sự khác biệt đó.

public int indexOf(Object o) { 
    int index = 0; 
    if (o==null) { 
     for (Entry e = header.next; e != header; e = e.next) { 
      if (e.element==null) 
       return index; 
      index++; 
     } 
    } else { 
     for (Entry e = header.next; e != header; e = e.next) { 
      if (o.equals(e.element)) 
       return index; 
      index++; 
     } 
    } 
    return -1; 
} 

HashMap.containKey sử dụng hàm băm của khóa để lấy tất cả khóa bằng băm đó (nhanh) và sau đó chỉ sử dụng trên các khóa đó, vì vậy có cải thiện ở đó; nhưng containsValue() đi qua các giá trị với một for.

TreeMap.containsKey dường như thực hiện tìm kiếm thông báo bằng cách sử dụng bộ so sánh để tìm Key nhanh hơn, vì vậy vẫn tốt hơn; nhưng chứaValue vẫn có vẻ đi qua toàn bộ ba cho đến khi nó tìm thấy một giá trị.

Nói chung tôi nghĩ bạn nên sử dụng các phương pháp, vì chúng dễ viết hơn làm vòng lặp mỗi lần :).

Answer 6

Điều này làm cho không differency từ chứa (o) gọi indexOf (o) mà chỉ đơn giản lặp như thế này:

for (int i = 0; i < size; i++) 
    if (o.equals(elementData[i])) 
     return i; 

(Kiểm tra trong ArrayList)