Mảng nhanh nhất giải quyết

Question

Tôi đang chạy mã phân tích hình ảnh trên một mảng lưu trữ thông tin về hình ảnh. Thật không may, mã này rất nặng và mất trung bình 25 giây để chạy qua một khung hình duy nhất. Vấn đề chính tôi thấy là việc giải quyết mảng. Đó là cách nhanh nhất để chạy thông qua một mảng 2ngày và đang có ở tất cả bất kỳ sự khác biệt trong

ngang sau đó dọc

for (int y = 0; y < array.Length; ++y) 
    for (int x = 0; x < array[].Length; ++x) 
     //Code using array[y][x] 

và dọc sau đó horrizontal?

for (int x = 0; x < array[].Length; ++x) 
    for (int y = 0; y < array.Length; ++y) 
     //Code using array[y][x] 

Hơn nữa, tôi cố gắng tránh sử dụng trực tiếp và sử dụng con trỏ.

for (int y = 0; y < array.Length; ++y) 
    int* ptrArray = (int*)array[0]; 
    for (int x = 0; x < array[].Length; ++x, ++ptrArray) 
     //Code using ptrArray for array[y][x] 

hoặc

for (int x = 0; x < array[].Length; ++x) 
    int* ptrArray = (int*)array[0]; 
    for (int y = 0; y < array.Length; ++y, ptrArray += array[].Length) 
     //Code using ptrArray for array[y][x] 

Any help is appreciated rất nhiều. Max

Answer 1

Một lựa chọn là sử dụng ngược looping (bắt đầu for() loop của bạn từ array.Length xuống 0)

Điều đó sẽ đẩy mọi thứ lên Abit.

ví dụ,

for (int x = array[].Length-1; x >= 0; --x) 
    int* ptrArray = (int*)array[0]; 
    for (int y = array.Length-1; y >= 0 ; --y, ptrArray += array[].Length) 
     //Code using ptrArray for array[y][x] 

Answer 2

Tôi không có ý tưởng, nhưng bạn đã đưa ra các ví dụ. Vì vậy, bạn có thể chạy các mẫu mã của bạn trong một vòng lặp và cấu hình nó cho mình.

var sw = new Stopwatch(); 
sw.Start(); 
ExecuteMyCode(); 
sw.Stop(); 
Console.WriteLine("Time: " + sw.Elapsed); 

Bạn có thể tăng tốc quá trình xử lý bằng cách sử dụng cấu trúc đa luồng like Parallel.ForEach. Điều này sẽ làm việc tốt nếu mã trong vòng lặp của bạn tránh sự phụ thuộc giữa lặp vòng lặp.

Answer 3

Bạn có thể không an toàn không? Con trỏ. Vấn đề với mảng là bạn STILL có kiểm tra ranh giới trên mọi truy cập. Con trỏ loại bỏ điều đó. Lưu ý rằng điều này hoàn toàn được C# hỗ trợ - nhưng bạn cần phải đặt nó vào một khối không an toàn. Điều này cũng có nghĩa là bạn phải ABLE để chạy mã không an toàn, không phải lúc nào cũng là một mã nhất định.

http://msdn.microsoft.com/en-us/library/28k1s2k6.aspx

có mẫu mã.

Answer 4

Nếu có thể, hãy cố gắng phân bổ lại mảng của bạn để thứ nguyên đầu tiên nhỏ hơn thứ hai. Nó sẽ tăng tốc độ mọi thứ một cách quyết liệt. Một giải pháp khác là phân bổ lại dữ liệu trong một mảng đơn chiều như đã được đề xuất ở trên.

Answer 5

Luôn đảm bảo rằng vòng lặp trong cùng của bạn truy cập bộ nhớ tiếp giáp.

Đây thường là hàng của hình ảnh của bạn. Lưu ý rằng trong các mảng hình chữ nhật, bạn nên tạo chỉ mục cuối cùng này: array[y,x].

this paper cho thấy các mảng hình chữ nhật C# có sẵn (có nhiều chỉ mục) khá chậm. Tôi đã đọc nó trước đây, nhưng đây là tài liệu tham khảo duy nhất tôi có. Tôi sẽ bắt đầu với một mảng tuyến tính và tính toán một lần cho mỗi hàng. Không được quản lý sẽ chỉ giúp bạn trong các trường hợp thực sự tầm thường.

Nếu một khung đơn mất 25 giây, sau đó nó là một trong hai huuuuge, hoặc bạn làm chế biến rất phức tạp. Trong trường hợp đó, thật thú vị khi dành nỗ lực tối ưu hóa truy cập bộ nhớ nếu bạn truy cập nhiều pixel đầu vào cho mỗi pixel đầu ra.

Answer 6

Quy tắc quan trọng nhất là tất cả lý thuyết cho đến khi bạn lập hồ sơ. Tôi không giữ với những người nhấn mạnh rằng hồ sơ là tất cả mọi thứ (không có lý thuyết nào đó bạn không tốt hơn là một người trồng hàng hóa đặt dừa trên tai và đợi máy bay đến) nhưng lý thuyết của bạn luôn có thể sai hoặc không đầy đủ, hồ sơ là rất quan trọng.

Nói chung, chúng tôi muốn các nội quét là theo chiều ngang (về mảng, chứ không phải là hình ảnh, mặc dù đối với hầu hết các định dạng đó là như nhau). Lý do được rằng với một mảng như:

00 01 02 03 04 05 06 07 08 09 
10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 

Nó sẽ được đặt ra như:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 

Bạn muốn trở thành quét cùng khối tiếp giáp có thể được nạp vào bộ nhớ đệm CPU và sau đó sử dụng hoàn toàn, thay vì quét từ khối để chặn và cần phải thường xuyên thay đổi nội dung bộ nhớ cache CPU.

Điều này thậm chí còn quan trọng hơn nếu bạn cố gắng song song thuật toán. Bạn muốn mỗi luồng xử lý các khối liên tiếp của bộ nhớ của nó theo cả đầu vào và đầu ra đi, thay vì không chỉ theo cách mã đơn luồng làm việc với tần suất truy cập bộ nhớ cache kém mà còn khiến bộ đệm của nhau bị bẩn và cần làm mới. Điều này có thể là sự khác biệt giữa song song dẫn đến tăng tốc và song song thực sự làm chậm những thứ xuống.

Một điều khác là sự khác biệt giữa mảng 2 chiều byte[,] thay vì mảng mảng byte[][], nhận xét của bạn trong câu hỏi "mảng [y] [x]" khiến tôi tự hỏi liệu có lẽ bạn đang sử dụng hay không. Với cựu để có được arr [1,2] logic là:

1. Kiểm tra Bounds
2. vị trí Tính (đơn giản số học nhanh)
3. Lấy giá trị.

Với trường hợp sau, logic là:

1. Kiểm tra giới hạn
2. Lấy mảng thông qua con trỏ.
3. Kiểm tra giới hạn
4. Lấy giá trị.

Ngoài ra còn có ít bộ nhớ cache-hit-frequence tốt hơn. Sau này có lợi ích khi cấu trúc "lởm chởm" là cần thiết, nhưng đó không phải là trường hợp ở đây. 2D hầu như luôn nhanh hơn mảng mảng.

Những điều tôi không thấy như có khả năng giúp đỡ, nhưng tôi chắc chắn sẽ thử chúng trong tình huống của bạn:

Bạn có thể tìm thấy một sự thúc đẩy từ làm 1d < => 2d logic của bạn. Có mảng đơn chiều, trong đó idx = y * width + x. Nó không nên tạo sự khác biệt đáng kể, nhưng nó đáng để thử.

Tối ưu hóa cố gắng cả hai cuộc gọi đến .Length và bỏ qua việc kiểm tra không cần thiết, vì vậy bạn có thể tìm kiếm thủ công và chuyển sang số học con trỏ không đạt được bất kỳ điều gì, nhưng trong trường hợp bạn thực sự cần phải giảm thời gian xuống chắc chắn là đáng giá.

Cuối cùng. Bạn đã lược tả tốc độ mã của bạn đang quét mảng và không làm gì cả? Nó có thể là một phần khác của mã là nút cổ chai thực sự, và bạn đang sửa chữa những điều sai trái.