Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00099 007802 10476330 na godz. na dobę w sumie
Przetwarzanie danych dla programistów - książka
Przetwarzanie danych dla programistów - książka
Autor: Liczba stron: 264
Wydawca: Helion Język publikacji: polski
ISBN: 83-246-0407-3 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> inne - programowanie
Porównaj ceny (książka, ebook, audiobook).

Przetwarzanie danych to czynność, którą programiści na całym świecie wykonują niemal codziennie. Konwersja danych pomiędzy systemami informatycznymi, zmiana formatów plików tekstowych, przeszukiwanie logów serwerów WWW -- to wszystko można nazwać przetwarzaniem danych. Znajomość technik, dzięki którym takie procesy odbywają się szybko i efektywnie, to jedna z najważniejszych umiejętności programisty. Trudnością może okazać się brak jednego uniwersalnego sposobu przetwarzania danych. Do każdego typu problemu należy podejść w sposób indywidualny, próbując rozłożyć go na sekwencję prostych przekształceń, łatwych do implementacji i testowania.

Czytając książkę 'Przetwarzanie danych dla programistów', poznasz metody rozwiązywania problemów programistycznych związanych z konwersją danych różnego typu. Nauczysz się analizować istotę zagadnienia i dobierać najbardziej optymalny sposób realizacji zadania. Dowiesz się, jak w systemach Unix/Linux wykorzystać wyrażenia regularne i powłoki tekstowe do przetwarzania danych tekstowych. Przeczytasz o użytecznych, lecz często niedocenianych cechach języków Java i Python oraz innych języków programowania. Przekonasz się, że mimo rozbieżności pomiędzy różnymi typami danych istnieje kilka ogólnych wzorców, które powtarzają się w wielu zastosowaniach niezależnie od użytego języka programowania lub detali implementacyjnych.

Opanuj jedną z podstawowych umiejętności profesjonalnego programisty.

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREŒCI SPIS TREŒCI KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOŒCIACH O NOWOŒCIACH ZAMÓW CENNIK ZAMÓW CENNIK CZYTELNIA CZYTELNIA FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Przetwarzanie danych dla programistów Autor: Greg Wilson T³umaczenie: Marek Pêtlicki ISBN: 83-246-0407-3 Tytu³ orygina³u: Data Crunching Format: B5, stron: 264 Przetwarzanie danych to czynnoœæ, któr¹ programiœci na ca³ym œwiecie wykonuj¹ niemal codziennie. Konwersja danych pomiêdzy systemami informatycznymi, zmiana formatów plików tekstowych, przeszukiwanie logów serwerów WWW — to wszystko mo¿na nazwaæ przetwarzaniem danych. Znajomoœæ technik, dziêki którym takie procesy odbywaj¹ siê szybko i efektywnie, to jedna z najwa¿niejszych umiejêtnoœci programisty. Trudnoœci¹ mo¿e okazaæ siê fakt, ¿e nie istnieje brak jednego, uniwersalnego sposobu przetwarzania danych. Do ka¿dego typu problemu nale¿y podejœæ w sposób indywidualny, próbuj¹c roz³o¿yæ go na sekwencjê prostych przekszta³ceñ, ³atwych do implementacji i testowania. Czytaj¹c ksi¹¿kê „Przetwarzanie danych dla programistów”, poznasz metody rozwi¹zywania problemów programistycznych zwi¹zanych z konwersj¹ danych ró¿nego typu. Nauczysz siê analizowaæ istotê zagadnienia i dobieraæ najbardziej optymalny sposób realizacji zadania. Dowiesz siê, jak w systemach Unix/Linux wykorzystaæ wyra¿enia regularne i pow³oki tekstowe systemów z rodziny Unix/Linux do przetwarzania danych tekstowych., Pprzeczytasz o u¿ytecznych, lecz czêsto niedocenianych cechach jêzyków Java i Python oraz innych jêzyków programowania. Przekonasz siê, ¿e mimo rozbie¿noœciró¿nic pomiêdzy ró¿nymi typami danych istnieje kilka ogólnych wzorców, które powtarzaj¹ siê w wielu zastosowaniach niezale¿nie od u¿ytegozastosowanego jêzyka programowania lub detali implementacyjnych. (cid:129) Przetwarzanie danych tekstowych za pomoc¹ pow³oki Uniksa (cid:129) Stosowanie wyra¿eñ regularnych (cid:129) Analiza dokumentów XML (cid:129) Pakowanie i rozpakowywanie danych binarnych (cid:129) Zapytania w relacyjnych bazach danych (cid:129) Testowanie mechanizmów konwersji danych Opanuj jedn¹ z podstawowych umiejêtnoœci profesjonalnego programisty Rozdział 1. Wprowadzenie .................................................... 5 1.1. Narysować molekułę ................................................................5 1.2. Czarna owca ...........................................................................7 1.3. Morał .....................................................................................8 1.4. Pytania o przetwarzanie danych ................................................9 1.5. Plan książki ...........................................................................13 Rozdział 2. Tekst ................................................................. 17 2.1. Odwracanie kolejności wierszy w pliku ....................................17 2.2. Przeformatowanie danych ......................................................20 2.3. Obsługa rekordów wielowierszowych .......................................29 2.4. Testowanie kolizji ..................................................................36 2.5. Włączanie plików zewnętrznych ..............................................42 2.6. Powłoka Uniksa ....................................................................47 2.7. Bardzo duże zbiory danych ....................................................56 2.8. Podsumowanie ......................................................................57 Rozdział 3. Wyrażenia regularne ......................................... 59 3.1. Powłoka ................................................................................61 3.2. Podstawy wzorców dopasowań ...............................................63 3.3. Wydobywanie dopasowanych wartości ....................................72 4 Przetwarzanie danych dla programistów 3.4. Zastosowania praktyczne .......................................................83 3.5. Różne języki ..........................................................................95 3.6. Inne systemy ..........................................................................99 3.7. Podsumowanie ....................................................................104 Rozdział 4. XML ................................................................ 105 4.1. Szybkie wprowadzenie .........................................................106 4.2. SAX ..................................................................................112 4.3. DOM .................................................................................126 4.4. XPath ................................................................................137 4.5. XSLT ................................................................................143 4.6. Podsumowanie ....................................................................153 Rozdział 5. Dane binarne ................................................... 157 5.1. Liczby ................................................................................158 5.2. Wejście i wyjście ..................................................................165 5.3. Ciągi znaków .......................................................................171 5.4. Podsumowanie ....................................................................182 Rozdział 6. Relacyjne bazy danych .................................... 185 6.1. Proste zapytania ..................................................................186 6.2. Zagnieżdżanie i negacja .......................................................197 6.3. Agregacje i perspektywy .......................................................203 6.4. Tworzenie, modyfikacja i usuwanie .......................................207 6.5. Zastosowanie SQL-a w programach .....................................216 6.6. Podsumowanie ....................................................................220 Rozdział 7. Diabeł tkwi w szczegółach .............................. 223 7.1. Testy jednostkowe ...............................................................223 7.2. Kodowanie i dekodowanie ....................................................235 7.3. Arytmetyka zmiennoprzecinkowa ..........................................239 7.4. Daty i czas ..........................................................................242 7.5. Podsumowanie ....................................................................248 Dodatek A Bibliografia ....................................................... 249 Skorowidz ........................................................................... 251 EKST JEST JEDNYM Z NAJSTARSZYCH FORMATÓW danych i nadal należy do najbardziej popularnych. Jednym z powodów po- pularności takiego formatu jest fakt, że dane w nim zapisane można przetwarzać i przeglądać za pomocą dowolnego edytora tekstów. Głębszy powód tej popularności leży w tym, że pisanie programów do automatycznej manipulacji tekstem jest bardzo łatwe. W tym rozdziale przyjrzymy się pro- gramom tego typu, ich możliwościom i podstawowej strukturze. Zatrzy- mamy się też chwilę przy wierszu poleceń systemów Unix, środowisku zo- rientowanemu tekstowo, które nadal trzyma się bardzo dobrze, pomimo niemal czterdziestoletniej tradycji. 2.1. Odwracanie kolejności wierszy w pliku Na początek weźmiemy pod uwagę zupełnie podstawowy problem przetwa- rzania danych tekstowych, jakim jest odwrócenie kolejności wierszy w pliku. Oto proste rozwiązanie tego problemu w Pythonie: import sys # Odczyt input = open(sys.argv[1], r ) lines = input.readlines() 18 Przetwarzanie danych dla programistów input.close() # Przetwarzanie lines.reverse() # Zapis output = open(sys.argv[2], w ) for line in lines: print output, line.strip() output.close() Kod jest trywialny, posiada jednak strukturę charakterystyczną dla większości procedur przetwarzających dane: 1. odczyt danych wejściowych, 2. przetwarzanie, 3. zapis wyniku. W wielu przypadkach możliwe jest zapisywanie wyniku na bieżąco w ramach przetwarzania, lecz prawie zawsze najlepiej jest podzielić problem na po- wyższe etapy. Po pierwsze, dzięki temu kod staje się czytelniejszy i łatwiej go wykorzystać ponownie (problemy tego typu bywają bardzo powtarzalne). Po drugie, to podejście jest niezwykle uniwersalne i działa prawie zawsze1, natomiast odmiana polegająca na połączeniu etapu drugiego z trzecim nie zawsze zadziała (przykładem jest właśnie odwracanie kolejności wierszy pliku). Zwolennicy mniej dynamicznych języków programowania mogą preferować następującą wersję napisaną w Javie: import java.util.*; import java.io.*; public class ReverseLines { public static void main(String[] args) { try { // Odczyt BufferedReader input = new BufferedReader(new FileReader(args[0])); ArrayList list = new ArrayList(); String line; while ((line = input.readLine()) != null) { list.add(line); } 1 Chyba że danych jest zbyt wiele, by mogły zmieścić się w pamięci. Do tego tematu wrócimy w dalszej części rozdziału. Rozdział 2. (cid:129) Tekst 19 input.close(); // Przetwarzanie Collections.reverse(list); // Zapis PrintWriter output = new PrintWriter(new BufferedWriter(new FileWriter(args[1]))); for (Iterator i=list.iterator(); i.hasNext(); ) { output.println((String)i.next()); } output.close(); } catch (IOException e) { System.err.println(e); } } Nietrudno zauważyć, że ten kod jest dłuższy od jego odpowiednika w Py- thonie, lecz obydwa realizują dokładnie tę samą funkcję w niemalże iden- tyczny sposób. Oczywiście bezpośrednie przełożenie kodu z jednego języka na drugi nie zawsze daje najbardziej naturalne lub optymalne rozwiązanie. Prawdziwi programiści Javy z pewnością preferują umieszczenie odczytu, przetwarza- nia i zapisu danych w osobnych metodach klasy, zechcą też pominąć wy- wołanie metody reverse(), a raczej zechcą odczytywać elementy pojedyn- czo, jednak w odwróconej kolejności: PrintWriter output = new PrintWriter(new BufferedWriter(new FileWriter(args[1]))); for (ListIterator i=list.listIterator(list.size()); i.hasPrevious(); ) { output.println((String)i .previous()); } output.close(); A co z obsługą błędów? W jaki sposób ma zachować się program, jeśli plik wejściowy nie istnieje lub plik wyjściowy nie może być utworzony? Co zrobić, jeśli plik wynikowy już istnieje: czy należy go nadpisać, zadać pytanie użyt- kownikowi („Zamazać wynik całego roku pracy [t]ak, [n]ie?”), czy wypi- sać komunikat o błędzie i zatrzymać działanie? Co z obsługą wielu plików jednocześnie lub z łączeniem plików w jedną całość? Co z głodem na świecie i efektem cieplarnianym? To wszystko są z pewnością bardzo ważne pytania, lecz dotyczą ergonomii aplikacji, nie przetwarzania danych. Jeśli jednak istnieje prawdopodobień- stwo, że pisany program będzie wykorzystywany przez nieznane nam osoby 20 Przetwarzanie danych dla programistów w czasie naszej nieobecności, warto poświęcić im przynajmniej kilka minut uwagi. A jeśli mamy za zadanie wykonanie jednorazowej operacji przefor- matowania pliku w starym formacie w taki sposób, aby mógł być wczytany przez nowy program, nie warto zaprzątać sobie głowy takimi detalami. 2.2. Przeformatowanie danych Wróćmy do problemu zmiany formatu zapisu definicji cząsteczek chemicz- nych na potrzeby wizualizacji 3D. Każda definicja cząsteczki jest zapisana w pliku PDB o następującej postaci: COMPND Ammonia AUTHOR DAVE WOODCOCK 97 10 31 ATOM 1 N 1 0.257 -0.363 0.000 ATOM 2 H 1 0.257 0.727 0.000 ATOM 3 H 1 0.771 -0.727 0.890 ATOM 4 H 1 0.771 -0.727 -0.890 TER 5 1 END W pierwszym wierszu definicji cząsteczki zapisana jest nazwa potoczna związku. Drugi wiersz zawiera nazwisko autora pliku i datę jego utworze- nia. Każdy wiersz rozpoczynający się od słowa kluczowego ATOM definiuje typ i położenie pojedynczego atomu. Nie wiadomo dokładnie, co oznaczają wiersze rozpoczynające się od słowa kluczowego TER ani do czego służy liczba 1 w czwartej kolumnie każdego wiersza ATOM, lecz w naszym przypad- ku nie ma to znaczenia. W pierwszym odruchu chciałoby się zacząć kodowanie od razu, lecz do- świadczenie2 uczy nas, że warto chwilę zastanowić się i rozważyć pewne założenia dotyczące formatu wejściowego. Na przykład: czy format PDF może zawierać puste wiersze? Czy wiersze COMPND i AUTHOR występują zaw- sze i to w takiej samej kolejności? Swoim początkującym studentom często powtarzam, że godzina ciężkiej pracy pozwoli zaoszczędzić sześćdziesiąt sekund szukania za pomocą Google. Wyszukiwanie hasła PDB format zwraca kilkadziesiąt adresów, w tym jeden 2 Doświadczenie to nazwa, jaką nadajemy naszym błędom — Oscar Wilde. Rozdział 2. (cid:129) Tekst 21 do oficjalnej specyfikacji3 napisanej pseudoprawniczym żargonem, który programiści chętnie stosują w przypadkach, gdy podejrzewają, że wśród odbiorców może znajdować się jakiś prawnik. Po chwili stwierdzamy, że pliki PDB mogą zawierać kilkadziesiąt różnych typów rekordów zorgani- zowanych w sekcje. Nam jednak potrzebne są tylko współrzędne atomów, zatem na razie możemy z powodzeniem zignorować wszelkie nierozpozna- walne przez nas dane. Zobaczymy, co z tego wyniknie. Jaś pyta... Czy tak wolno? Ignorowanie nierozpoznanych danych kojarzy się dość niebezpie- cznie. Co się stanie, jeśli atomy zostaną zdefiniowane w wierszach nierozpoczynających się słowem kluczowym ATOM? Co się stanie, jeśli ignorowane rekordy zmodyfikują znaczenie rekordów ATOM? Czy nie należy przestudiować specyfikacji z zakreślaczem w ręku, a program napisać po upewnieniu się co do słuszności decyzji? W tym przypadku odpowiedź brzmi „nie”. Czytanie specyfikacji formatu PDB zajęłoby więcej czasu, niż ręczne przekształcenie formatów. Oczywiście dogłębna znajomość specyfikacji może przyczynić się do uniknięcia błędów, lecz koszt takich błędów jest bliski zeru. Tego typu decyzja oczywiście byłaby nieodpowie- dzialna, jeśli mielibyśmy do czynienia z formatem danych karto- teki pacjentów szpitala lub dokumentacji silników odrzutowych samolotów pasażerskich, lecz w tym przypadku jest to podejście jak najbardziej praktyczne. Zadanie realizujemy w jak najprostszy sposób i poprawiamy później, jeśli wystąpią błędy. W tym przy- padku jednak kluczowe jest, aby dokładnie znać format wyjściowy, aby natychmiast zauważyć wszelkie błędy. Przyjrzyjmy się zatem formatowi wyjściowemu: -- atom azotu 1 17 0.5 0.257 -0.363 0.000 3 http://www.rcsb.org/pdb/docs/format/pdbguide2.2/guide2.2_frame.html 22 Przetwarzanie danych dla programistów -- atomy wodoru 1 6 0.2 0.257 0.727 0.000 1 6 0.2 0.771 -0.727 0.890 1 6 0.2 0.771 -0.727 -0.890 Wiersze rozpoczynające się od dwóch myślników to oczywiście komentarz, można zatem założyć, że możemy w ich charakterze wykorzystać dowolne informacje lub zupełnie je pominąć. Pierwsza kolumna o wartości 1 ozna- cza kulę, następnie występuje kod koloru, średnica atomu oraz współrzędne XYZ. Na początek wiadomo, że do tłumaczenia symboli atomów (w przykładzie N i H) z pliku PDB na pierwsze trzy kolumny formatu VU3 potrzebna będzie tablica przeglądowa. Na razie jednak odłóżmy ten problem na bok i skupmy się na przekształceniu współrzędnych XYZ z pliku PDB. Ogólny schemat działania algorytmu będzie następujący: dla każdego pliku PDB: odczyt atomów z pliku ustalenie nazwy pliku wynikowego zapis danych atomów i innych danych w pliku wynikowym W Pythonie zakodujemy to następująco: import sys for inputName in sys.argv[1:]: atoms = readPdb(inputName) outputName = translateName(inputName) writeVu3(outputName, atoms) Odczyt atomów z pliku PDB to dość proste zadanie: wystarczy wyłowić wiersze rozpoczynające się słowem kluczowym ATOM i podzielić je na indy- widualne pola. Trzecie pole informuje o typie atomu; piąte, szóste i siódme zawiera współrzędne XYZ. Listy Pythona są indeksowane od zera (po- dobnie, jak tablice w C i Javie), więc musimy odczytać pola o indeksach 2 i 4 odpowiednio dla pól 3. i 5. def readPdb(inputName): input = open(inputName, r ) result = [] for line in input: if line[:4] == ATOM : fields = line.split() atom = fields[2] + fields[4:7] result.append(atom) input.close() return result Rozdział 2. (cid:129) Tekst 23 Wyrażenie line.split() dokonuje podziału wiersza na pola. Jako separator pól możemy podać dowolny ciąg znaków, na przykład w celu wykorzystania średnika jako separatora należy zastosować wyrażenie line.split( ; ). Domyślnie jako separator stosowany jest dowolny ciąg białych znaków, co dokładnie odpowiada naszym potrzebom w tym przypadku. Nie zadajemy sobie trudu sprawdzania poprawności składowej danych wejściowych. Jeśli rekord ATOM będzie zawierał mniejszą od oczekiwanej liczbę pól, wyrażenie fields[2] + fields[4:7] wywoła wyjątek przekrocze- nia zakresu. Nie jest to wielki problem, ponieważ w tej postaci kodu spo- woduje to wypisanie komunikatu, stosu wywołań oraz zatrzymanie działania programu. W przypadku produktu przeznaczonego dla użytkowników końcowych takie zachowanie programu raczej nie byłoby wskazane, lecz w przypadku prostego narzędzia do przetwarzania danych jest jak najbar- dziej do przyjęcia. Zanim przejdziemy dalej, zastanówmy się, co ta prosta funkcja ma rze- czywiście „do zrobienia”. Jednym ze sposobów sprawdzenia tego jest uru- chomienie kodu w debugerze i śledzenie zawartości listy atoms zwracanej przez funkcję readPdb(). Inny sposób polega na zmodyfikowaniu głównej pętli w taki sposób, aby na bieżąco wypisywała na ekranie listę atomów: for inputName in sys.argv[1:]: atoms = readPdb(inputName) for a in atoms: print a outputName = translateName(inputName) writeVu3(outputName, atoms) Uruchommy ten kod z plikiem ammonia.pdb: Traceback (most recent call last): File pdb2vu3.py , line 15, in ? atoms = readPdb(inputName) File pdb2vu3.py , line 7, in readPdb atom = fields[2] + fields[4:7] TypeError: cannot concatenate str and list objects Błąd: wyrażenie fields[2] wybiera z listy pojedynczy ciąg znaków, nato- miast fields[4:7] wybiera podlistę, a Python nie wie, co w rzeczywistości chcemy zrobić, „dodając” do siebie ciąg znaków i listę. W każdym języku programowania występują tego typu „przypadki specjalne”, gdy różne użyteczne koncepcje nie pasują do siebie wzajemnie. Jednym z powodów, 24 Przetwarzanie danych dla programistów dla których języki Python, Ruby czy Java zdobywają stopniowo przewagę nad językami Perl czy C++ jest to, że w tych pierwszych, dzięki jasno zdefiniowanym regułom, ilość tego typu niejednoznaczności jest znacznie zmniejszona. Sytuację można naprawić, na przykład opakowując ciąg znaków w listę jednoelementową ([]): def readPdb(inputName): input = open(inputName, r ) result = [] for line in input: if line[:4] == ATOM : fields = line.split() atom = [fields[2]] + fields[4:7] result.append(atom) input.close() return result Tym razem wynik będzie następujący: [ N , 0.257 , -0.363 , 0.000 ] [ H , 0.257 , 0.727 , 0.000 ] [ H , 0.771 , -0.727 , 0.890 ] [ H , 0.771 , -0.727 , -0.890 ] Ten przykład nie miał na celu pokazać skutku tego banalnego (aczkolwiek dość często popełnianego) błędu; chodziło mi o to, aby pokazać konieczność testowania napisanego kodu przed przejściem do kolejnego etapu prac. Podział pracy na etapy wczytywania danych, przetwarzania i zapisu w prze- twarzaniu danych jest przydatny między innymi właśnie do tego typu przy- rostowego testowania. Następny etap polega na określeniu nazwy pliku wynikowego. W tym przypadku reguła jest prosta: należy zastąpić rozszerzenie .pdb rozszerze- niem .vu3: def translateName(inputName): return inputName[ :-4] + .vu3 Już słyszę okrzyki purystów Pythona: właściwy sposób wydobycia rozsze- rzenia z nazwy pliku polega na zastosowaniu funkcji os.path.splitext(). Jednakże ten przykładowy kod piszę dla własnego użytku, jestem pewny, że użyję go tylko kilka razy w życiu i gdy odkryję, że wystąpił problem z danymi, mogę go usunąć i uruchomić skrypt jeszcze raz, a przede wszyst- kim nie chcę odstraszać mniej doświadczonych Czytelników, oszałamiając Rozdział 2. (cid:129) Tekst 25 ich nadmierną liczbą bibliotek, których nigdy wcześniej nie spotkali. Dlatego zdecydowałem, że w tym konkretnym przypadku zadanie nieco uproszczę. Może się wydać, że nareszcie nadszedł czas, aby zapisać plik VU3. Jed- nakże jeszcze nie wiadomo, w jaki sposób przekształcić symbole atomowe formatu PDB na kod kształtu, koloru i średnicy, typowe dla formatu VU3. Najprostszy sposób polega po prostu na zakodowaniu w programie tablicy przeglądowej. Jeśli program napotka symbol atomu, którego nie znajdzie w tej tablicy, jego działanie zakończy się błędem, możemy jednak szybko uzupełnić tablicę o brakujące wpisy i ponownie uruchomić program. Taka decyzja jest do przyjęcia. Mamy więc: Lookup = { H : (1, 6, 0.2), N : (1, 17, 0.5) } def writeVu3(outputName, atoms): output = open(outputName, w ) for (symbol, X, Y, Z) in atoms: if symbol not in Lookup: print sys.stderr, Nieznany symbol atomu s symbol sys.exit(1) shape, color, radius = Lookup[symbol] print output, shape, color, radius, X, Y, Z output.close() Tablice przeglądowe są prawie zawsze o wiele czytelniejsze od długich serii warunków if…then…else. Jednym z powodów, dla których zręczne języki, do jakich zalicza się Python, są tak użyteczne, jest fakt, że dużo informacji i logiki aplikacji można w nich zapisać w postaci struktury danych, w przeci- wieństwie do bardziej sztywnych języków, do których zalicza się na przy- kład Java. W tym momencie możemy przekształcić pierwszy plik z formatu PDB do formatu VU3. Czy uda się przekształcić kolejny? Przejdźmy nieco dalej w kolejce plików i spróbujmy definicji cząsteczki mentolu, która składa się z trzydziestu jeden atomów. Prawie natychmiast program wyrzuci nastę- pujący komunikat: Nieznany symbol atomu C 26 Przetwarzanie danych dla programistów Dobrze, właśnie tego się spodziewaliśmy. Po wprowadzeniu poprawek w kodzie i uzupełnieniu tablicy przeglądowej o definicje atomów węgla i tlenu (które również występują w mentolu) nasz program bez dalszych problemów wygeneruje odpowiedni plik VU3. Najwyższy czas na ostateczny test. Po skopiowaniu wszystkich 112 plików PDB do jednego katalogu uruchamiamy następujące polecenie: $ python pdb2vu3.py *.pdb Potrzebujemy czterech podejść, aby uzupełnić wszystkie brakujące pier- wiastki (siarka, chlor, żelazo i brom). Przy okazji okazuje się, że symbole atomów mogą być zapisywane wielkimi literami, np. CL, jak i za pomocą kombinacji wielkich i małych liter, np. Cl. Tego typu niespójności są na porządku dziennym w zadaniach przetwarzania danych, ponieważ dla człowieka nie stanowią problemu, są rozumiane intuicyjnie. Jednak program musi być odpowiednio zakodowany, aby był w stanie radzić sobie z nimi w sposób właściwy. Mamy dwa wyjścia: albo dopisać do tablicy przeglądowej odpowiednie wpisy reprezentujące każdą z możliwych pisowni symbolu pierwiastka, albo znormalizować symbole przed odczytem z tablicy przeglądowej. Pierwszy sposób doprowadzi nas do tablicy o następującej postaci: Lookup = { BR (1, 2, 0.9), Br (1, 2, 0.9), C (1, 3, 0.5), CL (1, 8, 0.6), Cl (1, 8, 0.6), FE (1, 13, 1.1), Fe (1, 13, 1.1), H (1, 6, 0.2), N (1, 17, 0.5), O (1, 19, 0.5), S (1, 17, 0.7) } To jest dobra opcja w tej konkretnej sytuacji: liczba zduplikowanych wierszy jest niewielka, zadanie można sobie uprościć przez kopiowanie i wklejanie istniejących wierszy i modyfikację symbolu. A jeśli jakaś wersja pisowni zostanie pominięta, program się o to upomni. Rozdział 2. (cid:129) Tekst 27 DRY Jedną z ogólnych zasad programowania określa się akronimem DRY: ang. Don’t Repeat Yourself (nie powtarzaj się) [HT00]. Jeśli informacja zostanie powielona w dwóch miejscach lub ich większej liczbie, prędzej czy później zapomni się uzupełnić jedną z tych kopii, co doprowadzi do błędu trudnego do wykrycia, ponieważ programista będzie przekonany, że „przecież już to poprawił”. Fakt, że programy do przetwarzania danych bardzo często z założenia służą rozwiązaniu jednorazowego problemu, nie powinien być wymówką dla niedbałego programowania. Doświadczenie uczy bowiem, że jednorazowy kod często przydaje się wielokrotnie, a złe nawyki nabyte przy okazji rozwiązań prowizorycznych pozo- stają na stałe i ujawniają się również przy tworzeniu bardziej od- powiedzialnego kodu. Co się jednak stanie, gdy symbole pierwiastków będą w plikach źródłowych występowały we wszystkich możliwych kombinacjach wielkich i małych liter? Żelazo można zapisać jako FE, Fe, fE i fe. Wszystkie symbole jednoliterowe miałyby w pliku po dwa wpisy, natomiast symbole dwuliterowe aż po cztery. Wydaje się dość mało prawdopodobne, że ktokolwiek celowo zapisał symbol żelaza jako fE. Jeśli jednak dane są wprowadzane ręcznie, jest to zupełnie możliwe w wyniku przypadkowego wciśnięcia klawisza Caps Lock lub innej omyłki4. Co się jednak stanie, gdy zdecydujemy się zmienić kolor lub średnicę kul reprezentujących atomy określonych pierwiastków? Jeśli w tabeli będziemy mieli cztery wpisy dotyczące żelaza, musimy pamiętać o tym, aby zmienić wszystkie cztery. Jeśli pominęlibyśmy jeden z nich, nie miałoby to większego znaczenia, lecz w przypadku tysięcy plików zawierających kilkadziesiąt róż- nych pierwiastków istnieje wysokie prawdopodobieństwo, że w końcowym rozrachunku mielibyśmy na różnych prezentacjach odmienne rozmiary i kolory kul reprezentujących atomy tego samego pierwiastka. 4 I winę za takie sytuacje nie zawsze ponosi ludzkie zmęczenie. Użytkownicy „inteligentnych” edytorów tekstu niejednokrotnie padają ofiarą opcji Poprawiaj dwa początkowe wersaliki przekształcającej na przykład skrót PL na Pl. 28 Przetwarzanie danych dla programistów To sprowadza nas do drugiej z dostępnych opcji: normalizacji symboli atomów. Jeśli zdecydujemy, że symbole muszą zawsze mieć poprawną po- stać (pierwsza litera wielka, druga mała) niezależnie od tego, w jaki sposób były zapisane w oryginalnym pliku, nasza tabela przeglądowa zawierać będzie po jednym wpisie dla każdego atomu. W takim przypadku warto jednak dopisać komentarz, że przetwarzane w programie nazwy atomów nie muszą odpowiadać temu, co jest odczytywane z plików. Taki komentarz to dodatkowe dziesięć sekund pracy, które mogą oszczędzić wielu minut poszukiwań przyczyny problemu w przyszłości, gdy przyjdzie nam poprawić spostrzeżony błąd w danych wyjściowych. Pozostał jeszcze jeden wybór. Czy symbole pierwiastków powinny być normalizowane przy odczycie danych z pliku PDB, czy też lepiej wykonać dodatkowy przebieg po liście atomów wczytanych z pliku zamieniający ich symbole w tej liście? Aby każdy z etapów działania algorytmu był jak naj- bardziej czytelny i zwarty, lepiej jest zdecydować się na drugą opcję. W ten sposób główna pętla programu przyjmie następująca postać: for inputName in sys.argv[1:]: atoms = readPdb(inputName) normalizeSymbols(atoms) outputName = translateName(inputName) writeVu3(outputName, atoms) Nowa funkcja normalizeSymbols() będzie wyglądać tak: def normalizeSymbols(atoms): for record in atoms: record[0] = record[0].capitalize() Jak pamiętamy, każdy element listy atoms jest listą złożoną z podciągów wczytanej wcześniej definicji atomu w cząsteczce (zapisanej w pojedynczym wierszu pliku wejściowego). Jeśli wiersz miał poprawny format, nazwa atomu znalazła się w elemencie o indeksie zero. Metoda capitalize() obiektu tek- stowego zwraca jego kopię z pierwszą literą zamienianą na wielką i pozosta- łymi zamienionymi na małe, na przykład ciąg aBC zostanie zamieniony na Abc. Muszę coś wyznać. Gdy pisałem przedstawiony tutaj kod, nie przyszło mi nawet do głowy, aby duplikować wiersze w tabeli przeglądowej. Gdy się przez wiele lat spotyka podobne problemy, normalizacja danych staje się Rozdział 2. (cid:129) Tekst 29 nawykiem, podobnie jak logiczny podział operacji przetwarzania na osob- ne etapy. Nawyki tego typu zapewne nie w każdej sytuacji prowadzą do optymalnego kodu, lecz dzięki nim nie muszę każdego przypadku rozpa- trywać w zupełnym oderwaniu od innych. 2.3. Obsługa rekordów wielowierszowych Znamy już sposób przetwarzania plików po jednym wierszu, zdarza się jednak spotykać pliki, w których rekordy mogą zajmować większą liczbę wierszy. Aby nieco urealnić nasz kod, zajmijmy się przetwarzaniem plików .ini, typowych dla starszych wersji systemu Windows, w których zapisywało się ustawienia konfiguracyjne. Przekształćmy tego typu pliki .ini na pliki XML. Z tego typu zadaniem spotkałem się kilka lat temu, gdy firma, w której pracowałem, została zaangażowana do wsparcia w przejściu ze starego programu CAD do nowej wersji, z założeniem, że ustawienia użyt- kowników miały być przeniesione do tego nowego systemu. Jak wiele nieustandaryzowanych formatów, pliki konfiguracyjne systemu Windows posiadają własną składnię, która z czasem stawała się coraz bardziej skomplikowana. Nie musimy obsługiwać wszystkich detali i dzi- wactw, skupimy się na następujących, podstawowych zagadnieniach: t Plik .ini zawiera zero lub większą liczbę sekcji. t Każda sekcja posiada tytuł i treść, treść może być pusta. t Tytuł składa się z wiersza zawierającego tekst ujęty w nawiasy kwadratowe, np. [laser6] czy [recently used]. Żadna z sekcji nie może wystąpić w jednym pliku więcej, niż jeden raz. t Treść zawiera zero lub większą liczbę właściwości. Każda właściwość składa się z klucza i wartości oddzielonych znakiem równości, np. color=blue czy file3=C:ookintro.pml. t Komentarze rozpoczynają się w dowolnym miejscu wiersza od znaku # i obowiązują do końca wiersza. 30 Przetwarzanie danych dla programistów Typowy plik .ini ma następującą postać: # Ustawienia instalacyjne [Bootstrap] Location=$SYSUSERCONFIG/sversion.ini BaseInstallation=$ORIGIN/.. buildid=645m44(Build:8784) InstallMode=STANDALONE ALL_USERS ProductPatch= # pusta # Obsługa błędów [ErrorReport] ErrorReportPort=80 ErrorReportServer=services.caribou.org Na razie nie będziemy zajmować się specjalnym znaczeniem wartości roz- poczynających się od znaku $ i skupimy się na odczytywaniu pliku i prze- kształcaniu do postaci: configure section title= Bootstrap entry key= Location $ SYSUSERCONFIG/sversion.ini /entry entry key= BaseInstallation $ORIGIN/.. /entry entry key= buildid 645m44(Build:8784) /entry entry key= InstallMode STANDALONE amp;ALL_USERS /entry entry key= ProductPatch /entry /section section title= ErrorReport entry key= ErrorReportPort 80 /entry entry key= ErrorReportServer services.caribou.org /entry /section /configure Odczyt pliku w formacie .ini jest trudniejszy od odczytu pliku PDB, po- nieważ tam mieliśmy zagwarantowane, że każdy rekord mieścił się w jednym wierszu. W tym przypadku tak nie jest. Najprostsze podejście do tego problemu polega na odfiltrowaniu podczas odczytu wszystkich elementów pliku, które nie są poddawane przekształceniu, przekształceniu tego, co zostanie, i zapisaniu wyniku w pliku XML. Oczywiście należy również przekształcić znaki , i odpowiednio w amp;, lt; i gt;, co jest wyma- gane przez format XML. Zaczniemy od zwyczajowego szablonu program przetwarzającego: for inputName in sys.argv[1:]: lines = readIni(inputName) settings = process(lines) outputName = translateName(inputName) writeXml(outputName, settings) Rozdział 2. (cid:129) Tekst 31 Funkcja readIni() nie polega na zwykłym wczytaniu wierszy tekstu z pliku .ini, do jej zadań należy też oczyszczenie danych z komentarzy i pustych wierszy. Najprostszy sposób realizacji tego zadania polega na odrzuceniu komentarza (o ile istnieje) i usunięciu białych znaków na początku i końcu pozostałego wiersza. Jeśli wynik takiej obróbki jest pustym ciągiem znaków, po prostu go odrzucamy. W przeciwnym wypadku dopisujemy go na końcu listy wierszy, które będą zwrócone jako wynik tej funkcji: def readIni(inputName): input = open(inputName, r ) result = [] for line in input: # Usunięcie części wiersza od znaku # do końca first = line.find( # ) if first = 0: line = line[:first] # Oczyszczenie tekstu z okalających białych znaków line = line.strip() # Jeśli nic nie zostało, pomijamy wiersz if not line: continue # W przeciwnym wypadku zapisujemy to, co zostało result.append(line) # Koniec pracy input.close() return result To dość proste. Mamy jednak do czynienia z sytuacją potencjalnego błędu w przypadku, gdy dopuszczamy występowanie znaku # w wartościach atry- butów. Należy bowiem odpowiedzieć sobie na pytanie, czy w naszych plikach .ini dopuszczalne są wartości następującej postaci: SongTitle= Love Potion #9 # ostatni odtwarzany utwór Jeśli taki zapis jest poprawny, nasz algorytm zwróci błędną wartość, ponie- waż odrzuca wszystkie znaki od znaku # do końca wiersza. Co gorsza, ten błąd wystąpi w sposób niezauważony — zamiast wywołać wyjątek, kod odrzuci w pełni poprawne dane. 32 Przetwarzanie danych dla programistów Opisany problem można rozwiązać, wyszukując w wierszach znaki cudzy- słowów i inne znaczniki specjalne. Zadanie znacznie uprościłyby wyrażenia regularne, które omówię w rozdziale 3., a na razie przejdę do następnego zadania naszego kodu: wygenerowania pliku XML zawierającego oczysz- czone definicje z pliku .ini. Krótkie przypomnienie: głównym blokiem w naszym pliku XML będzie configure i /configure . Za każdym razem, gdy w pliku napotkamy sekcję [nazwa], w pliku wynikowym musi znaleźć się zapis section title= nazwa . Oczywiście przed otwarciem nowej sekcji należy zamknąć poprzednią: /section . Ponadto każdy atrybut postaci nazwa=wartość musi być odzwier- ciedlony w wyniku jako entry key= nazwa wartość /entry . Nie ma problemu, kod realizujący te funkcje jest następujący: def process(lines): result = [ configure ] for line in lines: # Początek nowej sekcji if line[0] == [ : # Zamknięcie poprzedniej sekcji result.append( /section ) # Początek nowej sekcji title = line[1:-1] result.append( section title= s title) # Wpis w bieżącej sekcji else: key, value = line.split( = , 1) value = escape(value) result.append( entry key= s s /entry (key, value)) # Gotowe result.append( /configure ) return result Wywołanie line.split( = , 1) powoduje rozłożenie zmiennej line na elementy z zastosowaniem znaku równości w charakterze separatora. Funkcja escape() zastępuje znaki specjalne dla formatu XML na odpo- wiadające im kody XML: def escape(s): return s.replace( , amp; ).replace( , lt; ).replace( , gt; ).replace( , apos; ).replace( , quot; ) Czy ten program jest już poprawny? Nie. Popełniłem dwa błędy i propo- nuję przyjrzeć się mu jeszcze raz. A jeszcze lepiej: proponuję wykonać go z następującym, testowym plikiem .init: Rozdział 2. (cid:129) Tekst 33 # Ustawienia instalacyjne [Bootstrap] ProductKey=Caribou CAD 1.1 Location=$SYSUSERCONFIG/sversion.ini # Obsługa błędów [ErrorReport] ErrorReportPort=80 W wyniku funkcji process() powstanie następujący plik: configure /section section title= Bootstrap entry key= ProductKey Caribou CAD 1.1 /entry entry key= Location $SYSUSERCONFIG/sversion.ini /entry /section section title= ErrorReport entry key= ErrorReportPort 80 /entry /configure W tym pliku znalazły się dwa błędy. Po pierwsze, znacznik zamykający /section pojawił się przed znacznikiem otwierającym section title= Boot åstrap , ponieważ znacznik zamykający wypisujemy zawsze, nawet przed pierwszą sekcją w pliku. Po drugie, nie zamknęliśmy ostatniej sekcji w pliku, jak również nie zapisaliśmy znacznika kończącego konfigurację. Pierwszy błąd naprawimy, wykorzystując znacznik boolowski zawierający informację o tym, czy przetwarzana sekcja jest pierwsza w pliku. Rozwią- zanie drugiego błędu polega na tym, że zamykający znacznik /section jest zapisywany zawsze przed zamykającym znacznikiem /configure . Spowo- duje to, że w przypadku próby przekształcenia pustego pliku .ini powstanie następujący plik wynikowy: configure /section /configure Zamykający znacznik /section powinien być zapisywany wyłącznie w przy- padku, gdy program przetworzył przynajmniej jedną sekcję. Do tego celu wykorzystamy kolejny znacznik boolowski. Inne rozwiązanie mogłoby pole- gać na zastąpieniu licznikiem wystąpień pierwszego z pomocniczych znaczni- ków boolowskich. Jeśli licznik jest równy zeru i znajdujemy się w pętli, oznacza to, że nie należy wypisywać zamykających znaczników /section . Jeśli licznik jest różny od zera i znajdujemy się poza pętlą, należy wypisać ten znacznik. Oto ostateczna postać naszej funkcji: 34 Przetwarzanie danych dla programistów def process(lines): result = [ configure ] count = 0 for line in lines: # Początek nowej sekcji if line[0] == [ : # Zamknięcie poprzedniej sekcji if count 0: result.append( /section ) # Początek nowej sekcji title = line[1:-1] result.append( section title= s title) count += 1 # Wpis w bieżącej sekcji else: key, value = line.split( = , 1) value = escape(value) result.append( entry key= s s /entry (key, value)) # Gotowe if count 0: result.append( /section ) result.append( /configure ) return result Ostatnie brakujące dwie funkcje naszego programu są raczej oczywiste: def translateName(inputName): return inputName[:-4] + .xml def writeXml(outputName, settings): output = open(outputName, w ) for line in settings: print output, line output.close() Wystarczyło kilka prostych testów, aby przekonać się, że zaimplemento- wane funkcje realizują poprawnie swoje zadania, zatem uznałem program za ukończony. Przykładowe błędy w funkcji process() są bardzo reprezentatywne dla tej klasy problemów, jako że błędy w przetwarzaniu danych pojawiają się naj- częściej na początku i końcu procesu. Dlatego podczas sprawdzania popraw- ności kodu przetwarzającego dane, warto zastosować następujące dane testowe: t puste dane wejściowe (o ile przetwarzany format na to zezwala); t pojedynczy rekord; Rozdział 2. (cid:129) Tekst 35 Znaczniki ograniczające i automaty skończone Ograniczanie bloków tekstu określonymi znacznikami początku i końca należy do bardzo powszechnych technik w informatyce. Obsługa tego typu formatów danych polega na zastosowaniu następującego algorytmu: for (dla każdego rekordu wejściowego) if (rekord jest znacznikiem początku sekcji) if (nie pierwsza sekcja) zamknij poprzednią sekcję zacznij nową sekcję else utwórz rekord wyjściowy if (utworzona jakakolwiek sekcja) zamknij sekcję główną Jeśli przetwarzany tekst może być wczytany w całości do pamięci, można zastosować następującą uproszczoną postać: for (dla każdej sekcji) rozpocznij nową sekcję for (dla każdego rekordu wejściowego w sekcji) utwórz rekord wyjściowy zakończ sekcję Drugi z algorytmów upraszcza logikę przetwarzania, program napisany w ten sposób łatwiej jest zrozumieć i usuwać jego błędy, wymaga jednak zastosowania bardziej skomplikowanych struktur danych (mamy w tym przypadku do czynienia z listą list zamiast jednej, płaskiej listy). Zadania związane z przetwarzaniem danych z reguły wiążą się z koniecznością podejmowania kompromisów pomiędzy poziomem komplikacji danych a poziomem komplikacji kodu. Dobrzy programiści wykorzystują w takich zastosowaniach technikę noszącą ogólną nazwę automatów skończonych (lub automatów o skończonej liczbie stanów). Automaty skończone wybiegają poza tematykę tej książki, zainteresowani znajdą bardzo czytelne wpro- wadzenie do tego zagadnienia w pozycji [HF04]. t dwa rekordy (to znaczy mamy tu do czynienia wyłącznie z pierwszym i ostatnim rekordem, nie ma rekordów „środkowych”); t trzy rekordy lub ich większa liczba. 36 Przetwarzanie danych dla programistów Jeśli zasady rządzące przetwarzanymi danymi są proste, dane testowe można przygotować, wykorzystując rzeczywiste dane. Jeśli przetwarzane dane są bardziej skomplikowane, najczęściej najprościej jest przygotować dane testowe samodzielnie. 2.4. Testowanie kolizji Zadowolony z siebie przesłałem ten program do szefa. Kilka minut później otrzymałem odpowiedź: „Nie działa, zapraszam do siebie”. Zrozumienie przyczyny błędu zajęło poniżej minuty. Stary program CAD zezwalał na to, aby w plikach .ini te same klucze występowały wielokrotnie, na przykład: [View] WindowSize=1024,768 BackgroundColor=green7 WindowSize=1280,1024 Nowy program CAD zezwalał natomiast, aby każda wartość występowała w jednej sekcji tylko raz. W przypadku, gdy w pliku XML w jednej sekcji wystąpiło kilka wartości tego samego klucza, program nie uruchamiał się. Szybkie śledztwo w kilku różnych plikach .ini potwierdziło, że wartości atrybutów pomiędzy sekcjami, a nawet w ramach sekcji, nie muszą być unikalne. Na przykład następująca zawartość pliku .ini jest zupełnie legalna: [View] WindowSize=1024,768 BackgroundColor=green7 WindowSize=1280,1024 [Print] BackgroundColor=green5 To doskonałe pole do popisu dla słowników. Słowniki Jeśli przetwarzane dane muszą być w jakiś sposób unikalne, najczęściej okazuje się, że najprostszym rozwiązaniem jest wykorzystanie słownika. W zależności od języka programowania słowniki noszą nazwę odwzorowań Rozdział 2. (cid:129) Tekst 37 (ang. map, na przykład w Javie), haszy (ang. hash, np. Perl) albo tablic asocjacyjnych lub skojarzeniowych. Niezależnie od nazwy, słownik działa jak tabela dwukolumnowa, gdzie w lewej kolumnie wpisywane są klucze, a w prawej skojarzone z nimi wartości. Doskonałym przykładem słownika może być tabela cen, w której kodom produktów (kluczom) przyporząd- kowane są ich ceny (wartości): ANW-400 179.95 ANW-407 179.95 ANW-460 209.95 Słowniki mają następujące, bardzo ważne cechy: t Każdy klucz może wystąpić w słowniku tylko jeden raz. Pojedynczy słownik nie może zawierać na przykład trzech pozycji o kluczu ANW-400. Jeśli jedna pozycja w słowniku musi zawierać większą liczbę informacji, najczęściej w wartości umieszcza się listę (lub zbiór) wartości. t Klucze nie posiadają ustalonej kolejności. Powyższa tabela przedstawia klucze w kolejności alfabetycznej, lecz fizyczna kolejność kluczy w słowniku może być odwrotna lub zupełnie dowolna. Każdy dobry podręcznik na temat struktur danych (jak [Sed97]) wyjaśni dokładnie przyczynę takiego stanu rzeczy. W tym miejscu wystarczy pamiętać, że tak właśnie jest, i unikać założenia o ustalonej kolejności kluczy. t Wyszukiwanie w słowniku jest szybkie. Ta cecha jest największą zaletą słowników i głównym powodem ich stosowania w miejsce na przykład list par wartości. Zamiast sprawdzać wszystkie wartości klucza (co oznacza N porównań dla słownika o liczbie kluczy równej N), słownik przeszukuje klucze w czasie prawie niezależnym od rozmiaru5. W przypadku, gdy słownik zawiera kilkanaście elementów, różnica w stosunku do przeszukania zwykłej listy może być niezauważalna, ale może mieć zasadnicze znaczenie przy słownikach o rozmiarze milionów kluczy. 5 Rzeczywisty czas wyszukiwania jest uzależniony od tego, jak bardzo klucze różnią się od siebie, co z kolei ma wpływ na potencjalne wystąpienie kolizji. Szczegóły można znaleźć w [Sed97]. 38 Przetwarzanie danych dla programistów Warto ponadto zauważyć, że klucze nie muszą być liczbami całkowitymi, jak indeksy list, mogą być na przykład ciągami znaków lub obiektami. W prakty- ce większość słowników wykorzystuje klucze w postaci ciągów znaków, lecz można stosować liczby całkowite, współrzędne XY, wskaźniki funkcji — wybór jest bardzo szeroki. Załóżmy więc, że mamy listę nieunikalnych adresów e-mail i chcemy zliczyć, ile razy każdy z tych adresów powtarza się na liście. Lista adresów może pochodzić na przykład z listy dyskusyjnej, a taka funkcja pozwoli nam określić najbardziej aktywnych uczestników. Oto przykład tego typu listy: see@spot.run.com see@spot.run.com jane@up-the-hill.org see@spot.run.com jane@up-the-hill.org purple.dinosaur@bad.tv jane@up-the-hill.org A oto przykładowy program, który realizuje nasze zadanie: Line 1 import sys - - count = {} - for address in sys.stdin: 5 address = address.rstrip() - if address not in count: - count[address] = 1 - else: - count[address] += 1 10 - addresses = count.keys() - addresses.sort() - for address in addresses: - print address, count[address] Przyjrzyjmy się temu programowi nieco bliżej. W wierszu 3. tworzony jest pusty słownik i przypisany zmiennej count. Pętla rozpoczynająca się w wier- szu 4. odczytuje adresy e-mail po jednym, w wierszu 5. następuje oczyszcze- nie białych znaków (to znaczy sekwencji znaków końca wiersza odpowied- nich dla różnych systemów operacyjnych, na przykład Unix i Windows). W wierszu 6. następuje sprawdzenie, czy dany adres był już odczytany. Jeśli nie, należy go dopisać do słownika z licznikiem równym 1. Jeśli pozycja występuje już w słowniku, należy zwiększyć o jeden wartość przypisanego jej licznika. Rozdział 2. (cid:129) Tekst 39 Druga część programu otrzymuje listę kluczy słownika zawierającą wszystkie odczytane adresy (wiersz 11.), sortuje je alfabetycznie (wiersz 12.), po czym wypisuje kolejno wraz z licznikiem. Program wywołuje się następująco: python freq.py email.txt Przy powyższym wywołaniu program zwróci następujący wynik: jane@up-the-hill.org 3 purple.dinosaur@bad.tv 1 see@spot.run.com 3 To samo zadanie możemy równie łatwo zrealizować w Javie (do zliczania adresów musimy wykorzystać obiekty klasy Integer, nie prymitywne warto- ści całkowite, ponieważ w Javie wartościami słowników mogą być wy- łącznie obiekty): import java.util.*; import java.io.*; class Freq { public static void main(String[] args) { BufferedReader input = new BufferedReader(new InputStreamReader(System.in)); Map m = new HashMap() ; String line; try { while ((line = input.readLine()) != null) { line = line.trim(); if (m.containsKey(line)) { Integer tmp = (Integer)m.get(line); m.put(line, new Integer(tmp.intValue() + 1)); } else { m.put(line, new Integer(1)); } } input.close(); } catch (IOException e) { System.err.println(e); } Set keySet = m.keySet(); List keyList = new LinkedList(keySet); Collections.sort(keyList); for (Iterator i=keyList.iterator() ; i.hasNext(); ) { String key = (String)i.next(); Integer value = (Integer)m.get(key); System.out.println(key + + value); } } } 40 Przetwarzanie danych dla programistów Program w Javie jest dwa i pół raza większy od programu w Pythonie i w przypadku plików o niewielkich rozmiarach będzie też działał wolniej6. Przed uruchomieniem musimy go skompilować, lecz oprócz tego wszyst- kiego jest prawie tak samo prosty… Powrót do plików konfiguracyjnych Wróćmy zatem do naszych plików konfiguracyjnych XML i zadbajmy o to, aby wartość każdego atrybutu w sekcji była ustawiona tylko jeden raz. Funk- cja wczytująca zawartość pliku .ini nie wymaga żadnych modyfikacji, podob- nie funkcja zastępująca znaki specjalne , i ich sekwencjami. Zmodyfi- kować musimy natomiast funkcję process(). Na początku każdej sekcji utworzymy pusty słownik. Jako że atrybuty są same w sobie kluczami i wartościami, możemy wykorzystać to w naszym słowniku. Jeśli dowolny klucz wystąpi w sekcji więcej, niż jeden raz, kolejne wystąpienia przesłonią poprzednie, co spowoduje, że na końcu będzie widoczna tylko ostatnio ustawiona wartość: def process(lines): result = [] section = None content = {} for line in lines: # Początek nowej sekcji if line[0] == [ : # Zapisanie starych wartości (jeśli są) if section: entry = [section, content] result.append(entry) # Początek nowej sekcji section = line[1:-1] content = {} 6 Java z reguły działa szybciej od Pythona, ponieważ w Javie typy zmiennych są kontrolowane na etapie kompilacji, natomiast w przypadku Pythona typ zmiennych musi być kontrolowany w trakcie wykonania. Maszyna wirtualna Javy ma jednak o wiele większe rozmiary od interpretera Pythona, podobnie jej biblioteki mają większe wymagania pamięciowe. To powoduje, że w przypadku przetwarzania plików o niewielkich rozmiarach czas niezbędny na załadowanie do pamięci całej maszyny wirtualnej sprawia, iż pomimo faktu, że Java jest szybsza w działaniu, program będzie wykonywał się dłużej. Rozdział 2. (cid:129) Tekst 41 # Dodaj do bieżącego słownika. else: key, value = line.split( = , 1) content[key] = escape(value) # Zakończ if section: entry = [section, content] result.append(entry) return result Ta funkcja ponownie musi wziąć pod uwagę przypadki specjalne na po- czątku i końcu przetwarzania. Mimo zmian, jej działanie nadal jest bardzo intuicyjne. Zwracany wynik jest listą par. Pierwszym elementem każdej pary jest tytuł sekcji, drugim natomiast słownik zawierający ostateczną wartość każdego atrybutu w tej sekcji. Zmieniliśmy format danych zwracanych z funkcji process(), musimy zatem zmienić też wykorzystującą je funkcję writeXml(): def writeXml(outputName, settings): output = open(outputName, w ) print output, configure for (section, content) in settings: print output, s section for key in content: value = content[key] print output, s s / s (key, value, key) print output, / s section print output, /configure output.close() Na koniec należy przetestować działanie kodu. Przede wszystkim należy sprawdzić go w tych danych, których porażkę poniosła pierwsza wersja programu. Na potrzeby testów przygotowałem więc specjalnie spreparowany plik .ini zawierający szczególnie ważne cechy: [Section1] Key=a Key=b [Section2] Key=c [Section3] Red=crimson Green=lime Red=vermilion Green=chartreuse [Section4] 42 Przetwarzanie danych dla programistów Wynik działania programu jest następujący: configure Section1 Key b /Key /Section1 Section2 Key c /Key /Section2 Section3 Green chartreuse /Green Red vermilion /Red /Section3 Section4 /Section4 /configure Jeszcze chwila… Przyjrzyjmy się sekcji Section3. W pliku .ini klucz Red wy- stąpił przed kluczem Green. W pliku .xml pojawił się później. Czy to błąd? Nie, to działanie zamierzone. Jak wspominałem wcześniej, klucze w słow- nikach nie mają uporządkowanej kolejności. Ta cecha słowników spowo- dowała, że Green pojawił się przed Red, nawet pomimo tego, że w danych wejściowych występował wcześniej. Czy to jest problem? To zależy wyłącznie od tego, czy znaczenie ma ko- lejność kluczy w sekcji, co z kolei zależy od programu CAD wykorzystują- cego tę konfigurację. Jeśli nie ma to znaczenia dla programu, nie warto się tym przejmować. Jeśli jednak ma to znaczenie, można zmodyfikować kod, na przykład zachowując kolejność kluczy atrybutów w dodatkowych słow- nikach, dla każdej sekcji z osobna. 2.5. Włączanie plików zewnętrznych Na szczęście w tym przypadku kolejność kluczy nie miała znaczenia. Pojawił się jednak inny problem. W trakcie konwersji plików .ini na format XML okazało się, że pliki .ini mogły odwoływać się do innych plików .ini, dzięki czemu część konfiguracji mogła być zdefiniowana w jednym, stałym miejscu. Na przykład jedna z grup inżynierów w firmie wykorzystywała plik .ini o następującej zawartości: Rozdział 2. (cid:129) Tekst 43 general.ini [View] WindowSize=1024,768 BackgroundColor=green7 WindowSize=1280,1024 Natomiast zawartość pliku general.ini była następująca: [Drawing] LineWidth=2 Corners=Rounded [File] DefaultName=$PROJECT.$VERSION DefaultTitle=off Niestety, nowy format XML nie uwzględniał tej możliwości: każdy plik musiał być samodzielną całością. W pierwszej kolejności należy oszacować skalę problemu. W firmie było zatrudnionych około osiemdziesięciu inżynierów, z czego tylko piętnastu wykorzystywało konfiguracje włączające pliki zewnętrzne. Żaden z przy- padków nie był wielokrotnie zagnieżdżony (to znaczy drugi plik nie zawierał włączenia kolejnego pliku). Pliki konfiguracyjne muszą być skonwertowane tylko raz, zdecydowałem więc, że po prostu ręcznie połączę te piętnaście plików .ini w całości i uruchomię procedurę przekształcającą. To zadanie zajęło około dwudziestu minut, z których większość spędziłem na poszukiwaniu administratora sieci w celu udostępnienia mi tych plików do odczytu. Gdyby plików do przetwarzania było około setki lub gdyby okazało się, że wykorzystuję wielokrotne, rekurencyjne włączanie, z pew- nością zdecydowałbym się zmodyfikować swój program ini2xml.py. Jak zawsze na początek zdecydowałbym, w którym miejscu skryptu muszę wprowadzić poprawki. Jednym ze sposobów może być napisanie kolejnej funkcji filtrującej, zastępującej zawartością pliku wszystkie wystąpienia in- strukcji włączającej plik zewnętrzny. Ta metoda zadziała jedynie w przy- padku, gdy nie mamy do czynienia z rekurencyjnym włączaniem, jeśli jednak byłoby inaczej, należy zastosować odpowiednią pętlę, na przykład: lines = readIni(filename) while containsIncludes(lines): index = findFirstInclude(lines) expansion = readIni(index) lines = insert(lines, index, expansion) 44 Przetwarzanie danych dla programistów To nie wygląda najgorzej, lecz wszyscy Czytelnicy, którzy mieli okazję prze- twarzać pliki tekstowe włączające inne pliki, z pewnością uśmiechną się z powątpiewaniem. Należy bowiem pamiętać o możliwości wystąpienia błędnej sytuacji samowłączenia pliku, na przykład (plik nosi nazwę selfinc- lusion.ini): [Foo] a = b selfinclusion.ini Po pierwszym przebiegu pętli program przetwarzający będzie zawierał następujące dane: [Foo] a = b [Foo] a = b selfinclusion.ini Po drugim przebiegu postać danych będzie następującą: [Foo] a = b [Foo] a = b [Foo] a = b selfinclusion.ini Przetwarzanie będzie odbywać się w nieskończoność, a raczej do momentu zapełnienia pamięci lub przerwania działania programu kombinacją Ctrl+C. Wystąpienie takiego przypadku w rzeczywistości wydaje się dość mało praw- dopodobne. W końcu, komu przyszłoby do głowy włączać plik w nim samym? Zupełnie prawdopodobny jest jednak tylko trochę bardziej skomplikowany przypadek, gdy plik A włącza plik B, który włącza C, który z kolei włącza na powrót plik A (rysunek 2.1). Taka sytuacja jest zupełnie powszechna w językach programowania C i C++, gdzie często zdarza się, że biblioteki standardowe są uzależnione wzajemnie od siebie. Standardowe rozwiązanie tego problemu wykorzystuje stos przetwarzanych aktualnie plików i wówczas gdy zostanie napotkany przypadek włączenia jednego z przetwarzanych plików, procedura jest przerywana. W naszym przypadku możemy to zaimplementować za pomocą rekurencji w funkcji Rozdział 2. (cid:129) Tekst 45 Rysunek 2.1. Cykliczne włączanie plików nagłówkowych readIni(). Wraz z nazwą włączanego pliku redIni() musi otrzymać listę (a dokładniej: stos) nazw aktualnie przetwarzanych plików. Gdy natrafi na instrukcję włączenia pliku, sprawdza, czy nazwa tego pliku nie znajduje się aktualnie na stosie. Jeśli nie, umieszcza tę nazwę na szczycie stosu, wywo- łuje się rekurencyjnie z tą nazwą pliku i zmodyfikowanym stosem. Wynik wywołania rekurencyjnego jest zapisywany na liście przetworzonych wierszy. Zmodyfikowany fragment skryptu znajduje się na poniższym listingu: def error(msg): print sys.stderr, msg sys.exit(1) def readIni(inputName, stack): input = open(inputName, r ) result = [] for line in input: # ten fragment pozostaje bez zmian line = line.strip() first = line.find( # ) if first = 0: line = line[:first] 46 Przetwarzanie danych dla programistów if (not line) or (line[0] == # ): continue # zwykły wiersz if line[0] != : result.append(line) # włączenie else: filename = line[1:-1] if filename in stack: error( Rekurencyjne włączenie pliku s: s (filename, repr(stack))) newStack = stack + [filename] inclusion = readIni(filename, newStack) result = result + inclusion return result Wywołanie funkcji readIni() w głównej części programu zmieniamy na następujące: lines = readIni(inputName, [inputName]) Czas na przetestowanie nowej wersji. Czy skrypt działa poprawnie w przy- padku plików .ini nie włączających innych plików? Czy działa poprawnie w przypadku włączenia pliku w samym sobie? Praktycznie natychmiast zwraca komunikat o błędzie i kończy działanie7. Co się stanie w przypadku, „plik A włącza plik B, który włącza plik C, który włącza plik A”? Przy- gotowanie odpowiedniego zestawu testowego zajmuje dosłownie chwilę, warto więc sprawdzić taki przypadek. Wszystko w porządku, również w tym przypadku program zachowuje się zgodnie z założeniami. Wnioski To ćwiczenie z przetwarzania danych tekstowych pozwala zdobyć sporo uniwersalnych doświadczeń związanych z przetwarzaniem danych. Po pierw- sze: nie można zbyt wcześnie uznać, że zadanie jest skończone. Pierwsze rozwiązanie problemu związanego z przetwarzaniem danych z reguły nie uwzględni kilku ważnych szczegółów, kluczowe jest zatem, aby kod pisać w sposób czytelny, nawet w przypadku gdy kod z założenia ma być jedno- razowego użytku. Warto też przechować taki kod w systemie kontroli wersji, aby móc odszukać go za jakiś czas, gdy mimo wszystko okaże się potrzebny. 7 W zależności od potrzeb, zamiast kończyć działanie z błędem, można po prostu pomijać plik włączany w sposób rekurencyjny. Rozdział 2. (cid:129) Tekst 47 Drugie spostrzeżenie dotyczy użyteczności programowalnych edytorów tekstu, jak Emacs czy Vim. W opisanej sytuacji edycji piętnastu plików (gdy włączałem w nich zawartość innych plików .ini) oczywiście nie wyko- nywałem tej czynności piętnaście razy. Zamiast ręcznej edycji zapisałem makro podczas edycji pierwszego pliku i wywołałem je czternaście razy (po czym zapisałem na wszelki wypadek). Gdybym miał do czynienia z przypadkiem rekurencyjnego włączania lub innych skomplikowanych struktur danych, zapewne nie poważyłbym się na ich obróbkę w edytorze tekstu8, lecz zdumiewająco wiele przypadków z życia udaje się sprowadzić do tak prostych rozwiązań. 2.6. Powłoka Uniksa Gdyby jakość produktu mierzyć czasem jego aktywnego użytkowania, po- włokę Uniksa9 należałoby uznać za najlepsze narzędzie do przetwarzania danych tekstowych w historii komputeryzacji. Powłoka Uniksa ma ponad trzydzieści pięć lat i jest nadal wykorzystywana przez wielu programistów jako ulubione narzędzie do przetwarzania informacji. Jak stwierdzili ich twórcy [KP99], języki powłoki zawdzięczają swoje możliwości filozofii „dużej liczby niewielkich, specjalizowanych narzędzi”. Zamiast bowiem oferować wielkie programy „do wszystkiego”, powłoka Uniksa daje do użytku wiele małych programików, które realizują zaled- wie pojedyncze funkcje, za to realizują je doskonale. Co więcej, powłoka ułatwia łączenie tych narzędzi na różne sposoby oraz dodawanie nowych. Aby ta filozofia sprawdzała się w życiu, dobre narzędzie powłoki Uniksa powinno być napisane w zgodzie z następującymi zasadami: 8 Programiści znający doskonale Emacs Lisp zapewne mogą być innego zdania. 9 Jeśli chodzi o ścisłość, nie powinniśmy mówić „powłoka Uniksa”, ponieważ nie istnieje jeden jedyny produkt noszący tę nazwę. Mamy bowiem do czynienia z dziesiątkami języków skryptowych, które mogą działać jako powłoki Uniksa, począwszy od klasycznego już /bin/sh, po mój ulubiony bash. W tej książce zastosuję jak najbardziej przenośną składnię zgodną z większo
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Przetwarzanie danych dla programistów
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: