The fastest algorithm for returning max length of consecutive same value fields of matrix? -



The fastest algorithm for returning max length of consecutive same value fields of matrix? -

here given example:

we have function takes 1 matrix , it's number of columns , it's number of rows , returns int (this gonna length). example:

int function (int** matrix, int n, int m)

the question what's fastest algorithm implementing function returns maximum length of consecutive fields same value (doesn't matter if same values in 1 column or in 1 row, in illustration on image it's 5 fields of 1 column value 8)? values can 0-255 (grayscale example). in given illustration function should homecoming 5.

if bottleneck , matrix large, first optimization seek create 1 pass on matrix in sequential memory order (row-by-row in c or c++) rather two. because it's expensive traverse 2d array in other direction. cache , paging behavior worst possible.

for need row-sized array track number of consecutive values in current run within each column.

int function (int a[][], int m, int n) { if (n <= 0 || m <= 0) homecoming 0; int longest_run_len = 1; // accumulator homecoming value. int current_col_run_len[n]; // accumulators each column int current_row_run_len = 1; // accumulator current row. // initialize column accumulators , check first row. current_col_run_len[0] = 1; (int j = 1; j < n; j++) { current_col_run_len[j] = 1; if (a[0][j] == a[0][j-1]) { if (++current_row_run_len > longest_run_len) longest_run_len = current_row_run_len; } else current_row_run_len = 1; } // rest of rows... (int = 1; < m; i++) { // first column: if (a[i][0] == a[i-1][0]) { if (++current_col_run_len[0] > longest_run_len) longest_run_len = current_col_run_len[0]; } else current_col_run_len[0] = 1; // other columns. current_row_run_len = 1; (int j = 1; j < n; j++) { if (a[i][j] == a[i][j-1]) { if (++current_row_run_len > longest_run_len) longest_run_len = current_row_run_len; } else current_row_run_len = 1; if (a[i][j] == a[i-1][j]) { if (++current_col_run_len[j] > longest_run_len) longest_run_len = current_col_run_len[j]; } else current_col_run_len[j] = 1; } } homecoming longest_run_len; }

algorithm matrix

Comments

Post a Comment

Popular posts from this blog

Delphi change the assembly code of a running process -

Delphi change the assembly code of a running process - i'm trying alter address 00741fa5 has push test.009e721c . alter push test.009e71c8 . procedure callback; asm force $9e71c8 end; procedure tform2.btn1click(sender: tobject); var ppid :dword; pprocess : cardinal; begin getwindowthreadprocessid(findwindow(nil,pchar('test')), @ppid); pprocess := openprocess(process_all_access, false, ppid); injectasm(pprocess, $741fa5, 10, integer(@callback), 0); end; here injectasm function (with error checking) function injectasm(process: longword; injectaddress, injectsize, codeaddress, codesize : integer): pointer; var csize, rsize : integer; replaced : array of byte; jmp : array [0..4] of byte; jmpaddress : integer; nopv : byte; : integer; nbr: ulong_ptr; begin //injectsize must equal or greater 5, because need space our //(far) jmp wwxxyyzz instruction //if there's no space, inject in place of few instructions if injectsize ...
Read more

json - Hibernate and Jackson (java.lang.IllegalStateException: Cannot call sendError() after the response has been committed) -

json - Hibernate and Jackson (java.lang.IllegalStateException: Cannot call sendError() after the response has been committed) - hello have problem hibernate , jackson. have 2 pojos @entity @table(name = "users") public class user implements serializable { static final long serialversionuid = 4235637833262722256l; @id @generatedvalue private int id; @column(name = "creation_date") private date creationdate; @column(name = "first_name") private string firstname; @column(name = "last_name") private string lastname; @version @column(name = "version") private int version; @column(name = "e_mail") private string email; @column(name = "enabled") private boolean enabled; @column(name = "login") private string login; @column(name = "password") private string password; @jsonmanagedreference("role") @onetomany(mappedby = "user", cascade = cascadetype.all,fetch = fetchtyp...
Read more

C++ 11 "class" keyword -

C++ 11 "class" keyword - i've started using c++ 11 little bit more , have few questions on special uses of class keyword. know it's used declare class, there's 2 instances have seen don't understand: method<class t>(); and class class_name *var; why precede typename keyword class in first example, , keyword pointer in sec example? that known elaborated type specifier , necessary when class name "shadowed" or "hidden" , need explicit. class t { }; // love of god don't t t; t t2; if compiler smart, give these warnings: main.cpp:15:5: error: must utilize 'class' tag refer type 't' in scope t t2; ^ class main.cpp:14:7: note: class 't' hidden non-type declaration of 't' here t t; ^ if class not defined, deed forwards declaration. for example: template <typename t> void method() { using type = typename t::value_type; } method...
Read more