Tại sao việc lặp lại Danh sách nhanh hơn lập chỉ mục thông qua Danh sách?

Question

Đọc Java documentation for the ADT List nó nói:

danh sách giao diện cung cấp bốn phương pháp cho vị trí truy cập (lập chỉ mục) để liệt kê các yếu tố. Các danh sách (như các mảng Java) không dựa trên. Lưu ý rằng các hoạt động này có thể thực thi theo thời gian tỉ lệ với giá trị chỉ mục cho một số hiện thực (ví dụ như lớp LinkedList). Do đó, việc lặp qua các phần tử trong danh sách thường thích hợp hơn để lập chỉ mục thông qua nó nếu người gọi không biết thực hiện.

Điều này có nghĩa là gì? Tôi không hiểu kết luận được rút ra.

Answer 1

Trong một danh sách liên kết, mỗi phần tử có một con trỏ tới phần tử tiếp theo:

head -> item1 -> item2 -> item3 -> etc. 

Để truy cập item3, bạn có thể thấy rõ rằng bạn cần phải đi bộ từ đầu thông qua mọi nút cho đến khi bạn đạt đến mục 3, vì bạn không thể nhảy trực tiếp.

Như vậy, nếu tôi muốn in giá trị của mỗi phần tử, nếu tôi viết những dòng này:

head -> print head 
head -> item1 -> print item1 
head -> item1 -> item2 -> print item2 
head -> item1 -> item2 -> item3 print item3 

Đây là khủng khiếp không hiệu quả vì mỗi lần:

for(int i = 0; i < 4; i++) { 
    System.out.println(list.get(i)); 
} 

những gì sẽ xảy ra đây là bạn đang lập chỉ mục nó khởi động lại từ đầu danh sách và đi qua mọi mục. Điều này có nghĩa là sự phức tạp của bạn có hiệu quả là O(N^2) chỉ để duyệt qua danh sách!

Nếu thay vào đó tôi đã làm điều này:

for(String s: list) { 
    System.out.println(s); 
} 

sau đó điều gì sẽ xảy ra đây là:

head -> print head -> item1 -> print item1 -> item2 -> print item2 etc. 

tất cả trong một traversal duy nhất, đó là O(N).

Bây giờ, hãy thực hiện một số khác là List là ArrayList, được hỗ trợ bởi một mảng đơn giản. Trong trường hợp đó, cả hai giao điểm trên đều tương đương nhau, vì một mảng nằm liền kề nên nó cho phép nhảy ngẫu nhiên đến các vị trí tùy ý.

Answer 2

Câu trả lời được ngụ ý ở đây:

Lưu ý rằng các hoạt động này có thể thực hiện trong thời gian tương ứng với giá trị chỉ số cho một số hiện thực (lớp LinkedList, ví dụ)

Một danh sách liên kết doesn không có chỉ mục vốn có; gọi .get(x) sẽ yêu cầu triển khai danh sách để tìm mục nhập đầu tiên và gọi .next() x-1 lần (đối với truy cập thời gian O hoặc n), trong đó danh sách được hỗ trợ theo mảng chỉ có thể lập chỉ mục thành backingarray[x] trong O (1) hoặc liên tục thời gian.

Nếu bạn nhìn vào JavaDoc for LinkedList, bạn sẽ thấy những nhận xét

Tất cả các hoạt động thực hiện như có thể được dự kiến ​​cho một danh sách gấp đôi được liên kết. Các hoạt động mà chỉ mục trong danh sách sẽ đi qua danh sách từ đầu hoặc cuối, tùy theo điều nào gần với chỉ mục được chỉ định.

trong khi JavaDoc for ArrayList có tương ứng

thực hiện Resizable mảng của giao diện danh sách. Thực hiện tất cả các hoạt động danh sách tùy chọn và cho phép tất cả các phần tử, bao gồm cả null. Ngoài việc triển khai thực hiện giao diện Danh sách, lớp này cung cấp các phương thức để thao tác kích thước của mảng được sử dụng trong nội bộ để lưu trữ danh sách. (Lớp này là tương đương với Vector, ngoại trừ việc nó là không đồng bộ.)

Các size, isEmpty, get, set, iterator, và listIterator hoạt động chạy trong thời gian không đổi. Phép cộng thêm chạy trong thời gian cố định được phân bổ, tức là thêm các phần tử n yêu cầu thời gian O (n). Tất cả các hoạt động khác chạy trong thời gian tuyến tính (gần như nói). Các yếu tố không đổi là thấp so với việc thực hiện LinkedList.

A related question titled "Big-O Summary for Java Collections Framework" có câu trả lời chỉ tới tài nguyên này, "Java Collections JDK6" mà bạn có thể thấy hữu ích.

Answer 3

Để tìm phần tử thứ i của một số LinkedList, việc triển khai thực hiện qua tất cả các phần tử cho đến lần thứ i.

Vì vậy

for(int i = 0; i < list.length ; i++) { 
    Object something = list.get(i); //Slow for LinkedList 
} 

Answer 4

Trong khi câu trả lời được chấp nhận là chắc chắn chính xác nhất, tôi có thể chỉ ra một lỗ hổng nhỏ. Quoting Tudor:

Bây giờ, hãy triển khai danh sách khác của Danh sách là ArrayList, một danh sách được hỗ trợ bởi một mảng đơn giản. Trong trường hợp đó cả hai bên trên truyền tải là tương đương, vì một mảng liền kề nên nó cho phép nhảy ngẫu nhiên đến các vị trí tùy ý.

Điều này không hoàn toàn đúng. Sự thật là, rằng

Với một ArrayList, một vòng lặp đếm viết tay là khoảng 3x nhanh hơn

source: Designing for Performance, Google's Android doc

Lưu ý rằng vòng tay đề cập đến việc lặp được lập chỉ mục. Tôi nghi ngờ của nó vì các iterator được sử dụng với tăng cường cho vòng. Nó tạo ra một hiệu suất nhỏ trong hình phạt trong một cấu trúc được hỗ trợ bởi một mảng liền kề. Tôi cũng nghi ngờ điều này có thể đúng với lớp Vector.

Quy tắc của tôi là sử dụng vòng lặp tăng cường bất cứ khi nào có thể và nếu bạn thực sự quan tâm đến hiệu suất, hãy sử dụng lặp lại chỉ mục cho ArrayLists hoặc Vectors.Trong hầu hết các trường hợp, bạn thậm chí có thể bỏ qua điều này - trình biên dịch có thể tối ưu hóa điều này trong nền.

Tôi chỉ muốn chỉ ra rằng trong bối cảnh phát triển trong Android, cả hai giao điểm của ArrayLists là không nhất thiết phải tương đương. Chỉ là thức ăn cho sự suy nghĩ.

Answer 5

Lặp lại danh sách có bù đắp cho tra cứu, chẳng hạn như i, tương tự như Shlemiel thuật toán của họa sĩ.

Shlemiel nhận công việc làm họa sĩ đường phố, vẽ các đường chấm chấm ở giữa đường. Vào ngày đầu tiên, anh ta có thể sơn ra đường và hoàn thành 300 thước đường. "Đó là khá tốt!" nói ông chủ của mình, "bạn là một công nhân nhanh!" và trả cho anh ta một kopeck.

Ngày hôm sau Shlemiel chỉ được thực hiện 150 yard. "Vâng, đó không phải là gần như tốt như ngày hôm qua, nhưng bạn vẫn là một công nhân nhanh. 150 yards là đáng kính" và trả cho anh ta một kopeck.

Ngày hôm sau Shlemiel vẽ 30 ​​thước đường. "Chỉ 30 thôi!" hét lên ông chủ của mình. "Điều đó là không thể chấp nhận được! Vào ngày đầu tiên bạn làm mười lần nhiều việc đó! Có chuyện gì vậy?"

"Tôi không thể giúp được," Shlemiel nói. "Mỗi ngày tôi có thể xa hơn và xa hơn cách xa thùng sơn!"

Source.

Câu chuyện nhỏ này có thể giúp bạn dễ dàng hiểu nội dung đang diễn ra trong nội bộ và lý do khiến nó không hiệu quả.