algorithm - what to choose when dealing with large sequence of input -


i stumbled on question

how find intersection of 2 sequence when each sequence can have duplicate numbers , size big (close 1 million) , data type dealt long.

i thought sorting , finding intersection not viable solution thought hash table not work space consideration has optimum

can suggest better way handle it?

thanks reading post

the question claims “sorting , finding intersection ... not viable solution”. however, standpoint of ease , clarity of coding, sorting among best solutions. one-off problem, spending 10 minutes writing sorting solution more reasonable spending 15 minutes writing hashing solution, or half hour writing special tree program.

sorting million doubles python code shown below takes 1.3 seconds on old pc (amd athlon 5000, 2ghz) , can done 4 5 times faster on current processors. sorting 2 arrays in time o(n lg n) , looking matches in time o(n), required question, might take second or 2 on modern pc.

in [237]: import random  in [238]: v = [random.random() in range(1000000)]  in [239]: %time u = sorted(v) cpu times: user 1.32 s, sys: 0.00 s, total: 1.32 s wall time: 1.33 s

note, question #8630965 refers sorting million floating point values in 1.168 seconds.


Comments

Post a Comment

Popular posts from this blog

ios - iPhone/iPad different view orientations in different views , and apple approval process -

i force app's home screen portrait , other views landscape. apple rejects app if this? if not , how force first screen launch in portrait mode? , force other screens launch in landscape. this not duplicate question search every possible answer in website. i force app's home screen portrait , other views landscape. apple rejects app if this? no apple not reject app this. have lot of apps doesn't support orientation. forcing on 1 screen won't cause app reject. if not , how force first screen launch in portrait mode? , force other screens launch in landscape. can on write : -(nsuinteger)supportedinterfaceorientations; function.
Read more

php - HTTP_REFERER woes: How can I allow access to a specific page, only when a visitor has visited another specific page beforehand? -

php newbie here, struggling crazy head around how go implementing http_referer-based security feature woefully inept downloads system. basically, have file download pages have specific string appended end of url, specific string being: ?thanks if visible in url, users able download file situated on it. works great, it's easy 'unlock' page adding '?thanks' part onto url themselves. allowing users bypass clumsy security , access premium files ease. if possible, i'd add security measure whereby attempting access page containing string '?thanks' did not arrive page containing '?pending' redirected homepage. make perfect solution me. just clarity, typical pre-download process goes this: user visits download page: [website]/download/page/123/ user completes recaptcha, gets redirected here: [website]/download/page/123/?pending user fills in details, gets redirected here: [website]/download/page/123/?thanks user receives file long-...
Read more

java Extracting Zip file -

i'm looking way extract zip file. far have tried java.util.zip , org.apache.commons.compress, both gave corrupted output. basically, input zip file contain 1 single .doc file. java.util.zip: output corrupted. org.apache.commons.compress: output blank file, 2 mb size. so far commercial software winrar work perfectly. there java library make use of this? this method using java.util library: public void extractzipnative(file filezip) { zipinputstream zis; stringbuilder sb; try { zis = new zipinputstream(new fileinputstream(filezip)); zipentry ze = zis.getnextentry(); byte[] buffer = new byte[(int) ze.getsize()]; fileoutputstream fos = new fileoutputstream(this.tempfolderpath+ze.getname()); int len; while ((len=zis.read(buffer))>0) { fos.write(buffer); } fos.flush(); fos.close(); } catch (filenotfoundexception e) { // todo auto-generated catch block ...
Read more