W dniu niedziela, 7 stycznia 2018 22:30:41 UTC+1 użytkownik Maciej Sobczak napisał:
> > Co do istoty, iteracja nie jest bardziej wydajna, niż rekurencja,
> > bo iteracja jest tylko specjalizacją rekurencji.
>
> Ale ja do ich uruchomienia używam nie "istoty", tylko procesora. A tam iteracja
działa szybciej.

Mylisz się.
Pewne strategie implementacji rekurencji działają wolniej
(i zużywają więcej zasobów) od typowych strategii implementacji
iteracji, i tyle.
Istnieją strategie, pozwalające implementować rekurencję
ogonową (czyli taką, która realizuje iterację) bez narzutu.

> > Dobrze jest to wyjasnione w "Strukturze i Interpretacji Programów
> > Komputerowych",
>
> A jeszcze lepiej w dokumentacji procesora.

W dokumentacji procesora nie używa się takich pojęć, jak
"proces obliczeniowy".

> > Rekurencja natomiast zarówno może więcej (jest mniej wyspecjalizowana),
> > jak również jest prostsza (w sensie złożoności) od iteracji.
>
> Tego nie pokazałeś.

Nie pokazałem, ale mógłbym łatwo pokazać, definiując funkcję, której
Ty użyłeś, za pomocą rekurencji.

> Moja iteracyjna definicja przodka była prostsza od Twojej rekurencyjnej.

W jaki sposób chciałbyś uzasadnić, że była prostsza?

> Moja iteracyjna metoda wyboru elementów z listy też była prostsza.

W jaki sposób chciałbyś uzasadnić, że była prostsza?

> > W przypadku podanego przez Ciebie przykładu, zrozumienie zapisu x[[1 ;; ;; 2]]
> > wymaga odwołania do dokumentacji
>
> Tak.
>
> > W rozwiązaniu Kaya jedyna przypadkowa złożoność
> > jest w nazwach. Ale w tej kwestii z pomocą przychodzi nam dorobek
> > Burstalla,
>
> I teraz zrozumienie Twojego przykładu wymaga odwołania się do dorobku Burstalla.

Nie wymaga.

> Nie przekonałeś mnie, że jest to prostsze. A mój zapis dalej jest krótszy. Co
więcej, jeśli będę chciał mieć nie co drugi element, tylko co dziesiąty, to zmienię 2
na 10 i działa: x[[1;; ;;10]]. Złożoność tego zapisu się nie zmieniła. Co musisz
zmienić w swoim przykładzie, żeby wybrać z listy co dziesiąty element?

Pewnie musiałbym zmienić więcej. Co nie oznacza, że Twoje rozwiązanie
jest prostsze, tylko to, że Twoje rozwiązanie można łatwiej dostosować
do pewnej klasy zmian wymagań (z czym się zasadniczo zgadzam)

do góry

> Mylisz się.
> Pewne strategie implementacji rekurencji działają wolniej
> (i zużywają więcej zasobów) od typowych strategii implementacji
> iteracji, i tyle.
> Istnieją strategie, pozwalające implementować rekurencję
> ogonową (czyli taką, która realizuje iterację) bez narzutu.

Tak, jak kompilator zamieni rekurencję na iterację, to działa tak szybko, jak
iteracja. Nie jest jednak prawdą, że bez narzutu, bo tym narzutem może być też
większy koszt kompilacji i optymalizacji kodu. Bo co przepłacać?
Natomiast iteracja zawsze działa tak szybko, jak iteracja. I zawsze jest tak tania,
jak iteracja.

> > Moja iteracyjna definicja przodka była prostsza od Twojej rekurencyjnej.
>
> W jaki sposób chciałbyś uzasadnić, że była prostsza?

Już pisałem: mniej liter, krótsza gramatycznie, nie odwołuje się do definiowanego
pojęcia.

> > Moja iteracyjna metoda wyboru elementów z listy też była prostsza.
>
> W jaki sposób chciałbyś uzasadnić, że była prostsza?

Ma mniej liter? Mniej razy się pomylę? Mniej bugów będę tam poprawiał?

> > Co musisz zmienić w swoim przykładzie, żeby wybrać z listy co dziesiąty element?
>
> Pewnie musiałbym zmienić więcej.

To zmień i pokaż. Bo szczerze mówiąc nie za bardzo mi się chce szarpać w
nieskończoność o filozofię natury, istoty, prostoty, czy czego tam.
Na razie niczego użytecznego w tej dyskusji nie ustaliliśmy.

> Co nie oznacza, że Twoje rozwiązanie
> jest prostsze, tylko to, że Twoje rozwiązanie można łatwiej dostosować
> do pewnej klasy zmian wymagań (z czym się zasadniczo zgadzam)

To też jest użyteczna miara prostoty. Jeśli coś można łatwiej do czegoś dostosować,
to chyba dobrze, co? Po co przepłacać?

Jeszcze raz, co dziesiąty z szeregu wystąp: x[[1;; ;;10]].

Pokaż wersję rekurencyjną i uzasadnij, że zawsze będzie to rekurencja ogonowa, bo
przecież nie chcemy, żeby tak prosta rzecz działała wolniej, niż potrzeba.

--
Maciej Sobczak * http://www.inspirel.com

do góry

W dniu poniedziałek, 8 stycznia 2018 14:21:00 UTC+1 użytkownik Maciej Sobczak
napisał:
> > Mylisz się.
> > Pewne strategie implementacji rekurencji działają wolniej
> > (i zużywają więcej zasobów) od typowych strategii implementacji
> > iteracji, i tyle.
> > Istnieją strategie, pozwalające implementować rekurencję
> > ogonową (czyli taką, która realizuje iterację) bez narzutu.
>
> Tak, jak kompilator zamieni rekurencję na iterację, to działa tak szybko, jak
iteracja. Nie jest jednak prawdą, że bez narzutu, bo tym narzutem może być też
większy koszt kompilacji i optymalizacji kodu. Bo co przepłacać?

Jest dokładnie odwrotnie.
Jeżeli przyjmiesz strategię kompilacji polegającą na tym,
że adres powrotu przekazujesz przez rejestr, a nie przez stos
(i to kompilowana funkcja ma wiedzieć, czy wartość rejestru
ma być odłożona na stosie), to nie dość, że masz mniej odwołań
do pamięci i koszt wywołania funkcji Ci maleje, to optymalizację
rekurencji ogonowej masz w zasadzie za darmo.
Mówienie w tym kontekście o "wyższym koszcie kompilacji i optymalizacji
kodu" jest pretensjonalne, zważywszy na to, jakich innych optymalizacji
dokonują współczesne kompilatory.

> Natomiast iteracja zawsze działa tak szybko, jak iteracja. I zawsze jest tak tania,
jak iteracja.

Nie ma czegoś takiego, jak "zawsze".
Jeżeli w Pythonie 2.0 iterujesz po range(n), to w skład kosztu
iteracji wchodzi zainicjalizowanie n komórek pamięci na wektor,
sama iteracja plus odśmiecenie tej pamięci.

> > > Moja iteracyjna definicja przodka była prostsza od Twojej rekurencyjnej.
> >
> > W jaki sposób chciałbyś uzasadnić, że była prostsza?
>
> Już pisałem: mniej liter, krótsza gramatycznie, nie odwołuje się do definiowanego
pojęcia.

Ale odwołuje się do frazy "i tak dalej", która - w przeciwieństwie
do rekurencji - nie jest zrozumiała sama przez się.

Tak samo jak x[[1 ;; ;; 10]] nie jest zrozumiałe samo przez się.

> > > Moja iteracyjna metoda wyboru elementów z listy też była prostsza.
> >
> > W jaki sposób chciałbyś uzasadnić, że była prostsza?
>
> Ma mniej liter? Mniej razy się pomylę? Mniej bugów będę tam poprawiał?

Jeżeli elementy są indeksowane od 0, to już się pomyliłeś i będziesz musiał
poprawić buga.

> > > Co musisz zmienić w swoim przykładzie, żeby wybrać z listy co dziesiąty
element?
> >
> > Pewnie musiałbym zmienić więcej.
>
> To zmień i pokaż. Bo szczerze mówiąc nie za bardzo mi się chce szarpać w
nieskończoność o filozofię natury, istoty, prostoty, czy czego tam.
> Na razie niczego użytecznego w tej dyskusji nie ustaliliśmy.

Jeżeli nie będziemy definiować używanych przez siebie pojęć, to
raczej niczego użytecznego nie ustalimy.
Jeżeli pod pojęciem prostoty będziemy rozumieć ilość znaków,
to nagle okaże się, że programy w APLu są najprostsze, albo
że Perl jest zasadniczo jakieś 30% prostszy od Pythona.

> > Co nie oznacza, że Twoje rozwiązanie
> > jest prostsze, tylko to, że Twoje rozwiązanie można łatwiej dostosować
> > do pewnej klasy zmian wymagań (z czym się zasadniczo zgadzam)
>
> To też jest użyteczna miara prostoty. Jeśli coś można łatwiej do czegoś dostosować,
to chyba dobrze, co? Po co przepłacać?

Nikt nie mówi, że to źle. Ale to, że coś łatwo do czegoś dostosować,
niekoniecznie jest miarą prostoty.

Na przykład łatwo dostosować telewizor do tego, żeby wyświetlił
jakiś obraz, niż namalować taki obraz na ścianie. A jednak ściana
jest czymś prostszym, niż telewizor.

> Jeszcze raz, co dziesiąty z szeregu wystąp: x[[1;; ;;10]].
>
> Pokaż wersję rekurencyjną i uzasadnij, że zawsze będzie to rekurencja ogonowa, bo
przecież nie chcemy, żeby tak prosta rzecz działała wolniej, niż potrzeba.

Ja widzę, że zupełnie nie rozumiesz, o co mi chodzi.
Jeżeli nie chcesz nawet spróbować zrozumieć, i będziesz się
w kółko upierał z jakąś niezdefiniowaną naturalnością i prostotą
rozumianą jako ilość znaków, to dalsza dyskusja raczej nie ma sensu.

do góry

> > Jeszcze raz, co dziesiąty z szeregu wystąp: x[[1;; ;;10]].
>
> Ja widzę, że zupełnie nie rozumiesz, o co mi chodzi.
> Jeżeli nie chcesz nawet spróbować zrozumieć, i będziesz się
> w kółko upierał z jakąś niezdefiniowaną naturalnością i prostotą
> rozumianą jako ilość znaków, to dalsza dyskusja raczej nie ma sensu.

Ale zapomniałeś pokazać swoją wersję, czy nie chciałeś jej pokazać?

Dla mnie pojęcie prostoty w programowaniu jest użyteczne tylko w takim kontekście, w
jakim pomaga mi podejmować decyzje projektowe i implementacyjne. Nie użyję rekurencji
do tego zadania, bo iteracja jest... prostsza. A fakt, że wolałeś napisać kolejny
nierozstrzygalny post na ileś zdań zamiast pokazać przykład kodu jest częścią miary
prostoty tych rozwiązań. Proste jest coś, co można prosto użyć.

x[[1;; ;;10]]

--
Maciej Sobczak * http://www.inspirel.com

do góry