Posts tagged ‘loop’

Pętla z wyróżnionym startem

2010-07-07 13:57

Jednym z powodów, dla których nie lubię diagramów blokowych, jest ich prymitywna notacja przedstawiania instrukcji sterujących. Jedyne, czym się tam dysponuje, to if i skok. Jak przy pomocy tylko tego można w klarowny sposób przedstawić jakikolwiek nietrywialny algorytm? To trochę tak, jakby w programowaniu używać tylko pętli nieskończonych i instrukcji break.
Można to robić, oczywiście, ale konsekwencje nie są zbyt ciekawe. Jeśli kryterium opuszczenia pętli jest tak skomplikowane, że trzeba je rozbić na kilka konstrukcji ifbreak i żadna z nich “nie zasługuje” na wyciągnięcie do warunku w samym while/for, to coś tu brzydko pachnie. Nie chciałbym być w skórze tego, kto będzie musiał później takie dzieło debugować.

W bardziej rozsądnych przypadkach da się uniknąć pętli nieskończonych, nawet jeśli od razu nie widać, jak można by to zrobić. I tak odkryłem na przykład, jak można to ładnie zrobić w sytuacji podobnej do poniższej:

  1. T foo;
  2. for (;;)
  3. {
  4.     foo = SomeFunction(sth);
  5.     if (!foo.IsOK()) break;
  6.  
  7.    // (Reszta pętli, zmieniająca sth na podstawie foo)
  8. }

Nazywam to pętlą z wyróżnionym startem, bo typowa jej postać, która nie zawiera (pozornie) nieskończonego kręcenia się w kółko, wygląda tak:

  1. for (T foo = SomeFunction(sth); foo.IsOK(); foo = SomeFunction(sth))
  2.     { /* Reszta pętli, jw. */}

Cała zabawa polega na tym, że pierwsze wywołanie SomeFunction może dać niepoprawną wartość w foo. (Może to być jakieś wyszukiwanie w pojemniku i element odpowiadający kluczowy sth nie został w ogóle znaleziony). Sama treść pętli nie może być wtedy wykonana, bo zdarzy się zapewne jakieś nieszczęście. Dlatego trzeba wyodrębnić to pierwsze wywołanie, i oczywiście zadbać także o kolejne. A to daje, jak widać, dublowanie kodu. Chciałoby się to zrobić lepiej.

I można, na szczęście. Możemy za to podziękować feature‘owi C++, który często bywa krytykowany jako ułatwiający popełnianie błędów. Bowiem to dzięki temu, że instrukcja przypisania zwraca wartość przypisywaną, możemy to wszystko zapisać tak:

  1. for (T foo; (foo = SomeFunction(sth)).IsOK(); /* nic */)
  2.     { /* Reszta pętli */ }

Zdaję sobie sprawę, że dla wielu fakt ten jest równie oczywisty jak pisanie return a == b; zamiast:

  1. if (a == b) return true; else return false;

ale dla niektórych taka postać pętli for może być zupełnie zaskakująca. Pamiętajmy, że kiedyś (prawie) każdy pisał też i takie ify jak powyżej ;-)

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

Nawet SQL ma pętle

2009-01-12 12:35

Stwierdzenie ‘programować w HTML’ jest rzecz jasna nadużyciem, ale istnieją przecież inne języki, dla których określenie ‘programistyczne’ (lub jego brak) nie jest wcale takie oczywiste. Weźmy choćby SQL, teoretycznie pretendujący do miana języków deklaratywnych. Charakteryzują się one tym, że pisząc w nich określamy tylko to, co ma zostać zrobione – nie zaś jak. Na pierwszy rzut oka ma to sens: w końcu pisząc proste lub nawet całkiem skomplikowane zapytanie SELECT w ogóle nas nie interesuje to, przy pomocy jakich struktur danych zostanie ono wykonane i jaka pętla będzie się za nim kryć.
Bo przecież SQL nie ma pętli, prawda? :)

Ano właśnie nieprawda. Ponadto czasami są one jedynym wyjściem, jeśli mamy do czynienia z nieco bardziej skomplikowanymi danymi – jak choćby z jakąś hierarchią drzewiastą. Zwykle zapisuje się ją w relacyjnej bazie danych tak, że każdy element zawiera informacje o identyfikatorze elementu do niego nadrzędnego. Jest to całkowicie wystarczającą informacją do odtworzenia ich hierarchii.
Do takiego drzewka łatwo dodawać nowego elementy, ale ich usuwanie może być już problemem. Wyrzucenie jednej pozycji powinno bowiem oznaczać odcięcie całego poddrzewa – zwłaszcza że na pozostawienie osieroconych potomków często nie pozwoli sam silnik bazy danych, jeśli sprawdza poprawność relacji. Musimy zatem usuwać od dołu, a następnie przesuwać się w górę… Tylko jak niby zapisać to w postaci zapytania SQL?
Okazuje się, że nic prostszego. No, a przynajmniej okazuje się, że da się to zrobić:

  1. CREATE PROCEDURE DeleteItem
  2.     @ID int
  3. AS
  4. BEGIN
  5.     DECLARE @cur CURSOR
  6.     DECLARE @ChildID int
  7.    
  8.     SET @cur = CURSOR FOR (SELECT ID FROM Items WHERE ParentID = @ID)
  9.     OPEN @cur
  10.     FETCH NEXT FROM @cur INTO @ChildID
  11.     WHILE @@FETCH_STATUS = 0
  12.     BEGIN
  13.         EXECUTE DeleteItem @ChildID
  14.         FETCH NEXT FROM @cur INTO @ChildID
  15.     END
  16.    
  17.     DELETE FROM Items WHERE ID = @ID
  18. END

Nawet bez specjalnej znajomości składni można się domyślić, co tutaj jest wykonywane. Oto używamy kursora (coś w stylu iteratora), żeby najpierw usunąć elementy podrzędne do tego, który zamierzamy wykasować. W tym celu dla każdego z nich wywołujemy po prostu tę samą procedurę. Na koniec dokonujemy usunięcia pierwotnego elementu, który teraz na pewno jest już liściem (nie ma żadnych potomków), więc może być wyrzucony bez przeszkód.

Całkiem proste, czyż nie? Można powiedzieć, że w każdym języku programowania algorytm ten wyglądałby podobnie… Sęk w tym, że tu właśnie tkwi problem. Bo skoro w rzekomo deklaratywnym języku SQL można (a w tej sytuacji nawet trzeba) używać takich narzędzi jak pętle czy rekurencja, to przecież nie różni się on wtedy niczym od “normalnych” języków programowania. Jeśli całą operację trzeba zakodować krok po kroku, to nie mamy już żadnej korzyści z filozofii polegającej na określaniu ‘co’, a nie ‘jak’.
Może więc znaczy to, że inaczej programować po prostu się nie da? :)

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

Pętla ‘for each’

2008-02-09 20:17

W bardzo wielu językach dostępna jest dodatkowa postać pętli for, znana powszechnie jako foreach. Jak jej nazwa wskazuje, służy ona do przeglądania elementów jakiejś kolekcji. Różnica pomiędzy tą konstrukcją a dowolną inną pętlą jest taka, iż przeglądanie to jest zrealizowane w sposób najprostszy z możliwych:

  1. List<string> strings = new List<string>();
  2. // ...
  3. foreach (string s in strings)
  4.    Console.WriteLine (s);

W szczególności nie potrzeba się posługiwać żadnymi indeksami ani też jawnie stosowanymi iteratorami. Dostęp do poszczególnych elementów zbioru odbywa się za pośrednictwem symbolicznej zmiennej, która przyjmuje wartości równe tymże elementom. Proste i skuteczne.
Zresztą, niektórym twórcom języków tak się ta koncepcja spodobała, że… całkowicie zrezygnowali z tradycyjnej postaci pętli for (w wersji od-do, jak w Pascalu, lub start-warunek-inkrement, jak w językach C-podobnych).Tak jest chociażby w Pythonie; można tam jednak uzyskać identyczny efekt pętli “liczbowej” w taki oto zabawny sposób:

  1. # drukuje 0, ..., 9
  2. for i in range(0, 10):
  3.    print i

Ogółem jednak pętla foreach wydaje się bardzo zgrabnym wynalazkiem. Świadczy o tym chociażby istnienie takich makr jak BOOST_FOREACH, które to ładnie adaptuje cały pomysł do kontenerów STL w C++, tablic i nie tylko.
Jest jednak pewne ‘ale’. foreach sprawdza się świetnie, jeśli tylko kolekcję przeglądamy, bez dokonywania w niej zmian. Jeśli musimy przy okazji coś do niej dodać lub usunąć, lub nawet tylko zmienić wartość jakiegoś elementu, to nagle pętla taka przestaje nam wystarczać. Z doświadczenia wiem, że po tym, jak radośnie i bez wysiłku wpisuję pętlę foreach, w 80% muszę w którymś momencie i tak zmienić ją na zwykły for :-)

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

Pętle w Pythonie

2007-08-12 12:21

Konstrukcje iteracyjne w C++ mają całkiem spore możliwości. Dotyczy to zwłaszcza instrukcji for, która jest o wiele elastyczniejsza niż w innych językach. Mimo to w dziedzinie pętli C++ ma pewne niedostatki.
Zwykle najbardziej brakuje nam sposobu na przerwanie zagnieżdżonych pętli. W C# czy Javie jest to możliwe za pomocą specjalnych wariantów instrukcji break. Lecz w C++ trzeba to robić albo z wykorzystaniem wyklętej (niezbyt zresztą słusznie) instrukcji goto, albo poprzez zastosowanie zmiennych logicznych. Istnieje też sposób z wykorzystaniem wyjątków, ale można go traktować chyba tylko jako ciekawostkę.

Jest jeszcze jedno usprawnienie mechanizmu pętli, którego C++ nie posiada, ale dla odmiany ten brak nie jest aż tak dolegliwy. Chodzi tu o klauzulę else występującą po pętli. Tę nietypową konstrukcję widziałem jak dotąd tylko w języku Python; wygląda ona następująco:

  1. # sprawdzenie, czy liczba x jest pierwsza
  2. for i in range(2, x):
  3.    if x % i == 0:
  4.       print x, " dzieli się przez ", i
  5.       break
  6. else:
  7.    print x, " jest liczbą pierwszą"

Fraza else odnosi się tutaj do pętli, a nie do instrukcji if. Jest ona wykonywana wtedy, gdy pętla kończy się normalnie, tzn. nie następuje wykonanie instrukcji break. Jak widać oznacza to zwykle, że jakiś rodzaj przeszukiwania dotarł do końca wyznaczonego zakresu bez znalezienia pasującego elementu (w tym przypadku – dzielnika).

Większość języków nie posiada tej dziwnej konstrukcji, bo najczęściej można się bez niej obejść. Przeszukiwanie dokonywane w pętli jest bowiem często zamykane w funkcję, którą można zapisać bez użycia break:
bool IsPrime(unsigned x)
{
for (unsigned i = 2; i < x; ++i) if (x % i == 0) return false; return true; }[/cpp] Pewne “nowoczesne” konstrukcje w nowszych językach programowania nie są więc zawsze lekarstwem na programistyczne bolączki. Czasami są zwykłym zawracaniem głowy.

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


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