burrows-wheeler transform vs shu

jsBenchIt.json

{"title":"burrows-wheeler transform vs shu","initialization":"var output = \"endrtednedd:/os....cp.rnnn.rhhps/.tt|sfeaiaaofd.ow.otooapa.asu./thhse\";\n","setup":"var col = output.split('');","tests":[{"name":"Burrow-wheeler transform","code":"var table = output.split('');\nfor (var j = output.length; j > 1; --j) {\n\ttable.sort();\n\tfor (var i = table.length-1; i >= 0; --i) {\n\t\ttable[i] = col[i] + table[i];\n\t}\n}","results":{"aborted":false,"count":113,"cycles":4,"hz":1219.8233562316002,"stats":{"moe":0.00002169566642856311,"rme":2.646488063857111,"sem":0.000011069217565593424,"deviation":0.00008209151456328668,"mean":0.0008197908286403857,"variance":6.73901676329431e-9,"numSamples":55},"times":{"cycle":0.09263636363636359,"elapsed":6.806,"period":0.0008197908286403857,"timeStamp":1611705678923}},"platforms":{"Mozilla/5.0 (Macintosh; Intel Mac OS X 11_1_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/87.0.4280.141 Safari/537.36":{"aborted":false,"count":58,"cycles":4,"hz":677.4569982405498,"stats":{"moe":0.00008744124646394956,"rme":5.923768435187935,"sem":0.000044612880848953855,"deviation":0.000348437738191804,"mean":0.0014761084505690242,"variance":1.2140885739622016e-7,"numSamples":61},"times":{"cycle":0.08561429013300341,"elapsed":6.231,"period":0.0014761084505690242,"timeStamp":1611705606508}},"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_6) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/14.0.2 Safari/605.1.15":{"aborted":false,"count":113,"cycles":4,"hz":1219.8233562316002,"stats":{"moe":0.00002169566642856311,"rme":2.646488063857111,"sem":0.000011069217565593424,"deviation":0.00008209151456328668,"mean":0.0008197908286403857,"variance":6.73901676329431e-9,"numSamples":55},"times":{"cycle":0.09263636363636359,"elapsed":6.806,"period":0.0008197908286403857,"timeStamp":1611705678923}}}},{"name":"Shu","code":"col.sort();\nvar table = output.split('');\nfor (var i = table.length-1; i >= 0; --i) {\n\ttable[i] += col[i];\n}\n\nvar used = Array(table.length);\nfor (var i=1; i < output.length-1; ++i) {\n\tused.fill(false);\n\tfor (var j=0; j < table.length; ++j) {\n\t\tfor (var k=0; k < table.length; ++k) {\n\t\t\tmatch:\n\t\t\tif (!used[k]) {\n\t\t\t\tfor (var l=0; l < i; ++l) {\n\t\t\t\t\tif (table[k][l] != table[j][l+1]) {\n\t\t\t\t\t\tbreak match;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\ttable[j] += table[k][i];\n\t\t\t\tused[k] = true;\n\t\t\t\tbreak;\n\t\t\t}\n\t\t}\n\t}\n}","results":{"aborted":false,"count":55,"cycles":4,"hz":618.5702471553458,"stats":{"moe":0.00007142738668201003,"rme":4.418285623355139,"sem":0.00003644254422551532,"deviation":0.00026779691484396637,"mean":0.0016166312631406975,"variance":7.171518759994657e-8,"numSamples":54},"times":{"cycle":0.08891471947273837,"elapsed":7.326,"period":0.0016166312631406975,"timeStamp":1611705685755}},"platforms":{"Mozilla/5.0 (Macintosh; Intel Mac OS X 11_1_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/87.0.4280.141 Safari/537.36":{"aborted":false,"count":27,"cycles":5,"hz":333.0760666025609,"stats":{"moe":0.00002313594626418598,"rme":0.7706029978803279,"sem":0.00001180405421642142,"deviation":0.00008911865499894133,"mean":0.0030023171889838555,"variance":7.94213466882033e-9,"numSamples":57},"times":{"cycle":0.0810625641025641,"elapsed":5.954,"period":0.0030023171889838555,"timeStamp":1611705612746}},"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_6) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/14.0.2 Safari/605.1.15":{"aborted":false,"count":55,"cycles":4,"hz":618.5702471553458,"stats":{"moe":0.00007142738668201003,"rme":4.418285623355139,"sem":0.00003644254422551532,"deviation":0.00026779691484396637,"mean":0.0016166312631406975,"variance":7.171518759994657e-8,"numSamples":54},"times":{"cycle":0.08891471947273837,"elapsed":7.326,"period":0.0016166312631406975,"timeStamp":1611705685755}}}},{"name":"Burrow-wheeler transform (es6)","code":"// test 3\nconst result = col.reduce((table, _, i) => {\n  return table.sort().map((v, i) => col[i] + v);\n}, output.split(''));\n\nconsole.log(result.find(s => s.startsWith('|')));","results":{"aborted":false,"count":97,"cycles":4,"hz":1145.2184179456906,"stats":{"moe":0.000008976292515222353,"rme":1.0279815513300685,"sem":0.0000045797410791950785,"deviation":0.000035474521859329045,"mean":0.0008731958762886599,"variance":1.2584417011480142e-9,"numSamples":60},"times":{"cycle":0.08470000000000001,"elapsed":7.35,"period":0.0008731958762886599,"timeStamp":1611705693105}},"platforms":{"Mozilla/5.0 (Macintosh; Intel Mac OS X 11_1_0) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/87.0.4280.141 Safari/537.36":{"aborted":false,"count":75,"cycles":2,"hz":648.2162559764622,"stats":{"moe":0.000025008111107902225,"rme":1.6210664151407757,"sem":0.000012759240361174604,"deviation":0.00008747294487970935,"mean":0.0015426950354609922,"variance":7.65151608592867e-9,"numSamples":47},"times":{"cycle":0.11570212765957441,"elapsed":5.946,"period":0.0015426950354609922,"timeStamp":1611705618706}},"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_6) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/14.0.2 Safari/605.1.15":{"aborted":false,"count":97,"cycles":4,"hz":1145.2184179456906,"stats":{"moe":0.000008976292515222353,"rme":1.0279815513300685,"sem":0.0000045797410791950785,"deviation":0.000035474521859329045,"mean":0.0008731958762886599,"variance":1.2584417011480142e-9,"numSamples":60},"times":{"cycle":0.08470000000000001,"elapsed":7.35,"period":0.0008731958762886599,"timeStamp":1611705693105}}}}]}