|
Size: 8258
Comment:
|
Size: 13534
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 8: | Line 8: |
| || ||||||<style="" & quot;text-align:center& quot; "">''film + rug'' ||||||<style="" & quot;text-align:center& quot; "">''bowling + rug'' ||||||<style="" & quot;text-align:center& quot; "">''film + bowling'' ||||||<style="" & quot;text-align:center& quot; ""> || | || ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">''film + rug'' ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">''bowling + rug'' ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">''film + bowling'' ||||||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; ""> || |
| Line 36: | Line 36: |
| ||fj47 ||4841µs ||831µs ||5.82 ||1948µs ||1384µs ||1.41 ||4395µs ||6061µs ||0.89 ||Java ||Switch between Zipper, binary on rest or Galopping. Use Sentinels || | ||fj47 ||4841µs ||831µs ||5.82 ||1948µs ||1384µs ||1.41 ||4395µs ||6061µs ||0.89 ||Java ||Switch between Zipper, binary on rest or Galloping. Use Sentinels || |
| Line 41: | Line 41: |
| ||ds371 ||1083µs ||260µs ||4.23 ||62µs ||31µs ||2.00 ||1217µs ||1147µs ||1.06 ||C++ ||Zipper, Galloping search, Sentinels || | |
| Line 54: | Line 55: |
| ||sn144 ||534 µs ||360µs ||1.48 ||135µs ||135µs||1.00 ||367µs ||519µs ||0.7||Java || Binary search in remaining ,Galloping,Sentinels || ||my28 + ab717 ||58394µs ||348878µs ||1.67 ||10117µs ||9901µs||1.02 ||39431µs ||90009µs ||0.43||Java || Binary search in remaining, Binary search in remaining ,Galloping || |
||sn144 ||534µs ||360µs ||1.48 ||135µs ||135µs ||1.00 ||367µs ||519µs ||0.7 ||Java ||Binary search in remaining ,Galloping,Sentinels || ||my28 + ab717 ||58394µs ||348878µs ||1.67 ||10117µs ||9901µs ||1.02 ||39431µs ||90009µs ||0.43 ||Java ||Binary search in remaining, Binary search in remaining ,Galloping || ||ye14 ||13218.2μs ||5620.8μs ||2.35 ||3759.6μs ||2465.2μs ||1.52 ||11873.0μs ||16458.0μs ||0.72 ||Java ||Galloping search, sentinel, binary search || ||vb128 ||14198μs ||2754μs ||5.15 ||6008μs ||754μs ||7.98 ||14887μs ||8958μs ||1.66 ||Java ||Zipper + Galloping with Binary search in range of gallop and last + sentinel. || ||fc54 ||8815μs ||1340μs ||6.58 ||1475μs ||1912μs ||0.77 ||13724μs ||11116μs ||1.23 ||Java ||Galloping search, sentinel, binary search || ||ms1323 ||5838μs ||1809μs ||3.23 ||440μs ||413μs ||1.07 ||1875μs ||2689μs ||0.70 ||c++ ||Combination of zipper with sentinel and Galloping search. || ||ch285 ||44375μs ||7303μs ||6.08 ||10964μs ||6841μs ||1.60 ||32075μs ||21204μs ||1.51 ||Java ||Combination of Zipper+Sentinel+Binary Search in Remainder of longer list || ||uw18 ||18979μs ||3812μs ||4.98 ||8497μs ||2459μs ||3.46 ||21383μs ||12295μs ||1.74 ||Java ||Zipper + Sentinels + Galloping Search || ||dk182 ||43156μs ||13012μs ||3.31 ||11096μs ||10486μs ||1.05 ||18792μs ||6931μs ||2.71 ||Java ||Combination of zipper with sentinels & galloping search & binary search. || ||pc49 ||3525μs ||722μs ||4.88 ||207μs ||94μs ||2.23 ||5063μs ||4590μs ||1.10 ||C++ ||Galloping search & sentinels & binary search. || ||jt20 ||1224µs ||418µs ||2.93 ||66µs ||57µs ||1.16 ||2157µs ||1429µs ||0.66 ||C++ ||Galloping search, sentinels, binary search, misc optimizations. || ||cf147 ||682µs ||408µs ||1.67 ||120µs ||110µs ||1.09 ||1201µs ||2086µs ||0.58 ||C++ ||Galloping search + binary search + Sentinels || ||sa194 + lf189 ||38165µs ||5906µs ||6.46 ||6599µs ||3648µs ||1.81 ||30105µs ||51320µs ||0.59 ||Java ||Galloping + Binary search in Remainder || ||cg248 + ar288||5858µs ||3593µs ||1.63 ||6139µs ||2518µs ||2.44||4606µs ||4021µs ||1.15||Java ||Zipper with sentinels (+ galloping search + binary search + shrinking search range)|| ||mu38 ||21664µs||3119µs||6.95||8234µs||2915µs||2.82||19449µs||18171µs||1.07||Java||Binary search|| ||fe73 ||6872µs ||5684µs ||1.21 ||93µs ||74µs ||1.26 ||2535µs ||2337µs ||1.08 ||Java ||Zipper with sentinels, logical simplification || ||jh363 + os85 ||1724µs ||681 µs||2.53 ||141µs || 139µs|| 1.01||1831µs ||3369µs ||0.54 ||C++ ||Galloping search || ||dr189-jb729||6378µs||2381µs||2.68||57µs||871µs||0.065||1975µs||10617µs||0.19||Java||Zipper with binary search, galloping search & SkipPointers|| |
Results for Exercise Sheet 3 (Intersecting Lists)
Add your row to the table below, following the examples already there. In the 1st column, write your account name, or name1+name2 if you work in a group. For each intersection result, write down (1) the runtime of the baseline algorithm, (2) the runtime of your improved algorithm (both in microseconds as an integer) and (3) the speedup ratio as float with exactly two digits of precision, measured as time_for_baseline / time_for_your_algorithm (<1 = slower, >1 = faster). In the last column briefly describe the improvements you implemented.
When you add your row after November 13, 5:30pm, please note that the order of columns has changed. film + rug bowling + rug film + bowling Name Baseline Yours Ratio Baseline Yours Ratio Baseline Yours Ratio Language Summary Improvements ck1028 8570µs 3298µs 2.59 545µs 520µs 1.05 12920µs 8796µs 1.46 Java Combination of zipper algorithm & binary search in remainder of longer list; sentinels. ck1028 1767µs 260µs 6.79 116µs 65µs 1.78 1898µs 1784µs 1.06 C++ Combination of zipper algorithm & galloping search; sentinels. he41 8957µs 1446µs 6.19 2631µs 1575µs 1.67 8184µs 1465µs 5.59 Java Combination of zipper algorithm & galloping search; sentinels; Bitwise Operations. ma269 1332µs 566µs 2.35 122µs 52µs 2.32 1901µs 1538µs 1.24 C++ Log(n)-step baseline or galloping search with sentinels. cb382 + mz111 5428µs 1487µs 3.65 1687µs 803µs 2.10 4842µs 2992µs 1.62 Java Combination of zipper with sentinels & galloping search yl100 1381µs 483µs 2.86 141µs 66µs 2.14 2061µs 1943µs 1.06 C++ Combination of zipper ,sentinels, and galloping search fk234 1896µs 466µs 4.07 146µs 91µs 1.60 2127µs 1670µs 1.27 C++ Zipper algorithm with sentinels and galloping search pk104 1293µs 355µs 3.65 95µs 50µs 1.87 1514µs 1318µs 1.14 C++ galloping search pg152 12301µs 3078µs 3.99 4777µs 1334µs 3.58 17024µs 11518µs 1.47 Java Binsearch at beginning, Galloping at end dd74 1631µs 575µs 2.84 144µs 143µs 1.01 1785µs 1951µs 0.91 C++ Zipper algorithm with sentinels, binary search je113 1124µs 497µs 2.26 90µs 89µs 1.01 2049µs 1872µs 1.09 Java Skip pointers with sentinels ck407 2102µs 1168µs 1.80 1447µs 1098µs 1.32 30959µs 28967µs 1.07 Java Combination of zipper with sentinels and galloping search. sm362 1549µs 432µs 3.58 127µs 81µs 1.57 1854µs 1831µs 1.01 C++ Combination of zipper algorithm & galloping search ak745 6060µs 1026µs 5.91 1893µs 790µs 2.40 6292µs 5245µs 1.20 Java Combination of Galloping search and binary search. yb36 1374µs 227µs 6.03 133µs 38µs 3.47 1443µs 1271µs 1.14 C++ Zipper + Galloping search + Binary search + Sentinels ph193 1249µs 541µs 2.30 81µs 39µs 2.06 1725µs 1589µs 1.09 C++ Combination of galloping search with zipper algorithm; sentinels sr285 969µs 587µs 1.65 255µs 118µs 2.16 4866µs 1533µs 3.17 Java Combination of Sentinels, Binary and Galloping fb234 11562µs 2570µs 4.50 1103µs 535µs 2.06 17199µs 9772µs 1.76 Java Skip pointers in remainder hn52 5996µs 4235µs 1.42 6178µs 4319µs 1.43 2990µs 2997µs 1.00 C++ Zipper with sentinels and galloping search es260 + ic30 1067µs 262µs 4.07 85µs 104µs 0.82 1293µs 5086µs 0.25 C++ Combination of galloping, binary and sentinel js603 1551µs 350µs 4.43 106µs 92µs 1.15 1385µs 1274µs 1.09 C++ Combination of galloping / binary search and baseline hs211+lb319 1816µs 591µs 3.07 123µs 66µs 1.86 1911µs 2272µs 0.84 C++ Combination of galloping search, predictable branches and remove of redundant initialization rb201 25315µs 9240µs 2.74 10713µs 7272µs 1.47 28211µs 27367µs 1.03 Java Zipper + Galloping search + Binary search + Sentinels (yes my hardware is old) ls305 8931µs 7499µs 1.19 4270µs 739µs 5.77 12293µs 7353µs 1.67 Java Zipper + Sentinels or Galloping ns202 1421µs 351µs 4.04 103µs 140µs 0.73 1434µs 2380µs 0.60 C++ Galloping nf55 1149µs 201µs 5.70 68µs 25µs 2.67 1254µs 1068µs 1.17 C++ Combining Zipper, Galloping search and Binary search fj47 4841µs 831µs 5.82 1948µs 1384µs 1.41 4395µs 6061µs 0.89 Java Switch between Zipper, binary on rest or Galloping. Use Sentinels df121+km109 7352µs 4937µs 1.49 3445µs 2895µs 1.19 7227µs 22216µs 0.33 Java Galloping search, skip pointers and Binary search cs568 10457µs 4071µs 2.57 824µs 1884µs 0.44 11487µs 51787µs 0.22 C++ Galloping and binary search in interval bb245 1066µs 369µs 2.89 150µs 125µs 1.20 1322µs 1862µs 0.71 C++ Galloping search mk813 1806µs 256µs 7.05 128µs 56µs 2.29 1935µs 2027µs 0.95 C++ Galloping search ds371 1083µs 260µs 4.23 62µs 31µs 2.00 1217µs 1147µs 1.06 C++ Zipper, Galloping search, Sentinels br106-ms1512 2274µs 531µs 4.28 159µs 150µs 1.06 2443µs 8665µs 0.28 C++ Galloping search, binary search, sentinels ht48 3004µs 1979µs 1.52 187µs 113µs 1.65 8388µs 4373µs 1.92 C++ Zipper, sentinels ds467 18113µs 8663µs 2.09 14441µs 5058µs 2.85 18535µs 19735µs 0.93 Java Galloping + Binary search pd95 24618µs 4248µs 5.79 6773µs 3847µs 1.76 22536µs 15037µs 1.49 Java Galloping + Binary search from remainder ak721 + bf87 1116µs 302µs 3.70 74µs 99µs 0.75 1376µs 1878µs 0.73 C++ Combination of Zipper with Sentinels and Galloping search with Sentinels rv25 38843µs 6917µs 5.61 13568µs 5924µs 2.29 37194µs 35132µs 1.06 Java Combination of Zipper and binary search with remainder plus sentinels kg190 57987µs 32344µs 1.79 6124µs 4293µs 1.43 37310µs 22280µs 1.67 Java Combination of zipper algorithm & binary search in longer list; sentinels and skip pointer. rs325 + ej35 1260µs 470µs 2.68 129µs 108µs 1.49 1956µs 1471µs 1.33 C++ Galloping and Binary mb930 + ng153 1184µs 461µs 2.57 107µs 90µs 1.19 1326µs 1260µs 1.05 C++ Zipper, Galloping search, Sentinels mg290 8943µs 7624µs 1.17 3628µs 3130µs 1.16 4657µs 4427µs 1.05 Java Combination of zipper algorithm with sentinels & Galloping pj46 1903µs 436µs 4.36 101µs 57µs 1.76 2748µs 2082µs 1.34 C++ Galloping & binary search + sentinels mf401 2012µs 504µs 3.99 236µs 138µs 1.71 2500µs 1574µs 1.59 C++ Galloping + Zipper with sentinels jh442 3242µs 264µs 12.28 178µs 49µs 3.63 3186µs 2596µs 1.23 C++ Skip Pointers for list A, Zipper + Galloping for list B, Sentinels sn144 534µs 360µs 1.48 135µs 135µs 1.00 367µs 519µs 0.7 Java Binary search in remaining ,Galloping,Sentinels my28 + ab717 58394µs 348878µs 1.67 10117µs 9901µs 1.02 39431µs 90009µs 0.43 Java Binary search in remaining, Binary search in remaining ,Galloping ye14 13218.2μs 5620.8μs 2.35 3759.6μs 2465.2μs 1.52 11873.0μs 16458.0μs 0.72 Java Galloping search, sentinel, binary search vb128 14198μs 2754μs 5.15 6008μs 754μs 7.98 14887μs 8958μs 1.66 Java Zipper + Galloping with Binary search in range of gallop and last + sentinel. fc54 8815μs 1340μs 6.58 1475μs 1912μs 0.77 13724μs 11116μs 1.23 Java Galloping search, sentinel, binary search ms1323 5838μs 1809μs 3.23 440μs 413μs 1.07 1875μs 2689μs 0.70 c++ Combination of zipper with sentinel and Galloping search. ch285 44375μs 7303μs 6.08 10964μs 6841μs 1.60 32075μs 21204μs 1.51 Java Combination of Zipper+Sentinel+Binary Search in Remainder of longer list uw18 18979μs 3812μs 4.98 8497μs 2459μs 3.46 21383μs 12295μs 1.74 Java Zipper + Sentinels + Galloping Search dk182 43156μs 13012μs 3.31 11096μs 10486μs 1.05 18792μs 6931μs 2.71 Java Combination of zipper with sentinels & galloping search & binary search. pc49 3525μs 722μs 4.88 207μs 94μs 2.23 5063μs 4590μs 1.10 C++ Galloping search & sentinels & binary search. jt20 1224µs 418µs 2.93 66µs 57µs 1.16 2157µs 1429µs 0.66 C++ Galloping search, sentinels, binary search, misc optimizations. cf147 682µs 408µs 1.67 120µs 110µs 1.09 1201µs 2086µs 0.58 C++ Galloping search + binary search + Sentinels sa194 + lf189 38165µs 5906µs 6.46 6599µs 3648µs 1.81 30105µs 51320µs 0.59 Java Galloping + Binary search in Remainder cg248 + ar288 5858µs 3593µs 1.63 6139µs 2518µs 2.44 4606µs 4021µs 1.15 Java Zipper with sentinels (+ galloping search + binary search + shrinking search range) mu38 21664µs 3119µs 6.95 8234µs 2915µs 2.82 19449µs 18171µs 1.07 Java Binary search fe73 6872µs 5684µs 1.21 93µs 74µs 1.26 2535µs 2337µs 1.08 Java Zipper with sentinels, logical simplification jh363 + os85 1724µs 681 µs 2.53 141µs 139µs 1.01 1831µs 3369µs 0.54 C++ Galloping search dr189-jb729 6378µs 2381µs 2.68 57µs 871µs 0.065 1975µs 10617µs 0.19 Java Zipper with binary search, galloping search & SkipPointers