|
Size: 1557
Comment:
|
Size: 8073
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| #acl Claudius Korzen:read,write All:read | #acl All:read,write = 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 '''micro'''seconds 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. |
| Line 3: | Line 5: |
| = 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. In the 2nd and 3rd column, write down the average runtime of the baseline algorithm and of your improved algorithm on your machine, in '''micro'''seconds as an integer. As mentioned in the lecture, repeat each measurement '''5 times''' and take the average. In the columns 4-6, write down the speedup ratios as floats with '''exactly two digits of precision''', measured as time_for_baseline / time_for_your_version (<1 = slower, >1 = faster). In the columns 7+8, give details about your programming language and your machine specifications. In the last column '''briefly''' describe the improvements you implemented. || |||| ''Average Runtime (in µs)'' |||||| ''Speedup ratio'' |||| || || ||'''Name''' || '''Baseline''' || '''Your version''' || '''existence + bielefeld''' ||'''them + bielefeld'''||'''them + existence'''||'''Language'''||'''Machine Spec'''||'''Summary Improvements'''|| || ck1028 || ? || ? || 0.00 || 0.00 || 0.00 || Java || ? || ? || || ck1028 || ? || ? || 0.00 || 0.00 || 0.00 || C++ || ? || ? || |
{{{#!html <span style="color:red; font-weight: bold">When you add your row after November 13, 5:30pm, please note that the order of columns has changed.</a> }}} || ||||||<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; ""> || ||'''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 Galopping. 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 || ||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 ||Java || Binary search in remaining ,Galloping,Sentinels || |
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 Galopping. 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 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 Java Binary search in remaining ,Galloping,Sentinels