www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - map! filter! and range algorithm

reply "Andrea Fontana" <nospam example.com> writes:
If I understand it correctly something like:

range.filter!(...).map!(...)

browse range 2 times, one for filter and one for mapping doesn't 
it?

Is there a way to "parallelize" this kind of operations?
Mar 04 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/04/2013 09:06 PM, Andrea Fontana wrote:
 If I understand it correctly something like:

 range.filter!(...).map!(...)

 browse range 2 times, one for filter and one for mapping doesn't it?
It does not.
 Is there a way to "parallelize" this kind of operations?
Interleaving is the default. To perform two traversals you'd have to force evaluation using eg. range.filter!(...).array.map!(...).
Mar 04 2013
parent reply "Andrea Fontana" <nospam example.com> writes:
On Monday, 4 March 2013 at 20:21:31 UTC, Timon Gehr wrote:
 On 03/04/2013 09:06 PM, Andrea Fontana wrote:
 If I understand it correctly something like:

 range.filter!(...).map!(...)

 browse range 2 times, one for filter and one for mapping 
 doesn't it?
It does not.
 Is there a way to "parallelize" this kind of operations?
Interleaving is the default. To perform two traversals you'd have to force evaluation using eg. range.filter!(...).array.map!(...).
Very interesting. IMHO that should be pointed out better in docs/example. You say interleaving is "default", how can I guess if a function doesn't use the "default" behaviour?
Mar 04 2013
parent reply "Jesse Phillips" <Jesse.K.Phillips+D gmail.com> writes:
On Monday, 4 March 2013 at 20:49:22 UTC, Andrea Fontana wrote:

 Very interesting. IMHO that should be pointed out better in 
 docs/example.
 You say interleaving is "default", how can I guess if a 
 function doesn't use the "default" behaviour?
It doesn't really make sense to point it out in the example since it is kind of fundamental to what ranges are. If it is eager than the docs should mention that. If an operation requires all its data upfront, sort, then you'll usually see a call for .array().
Mar 05 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 06, 2013 at 03:11:42AM +0100, Jesse Phillips wrote:
 On Monday, 4 March 2013 at 20:49:22 UTC, Andrea Fontana wrote:
 
Very interesting. IMHO that should be pointed out better in
docs/example.
You say interleaving is "default", how can I guess if a function
doesn't use the "default" behaviour?
It doesn't really make sense to point it out in the example since it is kind of fundamental to what ranges are. If it is eager than the docs should mention that. If an operation requires all its data upfront, sort, then you'll usually see a call for .array().
A range is an abstraction akin to C++'s iterators (except better, IMO). Just as iterators do not spontaneously consume the underlying data until you iterate over them, neither do ranges. T -- In a world without fences, who needs Windows and Gates? -- Christian Surchi
Mar 05 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
H. S. Teoh:

 A range is an abstraction akin to C++'s iterators (except 
 better, IMO).
Stepanov himself has commented very briefly about Alexandrescu/D Ranges in one of his video lessons. I have not fully understood what Stepanov has said with those few words spoken in a not so good English (not because of language, but because Stepanov is still out of my league, he's a Teacher) but I think he has dismissed the Ranges. A bit like a chemist would dismiss a person that says that molecules are more important than atoms and only molecules should be used. I think he has said that atoms are there (in a kind of mathematical Platonism), even if you try to ignore them, they are more fundamental. So Ranges are a little abstraction over C++-style iterators. They are maybe more handy, safer, they allow you to reason at a a bit higher lever, but they also forbid you to do few of the useful things that iterators can do. In the end I think ranges were a success for D. Almost every part of the design of D has problems; sometimes even large problems (like shared, problems with missing head and tail const, missing logic constness, problems with scope, and so on at nauseum), but most times D ranges work, despite some faults they have. Bye, bearophile
Mar 05 2013
parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 06, 2013 at 04:25:33AM +0100, bearophile wrote:
[...]
 Stepanov himself has commented very briefly about Alexandrescu/D
 Ranges in one of his video lessons. I have not fully understood what
 Stepanov has said with those few words spoken in a not so good
 English (not because of language, but because Stepanov is still out
 of my league, he's a Teacher) but I think he has dismissed the
 Ranges. A bit like a chemist would dismiss a person that says that
 molecules are more important than atoms and only molecules should be
 used.
 
 I think he has said that atoms are there (in a kind of mathematical
 Platonism), even if you try to ignore them, they are more
 fundamental. So Ranges are a little abstraction over C++-style
 iterators. They are maybe more handy, safer, they allow you to
 reason at a a bit higher lever, but they also forbid you to do few
 of the useful things that iterators can do.
 
 In the end I think ranges were a success for D. Almost every part of
 the design of D has problems; sometimes even large problems (like
 shared, problems with missing head and tail const, missing logic
 constness, problems with scope, and so on at nauseum), but most
 times D ranges work, despite some faults they have.
[...] I have used both C++ iterators and D ranges, and I have to say that even if some things possible with iterators are not possible with ranges, the concept of ranges has made std.algorithm/std.range so much easier to use. Consider how you would write code with composed ranges using C++ iterators. In D, because of the range abstraction, you can simply chain them in a logical manner; in C++, the fact that most algorithms need an iterator *pair* means chaining is very painful. You have to constantly keep track of which two iterators go together. Chaining requires wrappers to group iterator pairs together, unpack them when calling the next function, regroup them afterwards, etc.. Sure, everything is *possible* to do with iterators -- perhaps even more than ranges. But ranges are a much more convenient way to reason about and write these things, and the resulting code is much easier to read. T -- "Real programmers can write assembly code in any language. :-)" -- Larry Wall
Mar 05 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Mon, Mar 04, 2013 at 09:06:18PM +0100, Andrea Fontana wrote:
 If I understand it correctly something like:
 
 range.filter!(...).map!(...)
 
 browse range 2 times, one for filter and one for mapping doesn't it?
No, these algorithms are evaluated lazily (unless you put .array at the end). The range is only traversed once.
 Is there a way to "parallelize" this kind of operations?
What do you mean by "parallelize"? Run in multiple threads? I don't think you can do that, because the result of filter depends on what it gets from map. T -- Skill without imagination is craftsmanship and gives us many useful objects such as wickerwork picnic baskets. Imagination without skill gives us modern art. -- Tom Stoppard
Mar 04 2013
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
On 03/04/2013 12:06 PM, Andrea Fontana wrote:
 If I understand it correctly something like:

 range.filter!(...).map!(...)

 browse range 2 times, one for filter and one for mapping doesn't it?

 Is there a way to "parallelize" this kind of operations?
std.parallelism has lots of cool features to help with range parallelization. Here is map: http://dlang.org/phobos/std_parallelism.html#.TaskPool.map There are some examples of mine at http://ddili.org/ders/d.en/parallelism.html Here is an excerpt from the Summary section at that link: - parallel() executes the iterations of foreach loops in parallel. - asyncBuf() iterates the elements of an InputRange semi-eagerly in parallel. - map() calls functions with the elements of an InputRange semi-eagerly in parallel. - amap() calls functions with the elements of a RandomAccessRange fully-eagerly in parallel. - reduce() makes calculations over the elements of a RandomAccessRange in parallel. Ali
Mar 04 2013
parent "Andrea Fontana" <nospam example.com> writes:
On Monday, 4 March 2013 at 21:22:36 UTC, Ali Çehreli wrote:
 On 03/04/2013 12:06 PM, Andrea Fontana wrote:
 If I understand it correctly something like:

 range.filter!(...).map!(...)

 browse range 2 times, one for filter and one for mapping 
 doesn't it?

 Is there a way to "parallelize" this kind of operations?
std.parallelism has lots of cool features to help with range parallelization. Here is map: http://dlang.org/phobos/std_parallelism.html#.TaskPool.map There are some examples of mine at http://ddili.org/ders/d.en/parallelism.html Here is an excerpt from the Summary section at that link: - parallel() executes the iterations of foreach loops in parallel. - asyncBuf() iterates the elements of an InputRange semi-eagerly in parallel. - map() calls functions with the elements of an InputRange semi-eagerly in parallel. - amap() calls functions with the elements of a RandomAccessRange fully-eagerly in parallel. - reduce() makes calculations over the elements of a RandomAccessRange in parallel. Ali
Of course I used "parallelism" (with quotes) but i mean something like "interleaving" as guessed by Timon Gehr.
Mar 04 2013
prev sibling parent Russel Winder <russel winder.org.uk> writes:
On Mon, 2013-03-04 at 12:24 -0800, H. S. Teoh wrote:
[=E2=80=A6]
 Is there a way to "parallelize" this kind of operations?
=20 What do you mean by "parallelize"? Run in multiple threads? I don't think you can do that, because the result of filter depends on what it gets from map.
This shows the deficiency in thinking of explicit use of threads as the only way forward. filter =E2=86=92 map is a classic pipeline and if process= ed using a stream model over a thread pool using work stealing leads to code that is good. Alternatively do a parallel filter followed by a parallel map, data paralleism over a thread pool, more good code. --=20 Russel. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.winder ekiga.n= et 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Mar 05 2013