Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Last revision Both sides next revision
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 03:12]
fangfufu
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 11:20]
fangfufu
Line 4: Line 4:
 Sorting numbers inside a computer is a bit different to sorting objects in physical world. This is mainly because the uniform cost model does not apply in the physical world [(costmodel > https://​en.wikipedia.org/​wiki/​Analysis_of_algorithms#​Cost_models)]. However some of the concepts in algorithm analysis can still be applied to physical world, for example time complexity and space complexity [(https://​www.cs.utexas.edu/​users/​djimenez/​utsa/​cs1723/​lecture2.html)]. ​ Sorting numbers inside a computer is a bit different to sorting objects in physical world. This is mainly because the uniform cost model does not apply in the physical world [(costmodel > https://​en.wikipedia.org/​wiki/​Analysis_of_algorithms#​Cost_models)]. However some of the concepts in algorithm analysis can still be applied to physical world, for example time complexity and space complexity [(https://​www.cs.utexas.edu/​users/​djimenez/​utsa/​cs1723/​lecture2.html)]. ​
  
-In this blog post, we analyse the algorithm which Parkrun volunteers use to sort barcodes, using some concepts from computer science.+In this blog post, we analyse the algorithm which Parkrun volunteers use to sort barcodes, using some concepts from computer science. This blog post is written in such a way so you can follow it, even if you have not formally studied ​computer science. ​
  
 ===== Analysis of algorithms ​ ===== ===== Analysis of algorithms ​ =====
Line 59: Line 59:
 The first stage establishes a partial ordering [(https://​en.wikipedia.org/​wiki/​Partially_ordered_set)] of the original data structure (all of the barcodes) - there is ordering amongst the buckets, but there is no ordering within each bucket. To establish total ordering [(https://​en.wikipedia.org/​wiki/​Total_order)],​ each bucket need to be sorted using comparison sort.  ​ The first stage establishes a partial ordering [(https://​en.wikipedia.org/​wiki/​Partially_ordered_set)] of the original data structure (all of the barcodes) - there is ordering amongst the buckets, but there is no ordering within each bucket. To establish total ordering [(https://​en.wikipedia.org/​wiki/​Total_order)],​ each bucket need to be sorted using comparison sort.  ​
  
-==== Sorting individual buckets ====+==== Sorting individual buckets ​using insertion sort ====
 Different worker threads (volunteers) tend to use different sorting algorithm. Personally I use insertion sort, which is a comparison sort.  Different worker threads (volunteers) tend to use different sorting algorithm. Personally I use insertion sort, which is a comparison sort. 
  
Line 98: Line 98:
 However there are some physical optimisation which I made. I collapsed consecutive sorted barcodes into clusters. This is because physically inserting a barcode involves moving all the adjacent barcodes, which takes quite a bit of effort on a rough surface. The two figures below illustrate what I meant: ​ However there are some physical optimisation which I made. I collapsed consecutive sorted barcodes into clusters. This is because physically inserting a barcode involves moving all the adjacent barcodes, which takes quite a bit of effort on a rough surface. The two figures below illustrate what I meant: ​
  
-<columns 100% - - >+<columns 100% 50% 50% >
 <WRAP centeralign>​ <WRAP centeralign>​
 //​Uncollapsed barcodes, they became a bit unwieldy to shuffle around. // //​Uncollapsed barcodes, they became a bit unwieldy to shuffle around. //
 +
 +{{:​public:​parkrun:​20181225_102455.jpg?​400}}
 </​WRAP>​ </​WRAP>​
  
-{{ :​public:​parkrun:​20181225_102455.jpg?​400 |}} 
 <​newcolumn>​ <​newcolumn>​
 <WRAP centeralign>​ <WRAP centeralign>​
-//Partially collapsed clusters of consecutive barcodes, it was much easier to perform insertion. // +//Partially collapsed clusters of consecutive barcodes, ​this made it much easier to perform insertion. //
-</​WRAP>​+
  
-{{ :​public:​parkrun:​20181225_103446.jpg?​400 ​|}}+{{:​public:​parkrun:​20181225_103446.jpg?​400}} 
 +</​WRAP>​
 </​columns>​ </​columns>​
  
  • public/how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective.txt
  • Last modified: 2018/12/28 11:23
  • by fangfufu