Character Count using Distributed Programming

Question

I have a huge file (contains only ascii characters) and I need to find the character that appears most frequently.

My Approach:

1. Split the file and distribute it to a number of processing nodes.
2. Each node will count the characters and generate a character count array[256].
3. The parent node will receive all the count array from all nodes and calculates the most frequent character.

But I am wondering if the nodes need to transfer the entire count array to just calculate the most frequent character? Is there a way to reduce the amount of processed data transferred between the nodes.

Note: I am new to Distributed Programming, so trying to get familiar with the fundamental techniques.

Answer 1

If you let each node process e.g. 1 MiB then 1 KiB of response (256 times 4 bytes for int) is negligible.

And BTW look at mapreduce, especially hadoop. The "hello world" of map-reduce is word counting - almost exactly what you are looking for.

Answer 2

If you want to know the exact number of the most frequent character, then yes each node will need to return ALL counts, it is possible one node will count 1 million 'a' and another only 1 instance. To get the exact total, then you need all counts.

Also (unrelated), point 1 says you are going to "split and distribute the file". Does this imply reading it on one machine and sending it over a network? In this case you have already read part of the file into memory, so might as well scan it immediately, while it is still warm in caches. Of course if you have pre-distributed the file this won't matter.