Thread View: pl.comp.lang.funkcyjne
3 messages
3 total messages
Started by Wojciech Muła
Sat, 27 May 2006 13:02
Złożoność łącznia list
Author: Wojciech Muła
Date: Sat, 27 May 2006 13:02
Date: Sat, 27 May 2006 13:02
15 lines
1555 bytes
1555 bytes
Trochę się zdziwiłem, że w Ocamlu operator @ działa w czasie liniowym ze względu na długość pierwszego argumentu. Pogrzebałem trochę po Internecie i okazało się, że w zachwalanym tutaj Haskell jest tak samo. Macie pomysł dlaczego tak jest? Tzn. nie chodzi o sam algorytm łącznia, którego dość łatwo się domyśleć, ale dlaczego nie implementuje się list w taki sposób, żeby ich łącznie wykonywało się w stałym czasie -- przecież dodatkowy koszt pamięciowy byłby niewielki. Są jakieś poważniejsze przeciwwskazania? w. -- Tępi głupcy są własnymi nieprzyjaciółmi, gdy dopuszczają się złych uczynków, których owoce są gorzkie.
Re: Złożoność łącznia list
Author: Marcin Mankiewicz
Date: Sat, 27 May 2006 14:05
Date: Sat, 27 May 2006 14:05
19 lines
1857 bytes
1857 bytes
On Sat, 27 May 2006 13:02:00 +0000 (UTC), Wojciech Muła <wojciech_mula@poczta.null.onet.pl.invalid> wrote: > Trochę się zdziwiłem, że w Ocamlu operator @ działa w czasie liniowym ze > względu na długość pierwszego argumentu. Pogrzebałem trochę po Internecie > i okazało się, że w zachwalanym tutaj Haskell jest tak samo. > > Macie pomysł dlaczego tak jest? Tzn. nie chodzi o sam algorytm łącznia, > którego dość łatwo się domyśleć, ale dlaczego nie implementuje się list > w taki sposób, żeby ich łącznie wykonywało się w stałym czasie -- przecież > dodatkowy koszt pamięciowy byłby niewielki. Są jakieś poważniejsze > przeciwwskazania? to by wymuszało modyfikację pierwszego argumentu "w miejscu" co jest niefunkcyjnym zachowaniem. A tak pierwszy argument jest kopiowany a drugi jako referencja doklejany. (Pewnie trochę uprościłem, ale mam nadzieję, że oddałem intuicję). -- Marcin Mankiewicz
Re: Złożoność łącznia list
Author: Marcin 'Qrczak' Kowalczyk
Date: Sat, 27 May 2006 15:57
Date: Sat, 27 May 2006 15:57
15 lines
1877 bytes
1877 bytes
Marcin Mankiewicz <znyrba@eden.one.pl> writes:
> to by wymuszało modyfikację pierwszego argumentu "w miejscu" co jest
> niefunkcyjnym zachowaniem. A tak pierwszy argument jest kopiowany a
> drugi jako referencja doklejany. (Pewnie trochę uprościłem, ale mam
> nadzieję, że oddałem intuicję).
Dodam, że są implementacje ciągów, które mają inny
koszt różnych operacji bez zmian obiektów w miejscu,
np. http://www.google.pl/search?q=%22democratic+sequences%22
--
__("< Marcin Kowalczyk
\__/ qrczak@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads