Nowoczesne wyliczanie

2009-11-04 1:33

W chyba każdy języku posiadającym pojemniki (jak wektory czy listy) istnieje koncepcja iteratorów: obiektów, które pozwalają na przeglądanie kolekcji i są uogólnieniem wskaźników. W najprostszym pozwalają one tylko na pobranie aktualnego elementu i przejście do następnego, ale jest to zupełnie wystarczające do celów wyliczania.
Z wierzchu więc wyglądają one całkiem prosto i przejrzyście – zwłaszcza, jeśli język udostępnia pętlę typu foreach, która ładnie i przezroczyście je opakowuje. Dlatego może wydawać się dziwne, czemu zazwyczaj mechanizm ten jest używany właściwie tylko dla pojemników; w teorii bowiem za pomocą iteratorów (zwanych gdzieniegdzie enumeratorami) można by było przeglądać dosłownie wszystko.
Weźmy chociażby wyszukiwanie plików na dysku – sporo programów w jakimś momencie swojego działania musi znaleźć pliki np. o danej nazwie w określonym katalogu. Wtedy zwykle zakasujemy rękawy i piszemy odpowiednią procedurę rekurencyjną lub bawimy się ze stosem czy kolejką. A czy nie fajniej byłoby, gdyby dało się to zrobić po prostu tak:

  1. for (FsIterator it = ListFiles("c:\\", "*.exe"); it; ++it) { /* zrób coś */ }

oczywiście przeszukując w ten sposób również podkatalogi bez jawnego “wchodzenia” do nich?… Według mnie to by było bardzo fajne :)

Od razu zaznaczę więc, że wbrew pozorom taki iterator jest jak najbardziej możliwy do napisania. Problemem jest jednak to, jak należy przechowywać jego stan. Kiedy wyszukiwanie czy przeglądanie zaimplementowane jest bezpośrednio jako jedna funkcja, robi się to w zasadzie samo: w postaci zmiennych lokalnych (stos/kolejka) albo parametrów (rekurencja). Nikt specjalnie nie zwraca na ten fakt uwagi. Jednak w momencie próby “wyciągnięcia” z algorytmu operacji Next (w celu stworzenia iteratora) okazuje się nagle, że wymaga to jawnego pamiętania tych wszystkich danych, które pozwalają obliczyć następny element. Przy przeszukiwania katalogów trzeba by na przykład pamiętać jakiś systemowy uchwyt wyszukiwania dla aktualnego katalogu, poziom zagnieżdżenia oraz analogiczne uchwyty… dla każdego takiego poziomu!
Zawracanie głowy, prawda? :) Nic dziwnego, że traktowanie wyszukiwania “per iterator” nie jest popularną praktyką. Z punktu widzenia piszącego algorytm wyliczania nieporównywalnie łatwiej jest po prostu wymusić jakiś callback i wywołać go dla każdego elementu; niech się programista-klient martwi o to, jak ten callback wpasować w swój kod. A że ten byłby o wiele czytelniejszy, gdyby w grę wchodziły iteratory? No cóż, iteratorów tak łatwo pisać się nie da…

…chyba że programujemy w Pythonie. Tam bowiem “iteratory” (zwane generatorami) piszemy w zupełnie unikalny, łatwy sposób. Weźmy dla przykładu taką oto klasę drzewa binarnego (BST – Binary Search Tree):

  1. class Tree:
  2.     def __init__(self, key, left = None, right = None):
  3.         self.key = key
  4.         self.left = left
  5.         self.right = right
  6.     def __insert(self, k): # wstawianie elementu
  7.         if (k < self.key):
  8.             if (self.left != None): self.left.__insert (k)
  9.             else:                   self.left = Tree(k)
  10.         else:
  11.             if (self.right != None): self.right.__insert (k)
  12.             else:                   self.right = Tree(k)
  13.     def insert(self, *keys): # wst. wielu elementów
  14.         for k in keys: self.__insert(k)&#91;/python]
  15. Żeby dało się je przeglądać zwykła pętlą <code>for</code> w porządku <em>inorder</em> (dającym posortowanie kluczy), piszemy do niego odpowiedni generator:
  16. [python]    def inorder(self):
  17.         if (self.left != None):
  18.             for t in self.left.inorder(): yield t
  19.         yield self.key
  20.         if (self.right != None):
  21.             for t in self.right.inorder(): yield t

I już – to wystarczy, by poniższa pętla:

  1. for i in tree.inorder():

rzeczywiście “chodziła” po krawędziach drzewa “w czasie rzeczywistym” – bez żadnego buforowania elementów na liście.

Tajemnica tkwi tutaj w instrukcji yield – działa ona jak “tymczasowe zwrócenie” elementu, który jest przetwarzany przez ciało pętli for. Gdy konieczny jest następny element, funkcja inorder podejmuje po prostu działanie począwszy od kolejnej instrukcji – i tak do następnego yielda, kolejnego cyklu pętli i dalszej pracy funkcji. yield działa więc jak callback, tyle że w obie strony. Całkiem zmyślne, czyż nie?
Aż chciałoby się zapytać, czy w innych językach – zwłaszcza kompilowanych – nie dałoby się zrobić czegoś podobnego. Teoretycznie odpowiedź jest pozytywna: przy pomocy zmyślnych sztuczek na stosie wywołań funkcji (technika zwana ‘nawijaniem stosu’ – stack winding) można uzyskać efekt “zawieszenia funkcji” po zwróceniu wyniku i mieć możliwość powrotu do niej począwszy od następnej instrukcji. Nie jestem jednak przekonany, jak taki feature mógłby współpracować z innymi elementami współczesnych języków programowania, jak choćby wyjątkami. Trudno powiedzieć, czy jest to w ogóle możliwe.

Ale skoro w Pythonie się da, to może już C++2x będzie to miał? ;-)

Tags: , , , , ,
Author: Xion, posted under Programming »


4 comments for post “Nowoczesne wyliczanie”.
  1. w.:
    November 4th, 2009 o 10:36

    w c# yield return nie robi tego samego?

  2. Xion:
    November 4th, 2009 o 12:04

    W przybliżeniu tak. Przyznam, że nie wiedziałem o tym wcześniej, ale to tylko potwierdza, że C# ma już chyba wszystko, co da się wymyślić ;-) Dziwi mnie tylko fakt, że ten feature jest już obecny od wersji .NET 2.0, a ja nigdy wcześniej nie widziałem, by jakikolwiek kod go wykorzystywał. Enumeratory nie są popularne.

  3. Kauach:
    November 4th, 2009 o 19:13

    to nie czytałeś kodu Paszklara =). On po prostu uwielbia yield. Niestety słówko ma moim zdaniem jedną wadę – znakomicie zaciemnia kod =(

  4. Kos:
    November 12th, 2009 o 9:03

    Generatory lubie z jednego powodu: Unikaja niepotrzebnego zuzycia pamieci pozwalajac definiowac sam tylko data-flow bze wnikania w szczegoly.
    Czesto widzi sie kod, gdzie modul A prosi modul B o liste czegos tam, cos z nia robi (najczesciej cos mozliwego do opisania funkcyjnym mapowaniem, filtrowaniem lub redukcja) i przekazuje “przemielona” (lub nowa, utworzona od zera) liste dalej, do modulu C, ktory znowu cos z nia robi… Itd.

    Podejscie z “yield” pozwala na zrobienie tego w sensowniejszy sposob: Do obliczenia ostatecznego wyniku nigdy juz cala lista nie musi byc jednoczesnie w pamieci: jeden generator ciagnie elementy z drugiego, ktory wedle potrzeb sciaga i przetwarza elementy z trzeciego. Mozna to w pewien sposob przyrownac do strumieni. Wartosci posrednie sa obliczone dopiero wtedy, gdy sa potrzebne.

    Efekt jest chyba calkiem fajny, bo teoretycznie powinien dac lepsza wydajnosc. Wydaje mi sie tez, ze kod napisany w taki sposob (czysty data flow) powinien sie dac duzo latwiej zrownoleglic, co tez jest waznym argumentem.

Comments are disabled.
 


© 2019 Karol Kuczmarski "Xion". Layout by Urszulka. Powered by WordPress with QuickLaTeX.com.