4 ms·
I wrote software that finds textual graphics in a bitmap. I parallelised it by running, say, 4 (or any number of) threads, each handling 1/4 of the bitmap. It w
by zandorg 18y ago
I wrote software that finds textual graphics in a bitmap. I parallelised it by running, say, 4 (or any number of) threads, each handling 1/4 of the bitmap. It works really well, and there's no overlap.
- dangoldin 18y agoThere must be some overlap to share what they find with another? Let's say 2 of the threads each have half a letter. Do you just have another thread that does the matching?
- zandorg 18y agoEach thread has its area to search. At the end, when the last thread has finished, the results are merged into a single bitmap. The best way to see it is as 4 strips of tracing paper which have the exact same text on, and the strips are searched and the text traced in, then all 4 (clear) strips go in a pile to make the final image. [Edit] To clarify, if you search at position 200,268, if you hit a row of text in the centre, it scans. If you search the same bitmap at 200,350, what you find might not be clear. So each thread searches some of the same areas, but the end result is that all text is found, and heuristics reject certain rows as valid text.
- queensnake 18y agoThat's called an 'embarrassingly parallel' problem, it's not the general case. I guess, just like 'big O', people have to take a class to appreciate the space of what it's possible to parallelize and how much it buys you.
- zandorg 18y agoAt University we used to refer to big O as Roy Orbison. Just an example of our kind of smalltown humour.