Zadania do wykładu o strukturach wielowymiarowych

Perl: programowanie - struktury wielowymiarowe i różności

Na wykładzie poruszane były nie tylko tematy dotyczące struktur wielowymiarowych, ale także zagadnienia powiązane, np. wykorzystanie operatorów each, map, itp. Dlatego zadania poniższe są nieco trudniejsze i bogatsze treściowo od poprzednich. :)

1. Sprawdź działanie operatora each na prostym haszu kilkunastoelementowym. Wykorzystując pętlę oraz each, iteruj po wszystkich elementach hasza, a następnie przeprowadź testy, które odpowiedzą Ci na pytanie, czy dodanie/usunięcie/zmiana elementu hasza powoduje rozpoczęcie iteracji od nowa. Jak w takich przypadkach zachowuje się each?
   Operator each pobiera z hasza parę danych - odpowiadający sobie klucz i jego wartość. Operacja ta jest wykonywana w taki sposób, że each w magiczny sposób zapamiętuje stan hasza aby wiedzieć, jakie pary wartości już pobrano, a jakich nie. Dodanie do hasza nowego klucza burzy porządek zebranych w nim elementów i each może się wtedy pogubić. Operacja zmiany istniejącego elementu lub usunięcia istniejącego klucza nie ma wpływu na działanie operatora each. Dowód tego, że dodanie klucza zmienia działanie operatora można zobaczyć wykonując poniższy krótki program: #!/usr/bin/perl -w use strict; my %Z = ( 'abc' => 1, 'bcd' => 2, 'cde' => 3, 'def' => 4, 'efg' => 5, ); my $i = 0; while( my ($k,$v) = each %Z ){ print "$i. k='$k', v='$v'\n"; if($i==4){ $Z{fgh} = 6; $Z{ghi} = 7; $Z{hij} = 8; } $i++; }
2. * (gwiazdka dodana ze względu na złożoność zagadnienia) Transformacja Schwartza i sortowanie słownikowe: to zadanie składa się z podzadań.
   Sortowanie słownikowe jest tu rozumiane jako ustawienie słów w takiej kolejności, w której wielkość liter nie ma znaczenia, czyli "Czesne" znajduje się obok słowa "czesne", itp.
   1. Posortuj plik ze słowami (słowa.txt) za pomocą polecenia unixowego sort. Zaobserwuj kolejność elementów. Plik ze słowami zawiera mieszane słowa polskie i angielskie pisane z wielkiej lub z małej litery.
      Sortowanie listy słów podanych w pliku za pomocą unixowego polecenia sort daje w efekcie listę słów zaczynającą się od słów: "About above angielskie Anglistyki..." a kończący się słowami: "zgody zgromadzone zjawisko". Jak widać, efekt sortowania jest taki, że nie są uwzględniane wielkie litery w słowach.
   2. Napisz program, który posortuje słowa znajdujące się w pliku słowa.txt. Obejrzyj wynik sortowania i znajdź miejsca, w których sortowanie to jest różne od wyniku działania polecenia sort unixowego.
      Program taki można napisać w jednym wierszu nawet, np. tak: perl -e '@a=`cat slowa.txt`; print sort @a;' Kolejność słów otrzymana z takiego sortowania jest inna niż polecenia unixowego sort, bowiem pierwsze słowa z listy posortowanej to "About Anglistyki Assistant Assumptions...", natomiast ostatnie to "zgody zgromadzone zjawisko". Wygląda na to, że sortowanie perlowe wykonuje rozróżnienie pomiędzy małymi i wielkimi literami, i tak jest w rzeczywistości. Wielkie litery mają w tym przypadku pierwszeństwo przed małymi literami, zatem słowa "Abc, Bcd, abc" będą miały rzeczywistą kolejność "Abc, Bcd, abc" a nie jak w przypadku unixowego sort - "Abc, abc, Bcd". Uzupełnienie: doniesiono mi, że w testach studentów kolejność ta może być inna, jeżeli chodzi o przemienność wielkich i małych liter. Cóż - może zależy to od systemu? :) Uzupełnienie: doniesiono mi, że w testach studentów kolejność ta może być inna, jeżeli chodzi o przemienność wielkich i małych liter. Cóż - może zależy to od systemu? :)
   3. Napisz program, który sortuje słownikowo plik mieszanych słów angielskich i polskich z wielkimi i małymi literami na początku. Wykorzystaj operator sort oraz anonimową funkcję sortującą z operatorem cmp i napisami konwertowanymi na małe litery.
      Program taki jest bardzo prosty, i w rzeczywistości jest to tylko drobne rozwinięcie poprzedniego kodu. Oczywiście można łatwo wykonać sortowanie zgodne z tym, które robi polecenie unixowe sort, a sposób jest taki: perl -e '@a=`cat slowa.txt`; print sort { lc $a cmp lc $b } @a;' Wynik takiego sortowania jest prawie identyczny z tym, który generuje polecenie sort unixowe. Prawie - dlatego że słowa takie jak "Computer" i "computer", albo "wszelkie" i "Wszelkie", które znajdują się w pliku, w przypadku sortowania perlowego uzyskują kolejność "Computer computer" oraz "Wszelkie wszelkie" a w przypadku sortowania unixowego ich kolejność jest odwrotna.
   4. Napisz program (lub zmodyfikuj poprzedni) w taki sposób, aby zobaczyć, ile razy porównywane są ze sobą poszczególne słowa. Można i należy wykorzystać do tego celu zliczanie słów w haszach.
      Ilość porównań wykonywanych pomiędzy elementami może zaskakiwać! Oto kod, który wyświetli liczbę porównań wykonywanych dla każdego elementu oraz sam element (słowo): perl -e '@a=`cat slowa.txt`;@a=sort {$A{$a}++;$A{$b}++; lc$a cmp lc$b} @a; for(keys %A){print "$A{$_}: $_"}' Fragment wyniku działania tego programu przedstawiony jest poniżej: 11: represent 14: chunk 10: specializes 13: starting 13: Osoby 11: Internecie 13: behind 12: written 11: Uniwersytetu 9: polskiego 8: information 7: About 13: internetowych 5: years Jak widać, liczba porównań dla tablicy zawierającej 156 słów wynosi 1860! (Liczba ta to suma wszystkich porównań). Zwrócono mi tu uwagę, że porównanie to operacja obejmująca dwa napisy, zatem ilość aktów porównania jest mniejsza dwa razy, i wynosi 930. Trudno się z tym nie zgodzić, jednakże wolałbym liczyć każdy napis osobno, dlatego, że ten sam napis jest inną liczbę razy po lewej stronie operatora, a inną po prawej. Należy pamiętać, że TYLE SAMO razy jest wykonywana operacja lc zastosowana przy porównywaniu za pomocą cmp, aby nierozróżniane były wielkie i małe litery. Wykonanie aż tylu operacji lc jest zbędne i niepotrzebnie spowalnia program. W tym przypadku nie ma to jeszcze wielkiego znaczenia, ale często operacja podobna do lc zajmuje zbyt wiele czasu, aby można było sobie pozwolić na jej lekkomyślne powtarzanie (może to być np. odwołanie do zasobu dyskowego na sieci, pobieranie informacji przez sieć lub z powolnego urządzenia, itp.). Dlatego właśnie przydatna staje się Transformacja Schwartza.
   5. * Wykorzystując transformację Schwartza zoptymalizuj program w taki sposób, aby sortowanie odbywało się dla każdego słowa tylko raz. Wykorzystaj tymczasowe klucze oraz kombinację operatorów map{...} sort {...} map {...}. Gotowy kod powinien w efekcie pracować na tablicach anonimowych (stosowanie napisów i wyrażeń regularnych do ich rodzielania na razie sobie odpuszczamy).
      Transformacja Schwartza jest pewnym trickiem programistycznym wykorzystującym naturalne cechy języka perla. Nazwa została nadana na cześć Randala Schwartza, który kiedyś za jej pomocą rozwiązał pewne problemy i opublikował rozwiązanie na Usenecie. W zastosowaniu do sortowania naszych słów, transoformacja ta polega na pobraniu listy słów, a następnie stworzeniu dla każdego z nich pary złożonej ze słowa oryginalnego oraz słowa zmienionego przez operator lc. Takie pary słów są następnie przekazane do procedury sortującej, która porównuje z każdej pary już tylko przetworzone słowa, a następnie ze zwróconej listy par wybierana jest na powrót wartość oryginalna słowa. Cały kod, mimo dużego opisu jest bardzo krótki i przypomina wykonanie operacji sortowania na tymczasowych kluczach uzyskanych z listy wejściowej kluczy zamiast na oryginalnych kluczach. Oto treść programu, który wykonuje takie sortowanie: @a = `cat slowa.txt`; @a = map $_->[0], sort { $a->[1] cmp $b->[1] } map { [ $_, lc $_ ] } @a; Już na pierwszy rzut oka widać, że kod składa się z trzech operacji podstawowych: map ... sort ... map. Całe wyrażenie najlepiej czytać od końca, czyli od prawej strony, gdyż w podobny sposób się ono wykonuje. Oto mamy z prawej strony tablicę @a. Ta tablica jest przetwarzana przez polecenie map [ $_, lc $_ ], które robi tylko tyle, że dla każdego elementu tablicy @a stworzy tablicę anonimową zawierającą ten element oraz ten element skonwertowany przez operator lc. Dlatego zapisane jest [$_,lc $_] - jest to właśnie uzyskanie tablicy anonimowej z dwoma elementami (pierwszy oryginalny, drugi zmieniony) z elementu bieżącego przetwarzanej tablicy @a. Kolejnym krokiem do zrozumienia działania tej złożonej operacji jest fakt, że map użyty do generowania tablic anonimowych zwróci całą listę tych tablic. Generalnie wykonane zostanie coś takiego: @a wynik map $_ [$_,lc $_] BLA ['BLA','bla'] zupa ['zupa','zupa'] Abc ['Abc','abc'] ... ... i to po tym pierwszym od prawej map. Taka lista tablic anonimowych jest następnie pakowana na wejście operatora sort, który widzi z tej tablicy naraz dwa elementy, nazywane umownie $a i $b. Elementy te w tym przypadku to już nie są normalne słowa, jak byłoby przy prostym sortowaniu tablicy @a, ale referencje do anonimowych tablicy, czyli do elementów w postaci ['TEXT','text']. Taka referencja umożliwia dostanie się do poszczególnych elementów za pomocą zapisu np. $a->[0] (co daje "TEXT"), lub $a->[1] (co daje "text"). Dlatego wewnątrz bloku sortującego operatora sort istnieje zapis $a->[1] cmp $b->[1]. To po prostu porównanie tekstów zawartych w tablicach anonimowych, w dodatku porównanie tylko tekstów zmienionych za pomocą lc, który już przy tych porównaniach nie jest ponownie wywoływany, co oczywiste. Sortowanie daje w efekcie listę takich samych tablic anonimowych, z tym, że już odpowiednio ustawionch, w kolejności sortowania. Ostatnim elementem Transformacji Schwartza jest najbardziej lewostronny map, którego zadaniem jest po prostu wydobycie z listy tablic anonimowych, które otrzymuje, jedynie tych oryginalnych tekstów, które się tam także znajdują. Robiona jest więc w tym miejscu operacja odwrotna: map dostaje referencję do tablicy anonimowej i wyciąga z niej napis, który został oryginalnie na początku tam umieszczony: dostaje: zwraca: $_ $_->[0] ['TEXT','text'] 'TEXT' Wynik przypisany do tablicy powoduje, że znajdą się w niej oryginalne słowa posortowane przez sort w odpowiedni sposób, a tymczasowe tablice zawierające pary wartości zostaną usunięte z pamięci.
3. * Napisz program, który przeskanuje twój katalog domowy i zbuduje optymalną strukturę danych odwzorowującą wszystkie pliki i katalogi, jakie zostaną znalezione. Najprościej do tego celu wykorzystać funkcje opendir, readdir i closedir. Dodatkowo może zajść potrzeba utworzenia funkcji (jeżeli postawisz na rozwiązania rekurencyjne). W razie wątpliwości zapytaj prowadzącego. To zadanie oznakowałem gwiazdką dlatego, że nie było jeszcze mowy o funkcjach. Możliwe dalsze rozwinięcia programu: taki program można wykorzystać do tworzenia bazy swoich plików MP3 lub optymalnego podziału plików na katalogi po 700MB każdy przed ich nagraniem na płyty... sam algorytm skanowania dysku może się przydać do poszukiwania pliku np. konfiguracyjnego lub innego o ważnej treści... można także stworzyć raport zajętości wszystkich katalogów wyrażony jako suma kB przestrzeni zajmowanej przez ich podelementy :>
   Praca w perlu z katalogami jest trochę podobna do pracy z plikami: katalog należy otworzyć, aby można było z niego czytać. A to, co z niego czytamy to po prostu wszystkie nazwy plików, włącznie z kropką oznaczającą bieżący katalog oraz dwiema kropkami '..' oznaczającymi katalog nadrzędny. Procedura rekurencyjna, która wczytuje pliki do hasza może wyglądać tak: # wczytywanie całego drzewa katalogów i plików do hasza sub scan { my $path = shift; # sciezka do przeszukania my %files; # hasz na wczytane pliki i katalogi if(-e $path and -r _ and -x _){ # jezeli istnieje katalog i mozemy go czytac if( opendir my $dh,$path ){ # otworz katalog foreach my $item ( readdir $dh ){ # zasuwaj po wszystkich elementach wczytanych next if $item eq '.'; # pomijamy ten sam katalog . next if $item eq '..'; # pomijamy nadrzedny katalog .. next if -l "$path/$item"; # pomijamy lacza symboliczne, zeby nie zapetlic sie if( -d "$path/$item" ){ # jezeli to katalog, dodajemy do hasza wszystko z niego $files{$item} = { scan("$path/$item") }; # zauwaz ze jest to referencja: { ... } } elsif( -f "$path/$item" ){ # jezeli to plik, to tylko pobierz rozmiar $files{$item} = -s _; # za pomoca operatora -s (_ to skrot = poprzedni plik) } } closedir $dh; } else{ warn "Nie mozna otworzyc katalogu $path! $!\n"; } } return %files; # zwracamy po prostu liste nie martwiąc się o szczegóły wydajnościowe :P }