public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 03:06] – fangfufu | public:how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective [2018/12/28 11:17] – [Sorting individual buckets using insertion sort] fangfufu | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== How Parkrun volunteers sort barcodes - a computer scientist' | ====== How Parkrun volunteers sort barcodes - a computer scientist' | ||
- | On the Christmas day of 2018, I volunteered at Norwich Parkrun. Towards the end, I ended up helping out with sorting the plastic barcodes. I find the whole process interesting. This is because sorting algorithm is an essential part of computer science curriculum [(https:// | + | On the Christmas day of 2018, I volunteered at Norwich Parkrun. Towards the end, I ended up helping out with sorting the plastic barcodes. I find the whole process interesting. This is because sorting algorithm is an essential part of computer science curriculum [(https:// |
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:// | 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:// | ||
Line 59: | Line 59: | ||
The first stage establishes a partial ordering [(https:// | The first stage establishes a partial ordering [(https:// | ||
- | ==== Sorting individual buckets ==== | + | ==== Sorting individual buckets |
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> | ||
// | // | ||
+ | |||
+ | {{: | ||
</ | </ | ||
- | {{ : | ||
< | < | ||
<WRAP centeralign> | <WRAP centeralign> | ||
- | //Partially collapsed clusters of consecutive barcodes, it was much easier to perform insertion. // | + | //Partially collapsed clusters of consecutive barcodes, |
- | </ | + | |
- | {{ : | + | {{: |
+ | </ | ||
</ | </ | ||
Preallocation of enough empty space for the missing barcodes should help with the problem as well - that way you don't need to shuffle those out-of-place barcodes. | Preallocation of enough empty space for the missing barcodes should help with the problem as well - that way you don't need to shuffle those out-of-place barcodes. | ||
- | ==== Conclusion ==== | + | ===== Conclusion |
I quite enjoyed participating barcode sorting. It is quite of interesting to observe a physical implementation of bucket sort. A lot of computer algorithms are inspired by real life processes. I think perhaps the bucket sort algorithm you learn from textbooks is the abstraction of real life bucket sort process. After all, Wikipedia does not say who came up with bucket sort [(bucketsort)]. It really does make me think - a lot of assumptions in the physical world do not apply in computers, a lot of assumptions that work in computers do not apply in real life. If real life processes can inspire computer algorithms, then surely computer algorithms can inspire real life processes. | I quite enjoyed participating barcode sorting. It is quite of interesting to observe a physical implementation of bucket sort. A lot of computer algorithms are inspired by real life processes. I think perhaps the bucket sort algorithm you learn from textbooks is the abstraction of real life bucket sort process. After all, Wikipedia does not say who came up with bucket sort [(bucketsort)]. It really does make me think - a lot of assumptions in the physical world do not apply in computers, a lot of assumptions that work in computers do not apply in real life. If real life processes can inspire computer algorithms, then surely computer algorithms can inspire real life processes. | ||
- | ==== Further readings ==== | + | ===== Further readings ===== |
+ | There are other topics which link computer science into the way the physical world works, for example operational research [(https:// | ||
public/how_parkrun_volunteers_sort_barcodes_-_a_computer_scientist_s_perspective.txt · Last modified: 2018/12/28 11:23 by fangfufu