Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:prolog:prolog_lab:listy1 [2014/03/17 15:14] msl Dodano listy różnicowe dla zainteresowanych |
pl:prolog:prolog_lab:listy1 [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 69: | Linia 69: | ||
| <code prolog> | <code prolog> | ||
| ?- porownaj([a,b,c,d]). | ?- porownaj([a,b,c,d]). | ||
| - | No | + | false |
| ?- porownaj([a,b,c,c]). | ?- porownaj([a,b,c,c]). | ||
| - | Yes | + | true |
| </code> | </code> | ||
| Linia 78: | Linia 78: | ||
| ?- zamien([a,b,c,d],X). | ?- zamien([a,b,c,d],X). | ||
| X=[a,b,d,c] | X=[a,b,d,c] | ||
| - | Yes | + | true |
| </code> | </code> | ||
| Linia 399: | Linia 399: | ||
| ===== Dla Zainteresowanych ===== | ===== Dla Zainteresowanych ===== | ||
| + | |||
| + | ==== Minecraft ==== | ||
| + | Zastanówmy się nad próbą implementacji prostej gry typu [[http://pl.wikipedia.org/wiki/Minecraft|Minecraft]]. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych [[http://pl.wikipedia.org/wiki/Woksel|wokselami]]. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program {{:pl:prolog:prolog_lab:cuboid.pl|}} (wymagane XPCE) i przeanalizować jego działanie. | ||
| + | |||
| + | <code prolog> | ||
| + | ?- cuboid(2,2,2). | ||
| + | </code> | ||
| + | |||
| + | Następnie proszę zapoznać się z kodem odpowiadającym za animację {{:pl:prolog:prolog_lab:animation.pl|}}: | ||
| + | |||
| + | <code prolog> | ||
| + | ?- sm. | ||
| + | </code> | ||
| + | |||
| + | Zadania: | ||
| + | - Przerobić predykat ''cuboid'' tak, żeby można było sprecyzować jego pozycję w przestrzeni | ||
| + | - Napisać predykat ''cuboids'', który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku | ||
| + | - Przy pomocy predykatu ''cuboids'' należy zamodelować [[http://i.ytimg.com/vi/u1bX8kEy0pg/maxresdefault.jpg?|złożony obiekt ze świata Minecraft]] | ||
| + | - Bazując na kodzie z ''animation.pl'' należy wprawić krowę w ruch sinusoidalny, imitujący [[https://www.youtube.com/watch?v=QH2-TGUlwu4|kota z filmu]] | ||
| + | - [Dla odważnych] dodać do animacji [[https://archive.org/details/nyannyannyan|dźwięk]] podobny do tego z [[https://www.youtube.com/watch?v=QH2-TGUlwu4|filmu]] | ||
| + | |||
| + | Pytania: | ||
| + | - Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się [[http://et1337.com/2015/02/18/the-poor-mans-voxel-engine/#|link]] | ||
| + | - Czy możliwe jest zrobienie w podobny sposób imitacji poniższego [[http://goo.gl/YroZm|filmu]]? | ||
| + | |||
| ==== Efektywność odwracania list ==== | ==== Efektywność odwracania list ==== | ||
| Linia 424: | Linia 449: | ||
| Dużą bolączką operacji na listach w Prologu (jak też w innych językach programowania, które wymuszają przechodzenie po elementach listy od lewej do prawej, np. Haskell) jest nieefektywność operacji działających na końcu listy. Sztandarowym przykładem takiej operacji jest łączenie dwóch list, vel. predykat sklej/3 implementowany na tych laboratoriach — rezolucja musi w nim przejść kolejno po wszystkich elementach pierwszej listy; złożoność czasowa jest zatem liniowa i przy częstym sklejaniu list znacząco spowalnia działanie programu. | Dużą bolączką operacji na listach w Prologu (jak też w innych językach programowania, które wymuszają przechodzenie po elementach listy od lewej do prawej, np. Haskell) jest nieefektywność operacji działających na końcu listy. Sztandarowym przykładem takiej operacji jest łączenie dwóch list, vel. predykat sklej/3 implementowany na tych laboratoriach — rezolucja musi w nim przejść kolejno po wszystkich elementach pierwszej listy; złożoność czasowa jest zatem liniowa i przy częstym sklejaniu list znacząco spowalnia działanie programu. | ||
| - | Standardowym rozwiązaniem problemu są listy różnicowe (ang. //difference lists//), które reprezentują jedną listę jako **różnicę między dwiema listami**, np. lista <code prolog>[a,b,c].</code> może być reprezentowana równoważnie przez wszystkie poniższe pary list: | + | Standardowym rozwiązaniem problemu są listy różnicowe (ang. //difference lists//), które reprezentują jedną listę jako **różnicę między dwiema listami**. Różnicę rozumiemy jako odjęcie elementów z drugiej listy od końca pierwszej listy, np. lista <code prolog>[a,b,c].</code> może być reprezentowana równoważnie przez wszystkie poniższe pary list: |
| <code prolog> | <code prolog> | ||
| [a,b,c,d,e],[d,e]. | [a,b,c,d,e],[d,e]. | ||
| Linia 433: | Linia 458: | ||
| [a,b,c|End],End. | [a,b,c|End],End. | ||
| </code> | </code> | ||
| - | Szczególnie interesująca jest ostatnia linijka ze względu na swoją ogólność. Kążdą listę ''[L]'' można przedstawić jako parę ''[L|End]'',''End''. Kiedy ''End'' jest zmienną bez przypisanej wartości, listę o takiej postaci nazywam otwartą (ang. //open list//). Z proceduralnego punktu widzenia zmienna ''End'' jest "wskaźnikiem" na koniec listy ''L''; unifikując z ''End'' inną listę, wstawiamy jej elementy na koniec listy ''L''. Poniżej przedstawiony jest predykat ''sklej_roznicowo/3'', który wykonuje tę operację (uwaga: operator '-' służy tutaj jedynie grupowaniu argumentów; parę ''[L|End]'', ''End'' zapiszemy jako ''[L|End] - End.'') | + | Szczególnie interesująca jest ostatnia linijka ze względu na swoją ogólność. Każdą listę ''[L]'' można przedstawić jako parę ''[L|End]'',''End''. Kiedy ''End'' jest zmienną bez przypisanej wartości, listę o takiej postaci nazywamy otwartą (ang. //open list//). Z proceduralnego punktu widzenia zmienna ''End'' jest "wskaźnikiem" na koniec listy ''L''; unifikując z ''End'' inną listę, wstawiamy jej elementy na koniec listy ''L''. Poniżej przedstawiony jest predykat ''sklej_roznicowo/3'', który wykonuje tę operację (uwaga: operator '''-''' służy tutaj jedynie grupowaniu argumentów; parę ''[L|End]'', ''End'' zapiszemy jako ''[L|End] - End''). |
| <code prolog> | <code prolog> | ||
| - | sklej_roznicowo(L - End, L2, L) :- | + | sklej_roznicowo(L - End, End, L). |
| - | End = L2. | + | |
| </code> | </code> | ||
| Poniżej przykład wywołania predykatu: | Poniżej przykład wywołania predykatu: | ||
| <code prolog> | <code prolog> | ||
| - | ?:- sklej_roznicowo([a,b,c|End]-End, [d,e,f|End2]-End2, Wynik). | + | ?:- sklej_roznicowo([a,b,c|End]-End,[d,e,f],Wynik). |
| - | End = [d, e, f|End2], | + | End = [d, e, f], |
| - | Wynik = [a, b, c, d, e, f|End2]-End2. | + | Wynik = [a, b, c, d, e, f]. |
| </code> | </code> | ||
| - | Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowa; ''sklej roznicowe'' wykonuje zawsze jedynie jedną unifikację, ma więc stałą złożoność obliczeniową. | + | Predykat ten różni się od tego implementowanego na zajęciach pod względem złożoności obliczeniowej; ''sklej_roznicowo'' nigdy nie wchodzi w rekurencję, wykonuje jedynie jedną unifikację, ma więc stałą złożoność obliczeniową. |
| Idąc dalej, jeżeli ustalimy, że argumentami ''sklej_roznicowo'' mogą być jedynie listy różnicowe w postaci par ''L - End'', możemy go przepisać do poniższej, interesującej postaci: | Idąc dalej, jeżeli ustalimy, że argumentami ''sklej_roznicowo'' mogą być jedynie listy różnicowe w postaci par ''L - End'', możemy go przepisać do poniższej, interesującej postaci: | ||
| Linia 460: | Linia 485: | ||
| Podczas wywołania Prolog unifikuje koniec pierwszej listy z drugą listą, zapamiętując przy tym koniec drugiej listy --- dzięki temu lista wynikowa ''Wynik'' w parze z ''End2'' stanowi kolejną listę różnicową, do której łatwo dołożyć kolejne elementy. | Podczas wywołania Prolog unifikuje koniec pierwszej listy z drugą listą, zapamiętując przy tym koniec drugiej listy --- dzięki temu lista wynikowa ''Wynik'' w parze z ''End2'' stanowi kolejną listę różnicową, do której łatwo dołożyć kolejne elementy. | ||
| - | Do poczytania: | + | == Do przećwiczenia: == |
| + | |||
| + | * przetestować predykat ''sklej_roznicowo/3''; | ||
| + | * spróbować zastąpić predykat ''sklej/3'' predykatem ''sklej_roznicowo/3'' w predykatach zaimplementowanych na zajęciach; | ||
| + | * zastanowić się, jakie przewagi ma ''sklej/3'' nad ''sklej_roznicowo/3''; | ||
| + | * przepisać wybrany predykat z zajęć (poza ''sklej/3'') na wersję korzystającą z list różnicowych. | ||
| + | |||
| + | == Do poczytania: == | ||
| + | |||
| + | * [[http://en.wikipedia.org/wiki/Difference_list|Lista różnicowa na en.wikipeda]]; | ||
| + | * [[http://en.wikibooks.org/wiki/Prolog/Difference_Lists|Lista różnicowa w Prologu na en.wikibooks]]; | ||
| + | * [[http://stackoverflow.com/a/20441480|Pytanie o listy różnicowe na Stackoverflow]]; | ||
| + | * [[http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html|Otwarte i różnicowe listy w ambitnym kursie Prologa]]. | ||
| - | * [[http://en.wikipedia.org/wiki/Difference_list|Lista różnicowa na en.wikipeda]], | ||
| - | * [[http://en.wikibooks.org/wiki/Prolog/Difference_Lists|Lista różnicowa w Prologu na en.wikibooks]], | ||
| - | * [[http://stackoverflow.com/a/20441480|Pytanie o listy różnicowe na Stackoverflow]], | ||
| - | * [[http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html|Otwarte i różnicowe listy w ambitnym kursie Prologa]] | ||
| - | Do przećwiczenia: przepisać wybrany predykat z zajęć (poza ''sklej/3'') na wersję korzystającą z list różnicowych. | + | |
| --- //[[mateusz.slazynski@agh.edu.pl|Mateusz Ślażyński]] 2014/03/17 13:58// | --- //[[mateusz.slazynski@agh.edu.pl|Mateusz Ślażyński]] 2014/03/17 13:58// | ||
