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:



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:



 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