4 ms·
This pattern can be applied to a large set of collection representations, as long as a former collection can be divided into smaller parts which can be processe
by dwenzek 12y ago
This pattern can be applied to a large set of collection representations,
as long as a former collection can be divided into smaller parts
which can be processed independently giving partial results
to be combined into a final outcome using an associative combiner.
For instance, to compute a count of words,
the former word collection can be either a conc tree in memory
or a file divided in chunks or a bunch of files.
In each case, the sub counts can be computed independently
and reconciled into a total count.
The deep insight Guy Steele provides in his talk,
is how to deal with the non trivial cases
like the count of words in a file divided in chunks
where words can cross chunk boundaries.
Hence, I highly recommend watching this talk.
As further reading, I recommend too a post [1]
that I written after having watched Guy Steele talk.
[2] is a work in progress to implement the idea in OCaml.
[1] http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.html http://acidalie.free.fr/unfoldvalue/blog/map-reduce-spirit.h...
[2] https://github.com/didier-wenzek/odist https://github.com/didier-wenzek/odist
- agumonkey 12y agoIndeed the cross-chunk recombination is quite something. We're used to clean cut boundaries and here he is going away from this rule to bring new opportunities. But I wonder how hard it is to think about, design and test such assoc. combiners ..
- dwenzek 12y agoYes, it may be quit hard to design such a combiner due to constraints both on the input (as the need for cross-chunk recombination), and on the output (as too early finalization preventing further combinations); with the consequence that we often have to imagine a genuine intermediate data representation of the problem. But this complexity is mitigated by the fact that these associative combiners can be built incrementally using a reduced set of patterns, combiner compositions and transformations. Have a look to this remarkably well written post [1] on incremental regular expressions (it appears that incremental computation is deeply related with parallel computation). It shows well, on a non-trivial example, how to build such an intermediate data representation with its associative combiner. [1] http://jkff.info/articles/ire/ http://jkff.info/articles/ire/