tag:blogger.com,1999:blog-9193160645817040317.post1663568362487403013..comments2015-12-22T12:31:53.234+05:30Comments on Twisters - The New Age Java Quiz: Puzzle 61 - Set for Optimization?Saifuddin Merchanthttp://www.blogger.com/profile/09008041357659535766noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-9193160645817040317.post-52412400817281086122010-07-18T10:15:22.926+05:302010-07-18T10:15:22.926+05:30commonC = new ArrayList();
for (Long _l : listOf...commonC = new ArrayList();<br /> for (Long _l : listOf2)<br /> {<br /> if ((_l % 3) == 0)<br /> commonC.add(_l);<br /> }HRnoreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-22484803214569889992010-07-15T01:48:30.180+05:302010-07-15T01:48:30.180+05:30Collections.sort(listOf3);
commonC = new ArrayList...Collections.sort(listOf3);<br />commonC = new ArrayList();<br />int result = 0;<br />for (Long long1 : listOf2) {<br /> result = Collections.binarySearch(listOf3, long1);<br /> if (result >= 0) {<br /> commonC.add(long1);<br /> }<br />}Deepak Parmarhttps://www.blogger.com/profile/05801752058752922254noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-49305600897323498732010-07-14T16:49:16.254+05:302010-07-14T16:49:16.254+05:30Hi there! My try is:
startTimestamp = System.curr...Hi there! My try is:<br /><br />startTimestamp = System.currentTimeMillis();<br />HashSet hashSet = new HashSet(listOf2);<br />commonC = new ArrayList();<br />for (Long val : listOf3) {<br /> if (!hashSet.add(val)) { commonC.add(val); }<br />}1nd1gohttps://www.blogger.com/profile/00722857356085197099noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-28192093806809727822010-07-14T10:26:13.004+05:302010-07-14T10:26:13.004+05:30@Wouter - Umm I got a 5 year old P4 with 1G ram an...@Wouter - Umm I got a 5 year old P4 with 1G ram and stuff runs kinda really slow on it. If someone find the code running fast enough on their machine, I suggest increasing the LOOP value from 50,000 to 150,000 or higher. The performance contrast should be obvious.<br /><br />@All - There are lot of other comments (with answers). I'll be approving everything this weekend. Comments are hidden to prevent 'spoilers' for anyone reading the puzzle!Saifuddin Merchanthttps://www.blogger.com/profile/09008041357659535766noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-56162192150893047872010-07-14T04:46:08.841+05:302010-07-14T04:46:08.841+05:30Attempts 1 and 2 are the same.
new ArrayList(list...Attempts 1 and 2 are the same. <br />new ArrayList(listOf2).retainAll(listOf3) is the same as new ArrayList(listOf3).retainAll(listOf2). <br /><br />Btw both attempts run in slightly over 4 seconds on my simple laptop. Why does it take 60 sec when you run it?Wouternoreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-91467452778776897722010-07-14T01:21:19.597+05:302010-07-14T01:21:19.597+05:30Another solution which does not depend on order of...Another solution which does not depend on order of list elements:<br /><br /><br /> Set commonE = new HashSet(listOf2);<br /> <br /> commonC = new ArrayList();<br /> <br /> for (Long value : listOf3) {<br /> if (commonE.contains(value)) {<br /> commonC.add(value);<br /> }<br /> }<br /><br />Results of execution on my PC:<br /><br />For 50000 elements:<br /><br />Execution Time : 4238<br />Execution Time : 4158<br />Are Equal : true #16667<br />Execution Time : 27<br />Are Equal : true #16667<br /><br />For 100000 elements:<br /><br />Execution Time : 16288<br />Execution Time : 16609<br />Are Equal : true #33334<br />Execution Time : 39<br />Are Equal : true #33334Sergiy Yevtushenkohttps://www.blogger.com/profile/10444798721521171754noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-64909046174407576202010-07-14T00:55:43.569+05:302010-07-14T00:55:43.569+05:30Oh, and I forgot. The factor is x2000, not x10.Oh, and I forgot. The factor is x2000, not x10.Ran Bironhttps://www.blogger.com/profile/13745439632196949633noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-328521645864155232010-07-14T00:50:05.749+05:302010-07-14T00:50:05.749+05:30//Well, I got it to 0 (about 10M nano). My //origi...//Well, I got it to 0 (about 10M nano). My //original "number 1" was about 16 seconds though.<br />//I use a version of "merge-sort" tailored for this case<br />//The general case would be a bit more complex - but the only real requirement is that the lists are sorted.<br /><br /><br />commonC = new ArrayList(listOf2.size());<br /> int j=0;<br /> for(int i=0; i current3) {<br /> j++;<br /> current3 = listOf3.get(j);<br /> }<br /> if(current2.longValue() == current3.longValue()) {<br /> commonC.add(current2);<br /> }<br /> }Ran Bironhttps://www.blogger.com/profile/13745439632196949633noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-4021375207714199112010-07-14T00:37:08.597+05:302010-07-14T00:37:08.597+05:30First of all - great blog!
I have a guess, but un...First of all - great blog!<br /><br />I have a guess, but unfortunately based on a Set, not a List. To this particular case it doesn't matter, but in general case it makes my guess unacceptable.<br /><br />Here is the code:<br /><br /> commonC = new LinkedList(listOf2);<br /> Set b = new HashSet(listOf3);<br /> commonC.retainAll(b);<br /><br />And the measurements:<br /><br />[A] Execution Time : 146<br />[B] Execution Time : 153<br />[B] Are Equal : true<br />[C] Execution Time : 0 (505 milis)<br />[C] Are Equal : trueEurekinhttps://www.blogger.com/profile/12899228602227596377noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-17869335629018012482010-07-13T22:45:09.378+05:302010-07-13T22:45:09.378+05:30Since both lists are sorted, following solution wo...Since both lists are sorted, following solution works:<br /><br />...<br /> commonC = new ArrayList();<br /> <br /> int i = 0; <br /> <br /> for (Long elem : listOf2) {<br /> long res = elem.longValue() - listOf3.get(i).longValue();<br /> <br /> if (res >= 0) {<br /> <br /> if (res == 0) {<br /> commonC.add(elem);<br /> }<br /> <br /> i++;<br /> }<br /> }<br />...<br /><br />But in my environment is not in 10 times, but almost 1000 times faster:<br /><br /><br />Execution Time : 4234<br />Execution Time : 4149<br />Are Equal : true #16667<br />Execution Time : 11<br />Are Equal : true #16667<br /><br />(I'm displaying milliseconds instead of seconds and after results of comparison total number of elements in collection is provided).<br />With 100000 elements results even better:<br /><br />Execution Time : 16288<br />Execution Time : 16608<br />Are Equal : true #33334<br />Execution Time : 18<br />Are Equal : true #33334Sergiy Yevtushenkohttps://www.blogger.com/profile/10444798721521171754noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-56129518509050042292010-07-13T20:17:02.343+05:302010-07-13T20:17:02.343+05:30final Set setC = new HashSet(listOf3);
commonC = n...final Set setC = new HashSet(listOf3);<br />commonC = new LinkedList();<br />for (final Long value : listOf2){<br /> if (setC.contains(value)){<br /> commonC.add(value);<br /> }<br />}<br /><br />Execution Time : 4297<br />Execution Time : 4437<br />Are Equal : true<br />Execution Time : 36<br />Are Equal : trueGreg Haineshttp://greghaines.net/noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-53794312945866618922010-07-13T19:58:27.314+05:302010-07-13T19:58:27.314+05:30Long[] array = new Long[16667];
for(int i=0; i...Long[] array = new Long[16667];<br /> for(int i=0; i<array.length; i++) {<br /> array[i] = Long.valueOf(i*6);<br /> }<br /> commonC = Arrays.asList(array);Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-62049183946065940802010-07-13T01:58:15.224+05:302010-07-13T01:58:15.224+05:30The data set you are using is a Set and retainAll ...The data set you are using is a Set and retainAll is a set operation. If you use a set it will run 2000x faster or more. By tuning the JVM you can get each operation down to 12 milli-seconds.Peter Lawreyhttps://www.blogger.com/profile/17982030676088168612noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-31796461535020087852010-07-12T18:01:01.724+05:302010-07-12T18:01:01.724+05:30Convert lists to arrays:
Long[] array2 = listOf2....Convert lists to arrays:<br /><br />Long[] array2 = listOf2.toArray(new Long[listOf2.size()]);<br />Long[] array3 = listOf3.toArray(new Long[listOf3.size()]);<br /> <br />for (Long item : array2) { if (Arrays.binarySearch(array3, item) >= 0) commonC.add(item); }Yauhenihttp://www.facebook.com/profile.php?id=100001055127706noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-60736637832072683752010-07-12T12:37:09.401+05:302010-07-12T12:37:09.401+05:30For this particular case we need to find the numbe...For this particular case we need to find the numbers that divide by 2 and 3 smaller then 50000 * 2.<br /><br />commonC = new ArrayList();<br /> for ( int i = 0; i < ( 50000 * 2 ) / 3 ; i+=2 )<br /> {<br /> Long value = Long.valueOf(i*3);<br /> commonC.add( value );<br /> }Unknownhttps://www.blogger.com/profile/03576977165659733026noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-88019119295321790022010-07-12T10:12:14.134+05:302010-07-12T10:12:14.134+05:30@Colin - Eeeks! Your right. Not my intention at al...@Colin - Eeeks! Your right. Not my intention at all. I've corrected the puzzle and I'm hoping I've got it right this time.Saifuddin Merchanthttps://www.blogger.com/profile/09008041357659535766noreply@blogger.comtag:blogger.com,1999:blog-9193160645817040317.post-86765631718196695592010-07-12T02:30:58.729+05:302010-07-12T02:30:58.729+05:30You forgot to reset your list between the first an...You forgot to reset your list between the first and the second attempt. That's why your test isn't correct.<br /><br />At line 28 and 35 you pass a reference so you modify the original List at each time.<br /><br />To make it work faster on the third attempt you just have to write :<br />commonC = listOf3;Colin Heberthttps://www.blogger.com/profile/11704706036565373060noreply@blogger.com