I was recently watching a huge swarm of bees gathering nectar on a flowering plant. It got me thinking about how each bee does its own little tiny job, yet they all come together to collect a lot of nectar and keep the hive going in the end. I was inspired to try and come up with a way this system could be replicated in Perl.

One idea I had was regarding the problem of finding an element in a very large array. Using two well-known techniques, this problem could be "swarmed" and solved fairly quickly. The techniques are (1) splitting the array into smaller chunks, and (2) forking. Basically, you split the array up into much smaller arrays, then fork a process (a "bee") to search each of the chunks for the item. Once the item is found, all of the "bees" stop processing and return.

What do you think of this idea? And can you think of any other ways it could be applied?

Update: I just found Proc::Swarm. While it's not identical to my concept, it's certainly similar.

---
It's all fine and dandy until someone has to look at the code.

Replies are listed 'Best First'.
Re: "Swarming"
by jdporter (Paladin) on Jul 13, 2006 at 19:19 UTC
[reply]
Re: "Swarming"
by Joost (Canon) on Jul 13, 2006 at 19:26 UTC
    That's a strategy that can be applied to various problems. When you can use it, it's a very effective way to make use of multi-processors/machine clusters.

    It seems to be particulary well suited for problems where the processing can be split into more or less independent sections. Example: most fractals can be rendered partially - each process takes on a "tile" and calculate only that part.

    Recently, I've been thinking about audio processing - where parallel audio streams can be split out: 

    CPU 1       CPU 2          CPU 3

O source one               O source two
|                          |
+-----------+              |
|           |              |
O effect 1  O effect 2     O effect 3
|           |              |
|           +--------------+
O effect 4  O effect 5
|           |
|           |
O output 1  O output 2

    [download]
    Signals go in from the top and exit at the bottom (usually in small batches). Each column can in principle be taken on by a different process(or).

    "What should it profit a man, if he should win a flame war, yet lose his cool?"
[reply]
[d/l]
Re: "Swarming"
by neilwatson (Priest) on Jul 14, 2006 at 14:19 UTC
    I've used this technique for cleaning bad entries from large mailing lists. You can see it here.

    Neil Watson
    watson-wilson.ca

[reply]
Re: "Swarming"
by Anonymous Monk on Jul 14, 2006 at 19:20 UTC
    As stated before, this "divide and conquer" (also see http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm) approach can be applied to many problems, but you can also use hashes for this by maintaining your order in the values as such: 
    #!/usr/bin/perl

@a = qw(one two three);
%h = map({$_ => $count++} @a);
print "$_ => $h{$_}\n" foreach (keys(%h));
foreach (sort( {$h{$a} <=> $h{$b}} keys(%h))) {
   print "$_\n";
}

    [download]

    Janitored by tye: Add CODE tags

[reply]
[d/l]
[reply]

Back to Meditations