c++ - vorteil - python lambda funktionen




Rekursive Lambda-Funktionen in C++ 11 (9)

C ++ 14: Hier ist ein rekursiver anonymer stateless / no capture generischer Satz von lambdas, der alle Zahlen von 1, 20 ausgibt

([](auto f, auto n, auto m) {
    f(f, n, m);
})(
    [](auto f, auto n, auto m) -> void
{
    cout << typeid(n).name() << el;
    cout << n << el;
    if (n<m)
        f(f, ++n, m);
},
    1, 20);

Wenn ich das richtig verstehe, verwende ich die Y-Kombinator-Lösung

Und hier ist die Summe (n, m) Version

auto sum = [](auto n, auto m) {
    return ([](auto f, auto n, auto m) {
        int res = f(f, n, m);
        return res;
    })(
        [](auto f, auto n, auto m) -> int
        {
            if (n > m)
                return 0;
            else {
                int sum = n + f(f, n + 1, m);
                return sum;
            }
        },
        n, m); };

auto result = sum(1, 10); //result == 55

Ich bin neu in C ++ 11. Ich schreibe die folgende rekursive Lambda-Funktion, aber es kompiliert nicht.

sum.cpp

#include <iostream>
#include <functional>

auto term = [](int a)->int {
  return a*a;
};

auto next = [](int a)->int {
  return ++a;
};

auto sum = [term,next,&sum](int a, int b)mutable ->int {
  if(a>b)
    return 0;
  else
    return term(a) + sum(next(a),b);
};

int main(){
  std::cout<<sum(1,10)<<std::endl;
  return 0;
}

Kompilierungsfehler:

vimal @ linux-718q: ~ / Studie / 09C ++ / c ++ 0x / lambda> g ++ -std = c ++ 0x sum.cpp

sum.cpp: In der Lambda-Funktion: sum.cpp: 18: 36: Fehler: ' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum ' kann nicht verwendet werden als eine Funktion

GCC-Version

gcc Version 4.5.0 20091231 (experimentell) (GCC)

Aber wenn ich die Deklaration von sum() wie folgt ändere, funktioniert es:

std::function<int(int,int)> sum = [term,next,&sum](int a, int b)->int {
   if(a>b)
     return 0;
   else
     return term(a) + sum(next(a),b);
};

Könnte jemand bitte Licht darauf werfen?


Denken Sie über den Unterschied zwischen der Auto- Version und der voll spezifizierten Typ-Version nach. Das Schlüsselwort auto leitet seinen Typ von dem ab, mit dem es initialisiert wurde, aber was Sie initialisieren, muss wissen, was sein Typ ist (in diesem Fall muss der Lambda-Verschluss die Typen kennen, die er erfasst). Etwas von einem Huhn-und-Ei-Problem.

Auf der anderen Seite muss ein vollständig spezifizierter Funktionsobjekttyp nichts darüber wissen, was ihm zugewiesen wird, und so kann die Schließung des Lambdas ebenfalls vollständig über die Typen, die er erfasst, informiert werden.

Betrachten Sie diese geringfügige Änderung Ihres Codes und es könnte mehr Sinn machen:

std::function<int(int,int)> sum;
sum = [term,next,&sum](int a, int b)->int {
if(a>b)
    return 0;
else
    return term(a) + sum(next(a),b);
};

Offensichtlich würde dies nicht mit Auto funktionieren. Rekursive Lambda-Funktionen funktionieren perfekt (zumindest in MSVC, wo ich Erfahrung mit ihnen habe), nur dass sie nicht wirklich mit Typinferenz kompatibel sind.


Dies ist eine etwas einfachere Implementierung des Fixpoint-Operators, die es etwas genauer macht, was genau vor sich geht.

#include <iostream>
#include <functional>

using namespace std;

template<typename T, typename... Args>
struct fixpoint
{
    typedef function<T(Args...)> effective_type;
    typedef function<T(const effective_type&, Args...)> function_type;

    function_type f_nonr;

    T operator()(Args... args) const
    {
        return f_nonr(*this, args...);
    }

    fixpoint(const function_type& p_f)
        : f_nonr(p_f)
    {
    }
};


int main()
{
    auto fib_nonr = [](const function<int(int)>& f, int n) -> int
    {
        return n < 2 ? n : f(n-1) + f(n-2);
    };

    auto fib = fixpoint<int,int>(fib_nonr);

    for (int i = 0; i < 6; ++i)
    {
        cout << fib(i) << '\n';
    }
}

Diese Antwort ist schlechter als die von Yankes, aber trotzdem, hier ist es:

using dp_type = void (*)();

using fp_type = void (*)(dp_type, unsigned, unsigned);

fp_type fp = [](dp_type dp, unsigned const a, unsigned const b) {
  ::std::cout << a << ::std::endl;
  return reinterpret_cast<fp_type>(dp)(dp, b, a + b);
};

fp(reinterpret_cast<dp_type>(fp), 0, 1);

Ich habe eine andere Lösung, arbeite aber nur mit staatenlosen Lambdas:

void f()
{
    static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; };
    std::cout<<self(10);
}

Trick hier ist, dass Lambdas auf statische Variablen zugreifen können, und Sie können statuslose in Funktionszeiger umwandeln.

Sie können es mit Standardlambdas verwenden:

void g()
{
    int sum;
    auto rec = [&sum](int i) -> int
    {
        static int (*inner)(int&, int) = [](int& _sum, int i)->int 
        {
            _sum += i;
            return i>0 ? inner(_sum, i-1)*i : 1; 
        };
        return inner(sum, i);
    };
}

Seine Arbeit in GCC 4.7


Ich habe einen Benchmark durchgeführt, der eine rekursive Funktion mit einer rekursiven Lambda-Funktion vergleicht, indem ich die Methode std::function<> capture verwende. Mit vollen Optimierungen, die in der clang-Version 4.1 aktiviert waren, lief die Lambda-Version deutlich langsamer.

#include <iostream>
#include <functional>
#include <chrono>

uint64_t sum1(int n) {
  return (n <= 1) ? 1 : n + sum1(n - 1);
}

std::function<uint64_t(int)> sum2 = [&] (int n) {
  return (n <= 1) ? 1 : n + sum2(n - 1);
};

auto const ITERATIONS = 10000;
auto const DEPTH = 100000;

template <class Func, class Input>
void benchmark(Func&& func, Input&& input) {
  auto t1 = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i != ITERATIONS; ++i) {
    func(input);
  }
  auto t2 = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count();
  std::cout << "Duration: " << duration << std::endl;
}

int main() {
  benchmark(sum1, DEPTH);
  benchmark(sum2, DEPTH);
}

Produziert Ergebnisse:

Duration: 0 // regular function
Duration: 4027 // lambda function

(Anmerkung: Ich habe das auch mit einer Version bestätigt, die die Eingaben von cin übernommen hat, um die Kompilierzeitauswertung zu eliminieren)

Clang erzeugt auch eine Compiler-Warnung:

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

Was erwartet wird, und sicher, aber sollte beachtet werden.

Es ist großartig, eine Lösung in unseren Toolbelts zu haben, aber ich denke, die Sprache wird einen besseren Weg brauchen, um mit diesem Fall umzugehen, wenn die Performance mit den aktuellen Methoden vergleichbar sein soll.

Hinweis:

Wie ein Kommentator herausstellte, scheint die neueste Version von VC ++ einen Weg gefunden zu haben, dies bis zur gleichen Leistung zu optimieren. Vielleicht brauchen wir schließlich keinen besseren Weg, um damit fertig zu werden (außer für syntaktischen Zucker).

Wie einige andere SO-Posts in den letzten Wochen beschrieben haben, kann die Leistung von std::function<> selbst der Grund für die Verlangsamung gegen die Aufruffunktion sein, zumindest wenn die Lambda-Erfassung zu groß ist, um in einige Bibliotheksoptimierungen zu passen Leerzeichen std::function verwendet für kleine Funktoren (ich denke mal wie die verschiedenen kurzen String-Optimierungen?).


Sie können eine Lambda-Funktion veranlassen, sich selbst rekursiv aufzurufen. Das einzige, was Sie tun müssen, ist, es durch einen Funktions-Wrapper zu referenzieren, so dass der Compiler seinen Rückgabe- und Argumenttyp kennt (Sie können keine Variable - das Lambda selbst - erfassen, das noch nicht definiert wurde) .

  function<int (int)> f;

  f = [&f](int x) {
    if (x == 0) return 0;
    return x + f(x-1);
  };

  printf("%d\n", f(10));

Seien Sie sehr vorsichtig, um nicht aus dem Rahmen des Wrappers f zu gehen.


Sie benötigen einen Fixpunktkombinator. Sieh this .

oder schau dir den folgenden Code an:

//As decltype(variable)::member_name is invalid currently, 
//the following template is a workaround.
//Usage: t2t<decltype(variable)>::t::member_name
template<typename T>
struct t2t
{
    typedef T t;
};

template<typename R, typename V>
struct fixpoint
{
    typedef std::function<R (V)> func_t;
    typedef std::function<func_t (func_t)> tfunc_t;
    typedef std::function<func_t (tfunc_t)> yfunc_t;

    class loopfunc_t {
    public:
        func_t operator()(loopfunc_t v)const {
            return func(v);
        }
        template<typename L>
        loopfunc_t(const L &l):func(l){}
        typedef V Parameter_t;
    private:
        std::function<func_t (loopfunc_t)> func;
    };
    static yfunc_t fix;
};
template<typename R, typename V>
typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix = 
[](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t {
    fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) ->
        fixpoint<R, V>::func_t{
            //f cannot be captured since it is not a local variable
            //of this scope. We need a new reference to it.
            auto &ff = f;
            //We need struct t2t because template parameter
            //V is not accessable in this level.
            return [ff, x](t2t<decltype(x)>::t::Parameter_t v){
                return ff(x(x))(v); 
            };
        }; 
        return l(l);
    };

int _tmain(int argc, _TCHAR* argv[])
{
    int v = 0;
    std::function<int (int)> fac = 
    fixpoint<int, int>::fix([](std::function<int (int)> f)
        -> std::function<int (int)>{
        return [f](int i) -> int{
            if(i==0) return 1;
            else return i * f(i-1);
        };
    });

    int i = fac(10);
    std::cout << i; //3628800
    return 0;
}

Um Lambda rekursiv zu machen, ohne externe Klassen und Funktionen zu verwenden (wie std::function oder fixed-point combinator), kann man die folgende Konstruktion in C ++ 14 ( live example ) verwenden:

#include <utility>
#include <list>
#include <memory>
#include <iostream>

int main()
{
    struct tree
    {
        int payload;
        std::list< tree > children = {}; // std::list of incomplete type is allowed
    };
    std::size_t indent = 0;
    // indication of result type here is essential
    const auto print = [&] (const auto & self, const tree & node) -> void
    {
        std::cout << std::string(indent, ' ') << node.payload << '\n';
        ++indent;
        for (const tree & t : node.children) {
            self(self, t);
        }
        --indent;
    };
    print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});
}

Drucke:

1
 2
  8
 3
  5
   7
  6
 4

Hinweis, der Ergebnistyp von Lambda sollte explizit angegeben werden.





lambda