2009-10-02 41 views
37

Tại sao list.size()>0 chậm hơn list.isEmpty() bằng Java? Nói cách khác, tại sao isEmpty() thích hợp hơn size()>0?Tại sao list.size()> 0 chậm hơn list.isEmpty() trong Java?

Khi tôi nhìn vào thực hiện trong ArrayList, sau đó nó trông giống như tốc độ nên được như vậy:

ArrayList.size()

/** 
    * Returns the number of elements in this list. 
    * 
    * @return the number of elements in this list 
    */ 
    public int size() { 
     return size; 
    } 

ArrayList.isEmpty()

/** 
    * Returns <tt>true</tt> if this list contains no elements. 
    * 
    * @return <tt>true</tt> if this list contains no elements 
    */ 
    public boolean isEmpty() { 
     return size == 0; 
    } 

Nếu chúng ta chỉ viết một chương trình đơn giản để dành thời gian y cả hai phương pháp, trường hợp đó size() sẽ mất thêm isEmpty() trong mọi trường hợp, tại sao lại như vậy?

Đây là Mã thử nghiệm của tôi;

import java.util.List; 
import java.util.Vector; 

public class Main { 
    public static void main(String[] args) { 
     List l=new Vector(); 
     int i=0; 
     for(i=0;i<10000;i++){ 
      l.add(new Integer(i).toString()); 
     } 
     System.out.println(i); 
     Long sTime=System.nanoTime(); 
     l.size(); 
     Long eTime=System.nanoTime(); 
     l.isEmpty(); 
     Long eeTime=System.nanoTime(); 
     System.out.println(eTime-sTime); 
     System.out.println(eeTime-eTime); 
    } 
} 

Ở đây eTime-sTime>eeTime-eTime trong mọi trường hợp. Tại sao?

Trả lời

46

Mã thử nghiệm của bạn bị thiếu sót.

Chỉ cần đảo ngược thứ tự, tức là cuộc gọi làEmpty đầu tiên và kích thước> 0 giây và bạn sẽ nhận được kết quả đối diện với kết quả. Điều này là do quá trình tải lớp, lưu vào bộ nhớ cache, v.v.

+1

@ JLR: Có tôi chấp nhận quan điểm của bạn, có lỗ hổng, như thử nghiệm cả hai phương pháp trong 2 dự án riêng biệt và cả hai đều cho kết quả tương tự nhau. Thanx để xóa bỏ sự nghi ngờ của tôi –

1

Đếm các mục trong danh sách được liên kết có thể rất chậm.

+0

@spdenme: nhưng nó không đếm, nó chỉ trả về một giá trị? –

+0

Trong ví dụ của bạn, bạn có danh sách * ArrayList * –

+0

là một giao diện. Làm thế nào nó được thực hiện ảnh hưởng đến hiệu suất tương đối của hai phương pháp. Vì size() là một phương thức thường được gọi, hầu hết các triển khai quyết định chi phí của việc duy trì một trường kích thước là đáng giá. –

66

Đối với ArrayList s, vâng - bạn có quyền thực hiện các hoạt động (gần) cùng một lúc.

Đối với các triển khai danh sách khác - danh sách liên kết ngây thơ *, ví dụ - việc đếm kích thước có thể mất một thời gian rất dài, trong khi bạn chỉ thực sự quan tâm xem nó có lớn hơn 0 không.

Vì vậy, nếu bạn hoàn toàn biết rằng danh sách là triển khai ArrayList và sẽ không bao giờ thay đổi thì nó không thực sự quan trọng; nhưng:

  1. thực tiễn lập trình kém này là tự buộc bạn thực hiện cụ thể.
  2. Nếu mọi thứ thay đổi một vài năm xuống phù hợp với chuyển dịch cơ cấu mã, thử nghiệm sẽ cho thấy rằng "hoạt động" nhưng mọi thứ đang chạy ít hiệu quả hơn trước
  3. Ngay cả trong trường hợp tốt nhất, size() == 0 vẫn không phải là nhanh hơn isEmpty() , vì vậy không có lý do thuyết phục để sử dụng trước đây.
  4. isEmpty là định nghĩa rõ ràng hơn về những gì bạn thực sự quan tâm và đang thử nghiệm, do đó làm cho mã của bạn dễ hiểu hơn một chút.

(Ngoài ra, tôi muốn xem xét lại việc sử dụng NULL trong tiêu đề câu hỏi của bạn, câu hỏi chính nó, và các hoạt động này, không có gì để làm với việc bất kỳ đối tượng tài liệu tham khảo là null.)

* tôi ban đầu đã viết LinkedList ở đây, ngụ ý tham chiếu java.util.LinkedList, mặc dù triển khai cụ thể đó lưu trữ chiều dài của nó một cách rõ ràng, làm cho kích thước() một hoạt động O (1) ở đây. Một hoạt động danh sách liên kết ngây thơ hơn có thể không làm điều này, và theo nghĩa rộng hơn thì không có đảm bảo hiệu quả về việc triển khai Danh sách.

+5

"' LinkedList' (a.k.a 'java.util.LinkedList') cũng lưu trữ kích thước của nó để cuộc gọi' size() 'chỉ nhanh như đối với' ArrayList', nhưng điểm chung vẫn còn rất hợp lệ. –

+0

@dtszzs: Thời gian chạy không giống nhau, đó là những gì tôi đã thử nghiệm và chỉ khiến tôi không thoải mái .. –

+4

@Sam Rudolph: bạn đã thử nghiệm nó như thế nào? Có hàng ngàn cách để có được các dấu hiệu vi sinh như vậy sai. –

2

Với hai lần triển khai đó, tốc độ phải giống nhau, điều đó là đúng.

Nhưng đó không phải là cách triển khai duy nhất có thể cho các phương pháp này. Danh sách được liên kết nguyên thủy (danh sách không lưu trữ kích thước riêng biệt) ví dụ có thể trả lời isEmpty() nhanh hơn nhiều so với cuộc gọi size().

Quan trọng hơn: isEmpty() mô tả chính xác ý định của bạn, trong khi size()==0 là phức tạp không cần thiết (không quá phức tạp), nhưng tránh mọi phức tạp không cần thiết).

+0

but6 nếu u thấy có thực hiện, những người trông rất rất đơn giản? –

+0

Những cái bạn nhìn vào, vâng. Nhưng như @dtsazza đã giải thích khá rõ: việc triển khai không phải là điều quan trọng duy nhất, mục đích và khả năng đọc cũng rất quan trọng. Và có thể có các triển khai Collectons khác trong đó 'size()' có thể không được triển khai dễ dàng ('WeakHashMap' hoặc các bộ sưu tập động khác). –

5

Bạn nói:

Đây eTime-sTime>eeTime-eTime trong mọi trường hợp Tại sao?

Trước hết, có thể là do mã thử nghiệm của bạn. Bạn không thể kiểm tra tốc độ gọi l.size() và l.isEmpty() cùng một lúc, vì cả hai đều truy vấn cùng một giá trị. Rất có thể gọi l.size() đã tải kích thước danh sách của bạn vào bộ nhớ cache cpu và gọi l.isEmpty() nhanh hơn rất nhiều.

Bạn có thể thử gọi l.size() vài triệu lần và l.isEmpty() vài triệu lần trong hai chương trình riêng biệt nhưng về lý thuyết trình biên dịch chỉ có thể tối ưu hóa tất cả các cuộc gọi đó kể từ khi bạn ' không thực sự làm bất cứ điều gì với kết quả.

Trong mọi trường hợp, sự khác biệt về hiệu suất giữa hai điều này sẽ không đáng kể, đặc biệt khi bạn so sánh bạn cần làm để xem danh sách có trống không (l.size() == 0). Nhiều khả năng mã được tạo sẽ trông gần như hoàn toàn giống nhau. Như một số áp phích khác lưu ý, bạn muốn tối ưu hóa cho khả năng đọc trong trường hợp này, không phải tốc độ.

chỉnh sửa: Tôi đã tự mình thử nghiệm. Đó là khá nhiều một toss-up. size()isEmpty() được sử dụng trên Vector cho kết quả khác nhau về thời gian dài, không đánh bại kết quả khác một cách nhất quán. Khi chạy trên ArrayListsize() có vẻ nhanh hơn, nhưng không nhiều. Điều này rất có thể do thực tế rằng quyền truy cập vào Vector được đồng bộ hóa, vì vậy những gì bạn thực sự thấy khi cố gắng truy cập điểm chuẩn cho các phương thức này là phí đồng bộ hóa, có thể rất nhạy cảm.

Điều cần lưu ý ở đây là khi bạn đang cố gắng tối ưu hóa cuộc gọi phương thức với chênh lệch vài giây nano trong thời gian thực hiện, thì bạn đang làm sai sai. Nhận thông tin cơ bản ngay trước tiên, như sử dụng Long s nơi bạn nên sử dụng long.

+0

không thực sự chỉ không phải tôi chạy hai trường hợp trong các chương trình riêng biệt chỉ để rõ ràng các nghi ngờ và kết quả là cùng một kích thước() là lấy thời gian chạy nhiều hơn 10 lần so với isEmpty() –

15

Tôi xin lỗi, nhưng điểm chuẩn của bạn là thiếu sót. Hãy xem Java theory and practice: Anatomy of a flawed microbenchmark để có mô tả chung về cách tiếp cận điểm chuẩn.


Cập nhật: cho một chuẩn mực thích hợp, bạn nên xem xét Japex.

+0

Java.net dường như đã ngừng hoạt động ngay bây giờ. –

0

Không thể nói chung là nhanh hơn, bởi vì nó phụ thuộc vào việc thực hiện giao diện List bạn đang sử dụng.

Giả sử chúng ta đang nói về ArrayList. Tra cứu mã nguồn của ArrayList, bạn có thể tìm thấy nó trong tệp src.zip trong thư mục cài đặt JDK của bạn. Mã nguồn của các phương pháp isEmptysize trông như sau (Sun JDK 1.6 cập nhật 16 dành cho Windows):

public boolean isEmpty() { 
    return size == 0; 
} 

public int size() { 
    return size; 
} 

Bạn có thể dễ dàng thấy rằng cả hai biểu thức isEmpty()size() == 0 sẽ đi xuống một cách chính xác những điều khoản tương tự, vì vậy một chắc chắn không nhanh hơn cái kia.

Nếu bạn quan tâm đến cách hoạt động cho các triển khai khác của giao diện List, hãy tự tìm mã nguồn và tìm hiểu.

1

Theo PMD (bộ phân tích mã nguồn Java dựa trên quy tắc tĩnh) isEmpty() được ưu tiên. Bạn có thể tìm thấy bộ quy tắc PMD tại đây. Tìm kiếm quy tắc "UseCollectionIsEmpty".

http://pmd.sourceforge.net/rules/design.html

Theo tôi nó cũng giúp trong việc giữ toàn bộ mã nguồn phù hợp chứ không phải là một nửa trong số các folks sử dụng isEmpty() và phần còn lại sử dụng kích thước() == 0.

2

.size() phải xem toàn bộ danh sách, trong khi .isEmpty() có thể dừng ở danh sách đầu tiên.

Rõ ràng là thực hiện phụ thuộc, nhưng như đã nói trước đây, nếu bạn không cần biết kích thước thực tế, tại sao phải tính toán tất cả các yếu tố?

Các vấn đề liên quan