#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. {{{#!html When you add your row after November 13, 5:30pm, please note that the order of columns has changed. }}} ---- /!\ '''Edit conflict - other version:''' ---- || ||||||''film + rug'' ||||||''bowling + rug'' ||||||''film + bowling'' |||||| || ---- /!\ '''Edit conflict - your version:''' ---- || ||||||''film + rug'' ||||||''bowling + rug'' ||||||''film + bowling'' |||||| || ---- /!\ '''End of edit conflict''' ---- ||'''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 || ||ss844 ||1704µs ||349µs ||4.88 ||128µs ||93µs ||1.37 ||2100µs ||2042µs ||1.02 ||C++ ||Zipper, Binary 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 || ---- /!\ '''Edit conflict - other version:''' ---- ---- /!\ '''Edit conflict - other version:''' ---- ||sa194 + lf189 ||28736µs ||7847µs ||3.66 ||9752µs ||3204µs ||3.04 ||19251µs ||38666µs ||0.48 ||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 || ---- /!\ '''Edit conflict - your version:''' ---- ||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 || ||dz31 + lk202 ||1610µs ||1371µs ||1.17 ||114µs ||100µs ||1.14 ||1843µs ||3839µs ||0.48 ||C++ ||Skip pointer + sentinels || ||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 || ---- /!\ '''End of edit conflict''' ---- ---- /!\ '''Edit conflict - your version:''' ---- ||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 || ||nh189 ||54615µs ||20918µs ||2.61 ||25062µs ||46982μs ||0.53 ||55479μs ||46481μs ||1.19 ||Java ||Galloping || ---- /!\ '''End of edit conflict''' ----