thời gian phức tạp hoặc chi phí ẩn của <Array Name> .length trong java

Question

Tôi đã nhìn vào một dự án trong java và tìm thấy một vòng lặp for được viết như dưới đây:

for(int i=1; i<a.length; i++) 
{ 
    ........... 
    ........... 
    ........... 
} 

Câu hỏi của tôi là: là nó tốn kém để tính toán a.length (ở đây là tên mảng)? nếu không thì làm thế nào a.length là nhận được tính nội bộ (có nghĩa là làm thế nào JVM đảm bảo O (1) truy cập vào điều này)? Tương tự như:

int length = a.length; 
for(int i=1; i<length; i++) 
{ 
    ........... 
    ........... 
    ........... 
} 

ví dụ như truy cập giá trị của biến cục bộ bên trong hàm. Cảm ơn.

Answer 1

Câu hỏi của tôi là: là nó tốn kém để tính toán a.length

số Nó chỉ là một lĩnh vực trên mảng (xem JLS section 10.7). Nó không tốn kém, và JVM biết nó sẽ không bao giờ thay đổi và có thể tối ưu hóa các vòng một cách thích hợp. (Thật vậy, tôi mong đợi một JIT tốt để nhận thấy mô hình bình thường của việc khởi tạo một biến với một số không âm, kiểm tra xem nó có nhỏ hơn length và sau đó truy cập vào mảng không - nếu nó nhận thấy điều đó, nó có thể loại bỏ kiểm tra ranh giới mảng.)

Answer 2

a.length không phải là phép tính mà chỉ đơn thuần là quyền truy cập vào trường được giữ trong mảng. Đó là loại hoạt động đọc là siêu nhanh.

Nếu mã là một phần của một phương pháp được gọi là đủ thường xuyên, gần như chắc chắn rằng trình biên dịch JIT sẽ thực hiện tối ưu hóa bạn đề xuất để làm cho nó thậm chí còn nhanh hơn.

Chênh lệch tốc độ tiềm năng bằng nano giây ở đây (có thể không có "s").

Answer 3

trong mảng java đã được sửa. Một khi bạn khai báo nó, bạn không thể thay đổi kích thước của mảng đó trong bộ nhớ (nếu bạn cố thay đổi kích thước mảng, nó sẽ tạo một mảng mới trong bộ nhớ).

Vì lý do này, chúng tôi lấy O (1) tra cứu độ dài. Như chúng ta biết tổng kích thước trong bộ nhớ của mảng. Nếu chúng ta cũng tìm kiếm kích thước trong bộ nhớ của chỉ mục đầu tiên, chúng ta có thể thực hiện một phép tính nhanh để có được độ dài ở tốc độ O (1). Bất kể mảng của chúng ta lớn đến mức nào, nó sẽ mất cùng một khoảng thời gian để tra cứu kích thước trong bộ nhớ và tra cứu kích thước của chỉ mục đầu tiên

Answer 4

Trong một mảng, length không phải là chức năng như trong List.size(). Khi bạn tạo một mảng trong java, chiều dài của nó là một hằng số. Vì vậy, chi phí tối thiểu là

Answer 5

Để thuận tiện cho bạn, tôi đã vi phạm nó. Mã này:

public class ArrayLength 
{ 
    static final boolean[] ary = new boolean[10_000_000]; 
    static final Random rnd = new Random(); 
    @GenerateMicroBenchmark public void everyTime() { 
    int sum = rnd.nextInt(); 
    for (int i = 0; i < ary.length; i++) sum += sum; 
    } 
    @GenerateMicroBenchmark public void justOnce() { 
    int sum = rnd.nextInt(); 
    final int length = ary.length; 
    for (int i = 0; i < length; i++) sum += sum; 
    } 
} 

Kết quả:

Benchmark      Mode Thr Cnt Sec   Mean Mean error Units 
o.s.ArrayLength.everyTime thrpt 1  3 5 40215.790  1490.800 ops/msec 
o.s.ArrayLength.justOnce  thrpt 1  3 5 40231.192  966.007 ops/msec 

Tóm tắt: không thay đổi được phát hiện.