Ví dụ:Java: mảng đa chiều vs Một chiều
một)int [x][y][z]
vs
b)int[x*y*z]
Ban đầu tôi nghĩ rằng tôi muốn đi với a) để đơn giản
Tôi biết rằng Java không lưu trữ các mảng tuyến tính trong bộ nhớ như C. Nhưng điều này có ý nghĩa gì đối với chương trình của tôi?
Thường thì điều tuyệt vời nhất để làm gì khi tìm kiếm anwers cho các câu hỏi như vậy là để xem làm thế nào lựa chọn được biên dịch vào JVM bytecode:
multi = new int[50][50];
single = new int[2500];
này được dịch sang:
BIPUSH 50
BIPUSH 50
MULTIANEWARRAY int[][] 2
ASTORE 1
SIPUSH 2500
NEWARRAY T_INT
ASTORE 2
Vì vậy, như bạn có thể thấy, JVM đã biết rằng chúng ta đang nói về một mảng đa chiều.
Giữ nó tiếp tục:
for (int i = 0; i < 50; ++i)
for (int j = 0; j < 50; ++j)
{
multi[i][j] = 20;
single[i*50+j] = 20;
}
này được dịch (bỏ qua các chu kỳ) vào:
ALOAD 1: multi
ILOAD 3: i
AALOAD
ILOAD 4: j
BIPUSH 20
IASTORE
ALOAD 2: single
ILOAD 3: i
BIPUSH 50
IMUL
ILOAD 4: j
IADD
BIPUSH 20
IASTORE
Vì vậy, như bạn có thể thấy, mảng đa chiều được xử lý cục bộ trong máy ảo, không có chi phí nào được tạo ra bởi các hướng dẫn vô dụng, trong khi sử dụng một thiết bị duy nhất sử dụng thêm hướng dẫn vì bù đắp được tính bằng tay.
Tôi không nghĩ rằng hiệu suất đó sẽ là vấn đề như vậy.
EDIT:
tôi đã làm một số tiêu chuẩn đơn giản để xem những gì đang xảy ra ở đây. Tôi đã chọn thử các ví dụ khác nhau: đọc tuyến tính, viết tuyến tính, và truy cập ngẫu nhiên. Thời gian được biểu thị bằng millisec (và được tính bằng System.nanoTime(). Dưới đây là kết quả:
tuyến tính viết
tuyến tính đọc
ngẫu nhiên đọc
Lý do ngẫu nhiên là một chút sai lệch vì nó tạo ra 2 số ngẫu nhiên cho mảng đa chiều trong khi chỉ một cho một chiều (và PNRG có thể tiêu thụ một số CPU).
Hãy nhớ rằng tôi đã cố gắng để JIT hoạt động bằng cách đo điểm chuẩn chỉ sau lần chạy thứ 20 của cùng một vòng lặp. Cho đầy đủ java của tôi VM như sau:
phiên bản java "1.6.0_17" Java (TM) SE Runtime Environment (xây dựng 1.6.0_17-b04) Java HotSpot (TM) 64-Bit Server VM (xây dựng 14,3-b01, chế độ hỗn hợp)
Luôn luôn tốt đẹp để xem ai đó nhìn vào thực tế dưới mui xe thay vì chỉ đưa ra giả định. Tôi sẽ cung cấp cho bạn 100 nếu tôi có thể. –
Khi mã được trích xuất, số lượng lệnh JVM không liên quan. Điều quan trọng là bao nhiêu thời gian thực tế mã chạy, mà sẽ phụ thuộc vào những thứ như địa phương, dereferencing, và sử dụng bộ nhớ. – Gabe
Vui lòng cập nhật điểm chuẩn đọc ngẫu nhiên để tạo ra 2 số ngẫu nhiên cho cả hai phiên bản. Có lẽ phiên bản mảng đơn thậm chí sẽ nhanh hơn, vì yêu cầu ít bộ nhớ hơn (đọc ngẫu nhiên sẽ tạo ra nhiều bộ nhớ cache nhất), nhưng bạn không bao giờ có thể chắc chắn trước khi đo nó. –
Nếu bạn chọn tuyến đường thứ hai thì bạn sẽ phải thực hiện số học cho mỗi lần truy cập mảng đơn lẻ. Đó sẽ là một nỗi đau và dễ bị lỗi (trừ khi bạn quấn nó trong một lớp học cung cấp chức năng này).
Tôi không tin rằng có bất kỳ (đáng kể) tối ưu hóa trong việc lựa chọn mảng phẳng của bạn (đặc biệt là cho các số học được đưa vào chỉ mục vào nó). Như mọi khi với sự tối ưu hóa, bạn sẽ cần phải thực hiện một số phép đo và xác định xem nó có thực sự đáng giá không.
Ok, cảm ơn. Tôi sẽ sử dụng một mảng 3 chiều, và nếu tôi có vấn đề về hiệu suất thì nó sẽ so sánh. – Mikolan
Nếu bạn sử dụng một mảng đa chiều, thì bạn sẽ phải thực hiện một số truy cập bộ nhớ cho mỗi truy cập mảng đơn, điều này có thể giúp tôi * buch * chậm hơn một số học nhỏ. Nhưng vâng, với loại điều bạn thực sự cần đo trước khi hành động. –
Sử dụng phiên bản đầu tiên (3 chiều) vì nó dễ dàng hơn để tìm hiểu và có ít cơ hội để thực hiện một số lỗi logic (đặc biệt là nếu bạn đang sử dụng nó cho mô hình không gian 3 chiều)
Trên các CPU hiện tại, truy cập bộ nhớ non-cached là hàng trăm lần chậm hơn so với arithmetics (xem this presentation và đọc What every programmer should know about memory). Tùy chọn a) sẽ dẫn đến khoảng 3 lần tra cứu bộ nhớ trong khi tùy chọn b) sẽ dẫn đến khoảng 1 lần tra cứu bộ nhớ. Ngoài ra các thuật toán tìm nạp trước của CPU cũng có thể không hoạt động. Vì vậy, tùy chọn b) có thể nhanh hơn trong một số trường hợp (đó là điểm nóng và mảng không vừa với bộ nhớ cache của CPU). Nhanh hơn bao nhiêu? - điều đó sẽ phụ thuộc vào ứng dụng.
Cá nhân tôi trước tiên sẽ sử dụng tùy chọn a), vì nó sẽ dẫn đến mã đơn giản hơn. Nếu một profiler cho thấy truy cập mảng là một nút cổ chai, thì tôi sẽ chuyển nó thành tùy chọn b), để có một cặp phương thức trợ giúp để đọc và ghi các giá trị mảng (theo cách đó mã lộn xộn sẽ bị hạn chế đối với hai phương pháp).
Tôi đã tạo điểm chuẩn để so sánh mảng int 3 chiều (cột "Đa") với mảng int 1 chiều tương đương (cột "Đơn"). Mã số là here và kiểm tra here. Tôi chạy nó trên 64-bit jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 @ 3,0 GHz, 4 GB DDR2, sử dụng các tùy chọn JVM -server -Xmx3G -verbose:gc -XX:+PrintCompilation (Tôi đã gỡ bỏ kết xuất gỡ lỗi khỏi các kết quả sau). Kết quả là:
Out of 20 repeats, the minimum time in milliseconds is reported.
Array dimensions: 100x100x100 (1000000)
Multi Single
Seq Write 1 1
Seq Read 1 1
Random Read 99 90 (of which generating random numbers 59 ms)
Array dimensions: 200x200x200 (8000000)
Multi Single
Seq Write 14 13
Seq Read 11 8
Random Read 1482 1239 (of which generating random numbers 474 ms)
Array dimensions: 300x300x300 (27000000)
Multi Single
Seq Write 53 46
Seq Read 34 24
Random Read 5915 4418 (of which generating random numbers 1557 ms)
Array dimensions: 400x400x400 (64000000)
Multi Single
Seq Write 123 111
Seq Read 71 55
Random Read 16326 11144 (of which generating random numbers 3693 ms)
Điều này cho thấy mảng 1 chiều nhanh hơn. Mặc dù sự khác biệt quá nhỏ, nhưng đối với 99% các ứng dụng, nó sẽ không đáng chú ý.
Tôi cũng đã thực hiện một số phép đo để tạo ra các số ngẫu nhiên trong chuẩn đọc ngẫu nhiên bằng cách thay thế preventOptimizingAway += array.get(x, y, z); bằng preventOptimizingAway += x * y * z; và thêm các phép đo vào bảng kết quả ở trên bằng tay. Việc tạo các số ngẫu nhiên chiếm 1/3 hoặc ít hơn tổng thời gian của chuẩn Đọc ngẫu nhiên, do đó truy cập bộ nhớ chiếm ưu thế điểm chuẩn như mong đợi. Sẽ rất thú vị khi lặp lại điểm chuẩn này với các mảng có từ 4 chiều trở lên. Có lẽ nó sẽ làm cho sự khác biệt tốc độ lớn hơn, bởi vì các cấp cao nhất của đa chiều sẽ phù hợp với bộ nhớ cache của CPU, và chỉ các mức khác sẽ yêu cầu tra cứu bộ nhớ.
Xem thêm: http://stackoverflow.com/questions/2368761/performance-comparison-of-array-of-arrays-vs-multidimensional-arrays – polygenelubricants