So sánh hiệu suất mảng mảng so với mảng đa chiều

Question

Khi tôi đang sử dụng C++ ở đại học, tôi được yêu cầu sử dụng mảng đa chiều (MDA) bất cứ khi nào có thể, vì nó thể hiện vị trí bộ nhớ tốt hơn vì nó được phân bổ trong một đoạn lớn. Mảng mảng (AoA), mặt khác, được phân bổ trong nhiều khối nhỏ hơn, có thể nằm rải rác khắp nơi trong bộ nhớ vật lý bất cứ nơi nào vị trí tuyển dụng được tìm thấy.

Vì vậy, tôi đoán câu hỏi đầu tiên là: đây có phải là một huyền thoại hay đây có phải là lời khuyên đáng giá không?

Giả sử rằng đó là câu hỏi sau, thì câu hỏi tiếp theo sẽ là phải làm gì trong một ngôn ngữ như Java không có MDA thực. Nó không phải là khó để thi đua MDA với một 1DA, tất nhiên. Về cơ bản, đường cú pháp cho ngôn ngữ với MDA có thể được thực hiện như là hỗ trợ thư viện cho các ngôn ngữ không có MDA.

Đây có phải là nỗ lực đáng giá không? Đây có phải là mức độ quá thấp của một vấn đề tối ưu hóa cho một ngôn ngữ như Java không? Chúng ta có nên từ bỏ mảng và sử dụng List s ngay cả đối với nguyên thủy không?

---

Câu hỏi khác: trong Java, không phân bổ AoA cùng một lúc (new int[M][N]) có thể mang lại một cấp phát bộ nhớ khác với làm việc đó theo thứ bậc (new int[M][]; for (... new int[N])?

Answer 1

Java và C# cấp phát bộ nhớ theo nhiều cách khác nhau mà C++ thực hiện. Trong thực tế, trong .NET chắc chắn tất cả các mảng của AoA sẽ được đóng lại với nhau nếu chúng được phân bổ cái khác bởi vì bộ nhớ chỉ có một đoạn liên tục mà không có bất kỳ phân mảnh nào.

Nhưng điều này vẫn đúng đối với C++ và vẫn hợp lý nếu bạn muốn tốc độ tối đa. Mặc dù bạn không nên làm theo lời khuyên đó mỗi lần bạn muốn mảng đa chiều, bạn nên viết mã duy trì trước và sau đó cấu hình nó nếu nó chậm, tối ưu hóa sớm là gốc cho mọi điều ác trong thế giới này.

Answer 2

Tôi sẽ không lãng phí nỗ lực sử dụng mảng 1D dưới dạng mảng đa mảng trong Java vì không có cú pháp để trợ giúp. Tất nhiên người ta có thể định nghĩa các hàm (phương thức) để ẩn công việc cho bạn, nhưng bạn chỉ kết thúc với một cuộc gọi hàm thay vì theo sau một con trỏ khi sử dụng một mảng các mảng. Ngay cả khi trình biên dịch/thông dịch viên tăng tốc độ này cho bạn, tôi vẫn không nghĩ rằng nó là giá trị nỗ lực. Ngoài ra, bạn có thể gặp phải các biến chứng khi cố gắng sử dụng mã mong đợi các mảng 2D (hoặc N-Dim) mong đợi như mảng của mảng. Tôi chắc chắn rằng hầu hết các mã chung ra sẽ được viết cho các mảng như thế này trong Java. Ngoài ra, người ta có thể gán lại các hàng (hoặc các cột nếu bạn quyết định nghĩ như thế).

Nếu bạn biết rằng mảng đa phương thức này là một nút cổ chai, bạn có thể bỏ qua những gì tôi đã nói và xem liệu tối ưu hóa theo cách thủ công có giúp ích hay không.

Answer 3

Đây có phải là nỗ lực không? Đây có phải là mức độ quá thấp của một vấn đề tối ưu hóa cho một ngôn ngữ như Java không?

Nói chung, nó không phải là giá trị nỗ lực. Chiến lược tốt nhất để quên vấn đề này trong phiên bản đầu tiên của ứng dụng và thực hiện theo cách thẳng tiến (tức là dễ bảo trì). Nếu phiên bản đầu tiên chạy quá chậm đối với các yêu cầu của bạn, hãy sử dụng công cụ lược tả để tìm các nút cổ chai của ứng dụng. Nếu lược tả cho thấy mảng mảng có thể là vấn đề, hãy thực hiện một số thí nghiệm để thay đổi cấu trúc dữ liệu của bạn thành các mảng đa chiều được mô phỏng và cấu hình xem nó có tạo ra sự khác biệt đáng kể hay không. [Tôi nghi ngờ rằng nó sẽ không tạo ra nhiều khác biệt. Nhưng điều quan trọng nhất là không lãng phí thời gian của bạn để tối ưu hóa thứ gì đó không cần thiết.]

Chúng ta có nên từ bỏ mảng và sử dụng Danh sách ngay cả đối với nguyên thủy không?

Tôi sẽ không đi xa đến thế. Giả sử rằng bạn đang đối phó với mảng có kích thước định trước:

• mảng của các đối tượng sẽ được một chút nhanh hơn so với danh sách tương đương của các đối tượng, và
• mảng của nguyên thủy sẽ nhanh hơn đáng kể và sẽ chiếm nhiều chỗ ít hơn nhiều so với tương đương danh sách các trình bao bọc nguyên thủy.

Mặt khác, nếu ứng dụng của bạn cần "phát triển" mảng, sử dụng Danh sách sẽ đơn giản hóa mã của bạn.

Answer 4

Từ kinh nghiệm cá nhân trong Java, mảng đa chiều chậm hơn nhiều so với mảng một chiều nếu một tải một lượng lớn dữ liệu hoặc truy cập các phần tử trong dữ liệu ở các vị trí khác nhau. Tôi đã viết một chương trình chụp ảnh màn hình ở định dạng BMP và sau đó tìm kiếm ảnh chụp màn hình cho một hình ảnh nhỏ hơn. Tải ảnh chụp màn hình (khoảng 3 mb) vào một mảng đa chiều (ba chiều, [xPos] [yPos] [màu] (với màu = 0 là giá trị màu đỏ, và như vậy)) mất 14 giây. Để tải nó vào một mảng một chiều mất 1 giây. Mức tăng cho việc tìm kiếm hình ảnh nhỏ hơn trong hình ảnh lớn hơn là tương tự. Mất khoảng 28 giây để tìm hình ảnh nhỏ hơn trong hình ảnh lớn hơn khi cả hai hình ảnh được lưu trữ dưới dạng mảng đa chiều. Mất khoảng một giây để tìm hình ảnh nhỏ hơn trong hình ảnh lớn hơn khi cả hai hình ảnh được lưu trữ dưới dạng mảng một chiều. Điều đó nói rằng, lần đầu tiên tôi đã viết chương trình của tôi bằng cách sử dụng một mảng chiều để có thể đọc được.