Câu hỏi Khi nào sử dụng LinkedList trên ArrayList?


Tôi luôn là người chỉ đơn giản sử dụng:

List<String> names = new ArrayList<>();

Tôi sử dụng giao diện làm tên loại cho tính di động, khi tôi đặt câu hỏi như vậy, tôi có thể làm lại mã của mình.

Khi nào nên LinkedList được sử dụng trên ArrayList và ngược lại?


2568
2017-11-27 01:36


gốc


Xem thêm: Mảng so với danh sách được liên kết - Hawkeye Parker
Chỉ cần xem báo giá từ tác giả của LinkedList stackoverflow.com/a/42529652/2032701 và bạn sẽ hiểu được vấn đề thực tế. - Ruslan


Các câu trả lời:


Tóm lược  ArrayList với ArrayDeque thích hợp hơn nhiều nhiều trường hợp sử dụng hơn LinkedList. Không chắc chắn - chỉ cần bắt đầu với ArrayList.


LinkedList và ArrayList là hai triển khai khác nhau của giao diện Danh sách. LinkedList thực hiện nó với một danh sách liên kết gấp đôi. ArrayList thực hiện nó với một mảng tái định cỡ động.

Như với danh sách liên kết tiêu chuẩn và các hoạt động mảng, các phương thức khác nhau sẽ có các thời gian chạy thuật toán khác nhau.

Dành cho LinkedList<E>

  • get(int index) Là Trên) (với n / 4 bước trung bình)
  • add(E element) Là O (1)
  • add(int index, E element) Là Trên) (với n / 4 bước trung bình), nhưng O (1) khi nào index = 0  <--- lợi ích chính của LinkedList<E>
  • remove(int index) Là Trên) (với n / 4 bước trung bình)
  • Iterator.remove() Là O (1). <--- lợi ích chính của LinkedList<E>
  • ListIterator.add(E element) Là O (1)  Đây là một trong những lợi ích chính của LinkedList<E>

Lưu ý: Nhiều hoạt động cần n / 4 bước trung bình, không thay đổi số bước trong trường hợp tốt nhất (ví dụ: chỉ mục = 0) và n / 2 các bước trong trường hợp xấu nhất (giữa danh sách)

Dành cho ArrayList<E>

  • get(int index) Là O (1)  <--- lợi ích chính của ArrayList<E>
  • add(E element) Là O (1) khấu hao, nhưng Trên) trường hợp xấu nhất kể từ khi mảng phải được thay đổi kích thước và sao chép
  • add(int index, E element) Là Trên) (với n / 2 bước trung bình)
  • remove(int index) Là Trên) (với n / 2 bước trung bình)
  • Iterator.remove() Là Trên) (với n / 2 bước trung bình)
  • ListIterator.add(E element) Là Trên) (với n / 2 bước trung bình)

Lưu ý: Nhiều hoạt động cần n / 2 bước trung bình, không thay đổi số bước trong trường hợp tốt nhất (cuối danh sách), n các bước trong trường hợp xấu nhất (bắt đầu danh sách)

LinkedList<E> cho phép chèn hoặc xóa liên tục thời gian sử dụng trình vòng lặp, nhưng chỉ truy cập tuần tự các phần tử. Nói cách khác, bạn có thể đưa danh sách về trước hoặc lùi, nhưng việc tìm một vị trí trong danh sách sẽ mất thời gian tỉ lệ với kích thước của danh sách. Javadoc nói "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 hơn", vì vậy các phương pháp đó là Trên) (n / 4 bước) trung bình, mặc dù O (1) cho index = 0.

ArrayList<E>, mặt khác, cho phép truy cập đọc ngẫu nhiên nhanh, vì vậy bạn có thể lấy bất kỳ phần tử nào trong thời gian không đổi. Nhưng thêm hoặc loại bỏ từ bất cứ nơi nào nhưng kết thúc yêu cầu chuyển tất cả các yếu tố sau này, hoặc để thực hiện một mở hoặc lấp đầy khoảng trống. Ngoài ra, nếu bạn thêm nhiều phần tử hơn dung lượng của mảng cơ sở, một mảng mới (1,5 lần kích thước) được cấp phát và mảng cũ được sao chép sang mảng mới, vì vậy hãy thêm vào ArrayList Là Trên) trong trường hợp xấu nhất nhưng không đổi trung bình.

Vì vậy, tùy thuộc vào các hoạt động bạn định làm, bạn nên chọn các triển khai cho phù hợp. Iterating trên một trong hai loại Danh sách là thực tế không kém giá rẻ. (Lặp lại một ArrayList về mặt kỹ thuật nhanh hơn, nhưng trừ khi bạn đang làm điều gì đó thực sự nhạy cảm với hiệu suất, bạn không nên lo lắng về điều này - chúng đều là hằng số.)

Những lợi ích chính của việc sử dụng LinkedList phát sinh khi bạn sử dụng lại các trình lặp hiện có để chèn và loại bỏ các phần tử. Những hoạt động này sau đó có thể được thực hiện trong O (1) bằng cách chỉ thay đổi danh sách cục bộ. Trong một danh sách mảng, phần còn lại của mảng cần phải đã di chuyển (tức là sao chép). Ở phía bên kia, tìm kiếm trong một LinkedList có nghĩa là theo các liên kết trong Trên) (n / 2 bước) cho trường hợp xấu nhất, trong khi trong một ArrayList vị trí mong muốn có thể được tính toán và truy cập trong O (1).

Một lợi ích khác của việc sử dụng LinkedList phát sinh khi bạn thêm hoặc xóa khỏi đầu danh sách, vì các hoạt động đó O (1), trong khi họ Trên) cho ArrayList. Lưu ý rằng ArrayDeque có thể là một lựa chọn tốt để LinkedList để thêm và xóa khỏi đầu, nhưng nó không phải là List.

Ngoài ra, nếu bạn có danh sách lớn, hãy nhớ rằng việc sử dụng bộ nhớ cũng khác nhau. Mỗi phần tử của một LinkedList có nhiều chi phí hơn vì các con trỏ tới các phần tử tiếp theo và trước đó cũng được lưu trữ. ArrayLists không có phí này. Tuy nhiên, ArrayLists chiếm nhiều bộ nhớ như được phân bổ cho dung lượng, bất kể các phần tử có thực sự được thêm vào hay không.

Dung lượng ban đầu mặc định của một ArrayList là khá nhỏ (10 từ Java 1.4 - 1.8). Nhưng kể từ khi thực hiện cơ bản là một mảng, mảng phải được thay đổi kích thước nếu bạn thêm rất nhiều yếu tố. Để tránh chi phí thay đổi kích thước cao khi bạn biết bạn sẽ thêm nhiều yếu tố, hãy xây dựng ArrayList với công suất ban đầu cao hơn.


2847
2017-10-06 06:46



Quên đề cập đến chi phí chèn. Trong một LinkedList, một khi bạn có vị trí chính xác, chi phí chèn O (1), trong khi trong một ArrayList nó đi lên đến O (n) - tất cả các phần tử qua điểm chèn phải được di chuyển. - David Rodríguez - dribeas
Về việc sử dụng Vector: Có thực sự là không cần phải quay trở lại Vector. Cách để làm điều này là với việc thực hiện Danh sách ưa thích của bạn và một cuộc gọi đến SynchronList để cung cấp cho nó một trình bao bọc được đồng bộ hóa. Xem: java.sun.com/docs/books/tutorial/collections/implementations/… - Ryan Cox
Không, đối với LinkedList, nhận được vẫn là O (n) ngay cả khi bạn biết vị trí, bởi vì để có được vị trí đó, việc triển khai cơ bản phải đi theo con trỏ "tiếp theo" của danh sách liên kết để đến giá trị của vị trí đó. Không có điều như truy cập ngẫu nhiên. Đối với vị trí 2, việc đi bộ các con trỏ có thể rẻ, nhưng với vị trí 1 triệu, không quá rẻ. Vấn đề là, tỷ lệ thuận với vị trí, có nghĩa là O (n). - Jonathan Tran
@Kevin Nó có thể quan trọng mà bộ nhớ là "gần nhau". Phần cứng sẽ lưu trữ các khối bộ nhớ liền kề (RAM động) vào RAM tĩnh nhanh hơn trong bộ nhớ cache L1 hoặc L2. Về lý thuyết và phần lớn thời gian thực tế, bộ nhớ có thể được coi là truy cập ngẫu nhiên. Nhưng trên thực tế, việc đọc qua bộ nhớ tuần tự sẽ nhanh hơn một chút so với thứ tự ngẫu nhiên. Đối với một vòng lặp hiệu suất quan trọng, điều này có thể quan trọng. Họ gọi nó là "địa phương không gian" hoặc địa phương tham khảo. - Jonathan Tran
Không có thứ gì như O(n/2) hoặc là O(n/4). Ký hiệu O lớn cho bạn biết cách hoạt động quy mô lớn hơn n. và một hoạt động cần n/2 các bước cân chính xác như nhu cầu vận hành n các bước, đó là lý do tại sao các hằng số hoặc các thừa số liên tục bị loại bỏ. O(n/2) và O(n/4) vừa là vừa O(n). LinkedList và ArrayList có các yếu tố không đổi khác nhau, do đó, nó sẽ không tạo ra hàng rào để so sánh O(n/2) của một với một O(n/4) của người khác, cả hai chỉ biểu thị các hoạt động chia tỷ lệ tuyến tính. - Holger


Cho đến nay, không ai dường như đã giải quyết được dấu vết bộ nhớ của mỗi danh sách này ngoài sự đồng thuận chung rằng LinkedList là "nhiều hơn" hơn một ArrayList vì vậy tôi đã làm một số crunching để chứng minh chính xác bao nhiêu cả hai danh sách mất cho N null tài liệu tham khảo.

Vì các tham chiếu là 32 hoặc 64 bit (ngay cả khi null) trên các hệ thống tương đối của chúng, tôi đã bao gồm 4 bộ dữ liệu cho 32 và 64 bit LinkedLists và ArrayLists.

Chú thích: Kích thước hiển thị cho ArrayList dòng dành cho danh sách tỉa - Trong thực tế, khả năng của mảng sao lưu trong một ArrayList thường lớn hơn số phần tử hiện tại của nó.

Lưu ý 2:  (cảm ơn BeeOnRope) Như CompressedOops là mặc định bây giờ từ giữa JDK6 trở lên, các giá trị dưới đây cho các máy 64 bit về cơ bản sẽ phù hợp với các đối tác 32 bit của chúng, trừ khi tất nhiên bạn đặc biệt tắt nó đi.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Kết quả cho thấy rõ ràng rằng LinkedList nhiều hơn cả ArrayList, đặc biệt với số lượng phần tử rất cao. Nếu bộ nhớ là một yếu tố, hãy tránh xa LinkedLists.

Các công thức tôi đã sử dụng theo dõi, hãy cho tôi biết nếu tôi đã làm bất kỳ điều gì sai và tôi sẽ sửa chữa nó. 'b' là 4 hoặc 8 cho hệ thống 32 hoặc 64 bit, và 'n' là số phần tử. Lưu ý lý do cho các mod là bởi vì tất cả các đối tượng trong java sẽ chiếm nhiều không gian 8 byte bất kể nó có được sử dụng hay không.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

535
2017-11-27 14:20



Khá thú vị khi thấy rằng LinkedList yêu cầu nhiều bộ nhớ như ArrayList để lưu trữ một phần tử đơn lẻ. Làm thế nào không trực quan! Điều gì sẽ xảy ra nếu bạn chạy ví dụ của mình bằng -XX: + UseCompressedOops? - jontejj
Vấn đề với toán học của bạn là đồ thị của bạn phóng đại rất nhiều tác động. Bạn đang lập mô hình các đối tượng mà mỗi đối tượng chỉ chứa một int, vì vậy 4 hoặc 8 byte dữ liệu. Trong danh sách liên kết, về cơ bản có 4 "từ". Do đó, đồ thị của bạn cho thấy rằng các danh sách được liên kết sử dụng "năm lần" việc lưu trữ các danh sách mảng. Cái này sai. Các chi phí là 16 hoặc 32 byte cho mỗi đối tượng, như một điều chỉnh phụ gia, không phải là một yếu tố mở rộng quy mô. - Heath Hunnicutt
Không có đối tượng ArrayList / LinkedList / Node nào chỉ chứa một int, vì vậy tôi không hiểu những gì bạn đang nói ở đó. Tôi đã reworded 'object overhead' để 'object header' thành clarfy - có một tiêu đề 8 byte cho mọi đối tượng bất kể hệ thống, và có inlcudes tất cả các đối tượng Node trong LinkedList, tất cả đều được đếm chính xác đến mức tôi có thể nói. Ngẫu nhiên, khi nhìn vào nó một lần nữa, tôi đã tìm thấy một vài vấn đề khác với toán học của tôi trong LinkedList mà thực sự làm cho việc phân chia nó và ArrayList tệ hơn. Tôi vui mừng tiếp tục cập nhật nó vì vậy xin vui lòng không ngần ngại làm rõ và xây dựng furuther. - Numeron
Cần lưu ý rằng CompressedOops là mặc định ngay bây giờ trong tất cả các JDK gần đây (7, 8 và cập nhật của 6 trong một vài năm), do đó, 64-bit sẽ không tạo sự khác biệt trong ArrayList hoặc là LinkedList kích thước, trừ khi bạn đã tắt một cách rõ ràng oops nén vì một lý do nào đó. - BeeOnRope
Đó có phải là hình ảnh của biểu đồ có sẵn cho mục đích thương mại không? Tôi muốn sử dụng nó. - Ogen


ArrayList là những gì bạn muốn. LinkedList hầu như luôn là lỗi (hiệu suất).

Tại sao LinkedList hút:

  • Nó sử dụng rất nhiều đối tượng bộ nhớ nhỏ, và do đó tác động đến hiệu suất trong suốt quá trình.
  • Rất nhiều các đối tượng nhỏ là xấu cho bộ nhớ cache-địa phương.
  • Bất kỳ thao tác được lập chỉ mục nào đều yêu cầu một quá trình truyền tải, tức là có hiệu suất O (n). Điều này không rõ ràng trong mã nguồn, dẫn đến thuật toán O (n) chậm hơn nếu ArrayListđã được dùng.
  • Nhận được hiệu suất tốt là khó khăn.
  • Ngay cả khi hiệu suất lớn-O cũng giống như ArrayList, nó có lẽ sẽ chậm hơn đáng kể.
  • Thật là căm thù khi thấy LinkedList trong nguồn bởi vì nó có lẽ là sự lựa chọn sai.

190
2018-01-01 20:23



Lấy làm tiếc. đánh dấu bạn xuống. LinkedList không hút. Có những tình huống mà LinkedList là lớp chính xác để sử dụng. Tôi đồng ý rằng không có nhiều tình huống mà nó tốt hơn một danh sách, nhưng chúng tồn tại. Giáo dục những người làm những điều ngớ ngẩn! - David Turner
Rất tiếc khi thấy bạn nhận được nhiều phiếu bầu cho điều này. Có rất ít lý do để sử dụng LinkedList của Java. Ngoài hiệu suất kém, nó cũng sử dụng nhiều bộ nhớ hơn các lớp List cụ thể khác (mỗi nút có hai con trỏ bổ sung và mỗi nút là một đối tượng bao bọc riêng biệt với các byte phụ thừa đi kèm với chúng). - Kevin Brock
Đây là một trong những câu trả lời hữu ích nhất ở đây. Thật là xấu hổ vì vậy nhiều lập trình viên không hiểu (a) sự khác biệt giữa các kiểu dữ liệu trừu tượng và triển khai cụ thể, và (b) tầm quan trọng thực của các yếu tố liên tục và chi phí bộ nhớ trong việc xác định hiệu suất. - Porculus
-1: Đây là chế độ xem khá chớp mắt. Vâng, đúng là ArrayList là một công cụ rất linh hoạt. Tuy nhiên, nó có những hạn chế của nó. Có những trường hợp trong đó điều này sẽ gây rắc rối cho bạn và bạn sẽ phải sử dụng LinkedList. Tất nhiên, nó là một giải pháp rất chuyên biệt, và, như bất kỳ công cụ chuyên biệt nào, trong hầu hết các trường hợp, nó được cải thiện tốt hơn một cách linh hoạt. Nhưng điều đó không có nghĩa là nó "hút" hay thứ gì đó như thế, bạn chỉ cần biết khi nào nên sử dụng nó. - Malcolm
@ DavidTurner: Chúng tồn tại, nhưng tôi nghĩ điểm của Tom là nếu bạn phải hỏi, bạn có thể muốn ArrayList. - Mehrdad


Là một người đã thực hiện kỹ thuật vận hành hiệu suất trên các dịch vụ web SOA có quy mô rất lớn trong khoảng một thập kỷ, tôi thích hành vi của LinkedList hơn ArrayList. Trong khi thông lượng trạng thái ổn định của LinkedList tồi tệ hơn và do đó có thể dẫn đến việc mua thêm phần cứng - hành vi của ArrayList dưới áp lực có thể dẫn đến các ứng dụng trong một cụm mở rộng mảng của chúng trong sự đồng bộ gần và với kích thước mảng lớn có thể dẫn đến thiếu đáp ứng trong ứng dụng và cúp điện, trong khi chịu áp lực, đó là hành vi thảm khốc.

Tương tự như vậy, bạn có thể nhận được thông lượng tốt hơn trong ứng dụng từ trình thu thập rác thông thường mặc định, nhưng khi bạn nhận được các ứng dụng java có dung lượng 10GB, bạn có thể khởi động ứng dụng trong 25 giây trong một GC đầy đủ gây ra timeouts và thất bại trong ứng dụng SOA và thổi SLA của bạn nếu nó xảy ra quá thường xuyên. Mặc dù trình thu thập CMS có nhiều tài nguyên hơn và không đạt được cùng một thông lượng thô, nhưng đó là lựa chọn tốt hơn nhiều vì nó có độ trễ dự đoán và nhỏ hơn nhiều.

ArrayList chỉ là một lựa chọn tốt hơn cho hiệu suất nếu tất cả những gì bạn muốn nói về hiệu suất là thông lượng và bạn có thể bỏ qua độ trễ. Theo kinh nghiệm của tôi trong công việc của tôi, tôi không thể bỏ qua độ trễ trường hợp xấu nhất.


125
2018-04-08 20:33



Sẽ không có giải pháp nào khác được quản lý kích thước của danh sách theo lập trình bằng cách sử dụng phương thức EnsureCapacity () của ArrayList không? Câu hỏi của tôi là tại sao có quá nhiều thứ được lưu trữ trong một loạt các cấu trúc dữ liệu giòn khi chúng có thể được lưu trữ tốt hơn trong một cơ chế bộ nhớ đệm hoặc db? Tôi đã có một cuộc phỏng vấn vào một ngày khác, nơi họ thề lên và xuống về những tệ nạn của ArrayList, nhưng tôi đến đây và tôi thấy rằng sự phân tích phức tạp là tất cả xung quanh tốt hơn! ĐIỂM TUYỆT VỜI CHO THẢO LUẬN, THOUGH. CẢM ƠN! - ingyhere
một khi bạn nhận được các ứng dụng java với heap 10GB, bạn có thể bắt đầu khóa ứng dụng trong 25 giây trong một GC đầy đủ gây ra timeouts Trên thực tế với LinkedList bạn giết người thu gom rác trong suốt các GC đầy đủ, nó phải lặp lại LinkedList quá lớn với bộ nhớ cache bỏ lỡ trên mỗi nút. - bestsss
Đó là ... một giải pháp khủng khiếp. bạn về cơ bản phụ thuộc vào GC làm sạch cho bạn, mà là cực kỳ tốn kém, khi bạn chỉ có thể gọi EnsureCapacity () trên một arraylist thay vì ... - Philip Devine
@Andreas: A LinkedList  luôn luôn phân bổ bộ nhớ năm lần so với một mảng tham chiếu đơn giản, vì vậy ArrayList tạm thời yêu cầu 2,5 lần vẫn tiêu tốn ít bộ nhớ hơn, ngay cả khi bộ nhớ không được khai hoang. Vì phân bổ mảng lớn bỏ qua không gian Eden, chúng không có bất kỳ tác động nào đến hành vi của GC, trừ khi thực sự không đủ bộ nhớ, trong trường hợp này, LinkedList thổi sớm hơn nhiều ... - Holger
@Andreas Vấn đề khác là cách bộ nhớ được cấp phát. LinkedListchỉ cần một phần nhỏ của bộ nhớ miễn phí để phân bổ cho phần tử tiếp theo. ArrayList sẽ cần một lượng lớn và liên tục miễn phí khối không gian để phân bổ các mảng thay đổi kích cỡ. Nếu heap bị phân mảnh, sau đó GC có thể kết thúc sắp xếp lại toàn bộ đống chỉ để giải phóng một khối bộ nhớ phù hợp. - Piotr Kusmierczyk


Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Thuật toán: Ký hiệu Big-Oh

ArrayLists là tốt cho viết-một lần đọc nhiều hoặc appenders, nhưng xấu tại thêm / loại bỏ từ phía trước hoặc giữa.


111
2018-05-19 11:21



Bạn không thể so sánh trực tiếp các giá trị lớn-O mà không suy nghĩ về các yếu tố không đổi. Đối với các danh sách nhỏ (và hầu hết các danh sách nhỏ), ArrayList's O (N) nhanh hơn O của LinkedList (1). - Porculus
Tôi không quan tâm đến hiệu suất danh sách nhỏ và máy tính của tôi cũng vậy trừ khi nó được sử dụng trong một vòng lặp bằng cách nào đó. - Maarten Bodewes
LinkedList thực sự không thể chèn ở giữa O(1). Nó phải chạy qua một nửa danh sách để tìm điểm chèn. - Thomas Ahle
LinkedList: chèn vào giữa O (1) - là WRONG! Tôi phát hiện ra rằng thậm chí chèn vào vị trí 1/10 của kích thước LinkedList là chậm hơn chèn một phần tử vào vị trí 1 / 10th của một ArrayList. Và thậm chí tệ hơn: kết thúc của bộ sưu tập. chèn vào các vị trí cuối cùng (không phải là cuối cùng) của ArrayList nhanh hơn sau đó vào các vị trí cuối cùng (không phải là cuối cùng) của LinkedList - kachanov
@kachanov Chèn vào LinkedList  Là  O(1)  nếu bạn có một iterator đến vị trí chèn, I E. ListIterator.add được cho là O(1) cho một LinkedList. - Anony-Mousse


Vâng, tôi biết, đây là một câu hỏi cổ xưa, nhưng tôi sẽ ném vào hai xu của tôi:

LinkedList mới là gần như luôn luôn sự lựa chọn sai, hiệu quả khôn ngoan. Có một số thuật toán rất cụ thể trong đó một LinkedList được gọi, nhưng chúng rất, rất hiếm và thuật toán thường sẽ phụ thuộc cụ thể vào khả năng chèn và xóa các phần tử của LinkedList ở giữa danh sách tương đối nhanh, khi bạn đã điều hướng ở đó với một ListIterator.

Có một trường hợp sử dụng phổ biến trong đó LinkedList vượt trội hơn ArrayList: đó là hàng đợi. Tuy nhiên, nếu mục tiêu của bạn là hiệu suất, thay vì LinkedList, bạn cũng nên xem xét sử dụng ArrayBlockingQueue (nếu bạn có thể xác định giới hạn trên trên kích thước hàng đợi của mình trước thời hạn và có thể phân bổ tất cả bộ nhớ lên phía trước) hoặc Triển khai CircularArrayList. (Vâng, nó là từ năm 2001, vì vậy bạn sẽ cần phải mở rộng nó, nhưng tôi có tỷ lệ hiệu suất tương đương với những gì được trích dẫn trong bài viết vừa rồi trong một JVM gần đây)


92
2017-11-27 01:39



Từ Java 6, bạn có thể sử dụng ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html - Thomas Ahle
ArrayDeque chậm hơn LinkedList trừ khi tất cả các hoạt động ở cùng một kết thúc. Đó là OK khi được sử dụng như một chồng nhưng nó không làm cho một hàng đợi tốt. - Jeremy List
Không đúng - ít nhất là để thực hiện của Oracle trong jdk1.7.0_60 và trong bài kiểm tra sau đây. Tôi tạo ra một bài kiểm tra mà tôi lặp cho 10 triệu lần và tôi có một Deque 10 triệu số nguyên ngẫu nhiên. Bên trong vòng lặp, tôi thăm dò ý kiến ​​một phần tử từ và cung cấp một phần tử không đổi. Trên máy tính của tôi, LinkedList chậm hơn 10 lần so với ArrayDeque và sử dụng ít bộ nhớ hơn). Lý do là không giống như ArrayList, ArrayDeque giữ một con trỏ đến phần đầu của mảng sao cho nó không phải di chuyển tất cả các phần tử khi đầu bị loại bỏ. - Henno Vermeulen
ArrayDeque có thể nhanh hơn Stack khi được sử dụng làm ngăn xếp và nhanh hơn LinkedList khi được sử dụng làm hàng đợi. - i_am_zero
Lưu ý rằng nhận xét của akhil_mittal là trích dẫn từ ArrayDeque tài liệu. - Stuart Marks


Đó là một câu hỏi hiệu quả. LinkedList là nhanh để thêm và xóa các phần tử, nhưng chậm để truy cập vào một phần tử cụ thể. ArrayList là nhanh để truy cập một phần tử cụ thể nhưng có thể chậm để thêm vào một trong hai đầu, và đặc biệt là chậm để xóa ở giữa.

Array vs ArrayList vs LinkedList vs Vectorđi sâu hơn, cũng như Danh sách liên kết.


50
2017-09-21 22:59





Chính xác hoặc không chính xác: Vui lòng thực hiện thử nghiệm cục bộ và tự quyết định!

Chỉnh sửa / Xóa nhanh hơn trong LinkedList hơn ArrayList.

ArrayList, được hỗ trợ bởi Array, mà cần phải được tăng gấp đôi kích thước, là tồi tệ hơn trong ứng dụng khối lượng lớn.

Dưới đây là kết quả kiểm tra đơn vị cho mỗi thao tác. Phép tính được tính bằng Nanoseconds.


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Đây là mã:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}

49
2018-04-21 00:03



ArrayList không cần phải tăng gấp đôi, chính xác. Vui lòng kiểm tra các nguồn trước. - Danubian Sailor
Cần lưu ý rằng ví dụ của bạn là thiếu sót ... Bạn đang loại bỏ khỏi chuỗi giữa: 18 + [2, 12] byte ("true0false", "true500000false"), trung bình 25 byte, là kích thước của các phần tử ở giữa. Nó được biết rằng khi kích thước byte phần tử tăng danh sách liên kết hoạt động tốt hơn, khi kích thước danh sách tăng lên, một mảng liền kề (danh sách) sẽ làm tốt hơn. Quan trọng nhất, bạn đang làm .equals () trên dây - mà không phải là một hoạt động giá rẻ. Nếu bạn thay vì sử dụng các số nguyên, tôi nghĩ rằng sẽ có một sự khác biệt. - Centril
- và đó cũng có thể là lý do tại sao có quá ít sự khác biệt để xóa / chứa. - Centril
"... tệ hơn trong ứng dụng âm lượng lớn": Đây là một sự hiểu lầm. LinkedList có nhiều chi phí bộ nhớ hơn vì vì mỗi phần tử có một đối tượng nút với năm trường. Trên nhiều hệ thống làm cho chi phí trên 20 byte. Giá trị bộ nhớ trung bình trên mỗi phần tử cho ArrayList là một từ và một nửa, làm cho 6 byte và 8 byte trong trường hợp xấu nhất. - Lii
Tôi đã thực hiện phiên bản điểm chuẩn tốt hơn ở đây, với kết quả - hiệu suất nối thêm cho danh sách mảng là giả tạo thấp cho bạn, bởi vì addAll đang đưa ra một mảng lưu trữ có kích thước ban đầu CHÍNH XÁC, do đó, chèn đầu tiên luôn kích hoạt mảng mảng. Ngoài ra, điều này bao gồm các chu kỳ khởi động để cho phép biên dịch JIT trước khi thu thập dữ liệu. - BobMcGee


ArrayList về cơ bản là một mảng. LinkedList được triển khai dưới dạng danh sách được liên kết kép.

Các get khá rõ ràng. O (1) cho ArrayList, bởi vì ArrayList cho phép truy cập ngẫu nhiên bằng cách sử dụng chỉ mục. O (n) cho LinkedList, bởi vì nó cần tìm chỉ mục đầu tiên. Lưu ý: có các phiên bản khác nhau của add và remove.

LinkedList nhanh hơn trong việc thêm và loại bỏ, nhưng chậm hơn trong có được. Tóm lại, LinkedList nên được ưu tiên nếu:

  1. không có số lượng lớn truy cập ngẫu nhiên của phần tử
  2. có một số lượng lớn các hoạt động thêm / xóa

=== Lập danh sách ===

  • thêm (E e)
    • thêm vào cuối ArrayList
    • yêu cầu thay đổi kích thước bộ nhớ.
    • O (n) tệ nhất, O (1) được khấu hao
  • thêm (int index, phần tử E)
    • thêm vào một vị trí chỉ mục cụ thể
    • yêu cầu dịch chuyển và chi phí thay đổi kích thước bộ nhớ có thể
    • Trên)
  • xóa (chỉ mục int)
    • xóa phần tử được chỉ định
    • yêu cầu dịch chuyển và chi phí thay đổi kích thước bộ nhớ có thể
    • Trên)
  • loại bỏ (Object o)
    • xóa lần xuất hiện đầu tiên của phần tử được chỉ định khỏi danh sách này
    • cần phải tìm kiếm phần tử trước, sau đó thay đổi và có thể thay đổi kích thước bộ nhớ
    • Trên)

=== LinkedList ===

  • thêm (E e)

    • thêm vào cuối danh sách
    • O (1)
  • thêm (int index, phần tử E)

    • chèn vào vị trí đã chỉ định
    • cần phải tìm vị trí đầu tiên
    • Trên)
  • tẩy()
    • xóa phần tử đầu tiên của danh sách
    • O (1)
  • xóa (chỉ mục int)
    • loại bỏ phần tử với chỉ mục được chỉ định
    • cần tìm phần tử trước
    • Trên)
  • loại bỏ (Object o)
    • loại bỏ sự xuất hiện đầu tiên của phần tử được chỉ định
    • cần tìm phần tử trước
    • Trên)

Đây là một con số từ programcreek.com (add và remove là loại đầu tiên, tức là thêm một phần tử ở cuối danh sách và xóa phần tử ở vị trí đã chỉ định trong danh sách.):

enter image description here


38
2017-11-27 01:41



"LinkedList nhanh hơn add / remove". Sai, kiểm tra câu trả lời ở trên stackoverflow.com/a/7507740/638670 - Nerrve


ArrayList có thể truy cập ngẫu nhiên, trong khi LinkedList thực sự rẻ để mở rộng và loại bỏ các yếu tố. Đối với hầu hết các trường hợp, ArrayList Ổn.

Trừ khi bạn đã tạo danh sách lớn và đo lường một nút cổ chai, có thể bạn sẽ không bao giờ cần phải lo lắng về sự khác biệt.


30
2017-07-07 09:22



LinkedList không phải là rẻ để thêm các yếu tố vào. Nó hầu như luôn luôn nhanh hơn để thêm một triệu phần tử vào một ArrayList hơn là thêm chúng vào một LinkedList. Và hầu hết các danh sách trong mã thực tế thậm chí không phải là một triệu phần tử dài. - Porculus
Tại bất kỳ thời điểm nào, bạn biết chi phí của việc thêm một mục vào LinkedList của bạn. ArrayList bạn không (nói chung). Thêm một mục vào ArrayList chứa một triệu mục có thể mất một thời gian rất dài - đó là một hoạt động O (n) cộng với gấp đôi dung lượng lưu trữ trừ khi bạn chiếm không gian. Thêm một mục vào một LinkedList là O (1). Tuyên bố cuối cùng của tôi là viết tắt. - Dustin
Thêm một mục vào ArrayList là O (1) bất kể nó là 1 triệu hay 1 tỷ. Thêm một mục vào một LinkedList cũng là O (1). "Thêm" có nghĩa là THÊM VÀO END. - kachanov
Bạn phải đọc phần thực hiện khác với tôi. Theo kinh nghiệm của tôi, việc sao chép mảng phần tử 1 tỷ sẽ mất nhiều thời gian hơn việc sao chép một mảng phần tử 1 triệu. - Dustin
@ kachanov bạn phải hiểu lầm Dustin. Trừ khi bạn đã khai báo một mảng 1 tỷ mục bạn sẽ cần phải thay đổi kích cỡ mảng của bạn, trong trường hợp này bạn sẽ cần phải sao chép tất cả các phần tử vào một mảng lớn hơn, do đó đôi khi bạn sẽ nhận được O (N). lấy O (1) - Stan R.