matrix - Calculate highest row sum in efficient way -


hi trying solve 1 problem. have m*n matrix. integer matrix 0 , 1 only.i want find out row sum of elements highest. solve simple solution. using 2 loops , calculating sum of each row. want find more efficient way this. 1 have idea it. need optimized solution. thank you.

let's consider 2 elements in different rows of matrix. pick two, doesn't matter ones long not in same row. set every other element of matrix zero. can choose row answer writing 1 in 1 of our chosen elements , 0 in other.

what says me in worst case, no matter how clever are, may have examine o(m*n) elements of matrix in order find 1 has sole non-zero value. can never have better worst-case running time o(m*n).

but can short-circuit procedure in cases. suppose far, highest sum of elements in row have examined far x. examining new row containing n elements. if, time have examined k of elements, sum of k elements less x - n + k, know sure sum of elements in row less x, , not need @ row further.

this algorithm still o(mn) in worst case, under reasonable assumptions contents of matrix, mean (average) running time less naive algorithm applied same matrix. can done parallel processing, although think lead more steps (on average), albeit divided on more processors. is, i'd expect "speedup factor" less number of processors used.


Comments

Post a Comment

Popular posts from this blog

javascript - RequestAnimationFrame not working when exiting fullscreen switching space on Safari -

request animation frame stops working when exiting fullscreen clicking on original space's safari window. fine if fullscreen mode canceled escape key or calling cancelfullscreen(). steps reproduce: open https://dl.dropboxusercontent.com/u/769042/prezi/safari-fullscreen.html click "draw raf", kittie appears click "fullscreen", go fullscreen click "draw raf", kittie appears go space original safari was, showing "click exit fullscreen mode", click anywhere, out fullscreen click "draw raf", nothing happens what handling click calling: window.requestanimationframe(draw); which draws on canvas context: function draw() { ctx.drawimage(img, math.random()*500|0, math.random()*400|0, 100, 100); } i checked .hidden , .visibilitystate, updated correctly. tested on osx 10.9.3, safari 7.0.4 (9537.76.4). has workaround/solution other switching old settimeout? this sounds webkit bug 88940 : using reque
Read more

Python ctypes access violation with const pointer arguments -

i have api i'm trying wrap in python (2.7.6 on win7) code using ctypes. here's api: client_dllfunc bool clientapi search_exporttoclipcopy(clienthsearch handle, int channel, lpctstr filename, const time_t& from, const time_t& to, const bool* cameras, int length, bool usepassword, lpctstr password, bool includetextin = false, bool excludeplayer = false); the issue i'm having cameras argument; , i've had issue other const pointer arguments well. here's how i'm wrapping api: def search_exporttoclipcopy(self, hsearch, csearch, filename, tfrom, tto, cameras, length, usepassword, password, includetextin=true, excludeplayer=false): exporttoclipcopy = self.sdkdll.search_exporttoclipcopy exporttoclipcopy.argtypes = [c_int, c_int, c_wchar_p, c_long, c_long, pointer(c_bool), c_int, c_bool, c_wchar_p, c_bool, c_bool] exporttoclipcopy.restype = c_bool exporttoclipcopy(hsearch, csearch, filename, tfrom, tto, cameras, length, usepassword, pass
Read more