digitalmars.D.learn - map! filter! and range algorithm
- Andrea Fontana (5/5) Mar 04 2013 If I understand it correctly something like:
- Timon Gehr (4/8) Mar 04 2013 Interleaving is the default. To perform two traversals you'd have to
- Andrea Fontana (5/19) Mar 04 2013 Very interesting. IMHO that should be pointed out better in
- Jesse Phillips (6/10) Mar 05 2013 It doesn't really make sense to point it out in the example since
- H. S. Teoh (7/20) Mar 05 2013 A range is an abstraction akin to C++'s iterators (except better, IMO).
- bearophile (22/24) Mar 05 2013 Stepanov himself has commented very briefly about Alexandrescu/D
- H. S. Teoh (19/40) Mar 05 2013 [...]
- H. S. Teoh (11/17) Mar 04 2013 No, these algorithms are evaluated lazily (unless you put .array at the
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (17/21) Mar 04 2013 std.parallelism has lots of cool features to help with range
- Andrea Fontana (3/30) Mar 04 2013 Of course I used "parallelism" (with quotes) but i mean something
- Russel Winder (18/23) Mar 05 2013 This shows the deficiency in thinking of explicit use of threads as the
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
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
On Monday, 4 March 2013 at 20:21:31 UTC, Timon Gehr wrote:On 03/04/2013 09:06 PM, 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?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
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
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: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 SurchiVery 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
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
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
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
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
On Monday, 4 March 2013 at 21:22:36 UTC, Ali Çehreli wrote:On 03/04/2013 12:06 PM, Andrea Fontana wrote:Of course I used "parallelism" (with quotes) but i mean something like "interleaving" as guessed by Timon Gehr.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
On Mon, 2013-03-04 at 12:24 -0800, H. S. Teoh wrote: [=E2=80=A6]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_winderIs 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.
Mar 05 2013