Dlaczego leniwa ocena jest przydatna?

119

Od dawna zastanawiałem się, dlaczego leniwa ocena jest przydatna. Nikt jeszcze nie wyjaśnił mi w sposób, który miałby sens; przeważnie kończy się to „zaufaniem mi”.

Uwaga: nie mam na myśli zapamiętywania.

Joel McCracken
źródło

Odpowiedzi:

96

Głównie dlatego, że może być bardziej wydajne - wartości nie muszą być obliczane, jeśli nie będą używane. Na przykład mogę przekazać do funkcji trzy wartości, ale w zależności od sekwencji wyrażeń warunkowych, w rzeczywistości może być używany tylko podzbiór. W języku takim jak C wszystkie trzy wartości i tak zostałyby obliczone; ale w Haskell obliczane są tylko niezbędne wartości.

Pozwala także na fajne rzeczy, takie jak nieskończone listy. Nie mogę mieć nieskończonej listy w języku takim jak C, ale w Haskell to żaden problem. Nieskończone listy są dość często używane w pewnych obszarach matematyki, więc przydatna może być umiejętność manipulowania nimi.

mipadi
źródło
6
Python leniwie ocenia nieskończone listy za pomocą iteratorów
Mark Cidade
4
W rzeczywistości możesz emulować nieskończoną listę w Pythonie za pomocą generatorów i wyrażeń generatorów (które działają podobnie do rozumienia list): python.org/doc/2.5.2/ref/genexpr.html
John Montgomery,
24
Generatory ułatwiają tworzenie leniwych list w Pythonie, ale inne techniki leniwej oceny i struktury danych są znacznie mniej eleganckie.
Peter Burns
3
Obawiam się, że nie zgodziłbym się z tą odpowiedzią. Kiedyś myślałem, że lenistwo dotyczy wydajności, ale po zastosowaniu Haskella w znacznej ilości, a następnie przestawieniu się na Scalę i porównaniu doświadczeń, muszę powiedzieć, że lenistwo ma znaczenie często, ale rzadko ze względu na wydajność. Myślę, że Edward Kmett trafia w prawdziwe powody.
Owen
3
Podobnie nie zgadzam się, chociaż nie ma wyraźnego pojęcia nieskończonej listy w C z powodu ścisłej oceny, możesz łatwo wykonać tę samą sztuczkę w dowolnym innym języku (i rzeczywiście, w większości rzeczywistej implementacji każdego leniwego języka), używając thunks i funkcji przekazywania wskaźniki do pracy ze skończonym prefiksem nieskończonej struktury utworzonej przez podobne wyrażenia.
Kristopher Micinski
71

Użytecznym przykładem leniwej oceny jest użycie quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Jeśli teraz chcemy znaleźć minimum z listy, możemy zdefiniować

minimum ls = head (quickSort ls)

Który najpierw sortuje listę, a następnie zajmuje pierwszy element listy. Jednak z powodu leniwej oceny obliczana jest tylko głowa. Na przykład, jeśli weźmiemy minimum z listy, [2, 1, 3,]quickSort najpierw odfiltruje wszystkie elementy mniejsze niż dwa. Następnie wykonuje na tym quickSort (zwraca listę singletonów [1]), co już wystarczy. Z powodu leniwej oceny reszta nigdy nie jest sortowana, co pozwala zaoszczędzić dużo czasu obliczeniowego.

To oczywiście bardzo prosty przykład, ale lenistwo działa w ten sam sposób w przypadku programów, które są bardzo duże.

Wszystko to ma jednak wadę: trudniej jest przewidzieć szybkość działania i wykorzystanie pamięci programu. Nie oznacza to, że leniwe programy działają wolniej lub zajmują więcej pamięci, ale dobrze jest wiedzieć.

Chris Eidhof
źródło
19
Mówiąc bardziej ogólnie, take k $ quicksort listzajmuje tylko O ​​(n + k log k) czas, gdzie n = length list. W przypadku nieleniwego sortowania porównawczego zajmie to zawsze O (n log n) czasu.
ephemient
@ephemient czy nie masz na myśli O (nk log k)?
MaiaVictor
1
@Viclib Nie, miałem na myśli to, co powiedziałem.
ephemient
@ephemient to chyba nie rozumiem, niestety
MaiaVictor
2
@Viclib Algorytm selekcji służący do znajdowania k górnych elementów spośród n to O (n + k log k). Gdy implementujesz quicksort w leniwym języku i oceniasz go tylko na tyle daleko, aby określić pierwsze k elementów (zatrzymując ocenę po), dokonuje dokładnie takich samych porównań, jak zrobiłby to nieleniwy algorytm selekcji.
ephemient
70

Uważam, że leniwe ocenianie jest przydatne w wielu przypadkach.

Po pierwsze, wszystkie istniejące języki leniwe są czyste, ponieważ bardzo trudno jest wnioskować o skutkach ubocznych w leniwym języku.

Czyste języki pozwalają wnioskować o definicjach funkcji za pomocą rozumowania równań.

foo x = x + 3

Niestety w ustawieniu nieleniwym więcej instrukcji kończy się niepowodzeniem niż w ustawieniu leniwym, więc jest to mniej przydatne w językach takich jak ML. Ale w leniwym języku możesz bezpiecznie rozumować o równości.

Po drugie, wiele rzeczy, takich jak „ograniczenie wartości” w ML, nie jest potrzebnych w leniwych językach, takich jak Haskell. Prowadzi to do wielkiego uporządkowania składni. ML jak języki muszą używać słów kluczowych, takich jak var lub fun. W Haskell wszystko to sprowadza się do jednego pojęcia.

Po trzecie, lenistwo pozwala napisać bardzo funkcjonalny kod, który można zrozumieć fragmentami. W Haskell często pisze się ciało funkcji takie jak:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Pozwala to pracować „z góry na dół” poprzez zrozumienie istoty funkcji. Języki podobne do ML zmuszają cię do używania letściśle ocenianego. W związku z tym nie odważysz się „podnieść” klauzuli let do głównej części funkcji, ponieważ jeśli jest droga (lub ma skutki uboczne), nie chcesz, aby była ona zawsze oceniana. Haskell może „odepchnąć” szczegóły do ​​klauzuli where wyraźnie, ponieważ wie, że zawartość tej klauzuli będzie oceniana tylko w razie potrzeby.

W praktyce mamy tendencję do używania osłon i zawalania ich dalej, aby:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Po czwarte, lenistwo czasami oferuje znacznie bardziej elegancki wyraz pewnych algorytmów. Leniwe „szybkie sortowanie” w Haskell jest jednolinijne i ma tę zaletę, że jeśli spojrzysz tylko na kilka pierwszych pozycji, zapłacisz tylko koszty proporcjonalne do kosztu wybrania tylko tych przedmiotów. Nic nie stoi na przeszkodzie, abyś zrobił to ściśle, ale prawdopodobnie za każdym razem musiałbyś ponownie kodować algorytm, aby osiągnąć taką samą asymptotyczną wydajność.

Po piąte, lenistwo pozwala zdefiniować nowe struktury kontrolne w języku. Nie możesz napisać nowego „if… then… else…”, na przykład konstrukcji w ścisłym języku. Jeśli spróbujesz zdefiniować funkcję taką jak:

if' True x y = x
if' False x y = y

w języku ścisłym obie gałęzie byłyby oceniane niezależnie od wartości warunku. Pogarsza się, gdy weźmiesz pod uwagę pętle. Wszystkie surowe rozwiązania wymagają od języka podania jakiegoś cytatu lub jawnej konstrukcji lambda.

Wreszcie, w tym samym duchu, niektóre z najlepszych mechanizmów radzenia sobie ze skutkami ubocznymi w systemie czcionek, takie jak monady, naprawdę można skutecznie wyrazić tylko w leniwym otoczeniu. Można to zobaczyć, porównując złożoność przepływów pracy F # z Haskell Monadami. (Możesz zdefiniować monadę w ścisłym języku, ale niestety często zawiedziesz jedno lub dwa prawa dotyczące monady z powodu braku lenistwa i przepływu pracy, w porównaniu do zbierania ton surowego bagażu.)

Edward KMETT
źródło
5
Bardzo dobrze; to są prawdziwe odpowiedzi. Kiedyś myślałem, że chodzi o wydajność (opóźnianie obliczeń na później), dopóki nie użyłem znacznej ilości Haskella i nie zobaczyłem, że to wcale nie jest powód.
Owen
11
Ponadto, chociaż technicznie nie jest prawdą, że leniwy język musi być czysty (na przykład R), prawdą jest, że nieczysty leniwy język może robić bardzo dziwne rzeczy (na przykład R).
Owen
4
Jasne, że tak. W ścisłym języku rekurencja letjest niebezpieczną bestią, w schemacie R6RS pozwala na #fpojawienie się przypadkowych znaków w twoim terminie wszędzie tam, gdzie wiązanie węzła ściśle prowadziło do cyklu! Żadna gra słów nie zamierzona, ale ściśle bardziej rekurencyjne letpowiązania są sensowne w leniwym języku. Ścisłość potęguje również fakt, że w whereogóle nie ma możliwości uporządkowania względnych efektów, z wyjątkiem SCC, jest to konstrukcja na poziomie instrukcji, jej skutki mogą następować w dowolnej kolejności, a nawet jeśli masz czysty język, kończysz z #fkwestia. Ścisłe wherezagadki twojego kodu nie są lokalne.
Edward KMETT
2
Czy możesz wyjaśnić, w jaki sposób lenistwo pomaga uniknąć ograniczenia wartości? Nie byłem w stanie tego zrozumieć.
Tom Ellis
3
@PaulBone O czym ty mówisz? Lenistwo ma wiele wspólnego ze strukturami kontrolnymi. Jeśli zdefiniujesz swoją własną strukturę kontrolną w ścisłym języku, będzie to albo musiało użyć kilku lambd lub podobnych, albo będzie do niczego. Ponieważ ifFunc(True, x, y)ma zamiar ocenić oba, xa yzamiast tylko x.
średnik
28

Istnieje różnica między normalną oceną kolejności a leniwą oceną (jak w Haskell).

square x = x * x

Obliczanie następującego wyrażenia ...

square (square (square 2))

... z gorliwą oceną:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... z normalną oceną zamówienia:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... z leniwą oceną:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

Dzieje się tak, ponieważ leniwa ocena patrzy na drzewo składni i wykonuje przekształcenia drzewa ...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

... podczas gdy normalna ocena zamówienia dotyczy tylko rozszerzeń tekstowych.

Dlatego my, używając leniwej oceny, stajemy się potężniejsi (ocena kończy się częściej niż inne strategie), podczas gdy wydajność jest równoważna gorliwej ocenie (przynajmniej w notacji O).

Thomas Danecker
źródło
25

Leniwa ocena związana z procesorem w taki sam sposób, jak czyszczenie pamięci związane z pamięcią RAM. GC pozwala ci udawać, że masz nieograniczoną ilość pamięci, a tym samym żądać tyle obiektów w pamięci, ile potrzebujesz. Środowisko wykonawcze automatycznie odzyskuje nieużywalne obiekty. LE pozwala udawać, że masz nieograniczone zasoby obliczeniowe - możesz wykonać tyle obliczeń, ile potrzebujesz. Środowisko wykonawcze po prostu nie wykona niepotrzebnych (dla danego przypadku) obliczeń.

Jaka jest praktyczna zaleta tych „udających” modeli? Uwalnia programistę (w pewnym stopniu) od zarządzania zasobami i usuwa część standardowego kodu ze źródeł. Ale ważniejsze jest to, że możesz efektywnie ponownie wykorzystać swoje rozwiązanie w szerszym zestawie kontekstów.

Wyobraź sobie, że masz listę liczb S i liczbę N. Musisz znaleźć najbliższą liczbę N liczbę M z listy S.Możesz mieć dwa konteksty: pojedynczy N i pewną listę L z Ns (ei dla każdego N w L szukasz najbliższego M w S). Jeśli używasz leniwego oceniania, możesz posortować S i zastosować wyszukiwanie binarne, aby znaleźć najbliższe M do N.Dla dobrego leniwego sortowania będzie wymagało O (rozmiar (S)) kroków dla pojedynczego N i O (ln (rozmiar (S)) * (size (S) + size (L))) kroki dla równo rozłożonego L. Jeśli nie masz leniwej oceny, aby osiągnąć optymalną wydajność, musisz zaimplementować algorytm dla każdego kontekstu.

Alexey
źródło
Analogia do GC trochę mi pomogła, ale czy możesz podać przykład „usuwa jakiś standardowy kod”?
Abdul
1
@Abdul, przykład znany każdemu użytkownikowi ORM: leniwe ładowanie skojarzeń. Ładuje asocjację z DB „w samą porę” i jednocześnie zwalnia programistę z potrzeby wyraźnego określenia, kiedy ma go załadować i jak go buforować (to jest schemat standardowy, mam na myśli). Oto kolejny przykład: projectlombok.org/features/GetterLazy.html .
Alexey
25

Jeśli wierzyć Simonowi Peytonowi Jonesowi, leniwa ocena nie jest ważna per se, ale tylko jako „fryzura”, która zmusiła projektantów do zachowania czystości języka. Uważam, że sympatyzuję z tym punktem widzenia.

Richard Bird, John Hughes i w mniejszym stopniu Ralf Hinze potrafią robić niesamowite rzeczy z leniwą oceną. Czytanie ich prac pomoże ci to docenić. Dobry punkt wyjścia to wspaniały solver Sudoku autorstwa Birda i artykuł Hughesa pt. Why Functional Programming Matters .

Norman Ramsey
źródło
To nie tylko zmusiło ich do zachowania czystości języka, ale także pozwoliło im na to, gdy (przed wprowadzeniem IOmonady) podpis mainbyłby String -> Stringi można by już pisać poprawnie interaktywne programy.
leftaround około
@leftaroundabout: Co powstrzymuje ścisły język przed wymuszeniem wszystkich efektów w IOmonadzie?
Tom Ellis
13

Rozważ program „kółko i krzyżyk”. Ma cztery funkcje:

  • Funkcja generująca ruch, która pobiera bieżącą planszę i generuje listę nowych plansz, z których każda ma jeden ruch.
  • Następnie istnieje funkcja „move tree”, która stosuje funkcję generowania ruchu do wyprowadzenia wszystkich możliwych pozycji na planszy, które mogą wynikać z tego.
  • Istnieje funkcja minimax, która przechadza się po drzewie (lub prawdopodobnie tylko po jego części), aby znaleźć najlepszy następny ruch.
  • Istnieje funkcja oceny planszy, która określa, czy któryś z graczy wygrał.

Tworzy to przyjemny i wyraźny rozdział obaw. W szczególności funkcja generowania ruchu i funkcje oceny planszy są jedynymi, które muszą zrozumieć zasady gry: drzewo ruchu i funkcje minimax są w pełni wielokrotnego użytku.

Teraz spróbujmy wprowadzić szachy zamiast gry w kółko i krzyżyk. W „chętnym” (tj. Konwencjonalnym) języku to nie zadziała, ponieważ drzewo przenoszenia nie zmieści się w pamięci. Więc teraz funkcje oceny planszy i generowania ruchów muszą być połączone z drzewem ruchu i logiką minimaksów, ponieważ logika minimaksu musi być używana do decydowania, które ruchy wygenerować. Nasza ładna, czysta struktura modułowa znika.

Jednak w leniwym języku elementy drzewa ruchu są generowane tylko w odpowiedzi na żądania funkcji minimax: całe drzewo ruchu nie musi być generowane, zanim zwolnimy minimaks na górnym elemencie. Tak więc nasza czysta struktura modułowa nadal działa w prawdziwej grze.

Paul Johnson
źródło
1
[W języku „chętnym” (tj. Konwencjonalnym) to nie zadziała, ponieważ drzewo ruchu nie zmieści się w pamięci] - w przypadku Kółko i krzyżyk na pewno tak. Do zapisania są maksymalnie 3 ** 9 = 19683 pozycje. Jeśli zapiszemy każdy z nich w ekstrawaganckich 50 bajtach, to prawie jeden megabajt. To nic ...
Jonas Kölker
6
Tak, o to mi chodzi. Chętne języki mogą mieć czystą strukturę dla trywialnych gier, ale muszą iść na kompromis z tą strukturą dla czegokolwiek rzeczywistego. Leniwe języki nie mają tego problemu.
Paul Johnson
3
Jednak szczerze mówiąc, leniwa ocena może prowadzić do problemów z pamięcią. Często zdarza się, że ludzie pytają, dlaczego haskell wysadza swoją pamięć na coś, co w gorliwej ocenie miałoby zużycie pamięci na poziomie O (1)
RHSeeger
@PaulJohnson Jeśli oceniasz wszystkie pozycje, nie ma znaczenia, czy oceniasz je chętnie, czy leniwie. Trzeba wykonać tę samą pracę. Jeśli zatrzymasz się w środku i ocenisz tylko połowę pozycji, to też nie ma znaczenia, bo w obu przypadkach połowa pracy musi być wykonana. Jedyna różnica między tymi dwoma ocenami polega na tym, że algorytm wygląda ładniej, jeśli jest napisany leniwie.
ceving
12

Oto jeszcze dwie kwestie, które, jak sądzę, nie zostały jeszcze poruszone w dyskusji.

  1. Lenistwo to mechanizm synchronizacji w środowisku współbieżnym. Jest to lekki i łatwy sposób na utworzenie odniesienia do niektórych obliczeń i udostępnienie ich wyników w wielu wątkach. Jeśli wiele wątków spróbuje uzyskać dostęp do nieocenionej wartości, tylko jeden z nich wykona ją, a pozostałe odpowiednio zablokują, otrzymując wartość, gdy stanie się dostępna.

  2. Lenistwo ma fundamentalne znaczenie dla amortyzacji struktur danych w czystym otoczeniu. Zostało to szczegółowo opisane przez Okasaki w książce Purely Functional Data Structures , ale podstawową ideą jest to, że leniwa ocena jest kontrolowaną formą mutacji, która ma kluczowe znaczenie dla umożliwienia nam wydajnej implementacji pewnych typów struktur danych. Chociaż często mówimy o lenistwie, który zmusza nas do noszenia czystej koszuli do włosów, ma to miejsce również w drugą stronę: są to para synergicznych cech językowych.

Edward Z. Yang
źródło
10

Po włączeniu komputera, a system Windows powstrzymuje się od otwierania każdego katalogu na dysku twardym w Eksploratorze Windows i powstrzymuje się od uruchamiania każdego programu zainstalowanego na komputerze, dopóki nie wskażesz, że potrzebny jest określony katalog lub określony program, że jest „leniwą” oceną.

Ocena „leniwa” polega na wykonywaniu operacji wtedy, gdy są potrzebne. Jest to przydatne, gdy jest to funkcja języka programowania lub biblioteki, ponieważ generalnie trudniej jest samodzielnie zaimplementować leniwą ocenę niż po prostu wstępnie obliczyć wszystko z góry.

yfeldblum
źródło
1
Niektórzy ludzie mogą powiedzieć, że to naprawdę „leniwa egzekucja”. Różnica jest naprawdę nieistotna, z wyjątkiem dość czystych języków, takich jak Haskell; Różnica polega jednak na tym, że nie chodzi tylko o opóźnienie obliczeń, ale także związane z nimi skutki uboczne (takie jak otwieranie i odczytywanie plików).
Owen
8

Rozważ to:

if (conditionOne && conditionTwo) {
  doSomething();
}

Metoda doSomething () zostanie wykonana tylko wtedy, gdy warunek conditionOne jest prawdziwy, a conditionTwo jest prawdziwy. W przypadku, gdy warunek conditionOne jest fałszywy, dlaczego trzeba obliczyć wynik warunku dwa? Ocena stanu Dwa będzie w tym przypadku stratą czasu, zwłaszcza jeśli stan jest wynikiem jakiejś metody.

To jeden z przykładów leniwego zainteresowania oceną ...

Romain Linsolas
źródło
Myślałem, że to zwarcie, a nie leniwa ocena.
Thomas Owens
2
Jest to leniwa ocena, ponieważ conditionTwo jest obliczane tylko wtedy, gdy jest naprawdę potrzebne (tj. Jeśli warunek conditionOne jest prawdziwy).
Romain Linsolas
7
Przypuszczam, że zwarcie jest zdegenerowanym przypadkiem leniwej oceny, ale zdecydowanie nie jest to powszechny sposób myślenia o tym.
rmeador
19
Zwarcie jest w rzeczywistości szczególnym przypadkiem leniwej oceny. Leniwa ocena obejmuje oczywiście znacznie więcej niż tylko zwarcie. Albo, co poza leniwą oceną ma zwarcie?
yfeldblum
2
@Juliet: Masz silną definicję „lenistwa”. Twój przykład funkcji pobierającej dwa parametry to nie to samo, co instrukcja zwarcia if. Zwarcie w instrukcji if pozwala uniknąć niepotrzebnych obliczeń. Myślę, że lepszym porównaniem do twojego przykładu byłby operator Visual Basic „andalso”, który wymusza ocenę obu warunków
8
  1. Może zwiększyć wydajność. To wygląda na oczywiste, ale tak naprawdę nie jest najważniejsze. (Zwróć też uwagę, że lenistwo również może zabić wydajność - fakt ten nie jest od razu oczywisty. Jednak przechowując wiele tymczasowych wyników zamiast ich natychmiastowego obliczania, możesz zużyć ogromną ilość pamięci RAM.)

  2. Pozwala zdefiniować konstrukcje sterowania przepływem w normalnym kodzie na poziomie użytkownika, a nie na stałe zakodowane w języku. (Np. Java ma forpętle; Haskell ma forfunkcję. Java obsługuje wyjątki; Haskell ma różne typy monad wyjątków. C # ma goto; Haskell ma monadę kontynuacji ...)

  3. Pozwala oddzielić algorytm generowania danych od algorytmu decydującego o ilości danych do wygenerowania. Możesz napisać jedną funkcję, która generuje teoretycznie nieskończoną listę wyników, i inną funkcję, która przetwarza tyle z tej listy, ile uzna za konieczne. Mówiąc dokładniej, możesz mieć pięć funkcji generatora i pięć funkcji konsumenckich, a także wydajnie tworzyć dowolne kombinacje - zamiast ręcznego kodowania funkcji 5 x 5 = 25, które łączą obie akcje jednocześnie. (!) Wszyscy wiemy, że rozłączanie jest dobrą rzeczą.

  4. W mniejszym lub większym stopniu zmusza cię to do zaprojektowania czysto funkcjonalnego języka. Zawsze kuszące jest pójście na skróty, ale w leniwym języku najmniejsza nieczystość sprawia, że ​​twój kod jest szalenie nieprzewidywalny, co zdecydowanie zapobiega chodzeniu na skróty.

MathematicalOrchid
źródło
6

Ogromną zaletą lenistwa jest możliwość pisania niezmiennych struktur danych z rozsądnymi amortyzowanymi granicami. Prostym przykładem jest niezmienny stos (przy użyciu F #):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

Kod jest rozsądny, ale dołączenie dwóch stosów xiy zajmuje O (długość x) czasu w najlepszym, najgorszym i średnim przypadku. Dołączanie dwóch stosów jest operacją monolityczną, dotyka wszystkich węzłów na stosie x.

Możemy ponownie zapisać strukturę danych jako leniwy stos:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazydziała poprzez zawieszenie oceny kodu w jego konstruktorze. Po ocenie przy użyciu .Force()wartość zwracana jest buforowana i ponownie używana przy każdym kolejnym .Force().

W wersji leniwej dołączenia są operacją O (1): zwraca 1 węzeł i zawiesza faktyczną przebudowę listy. Kiedy zdobędziesz nagłówek tej listy, oceni zawartość węzła, zmuszając go do zwrócenia głowy i utworzy jedno zawieszenie z pozostałymi elementami, więc zabranie nagłówka listy jest operacją O (1).

Tak więc nasza leniwa lista jest w ciągłym stanie przebudowy, nie ponosisz kosztów odbudowy tej listy, dopóki nie przejdziesz przez wszystkie jej elementy. Korzystając z lenistwa, lista ta obsługuje O (1) rozpatrywanie i dołączanie. Co ciekawe, ponieważ nie oceniamy węzłów, dopóki nie uzyskamy do nich dostępu, jest całkowicie możliwe utworzenie listy z potencjalnie nieskończonymi elementami.

Powyższa struktura danych nie wymaga ponownego obliczania węzłów przy każdym przejściu, więc różnią się one wyraźnie od zwykłych IEnumerables w .NET.

Julia
źródło
5

Ten fragment kodu pokazuje różnicę między leniwą i nie leniwą oceną. Oczywiście ta funkcja Fibonacciego mogłaby sama zostać zoptymalizowana i używać leniwej oceny zamiast rekurencji, ale to zepsułoby przykład.

Załóżmy, że MOŻEMY użyć pierwszych 20 liczb do czegoś, bez leniwej oceny wszystkie 20 liczb muszą zostać wygenerowane z góry, ale przy leniwej ocenie zostaną wygenerowane tylko w razie potrzeby. W związku z tym zapłacisz tylko cenę kalkulacyjną w razie potrzeby.

Przykładowe dane wyjściowe

Nie leniwe pokolenie: 0,023373
Leniwe pokolenie: 0,000009
Nie leniwy wynik: 0,000921
Leniwy wynik: 0,024205
import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)
Vinko Vrsalovic
źródło
5

Leniwa ocena jest najbardziej przydatna w przypadku struktur danych. Możesz zdefiniować tablicę lub wektor indukcyjnie określając tylko niektóre punkty w strukturze i wyrażając wszystkie inne w kategoriach całej tablicy. Umożliwia to bardzo zwięzłe generowanie struktur danych z wysoką wydajnością w czasie wykonywania.

Aby zobaczyć to w akcji, możesz rzucić okiem na moją bibliotekę sieci neuronowych zwaną instynktem . W dużym stopniu wykorzystuje leniwą ocenę dla elegancji i wysokiej wydajności. Na przykład całkowicie pozbywam się tradycyjnie imperatywnego obliczania aktywacji. Proste, leniwe wyrażenie robi wszystko za mnie.

Jest to używane na przykład w funkcji aktywacji, a także w algorytmie uczenia się wstecznej propagacji (mogę zamieścić tylko dwa linki, więc musisz sam sprawdzić learnPatfunkcję w AI.Instinct.Train.Deltamodule). Tradycyjnie oba wymagają znacznie bardziej skomplikowanych algorytmów iteracyjnych.

ertes
źródło
4

Inni ludzie już podali wszystkie ważne powody, ale myślę, że przydatnym ćwiczeniem pomagającym zrozumieć, dlaczego lenistwo jest takie ważne, jest próba napisania funkcji stałopozycyjnej w ścisłym języku.

W Haskell funkcja stałego punktu jest bardzo łatwa:

fix f = f (fix f)

to rozszerza się do

f (f (f ....

ale ponieważ Haskell jest leniwy, ten nieskończony łańcuch obliczeniowy nie stanowi problemu; ocena odbywa się „od zewnątrz do wewnątrz” i wszystko działa wspaniale:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

Co ważne, nie jest ważne, żeby fixbyć leniwym, ale żeby fbyć leniwym. Kiedy już dostałeś rygor f, możesz albo podnieść ręce w powietrze i poddać się, albo eta rozszerzyć i zaśmiecać rzeczy. (To jest bardzo podobne do tego, co mówił Noah o tym, że biblioteka jest surowa / leniwa, a nie język).

Teraz wyobraź sobie, że piszesz tę samą funkcję w ścisłej Scali:

def fix[A](f: A => A): A = f(fix(f))

val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

Oczywiście dostajesz przepełnienie stosu. Jeśli chcesz, aby to działało, musisz użyć fargumentu call-by-need:

def fix[A](f: (=>A) => A): A = f(fix(f))

def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)

val fact = fix(fact1)
piekarnik
źródło
3

Nie wiem, jak obecnie myślisz o rzeczach, ale uważam, że warto myśleć o leniwej ocenie jako o problemie z biblioteką, a nie o funkcji języka.

Chodzi mi o to, że w językach ścisłych mogę wdrożyć leniwą ocenę, budując kilka struktur danych, aw językach leniwych (przynajmniej Haskell) mogę prosić o ścisłość, kiedy tego chcę. Dlatego wybór języka tak naprawdę nie powoduje, że programy są leniwe lub nie, ale po prostu wpływa na to, który program otrzymujesz domyślnie.

Kiedy pomyślisz o tym w ten sposób, pomyśl o wszystkich miejscach, w których piszesz strukturę danych, której możesz później użyć do generowania danych (bez wcześniejszego patrzenia na to), a zobaczysz wiele zastosowań dla leniwych ocena.

Noah Lavine
źródło
1
Wdrażanie leniwej oceny w językach ścisłych jest często Turing Tarpit.
itsbruce
2

Najbardziej użytecznym wykorzystaniem leniwej oceny, którego użyłem, była funkcja, która wywoływała szereg podfunkcji w określonej kolejności. Jeśli którakolwiek z tych podfunkcji zawiodła (zwróciła wartość false), funkcja wywołująca musiała natychmiast powrócić. Mogłem więc zrobić to w ten sposób:

bool Function(void) {
  if (!SubFunction1())
    return false;
  if (!SubFunction2())
    return false;
  if (!SubFunction3())
    return false;

(etc)

  return true;
}

lub bardziej eleganckie rozwiązanie:

bool Function(void) {
  if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
    return false;
  return true;
}

Gdy zaczniesz go używać, zobaczysz możliwości korzystania z niego coraz częściej.

Marc Bernier
źródło
2

Bez leniwej oceny nie będziesz mógł napisać czegoś takiego:

  if( obj != null  &&  obj.Value == correctValue )
  {
    // do smth
  }
skórki
źródło
Cóż, imo, to zły pomysł. Chociaż ten kod może być poprawny (w zależności od tego, co próbujesz osiągnąć), jest trudny do odczytania, co zawsze jest złe.
Brann
12
Nie sądzę. Jest to standardowa konstrukcja w C i jej krewnych.
Paul Johnson
To jest przykład oceny zwarcia, a nie leniwej oceny. A może to faktycznie to samo?
RufusVS
2

Między innymi leniwe języki pozwalają na wielowymiarowe nieskończone struktury danych.

Podczas gdy schemat, python itp. Pozwalają na jednowymiarowe nieskończone struktury danych ze strumieniami, możesz przechodzić tylko wzdłuż jednego wymiaru.

Lenistwo jest przydatne w przypadku tego samego problemu z prążkami, ale warto zwrócić uwagę na połączenie z programami, o którym mowa w tym linku.

shapr
źródło
2

Leniwa ocena to słabe rozumowanie równań człowieka (w idealnej sytuacji można by oczekiwać, że będzie to wyprowadzanie właściwości kodu z właściwości typów i operacji).

Przykład gdzie działa całkiem dobrze: sum . take 10 $ [1..10000000000]. Które nie przeszkadza nam zredukowanie do sumy 10 liczb zamiast tylko jednego bezpośredniego i prostego obliczenia numerycznego. Oczywiście bez leniwej oceny stworzyłoby to gigantyczną listę w pamięci tylko po to, by użyć jej pierwszych 10 elementów. Z pewnością byłoby to bardzo powolne i mogłoby spowodować błąd braku pamięci.

Przykład gdzie to nie jest tak wielka, jak chcielibyśmy: sum . take 1000000 . drop 500 $ cycle [1..20]. Który faktycznie sumuje 1 000 000 liczb, nawet jeśli w pętli zamiast na liście; mimo to należy go zredukować do jednego bezpośredniego obliczenia numerycznego, z kilkoma warunkami i kilkoma formułami. Co byłoby o wiele lepsze niż zsumowanie 1 000 000 liczb. Nawet jeśli w pętli, a nie na liście (tj. Po optymalizacji wylesiania).


Inną rzeczą jest to, że umożliwia kodowanie w stylu modulo cons z rekurencją ogona i po prostu działa .

por. powiązana odpowiedź .

Will Ness
źródło
1

Jeśli przez „leniwe ocenianie” masz na myśli jak w kombinowanych wartościach logicznych, jak w

   if (ConditionA && ConditionB) ... 

wtedy odpowiedź brzmi po prostu, że im mniej cykli procesora zużywa program, tym szybciej będzie działał ... i jeśli fragment instrukcji przetwarzania nie będzie miał wpływu na wynik programu, to jest niepotrzebny (a zatem marnotrawstwo czasu) i tak je wykonać ...

jeśli tak, masz na myśli to, co nazywam „leniwymi inicjatorami”, na przykład:

class Employee
{
    private int supervisorId;
    private Employee supervisor;

    public Employee(int employeeId)
    {
        // code to call database and fetch employee record, and 
        //  populate all private data fields, EXCEPT supervisor
    }
    public Employee Supervisor
    { 
       get 
          { 
              return supervisor?? (supervisor = new Employee(supervisorId)); 
          } 
    }
}

Cóż, ta technika pozwala kodowi klienta wykorzystującemu klasę uniknąć konieczności wywoływania bazy danych dla rekordu danych przełożonego, z wyjątkiem sytuacji, gdy klient korzystający z obiektu Pracownik wymaga dostępu do danych przełożonego ... to przyspiesza proces tworzenia instancji Pracownika, a jednak, gdy będziesz potrzebować inspektora, pierwsze wywołanie właściwości Supervisora ​​wyzwoli wywołanie bazy danych, a dane zostaną pobrane i dostępne ...

Charles Bretana
źródło
0

Wyciąg z funkcji wyższego rzędu

Znajdźmy największą liczbę poniżej 100 000, która jest podzielna przez 3829. Aby to zrobić, przefiltrujemy po prostu zbiór możliwości, w których wiemy, że leży rozwiązanie.

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0 

Najpierw tworzymy listę wszystkich liczb poniżej 100 000, malejąco. Następnie filtrujemy go według naszego predykatu, a ponieważ liczby są sortowane malejąco, największa liczba spełniająca nasze predykaty jest pierwszym elementem przefiltrowanej listy. Nie musieliśmy nawet używać skończonej listy w naszym zestawie początkowym. To znowu lenistwo w akcji. Ponieważ w końcu używamy tylko początku przefiltrowanej listy, nie ma znaczenia, czy lista filtrowana jest skończona czy nieskończona. Ocena kończy się po znalezieniu pierwszego odpowiedniego rozwiązania.

onmyway133
źródło