• Advertisement

Archived

This topic is now archived and is closed to further replies.

"an algorithm is usually preferable to any hand-written loop"

This topic is 5098 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Advertisement
It''s beautiful when you can collapse an entire loop into one line of code:
for_each(accounts.begin(), accounts.end(), boost::bind(Account::Disconnect, _1)); 

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It''s essentially a reprint of one item (43) of Scott Meyers excellent book on STL.

Scott bring up a lot of good points on why you should do this.

The the biggest downside is that for each loop you are not writing you are probably writing another function so that you can pass it to the algorithm.

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
It''s essentially a reprint of one item (43) of Scott Meyers excellent book on STL.



I have the book but reckon there are plenty of people who don''t.

quote:
The the biggest downside is that for each loop you are not writing you are probably writing another function so that you can pass it to the algorithm.


I find, on the whole, that if I am refactoring code I will move the complicated contents of a loop into its own function with a nice clear name. Alternatively, if there''s not much going on in the loop, then, using boost.lambda, you can make simple one-liners.

Refactoring would suggest that if moving code into its own function makes it clearer what is happening then it''s a good idea.

Share this post


Link to post
Share on other sites
It''s a nice thought, but for it to have weight the algorithms in C++ would need to be more natural - which would require extensive modification of the language. Let''s take antareus'' example:
for_each(accounts.begin(), accounts.end(), boost::bind(Account::Disconnect, _1)); 
The thing is a horror! And that''s the simplest sort. It''s not an intuitive construction (until you actually start thinking in C++, which, frankly, is frightening), and it makes use of the completely orthogonal identifier _1 (which you and I may know as a bit of template magic to extract the positional iterator, dereference and apply to the function as a parameter, but does it visually suggest that?). Then complicate the matter by requiring multiple parameters.

An elegant construction would be something along the lines of
for acct in accounts
{
acct.Disconnect();
}
By Jove! Why does that seem so familiar...? Oh, wait, that''s Perl syntax! (Python is much the same, except replacing the braces with a colon and indentation.)

The article may make a perfectly valid academic opinion, but it fails to countenance the widely varying levels of skill of programmers and the horrible construction of most algorithms (restriction of the language, not deficiencies of the algorithm writers). So, bleh.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hmm... seems familar to me too... maybe...

for each acct in accounts
acct.disconnect
next acct

Ahh, vb anyone?

Share this post


Link to post
Share on other sites
What are the PERL, Python and VB equivalents of the following

find
find_if
adjacent_find
find_first_of
count
count_if
mismatch
equal
search
search_n
find_end
accumulate

These functions provide all the state variables needed without you having to worry about it. Something like search_n isn't a trivial thing to be writing out by hand every time.

It's easy to try and discount the whole idea of using algorithms just because using for_each doesn't seem to buy you much.

[edited by - petewood on March 5, 2004 9:00:12 AM]

Share this post


Link to post
Share on other sites
I agree, while for_each is somewhat cumbersome and ugly (i usually end up writing an iterator-for instead), many of the other stuff in algorithm is great!

[edited by - marijnh on March 6, 2004 8:07:53 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by petewood
These functions provide all the state variables needed without you having to worry about it. Something like search_n isn''t a trivial thing to be writing out by hand every time.
Agreed. In C++. In Python, I''d use a list comprehension or other tool.

quote:
It''s easy to try and discount the whole idea of using algorithms just because using for_each doesn''t seem to buy you much.
That''s not my point. My point is that the utility that these algorithms provide only exists because writing equivalent code is non-trivial - a language flaw. I''m no fan of adapting what are essentially system languages to high-level work; I feel it isn''t particularly productive. I would much rather use the system language to extend a truly high-level language, and thus gain the benefits of both where appropriate.

The STL is great. It''s a massive boon to C++ developers, poor devils that they are.

Share this post


Link to post
Share on other sites
quote:
Original post by Oluseyi
My point is that the utility that these algorithms provide only exists because writing equivalent code is non-trivial - a language flaw. I''m no fan of adapting what are essentially system languages to high-level work; I feel it isn''t particularly productive. I would much rather use the system language to extend a truly high-level language, and thus gain the benefits of both where appropriate.

The STL is great. It''s a massive boon to C++ developers, poor devils that they are.


Indeed. In my work I have to use C++. I''ve introduced Python as a replacement for our old macro language in applications but we aren''t going to be programming in the main in high-level languages any time soon. A lot of what I do is number crunching code, engineering calculations and fast display of large volumes of data graphically. I know choosing C++ is premature optimisation but that''s what we use.

Share this post


Link to post
Share on other sites
quote:
Original post by petewood
Indeed. In my work I have to use C++. I''ve introduced Python as a replacement for our old macro language in applications but we aren''t going to be programming in the main in high-level languages any time soon. A lot of what I do is number crunching code, engineering calculations and fast display of large volumes of data graphically. I know choosing C++ is premature optimisation but that''s what we use.
Two words: Numerical Python.

Share this post


Link to post
Share on other sites
I should clarify beautiful.

Beautiful in the purely masochistic sense. Learning boost::bind is not something you can just sit down and do in 30 minutes flat (maybe if you had functional background). I should be able to say:
for_each(accounts.begin(), accounts.end(), Account::Disconnect);

When we''re on the subject of the algorithm header, whats the deal with std::remove? It doesn''t actually remove anything, you have to call erase with it. Not at all intuitive.

However, I think C# does a very good job of making incremental improvements. It is a shame that generics are crippled like they are and we might not see something akin to the STL. Then again, maybe its a good thing.

Share this post


Link to post
Share on other sites
quote:
Original post by antareus
However, I think C# does a very good job of making incremental improvements. It is a shame that generics are crippled like they are and we might not see something akin to the STL. Then again, maybe its a good thing.
What''s your opinion of type?

I''m fond of strong, dynamic typing (which completely eliminates the need for templates/generics). I think that, like the algorithms, generics are another attempt to graft high-level methods onto a low-level approach.

Share this post


Link to post
Share on other sites
quote:
What are the PERL, Python and VB equivalents of the following


find the ''index'' member of list objects
find_if filter(pred, list)[0]
adjacent_find has no simple equivalent
find_first_of filter(lambda x: x not in list2, list1)
count ''count'' member of list obj
count_if has no simple equivalent
mismatch list1[first1:last1] == list2[first2: first2 + (last1 - first1)]
equal equality works this way anyway
search has no simple equivalent
search_n has no simple equivalent I can think of
find_end has no simple equivalent
accumulate has no simple equivalent

and by "simple" I mean one reasonable length line.

Share this post


Link to post
Share on other sites
quote:
Original post by Oluseyi
An elegant construction would be something along the lines of
for acct in accounts
{
acct.Disconnect();
}
By Jove! Why does that seem so familiar...? Oh, wait, that's Perl syntax! (Python is much the same, except replacing the braces with a colon and indentation.)


Actually perl would be more like

foreach my $acct (@accounts) { $acct->Disconnect(); }


or perhaps

map { $_->Disconnect(); } @accounts;


At least the way I'm used to writing it.

I do miss certain things in these "higher-level" control structures that you get in lower-level languages - in particular, having an integer index which increments with each loop iteration (have to add it in yourself; of course you basically do anyway in C++ etc., but I'd rather have something that feels more "automatic"), and some control over the iteration order - at minimum, the ability to go in reverse.

Sitting on my HD now is a sketch of what TPK would look like in my ideal language:


function main(string[] args) : int_4(d)
a : float_8[11]()
for x each a do x.read(stdin)
for x each a reverse_order counted_by i
y : f(x)
if (y > 400.0) do "% TOO LARGE".sub(i).write(stdout)
else do "%\t%\n".sub(i).sub(y).write(stdout)

function f(float_8 t) : float_8(|t|^ .5 + 5 * t ^ 3)


Of course, TPK tends not to show off high-level languages too well seeing as how it manipulates primitive types...



[edited by - Zahlman on March 5, 2004 2:47:41 PM]

Share this post


Link to post
Share on other sites
I''d never heard of TPK so I googled and found this page. I kind of like the ML version when reformulated as a functional program:

The SML Program: tpk.sml
1 (* tpk.sml -- Knuth''s TPK program in Standard ML *)
2 let
3 (* define the function f(x) = sqrt(|x|) + 5*x**3 *)
4 fun f (x) = Real.Math.sqrt (abs x) + 5.0 * (Real.Math.pow (x, 3.0));
5
6 (* define an auxiliary print function *)
7 fun pr (f) =
8 print ((if f>400.0 then " too large" else Real.toString f)^"\n");
9
10 (* define an auxiliary function to read real numbers; one per line *)
11 fun read () =
12 Option.valOf (Real.fromString (TextIO.inputLine TextIO.stdIn));
13
14 (* declare and initialize the values of the array "A" *)
15 val A = Array.tabulate (11, fn _ => read ());
16
17 val i = ref 10;
18 in
19 while !i>=0 do (pr (f (Array.sub (A, !i))); i:= !i - 1)
20 end;
21
22
23 (* Reformulation of TPK in a "functional" way. *)
24 local
25 fun f (x) = Real.Math.sqrt (abs x) + 5.0 * (Real.Math.pow (x, 3.0));
26 fun p (x) = x<400.0
27 in
28 fun tpk (l) = List.filter p (List.map f (List.rev l));
29 end;

Share this post


Link to post
Share on other sites
And here's a python version inspired by the ML version. Ok, I know it doesn't do *exactly* what TPK does but it's in the same spirit and I think it's pretty neat.

import math

def f(x):
return math.sqrt(abs(x)) + 5 * x ** 3

def p(x):
return x < 400

def tpk(l):
return filter(p, map(f, l[::-1]))

l = [int(raw_input('>')) for i in range(11)]
print tpk(l)


[edited by - mattnewport on March 5, 2004 4:16:00 PM]

[edited by - mattnewport on March 5, 2004 4:17:40 PM]

Share this post


Link to post
Share on other sites
Ok, just one more Python version... This time it''s closer to the exact behaviour of TPK. I think it''s a bit less elegant than the straight functional version but it does show off how handy Python''s dynamic typing can be.

import math

def f(x): return x, math.sqrt(abs(x)) + 5 * x ** 3

def p(x):
if x[1] > 400: return "TOO LARGE"
else: return x

def tpk(l): return map(p, map(f, l[::-1]))

l = [int(raw_input(''>'')) for i in range(11)]
for item in tpk(l): print item

Share this post


Link to post
Share on other sites
quote:
Original post by Oluseyi
What''s your opinion of type?

I''m fond of strong, dynamic typing (which completely eliminates the need for templates/generics). I think that, like the algorithms, generics are another attempt to graft high-level methods onto a low-level approach.

I don''t feel I have enough experience to comment adequetely. I have used strong/weak and static/dynamic typing, but I really have only done things of appreciable substance in a static, weak type system (C++).

Ask me again in two years.

Share this post


Link to post
Share on other sites
quote:
Original post by antareus
for_each(accounts.begin(), accounts.end(), Account::Disconnect);



I can give you
for_every(accounts, Account::Disconnect);


#include <MKH/Meta/FunctionSignature.hpp>

template<class Container, typename Functor>
Container& for_every(Container& c, Functor fn)
{
typename Container::iterator it = c.begin();
typename Container::iterator itEnd = c.end();
for(; it!=itEnd; ++it)
MKH::Meta::invoke(fn, *it);
return c;
}



//Deep Magic


#ifdef _MSC_VER
#pragma once
#endif

#ifndef MKH_FUNCTIONSIGNATURE_HPP
#define MKH_FUNCTIONSIGNATURE_HPP

#include <Loki/Typelist.h>

namespace MKH
{
namespace Meta
{
//BS prototype for us to specialize

template<typename R, typename T1 = void>
struct FunctionSignature;

//Member Functions

template<typename R, class Cls>
struct FunctionSignature<R (Cls::*)(void)>
{
typedef R (Cls::*Functor)(void);
typedef R Result;
typedef Cls Class;
typedef Loki::NullType Params;
static const int nParams = 0;
static R invoke(Functor fn, Cls& This)
{
return (This.*fn)();
}
};

template<typename R, class Cls, typename T1>
struct FunctionSignature<R (Cls::*)(T1)>
{
typedef R (Cls::*Functor)(void);
typedef R Result;
typedef Cls Class;
typedef TYPELIST_1(T1) Params;
static const int nParams = 1;
static R invoke(Functor fn, Cls& This, T1 t1)
{
return (This.*fn)(t1);
}
};

template<typename R, class Cls, typename T1, typename T2>
struct FunctionSignature<R (Cls::*)(T1, T2)>
{
typedef R (Cls::*Functor)(void);
typedef R Result;
typedef Cls Class;
typedef TYPELIST_2(T1, T2) Params;
static const int nParams = 2;
};
template<typename R, class Cls, typename T1, typename T2, typename T3>
struct FunctionSignature<R (Cls::*)(T1, T2, T3)>
{
typedef R (Cls::*Functor)(void);
typedef R Result;
typedef Cls Class;
typedef TYPELIST_3(T1, T2, T3) Params;
static const int nParams = 3;
};
template<typename R, class Cls, typename T1, typename T2, typename T3, typename T4>
struct FunctionSignature<R (Cls::*)(T1, T2, T3, T4)>
{
typedef R (Cls::*Functor)(void);
typedef R Result;
typedef Cls Class;
typedef TYPELIST_4(T1, T2, T3, T4) Params;
static const int nParams = 4;
};

//Normal Functions

template<typename R>
struct FunctionSignature<R (*)(void)>
{
typedef R (*Functor)(void);
typedef R Result;
typedef TYPELIST_1(void) Params;
};
template<typename R, typename T1>
struct FunctionSignature<R(*)(T1)>
{
typedef R (*Functor)(T1);
typedef R Result;
typedef TYPELIST_1(T1) Params;
};
template<typename R, typename T1, typename T2>
struct FunctionSignature<R(*)(T1, T2)>
{
typedef R (*Functor)(T1, T2);
typedef R Result;
typedef TYPELIST_2(T1, T2) Params;
};

template<class Invocable>
typename FunctionSignature<Invocable>::Result invoke(Invocable& invocable)
{
return FunctionSignature<Invocable>::invoke(invocable);
}
template<class Invocable, typename T1>
typename FunctionSignature<Invocable>::Result invoke(Invocable& invocable, T1 t1)
{
return FunctionSignature<Invocable>::invoke(invocable, t1);
}
template<class Invocable, typename T1, typename T2>
typename FunctionSignature<Invocable>::Result invoke(Invocable& invocable, T1 t1, T2 t2)
{
return FunctionSignature<Invocable>::invoke(invocable, t1, t2);
}
template<class Invocable, typename T1, typename T2, typename T3>
typename FunctionSignature<Invocable>::Result invoke(Invocable& invocable, T1 t1, T2 t2, T3 t3)
{
return FunctionSignature<Invocable>::invoke(invocable, t1, t2, t3);
}
template<class Invocable, typename T1, typename T2, typename T3, typename T4>
typename FunctionSignature<Invocable>::Result invoke(Invocable& invocable, T1 t1, T2 t2, T3 t3, T4 t4)
{
return FunctionSignature<Invocable>::invoke(invocable, t1, t2, t3, t4);
}

}//ns Meta

}//ns MKH


#endif //MKH_FUNCTIONSIGNATURE_HPP




[edited by - Magmai Kai Holmlor on March 5, 2004 9:56:00 PM]

Share this post


Link to post
Share on other sites
I ought to point out, the Collection iteration in VB is really very nice...


Public IntList as Collection
''Obviously IntList should actually be set somewhere

Public Sub Foo()
Dim Item as Variant

For Each Item In IntList
''something or the other...
Item = 5
Next Item
End Sub


VB is generally a bit on the verbose side, but it doesn''t really get much more obvious what you''re doing than in the above code sample. It practically reads as English.

Share this post


Link to post
Share on other sites
First of all, the original post doesn''t even make sense. It seems to suggest that an Algorithm and a hand-written loop are completely different things. A loop is the basis of virtually all algorithms and someone had to hand-write it to begin with.
The ONLY difference is that STL algorithms have been used by more people.

The only question is will a general purpose algorithm do, or are there things about my code/structures that STL does not know about that I can take advantage of to make my code faster, and do i NEED to make it faster!

I have been writing algorithms myself for over a decade with no regrets.

Share this post


Link to post
Share on other sites
quote:
Original post by iMalc
First of all, the original post doesn't even make sense.

!

quote:
It seems to suggest that an Algorithm and a hand-written loop are completely different things. A loop is the basis of virtually all algorithms and someone had to hand-write it to begin with.
The ONLY difference is that STL algorithms have been used by more people.

I have been writing algorithms myself for over a decade with no regrets.


The algorithms that the article refers to are those in the STL algorithm header

[edited by - petewood on March 6, 2004 6:33:07 AM]

Share this post


Link to post
Share on other sites

  • Advertisement