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
Python. Receptury
Autorzy: Alex Martelli, Anna Martelli
Ravenscroft, David Ascher
T³umaczenie: Wojciech Moch, Marek Pêtlicki
ISBN: 83-246-0214-3
Tytu³ orygina³u: Python Cookbook
Format: B5, stron: 848
Python zosta³ opracowany na pocz¹tku lat 90 i szybko zyska³ uznanie programistów.
Elastyczny i uniwersalny, pozwala³ na stosowanie zasad programowania obiektowego,
strukturalnego i funkcyjnego. By³ i nadal jest wykorzystywany nie tylko do tworzenia
skryptów, ale równie¿ przy du¿ych projektach, takich jak na przyk³ad serwer aplikacji
Zope. Decyduj¹c siê na korzystanie z Pythona, stajemy siê czêœci¹ niezwyk³ej
spo³ecznoœci programistów, chêtnie pomagaj¹cej ka¿demu, kto chce doskonaliæ
umiejêtnoœæ pos³ugiwania siê tym jêzykiem.
Ksi¹¿ka „Python. Receptury” to zbiór rozwi¹zañ problemów, z jakimi w codziennej pracy
borykaj¹ siê programiœci korzystaj¹cy z tego jêzyka. Materia³y do niej przygotowa³o
ponad 300 cz³onków spo³ecznoœci Pythona odpowiadaj¹cych na pytania zadawane
na forum internetowym. Rozwi¹zania zosta³y przetestowane w praktyce, co u³atwia ich
zaimplementowanie we w³asnych projektach.
W ksi¹¿ce umówiono m.in.:
(cid:129) Przetwarzanie tekstów
(cid:129) Operacje na plikach
(cid:129) Programowanie obiektowe
(cid:129) Przeszukiwanie i sortowanie
(cid:129) £¹czenie skryptów z bazami danych
(cid:129) Testowanie i usuwanie b³êdów
(cid:129) Programowanie wielow¹tkowe
(cid:129) Realizacjê zadañ administracyjnych
(cid:129) Obs³ugê interfejsów u¿ytkownika
(cid:129) Tworzenie aplikacji sieciowych
(cid:129) Przetwarzanie dokumentów XML
Ka¿dy programista Pythona, niezale¿nie od umiejêtnoœci,
znajdzie w tej ksi¹¿ce coœ dla siebie
Wstęp ........................................................................................................................................15
Rozdział 1. Tekst .......................................................................................................................31
37
1.1. Przetwarzanie tekstu po jednym znaku
38
1.2. Konwersja pomiędzy znakami a kodami numerycznymi
39
1.3. Sprawdzanie, czy obiekt jest podobny do ciągu znaków
41
1.4. Wyrównywanie ciągów znaków
42
1.5. Usuwanie spacji z końców ciągu znaków
42
1.6. Łączenie ciągów znaków
45
1.7. Odwracanie kolejności słów lub znaków w ciągu znaków
47
1.8. Sprawdzanie, czy ciąg znaków zawiera pewien zestaw znaków
50
1.9. Upraszczanie użycia metody translate
52
1.10. Filtrowanie ciągu znaków na podstawie znaków z określonego zbioru
55
1.11. Sprawdzanie, czy ciąg znaków jest tekstowy czy binarny
57
1.12. Kontrolowanie wielkości znaków
58
1.13. Odczytywanie podciągów
61
1.14. Zmiany wcięć w wielowierszowym ciągu znaków
63
1.15. Rozszerzanie i zawężanie tabulacji
65
1.16. Wstawianie zmiennych do ciągu znaków
67
1.17. Wstawianie zmiennych do ciągu znaków w Pythonie 2.4
69
1.18. Podmiana wielu wzorców w jednym przebiegu
72
1.19. Sprawdzanie końcówek w ciągu znaków
73
1.20. Obsługa tekstów międzynarodowych za pomocą Unikodu
76
1.21. Konwertowanie pomiędzy Unikodem i prostym tekstem
78
1.22. Wypisywanie znaków Unikodu na standardowe wyjście
79
1.23. Kodowanie danych w formatach XML i HTML
1.24. Przygotowanie ciągu znaków nierozróżniającego wielkości liter
82
1.25. Konwertowanie dokumentów HTML na zwykły tekst na terminalu uniksowym 85
3
Rozdział 2. Pliki .......................................................................................................................89
93
2.1. Czytanie z pliku
97
2.2. Zapisywanie do pliku
98
2.3. Wyszukiwanie i podmiany tekstu w pliku
99
2.4. Odczytanie z pliku określonego wiersza
100
2.5. Zliczanie wierszy w pliku
103
2.6. Przetwarzanie wszystkich słów z pliku
105
2.7. Wejście i wyjście o dostępie swobodnym
106
2.8. Aktualizowanie pliku o dostępie swobodnym
108
2.9. Odczytywanie danych z plików .zip
110
2.10. Obsługa plików .zip wewnątrz ciągu znaków
2.11. Archiwizowanie drzewa plików w skompresowanym pliku .tar
111
2.12. Wysyłanie danych binarnych na standardowe wyjście w systemach Windows 113
2.13. Stosowanie składni podobnej do składni obiektów iostream z języka C++
114
2.14. Przewijanie pliku wejściowego do początku
115
2.15. Przystosowywanie obiektów plikopodobnych
do obiektów rzeczywistych plików
118
119
2.16. Przeglądanie drzew katalogów
121
2.17. Zamiana jednego rozszerzenia plików na inne w całym drzewie katalogów
122
2.18. Wyszukiwanie pliku na podstawie ścieżki wyszukiwania
123
2.19. Wyszukiwanie plików na postawie ścieżki wyszukiwania i wzorca
124
2.20. Wyszukiwanie plików zgodnie ze ścieżką wyszukiwania Pythona
125
2.21. Dynamiczne modyfikowanie ścieżki wyszukiwania Pythona
2.22. Wyznaczanie ścieżki względnej z jednego katalogu do drugiego
127
2.23. Odczytywanie znaków niebuforowanych w sposób niezależny od platformy 129
130
2.24. Zliczanie stron dokumentów PDF w systemie Mac OS X
131
2.25. Modyfikowanie atrybutów plików w systemach Windows
132
2.26. Pobieranie tekstu z dokumentów OpenOffice.org
2.27. Pobieranie tekstu z dokumentów Microsoft Word
133
134
2.28. Blokowanie plików za pomocą międzyplatformowego API
136
2.29. Wersjonowanie nazw plików
2.30. Wyliczanie sum kontrolnych CRC-64
138
Rozdział 3. Czas i pieniądz ....................................................................................................141
147
149
151
152
153
155
158
3.1. Wyliczanie dnia jutrzejszego i wczorajszego
3.2. Którego był ostatni piątek?
3.3. Wyliczanie przedziału czasu i zakresu dat
3.4. Sumowanie czasów trwania piosenek
3.5. Wyznaczanie liczby dni roboczych pomiędzy dwoma datami
3.6. Automatyczne wyznaczanie dat świąt
3.7. Elastyczne odczytywanie dat
4
|
Spis treści
3.8. Sprawdzanie, czy aktualnie mamy czas letni czy zimowy
3.9. Konwersja stref czasowych
3.10. Powtarzanie wywołania polecenia
3.11. Tworzenie terminarza poleceń
3.12. Arytmetyka dziesiętna
3.13. Formatowanie liczb dziesiętnych jako waluty
3.14. Python jako prosta maszyna sumująca
3.15. Sprawdzanie sumy kontrolnej karty kredytowej
3.16. Sprawdzanie kursów wymiany walut
159
160
162
163
165
167
170
173
174
Rozdział 4. Skróty ...................................................................................................................177
179
182
184
185
186
188
191
192
194
196
197
199
201
203
204
206
208
210
212
214
215
217
219
4.1. Kopiowanie obiektu
4.2. Konstruowanie list za pomocą list składanych
4.3. Zwracanie elementu listy, o ile istnieje
4.4. Przeglądanie w pętli elementów sekwencji i ich indeksów
4.5. Tworzenie list bez współdzielenia referencji
4.6. Spłaszczanie zagnieżdżonej sekwencji
4.7. Usuwanie lub przestawianie kolumn na liście wierszy
4.8. Transponowanie tablic dwuwymiarowych
4.9. Pobieranie wartości ze słownika
4.10. Dodawanie pozycji do słownika
4.11. Budowanie słownika bez nadużywania cudzysłowów
4.12. Budowanie słownika na podstawie listy kluczy i wartości
4.13. Wydobywanie podzbioru elementów słownika
4.14. Odwracanie słownika
4.15. Wiązanie kilku wartości z kluczami słownika
4.16. Stosowanie słowników do wywoływania metod lub funkcji
4.17. Wyszukiwanie sum i części wspólnych słowników
4.18. Kolekcja elementów nazwanych
4.19. Przypisywanie i testowanie za pomocą jednej instrukcji
4.20. Stosowanie w Pythonie instrukcji printf
4.21. Losowe wybieranie elementów z zadanym prawdopodobieństwem
4.22. Obsługiwanie wyjątków wewnątrz wyrażeń
4.23. Sprawdzanie, czy nazwa jest zdefiniowana w danym module
Rozdział 5. Szukanie i sortowanie ....................................................................................... 221
226
227
229
231
234
5.1. Sortowanie słownika
5.2. Sortowanie listy ciągów znaków bez uwzględniania wielkości liter
5.3. Sortowanie listy obiektów na podstawie ich atrybutów
5.4. Sortowanie kluczy lub indeksów na podstawie związanych z nimi wartości
5.5. Sortowanie ciągów znaków zawierających liczby
Spis treści
|
5
5.6. Przetwarzanie wszystkich elementów listy w kolejności losowej
5.7. Utrzymywanie porządku w sekwencji
w czasie dodawania do niej nowych elementów
5.8. Pobieranie kilku najmniejszych elementów sekwencji
5.9. Wyszukiwanie elementów w sekwencji posortowanej
5.10. Wybieranie n-tego najmniejszego elementu w sekwencji
5.11. Algorytm quicksort w trzech wierszach kodu
5.12. Wykonywanie częstych testów obecności elementów sekwencji
5.13. Wyszukiwanie podsekwencji
5.14. Wzbogacanie typu dict o możliwość wprowadzania ocen
5.15. Sortowanie nazwisk i rozdzielanie ich za pomocą inicjałów
235
237
239
241
243
246
249
251
253
257
Rozdział 6. Programowanie obiektowe .............................................................................. 259
266
268
270
272
274
277
280
282
284
6.1. Konwertowanie między skalami temperatury
6.2. Definiowanie stałych
6.3. Ograniczanie dodawania atrybutów
6.4. Łączenie wyszukiwań danych w słowniku
6.5. Automatyczne delegacje jako alternatywa dla dziedziczenia
6.6. Delegowanie metod specjalnych w obiektach proxy
6.7. Implementowanie krotek z nazywanymi elementami
6.8. Unikanie stosowania powtarzalnych metod dostępu do właściwości
6.9. Tworzenie szybkiej kopii obiektu
6.10. Przechowywanie referencji metod powiązanych
bez wstrzymywania mechanizmu oczyszczania pamięci
6.11. Implementowanie bufora cyklicznego
6.12. Wykrywanie dowolnych zmian stanu egzemplarza
6.13. Sprawdzanie, czy obiekt ma wymagane atrybuty
6.14. Implementowanie wzorca Projektu Stanu
6.15. Implementowanie wzorca projektowego Singleton
6.16. Zastępowanie wzorca projektowego Singleton idiomem Borg
6.17. Implementowanie wzorca projektowego Obiektu Zerowego
6.18. Automatyczne inicjowanie zmiennych egzemplarzy
286
289
292
295
299
301
302
307
na podstawie argumentów metody __init__
310
6.19. Wywoływanie metody __init__ w klasie bazowej, jeśli taka metoda istnieje
312
6.20. Spójne i bezpieczne kooperatywne wywołania metod w klasach nadrzędnych 315
Rozdział 7. Trwałość danych i bazy danych ..........................................................................317
320
322
325
326
7.1. Serializowanie danych za pomocą modułu marshal
7.2. Serializowanie danych za pomocą modułów pickle i cPickle
7.3. Stosowanie kompresji w połączeniu z serializacją
7.4. Wykorzystanie modułu cPickle wobec klas i ich egzemplarzy
6
|
Spis treści
7.5. Przechowywanie metod powiązanych
w sposób pozwalający na ich serializację
7.6. Serializacja obiektów kodu
7.7. Modyfikowanie obiektów za pomocą modułu shelve
7.8. Użytkowanie bazy danych Berkeley DB
7.9. Uzyskiwanie dostępu do bazy danych MySQL
7.10. Zapisywanie danych typu BLOB w bazie danych MySQL
7.11. Zapisywanie danych typu BLOB w bazie danych PostgreSQL
7.12. Zapisywanie danych typu BLOB w bazie danych SQLite
7.13. Generowanie słownika odwzorowującego nazwy pól na numery kolumn
7.14. Wykorzystywanie modułu dtuple w celu uzyskania elastycznego dostępu
329
331
334
336
339
341
342
344
345
do wyników zapytania
347
7.15. Wypisywanie zawartości kursora bazy danych
349
7.16. Ujednolicenie stylu przekazywania parametrów w różnych modułach DB API 352
7.17. Wykorzystywanie Microsoft Jet poprzez interfejs ADO
354
7.18. Dostęp do bazy danych JDBC z poziomu servletu Jythona
356
7.19. Wykorzystywanie w Jythonie interfejsu ODBC
do odczytywania danych z Excela
358
Rozdział 8. Testy i debugowanie ......................................................................................... 361
362
8.1. Wyłączanie wykonania niektórych instrukcji warunkowych i pętli
363
8.2. Pomiar wykorzystania pamięci w Linuksie
365
8.3. Debugowanie procesu oczyszczania pamięci
366
8.4. Przechwytywanie i zachowywanie wyjątków
368
8.5. Śledzenie wyrażeń i komentarzy w trybie debugowania
371
8.6. Pobieranie dokładniejszych informacji ze śladów
374
8.7. Automatyczne uruchamianie debugera po nieprzechwyconym wyjątku
375
8.8. Najprostsze uruchamianie testów modułowych
8.9. Automatyczne uruchamianie testów modułowych
377
8.10. Używanie w Pythonie 2.4 modułu doctest w połączeniu z modułem unittest 378
8.11. Sprawdzanie w ramach testów modułowych,
czy wartość mieści się w przedziale
380
Rozdział 9. Procesy, wątki i synchronizacja ........................................................................383
387
9.1. Synchronizowanie wszystkich metod w obiekcie
390
9.2. Zatrzymywanie wątku
392
9.3. Używanie klasy Queue.Queue jako kolejki priorytetowej
9.4. Praca ze zbiorem wątków
394
9.5. Równoległe wykonywanie jednej funkcji z wieloma zestawami argumentów 397
399
9.6. Koordynacja wątków przez proste przekazywanie komunikatów
9.7. Zachowywanie informacji w poszczególnych wątkach
402
405
9.8. Kooperatywna wielozadaniowość bez wątków
Spis treści
|
7
9.9. Sprawdzanie, czy w systemach Windows działa już inny egzemplarz skryptu 407
9.10. Przetwarzanie komunikatów systemu Windows za pomocą funkcji
MsgWaitForMultipleObjects
9.11. Uruchamianie zewnętrznego procesu za pomocą funkcji popen
9.12. Przechwytywanie strumieni wyjściowego i błędów z polecenia uniksowego
9.13. Rozwidlanie procesu demona w Uniksie
409
412
413
416
Rozdział 10. Administracja systemem .................................................................................. 419
420
10.1. Generowanie losowych haseł
422
10.2. Generowanie haseł łatwych do zapamiętania
424
10.3. Uwierzytelnianie użytkowników za pomocą serwera POP
10.4. Obliczanie liczby odsłon stron serwera Apache z poszczególnych adresów IP 426
10.5. Obliczanie współczynnika zbuforowanych żądań klientów serwera Apache 428
429
10.6. Uruchomienie edytora tekstów ze skryptu
10.7. Kopie zapasowe plików
431
10.8. Selektywne kopiowanie pliku skrzynki pocztowej
433
10.9. Budowanie białej listy adresów e-mail w oparciu
o zawartość skrzynki pocztowej
10.10. Blokowanie duplikatów e-maili
10.11. Kontrola działania podsystemu dźwiękowego w Windows
10.12. Rejestrowanie i odrejestrowywanie bibliotek DLL w Windows
10.13. Sprawdzanie i modyfikacja listy zadań
uruchamianych przez system Windows podczas rozruchu
10.14. Utworzenie udostępnianego zasobu sieciowego w systemie Windows
10.15. Podłączenie do działającego egzemplarza Internet Explorera
10.16. Odczyt listy kontaktów programu Microsoft Outlook
10.17. Pobieranie szczegółowych informacji o systemie Mac OS X
434
435
437
438
440
441
442
444
446
Rozdział 11. Interfejsy użytkownika .....................................................................................449
451
453
11.1. Prezentacja wskaźnika postępu na konsoli tekstowej
11.2. Unikanie konstrukcji lambda przy tworzeniu funkcji zwrotnych
11.3. Wykorzystanie domyślnych wartości i ograniczeń
przy korzystaniu z funkcji tkSimpleDialog
454
11.4. Umożliwienie zmiany kolejności pozycji w obiekcie klasy Listbox
za pomocą myszy
455
11.5. Wpisywanie specjalnych znaków w elementach sterujących biblioteki Tkinter 457
11.6. Osadzanie obrazów GIF w kodzie skryptu
459
460
11.7. Przekształcanie formatów graficznych
11.8. Implementacja stopera za pomocą biblioteki Tkinter
463
11.9. Wykorzystanie interfejsów graficznych
wraz z asynchroniczną obsługą operacji wejścia-wyjścia za pomocą wątków
11.10. Wykorzystanie elementu Tree z programu IDLE
465
469
8
|
Spis treści
11.11. Obsługa wielokrotnych wartości w wierszu
w obiekcie Listbox modułu Tkinter
11.12. Kopiowanie metod i opcji wymiarowania
pomiędzy kontrolkami biblioteki Tkinter
11.13. Implementacja kontrolki notatnika z zakładkami w bibliotece Tkinter
11.14. Wykorzystanie obiektów klasy Notebook biblioteki wxPython z panelami
11.15. Implementacja wtyczki do programu ImageJ w Jythonie
11.16. Przeglądanie obrazów bezpośrednio z adresu URL
za pomocą Swinga i Jythona
11.17. Pobieranie danych od użytkownika w systemie Mac OS
11.18. Programowe generowanie interfejsu Cocoa GUI
11.19. Implementacja stopniowo pojawiających się okien z użyciem IronPythona
471
474
476
479
480
481
482
484
486
Rozdział 12. Przetwarzanie formatu XML ...........................................................................489
491
492
494
495
497
12.1. Sprawdzanie poprawności struktury danych XML
12.2. Zliczanie znaczników w dokumencie
12.3. Wydobywanie tekstu z dokumentu XML
12.4. Wykrywanie standardu kodowania dokumentu XML
12.5. Przekształcanie dokumentu XML w drzewo obiektów Pythona
12.6. Usuwanie z drzewa DOM węzłów zawierających
wyłącznie ciągi białych znaków
12.7. Parsowanie plików XML zapisanych przez Microsoft Excel
12.8. Walidacja dokumentów XML
12.9. Filtrowanie elementów należących do określonej przestrzeni nazw
12.10. Łączenie występujących po sobie zdarzeń tekstowych
w jedną całość za pomocą filtra SAX
12.11. Wykorzystanie MSHTML-a do parsowania formatu XML lub HTML
499
500
502
503
505
508
Rozdział 13. Programowanie sieciowe ................................................................................. 511
513
515
516
517
518
521
523
524
13.1. Przekazywanie komunikatów za pośrednictwem gniazd datagramowych
13.2. Pobieranie dokumentacji z WWW
13.3. Filtrowanie listy serwerów FTP
13.4. Odczytywanie czasu z serwera za pomocą protokołu SNTP
13.5. Wysyłanie listów e-mail w formacie HTML
13.6. Wykorzystanie wiadomości w formacie MIME do wysyłki wielu plików
13.7. Rozkładanie na części wieloczęściowej wiadomości w formacie MIME
13.8. Usuwanie załączników z listów elektronicznych
13.9. Poprawianie błędnych obiektów email uzyskanych za pomocą parsera
email.FeedParser z Pythona 2.4
13.10. Interaktywne przeglądanie skrzynki pocztowej POP3
13.11. Wykrywanie nieaktywnych komputerów
13.12. Monitorowanie sieci z użyciem HTTP
526
528
531
535
Spis treści
|
9
13.13. Przekazywanie i przeadresowywanie portów sieciowych
13.14. Tunelowanie połączeń SSL przez serwer pośredniczący
13.15. Implementacja klienta usługi dynamicznego DNS
13.16. Połączenie z serwerem IRC i zapis dziennika rozmów na dysku
13.17. Wykorzystanie serwerów LDAP
537
540
543
546
547
Rozdział 14. Programowanie WWW ....................................................................................549
550
553
555
556
558
559
560
14.1. Sprawdzanie, czy CGI działa poprawnie
14.2. Obsługa adresów URL w skryptach CGI
14.3. Przesyłanie plików na serwer WWW za pomocą CGI
14.4. Sprawdzanie istnienia strony WWW
14.5. Sprawdzanie typu zawartości za pomocą HTTP
14.6. Wznawianie pobierania pliku za pomocą HTTP
14.7. Obsługa cookies przy pobieraniu stron WWW
14.8. Uwierzytelnianie połączenia HTTPS
nawiązywanego za pośrednictwem pośrednika
14.9. Uruchamianie serwletów z użyciem Jythona
14.10. Wyszukiwanie cookie przeglądarki Internet Explorer
14.11. Generowanie plików OPML
14.12. Pobieranie wiadomości RSS
14.13. Przekształcanie danych w strony WWW z użyciem szablonów stron
14.14. Renderowanie dowolnych obiektów z użyciem Nevow
563
564
566
567
570
573
576
Rozdział 15. Oprogramowanie rozproszone ....................................................................... 579
582
583
585
587
15.1. Wywołanie metody XML-RPC
15.2. Obsługa żądań XML-RPC
15.3. Serwer XML-RPC wykorzystujący bibliotekę Medusa
15.4. Zdalne zamykanie serwera XML-RPC
15.5. Implementowanie mechanizmów ulepszających na potrzeby klasy
SimpleXMLRPCServer
15.6. Implementacja interfejsu graficznego wxPython dla serwera XML-RPC
15.7. Wykorzystanie mechanizmu Twisted Perspective Broker
15.8. Implementacja serwera i klienta CORBA
15.9. Zdalne uruchamianie poleceń powłoki z użyciem telnetlib
15.10. Zdalne uruchamianie poleceń powłoki z użyciem SSH
15.11. Uwierzytelnianie z użyciem klienta SSL za pomocą protokołu HTTPS
588
589
592
594
597
599
602
Rozdział 16. Programy o programach ..................................................................................605
611
612
613
615
16.1. Sprawdzanie, czy ciąg znaków jest poprawną liczbą
16.2. Importowanie dynamicznie wygenerowanego modułu
16.3. Importowanie modułów, których nazwy są ustalane w trakcie wykonania
16.4. Wiązanie parametrów z funkcjami (metoda Curry’ego)
10
|
Spis treści
16.5. Dynamiczne komponowanie funkcji
16.6. Kolorowanie kodu źródłowego w Pythonie z użyciem wbudowanego
mechanizmu analizy leksykalnej
16.7. Łączenie i dzielenie tokenów
16.8. Sprawdzanie, czy ciąg znaków ma odpowiednio zrównoważone nawiasy
16.9. Symulowanie typu wyliczeniowego w Pythonie
16.10. Odczyt zawartości rozwinięcia listy w trakcie jej budowania
16.11. Automatyczna kompilacja skryptów za pomocą py2exe
do postaci programów wykonywalnych systemu Windows
16.12. Łączenie skryptu głównego i modułów
w jeden plik wykonywalny systemu Unix
618
619
622
624
627
629
631
633
Rozdział 17. Rozszerzanie i osadzanie ................................................................................. 637
640
643
645
17.1. Implementacja prostego typu rozszerzeń
17.2. Implementacja prostego rozszerzenia za pomocą języka Pyrex
17.3. Wykorzystanie w Pythonie biblioteki napisanej w C++
17.4. Wywoływanie funkcji zdefiniowanych w bibliotekach DLL
systemu Windows
17.5. Wykorzystanie modułów wygenerowanych z użyciem SWIG
w środowisku wielowątkowym
17.6. Przekształcenie sekwencji Pythona na tablicę języka C z użyciem protokołu
PySequence_Fast
17.7. Odczyt elementów sekwencji Pythona
648
650
651
z wykorzystaniem protokołu iteratorów
655
17.8. Zwracanie wartości None w funkcji rozszerzeń w języku C
658
17.9. Debugowanie za pomocą gdb dynamicznie ładowanych rozszerzeń Pythona 659
17.10. Debugowanie problemów z pamięcią
660
Rozdział 18. Algorytmy .........................................................................................................663
667
669
673
674
675
677
679
681
684
687
690
692
694
18.1. Usuwanie duplikatów z sekwencji
18.2. Usuwanie duplikatów z sekwencji z zachowaniem kolejności
18.3. Generowanie losowych próbek z powtórzeniami
18.4. Generowanie losowych próbek bez powtórzeń
18.5. Zachowywanie wartości zwracanych przez funkcje
18.6. Implementacja kontenera FIFO
18.7. Buforowanie obiektów w kolejce FIFO
18.8. Implementacja typu wielozbiorowego (kolekcji)
18.9. Zasymulowanie w Pythonie operatora trójargumentowego
18.10. Wyliczanie liczb pierwszych
18.11. Formatowanie liczb całkowitych w postaci dwójkowej
18.12. Formatowanie liczb całkowitych w notacji o dowolnej podstawie
18.13. Przekształcanie liczb na notację ułamkową z użyciem ciągów Fareya
Spis treści
|
11
18.14. Obliczenia arytmetyczne z propagacją błędu
18.15. Sumowanie liczb z jak największą precyzją
18.16. Symulacja liczb zmiennoprzecinkowych
18.17. Wyliczanie powłoki wypukłej oraz średnicy zbioru punktów
w przestrzeni dwuwymiarowej
696
698
700
703
Rozdział 19. Iteratory i generatory ....................................................................................... 707
711
713
715
716
718
720
722
725
728
731
733
19.1. Implementacja funkcji range() o przyrostach zmiennoprzecinkowych
19.2. Budowanie listy z dowolnego obiektu iterowalnego
19.3. Generowanie ciągu Fibonacciego
19.4. Rozpakowanie kilku wartości w operacji wielokrotnego przypisania
19.5. Automatyczne rozpakowanie odpowiedniej liczby elementów
19.6. Dzielenie obiektu iterowanego na rozszerzone wycinki o szerokości n
19.7. Przeglądanie sekwencji za pomocą częściowo pokrywających się okien
19.8. Równoległe przeglądanie wielu obiektów iterowalnych
19.9. Przeglądanie iloczynu kartezjańskiego wielu obiektów iterowalnych
19.10. Odczytywanie zawartości pliku po akapitach
19.11. Odczyt wierszy ze znakami kontynuacji
19.12. Przeglądanie strumienia bloków danych
i interpretowanie go jako strumienia wierszy
19.13. Pobieranie dużych zestawów wyników z bazy danych
z wykorzystaniem generatora
19.14. Łączenie sekwencji posortowanych
19.15. Generowanie permutacji, kombinacji i selekcji
19.16. Generowanie rozkładów liczb całkowitych
19.17. Tworzenie duplikatu iteratora
19.18. Podglądanie wartości iteratora w przód
19.19. Uproszczenie wątków konsumentów kolejek
19.20. Uruchamianie iteratora w innym wątku
19.21. Obliczanie raportu podsumowującego za pomocą itertools.groupby()
734
735
737
740
742
744
747
750
751
753
Rozdział 20. Deskryptory, dekoratory i metaklasy ............................................................. 757
759
762
764
766
768
770
773
775
777
20.1. Przydzielanie nowych wartości domyślnych dla każdego wywołania funkcji
20.2. Kodowanie właściwości za pomocą funkcji zagnieżdżonych
20.3. Tworzenie aliasów wartości atrybutów
20.4. Buforowanie wartości atrybutów
20.5. Wykorzystanie jednej metody w charakterze akcesora wielu atrybutów
20.6. Dodawanie funkcjonalności klasie przez opakowanie metody
20.7. Wzbogacanie funkcjonalności klasy przez modyfikację wszystkich metod
20.8. Dodawanie metod do egzemplarza klasy w czasie wykonania
20.9. Sprawdzanie, czy zostały zaimplementowane określone interfejsy
12
|
Spis treści
20.10. Odpowiednie wykorzystanie metod __new__ i __init__
we własnych metaklasach
20.11. Zezwalanie na potokowe wykonywanie mutujących metod obiektów list
20.12. Implementacja bardziej zwartej składni wywołań metod klasy nadrzędnej
20.13. Inicjalizacja atrybutów egzemplarza bez użycia metody __init__()
20.14. Automatyczna inicjalizacja atrybutów egzemplarza
20.15. Automatyczna aktualizacja klas istniejących obiektów
po ponownym załadowaniu modułu
20.16. Wiązanie stałych w czasie kompilacji
20.17. Rozwiązywanie konfliktów metaklas
779
781
782
784
786
789
793
797
Skorowidz .............................................................................................................................. 801
Spis treści
|
13
ROZDZIAŁ 5.
5.0. Wprowadzenie
Pomysłodawca: Tim Peters, PythonLabs
W latach 60. producenci komputerów szacowali, że 25 czasu pracy wszystkich sprzedanych
przez nich urządzeń przeznaczane jest na zadania związane z sortowaniem. W rzeczywi-
stości było wiele takich instalacji, w których zadanie sortowania zajmowało ponad poło-
wę czasu pracy komputerów. Z tych danych można wywnioskować, że: a) istnieje wiele
bardzo ważnych powodów sortowania, b) wielokrotnie sortuje się dane bez potrzeby lub c)
powszechnie stosowane były nieefektywne algorytmy sortowania.
— Donald Knuth
The Art of Computer Programming, tom 3,
Sorting and Searching, strona 3.
Wspaniała praca profesora Knutha na temat sortowania i wyszukiwania ma niemal 800 stron
złożonego tekstu technicznego. W praktyce Pythona całą tę pracę redukuje się do dwóch im-
peratywów (ktoś inny przeczytał to „opasłe tomisko”, dlatego Czytelnik zostanie zwolniony
z tego obowiązku):
Jeżeli musimy sortować dane, to najlepiej będzie znaleźć sposób na wykorzystanie wbu-
·
dowanej w Pythona metody sort zajmującej się sortowaniem list.
Jeżeli musimy przeszukiwać dane, to najlepiej będzie znaleźć sposób na wykorzystanie
·
wbudowanego typu słowników.
Wiele receptur z niniejszego rozdziału kieruje się właśnie tymi dwoma zasadami. Najczęściej
stosowanym w nich rozwiązaniem jest implementacja wzorca DSU (ang. decorate-sort-undecorate
— dekoruj-sortuj-usuń dekorację). Jest to najogólniejsze rozwiązanie polegające na utworzeniu
listy pomocniczej, którą można posortować za pomocą domyślnej, szybkiej metody sort. Ta
technika należy do najużyteczniejszych spośród wszystkich prezentowanych w tym rozdziale.
Co więcej, wzorzec DSU jest tak dalece przydatny, że w Pythonie 2.4 wprowadzono kilka no-
wych funkcji ułatwiających jego stosowanie. W efekcie w Pythonie 2.4 wiele z prezentowanych
receptur można jeszcze bardziej uprościć, dlatego analiza starszych receptur została uzupełnio-
na o odpowiednie instrukcje.
221
Wzorzec DSU polega na wykorzystaniu niezwykłych właściwości wbudowanych w Pythona
porównań: sekwencje są porównywane leksykograficznie. Kolejność leksykograficzna jest uogól-
nieniem wszystkich znanych nam reguł porównywania ciągów znaków (czyli kolejności alfa-
betycznej), które rozciągnięte zostały na krotki i listy. W przypadku, gdy zmienne s1 i s2
są sekwencjami, wbudowana funkcja cmp(s1, s2) jest równoważna z następującym kodem
Pythona:
def lexcmp(s1, s2):
# Znajdź nierówną parę po lewej stronie.
i = 0
while i len(s1) and i len(s2):
outcome = cmp(s1[i], s2[i])
if outcome:
return outcome
i += 1
# Wszystkie równe do momentu wyczerpania przynajmniej jednej sekwencji.
return cmp(len(s1), len(s2))
Podany kod poszukuje pierwszej pary nierównych sobie elementów. Po znalezieniu takiej pary
na jej podstawie określany jest wynik porównania. W przeciwnym przypadku, jeżeli jedna
z sekwencji jest dokładnym przedrostkiem drugiej, to taki przedrostek uznawany jest za mniejszą
sekwencję. W końcu, jeżeli nie obowiązuje żaden z wymienionych wyżej przypadków, znaczy
to, że sekwencje są identyczne i w związku z tym uznawane są za równe. Oto kilka przykładów:
cmp((1, 2, 3), (1, 2, 3)) # identyczne
0
cmp((1, 2, 3), (1, 2)) # pierwsza większa, ponieważ druga jest przedrostkiem
1
cmp((1, 100), (2, 1)) # pierwsza jest mniejsza, ponieważ 1 2
-1
cmp((1, 2), (1, 3)) # pierwsza jest mniejsza, ponieważ 1==1, ale 2 3
-1
Bezpośrednią konsekwencją takich porównań leksykograficznych jest to, że w przypadku, gdy
chcielibyśmy posortować listę obiektów według klucza głównego, a w przypadku równości
wartości tego klucza — według klucza drugorzędnego, należy zbudować listę krotek, gdzie
każda krotka przechowuje klucz główny, klucz drugorzędny i oryginalny obiekt, dokładnie
w tej kolejności. Krotki porównywane są leksykograficznie, dlatego taka kolejność ich elemen-
tów automatycznie załatwia sprawę. W czasie porównywania krotek najpierw porównywane
są klucze główne, a jeżeli są one równe, to (tylko w takim przypadku) porównywane są klu-
cze drugorzędne.
Podawane w tym rozdziale przykłady wzorca DSU prezentują wiele zastosowań takiego po-
stępowania. Technikę DSU można stosować z dowolną liczbą kluczy. Krotki można uzupełniać
o kolejne klucze, umieszczając je w takiej kolejności, w jakiej mają być porównywane. W Py-
thonie 2.4 ten sam efekt można uzyskać, podając do metody sort opcjonalny parametr key=, tak
jak robione jest to w niektórych recepturach. Stosowanie parametru key= metody sort jest prost-
sze, efektywniejsze i szybsze od ręcznego tworzenia listy krotek.
Inną z nowości wprowadzonych do Pythona 2.4 w zakresie sortowania jest bardzo wygodny
skrót: wbudowana funkcja sorted pozwalająca na sortowanie dowolnego elementu iterowal-
nego. Takie sortowanie nie odbywa się „w miejscu”, ale przez kopiowanie danych do nowej
listy. W Pythonie 2.3 (oprócz nowego opcjonalnego parametru nazywanego, który można sto-
sować zarówno w funkcji sorted, jak i w metodzie list.sort) to samo działanie można zaim-
plementować bez większego wysiłku:
222
|
Rozdział 5. Szukanie i sortowanie
def sorted_2_3(iterable):
alist = list(iterable)
alist.sort()
return alist
Operacje kopiowania i sortowania listy nie są operacjami trywialnymi, a wbudowana funkcja
sorted i tak musi je wykonać, dlatego przekształcenie funkcji sorted w funkcję wbudowaną
nie dało praktycznie żadnego wzrostu prędkości jej działania. Jedyną zaletą jest tu po prostu
wygoda. Likwidacja konieczności powtarzalnego wpisywania nawet czterech prostych wierszy
kodu i świadomość, że pewne elementy mamy zawsze pod ręką, naprawdę stanowi ogromną po-
prawę wygody pracy. Z drugiej strony, zaledwie niewielka część prostych funkcji używana jest
na tyle powszechnie, żeby usprawiedliwiało to rozbudowę zbioru elementów wbudowanych.
W Pythonie 2.4 do tego zbioru dodane zostały funkcje sorted i reversed, ponieważ w ciągu
ostatnich lat często pojawiały się prośby o dodanie ich do elementów wbudowanych.
Największa zmiana w mechanizmach sortowania stosowanych w Pythonie od czasu pierwsze-
go wydania tej książki polegała na wprowadzeniu do Pythona 2.3 nowej implementacji algo-
rytmu sortowania. Pierwszą widoczną konsekwencją tej zmiany był wzrost prędkości w wielu
typowych przypadkach oraz fakt, że nowy algorytm jest stabilny, co oznacza, że dwa elementy,
które w oryginalnej liście są sobie równe, w posortowanej liście zachowują swoją względną
kolejność. Nowa implementacja była niezwykle udana, a szanse na przygotowanie lepszej były
tak nikłe, że Guido dał się przekonać, że w Pythonie metoda list.sort już zawsze będzie
stabilna. Nowa funkcja sortująca pojawiła się już w wersji 2.3, ale gwarancja stabilności algo-
rytmu sortowania wprowadzona została dopiero w wersji 2.4. Mimo to historia algorytmów sor-
towania każe nam pamiętać, że zawsze mogą zostać odkryte jeszcze lepsze algorytmy sorto-
wania. W związku z tym należałoby tutaj podać skróconą historię sortowania w Pythonie.
Krótka historia sortowania w Pythonie
We wczesnych wersjach Pythona metoda list.sort wykorzystywała funkcję qsort pocho-
dzącą z biblioteki języka C. Takie rozwiązanie nie sprawdzało się z wielu powodów, ale przede
wszystkim dlatego, że jakość funkcji qsort nie była jednolita na wszystkich komputerach. Nie-
które wersje działały wyjątkowo wolno w przypadkach, gdy miały posortować listę z wielo-
ma jednakowymi wartościami albo ułożoną w odwrotnej kolejności sortowania. Zdarzały się
też wersje powodujące zawieszenie się procesu, ponieważ nie pozwalały na stosowanie rekur-
sji. Zdefiniowana przez użytkownika funkcja __cmp__ może wywoływać metodę list.sort,
dlatego w efekcie ubocznym jedno wywołanie list.sort może powodować kolejne takie wy-
wołania w związku z wykonywanymi porównaniami. Na niektórych platformach funkcja qsort
nie była w stanie poradzić sobie z taką sytuacją. Zdefiniowana (w sposób głupi lub złośliwy)
przez użytkownika funkcja __cmp__ może też „zmutować” listę w czasie jej sortowania i dlate-
go na wielu platformach funkcja qsort może sobie nie radzić z takimi właśnie sytuacjami.
W Pythonie przygotowana została zatem specjalna implementacja algorytmu szybkiego sor-
towania (ang. quicksort algorithm). Była ona zmieniana w każdej następnej wersji języka, po-
nieważ znajdowane były kolejne przypadki rzeczywistych zastosowań, w których aktualna
w danym momencie implementacja okazywała się niezwykle powolna. Jak się okazuje, qu-
icksort to wyjątkowo delikatny algorytm!
W Pythonie 1.5.2 algorytm quicksort został zastąpiony hybrydą algorytmów sortowania przez
wybieranie (ang. samplesort) i sortowania przez wstawienia (ang. insertionsort). Ta implementa-
cja nie uległa zmianie przez ponad cztery lata, aż do momentu pojawienia się Pythona 2.3.
5.0. Wprowadzenie
|
223
Algorytm samplesort można traktować jak wariant algorytmu quicksort, w którym używane są
bardzo duże próbki do wybierania elementu rozdzielającego (metoda ta rekursywnie sortuje
algorytmem samplesort duży losowy podzbiór elementów i wybiera z nich medianę). Taki
wariant sprawia, że prawie nie jest możliwy wariant z czasem sortowania proporcjonalnym do
kwadratu liczby elementów, a liczba porównań w typowych przypadkach jest zdecydowanie
bliższa teoretycznemu minimum.
Niestety, algorytm samplesort jest na tyle skomplikowany, że jego administracja danymi oka-
zuje się zdecydowanie zbyt rozbudowana przy pracach z niewielkimi listami. Z tego właśnie
powodu małe listy (a także niewielkie wykrojenia powstające w wyniku podziałów dokony-
wanych przez ten algorytm) obsługiwane są za pomocą algorytmu insertionsort (jest to zwyczaj-
ny algorytm sortowania przez wstawianie, ale do określania pozycji każdego z elementów ko-
rzysta on z mechanizmów szukania binarnego). W większości tekstów na temat sortowania
zaznaczane jest, że takie podziały nie są warte naszej uwagi, ale wynika to z faktu, że w tekstach
tych uznaje się, że operacja porównania elementów jest mniej czasochłonna od operacji zamiany
tych elementów w pamięci, co nie jest prawdą w algorytmach sortowania stosowanych w Py-
thonie. Przeniesienie obiektu jest operacją bardzo szybką, ponieważ kopiowana jest tylko refe-
rencja tego obiektu. Z kolei porównanie dwóch obiektów jest operacją kosztowną, ponieważ
za każdym razem uruchamiany jest kod przeznaczony do wyszukiwania obiektów w pamięci
oraz kod odpowiedni do wykonania porównania danych obiektów. Jak się okazało, z tego wła-
śnie powodu w Pythonie najlepszym rozwiązaniem jest sortowanie binarne.
To hybrydowe rozwiązanie uzupełnione zostało jeszcze o obsługę kilku typowych przypadków
ukierunkowaną na poprawę prędkości działania. Po pierwsze, wykrywane są listy już po-
sortowane lub posortowane w odwrotnej kolejności i obsługiwane w czasie liniowym. W pew-
nych aplikacjach takie sytuacje zdarzają się bardzo często. Po drugie, dla tablicy w większości po-
sortowanej, w której nieposortowanych jest tylko kilka ostatnich elementów, całą pracę wykonuje
algorytm sortowania binarnego. Takie rozwiązanie jest znacznie szybsze od sortowania takich
list algorytmem samplesort, a przedstawiona sytuacja bardzo często pojawia się w aplikacjach,
które naprzemiennie sortują listę, dodają do niej nowe elementy, znowu sortują itd. W końcu
specjalny kod w algorytmie samplesort wyszukuje ciągi jednakowych elementów i zajmowaną
przez nie część listy od razu oznacza jako posortowaną.
W efekcie takie sortowanie w miejscu odbywa się z doskonałą wydajnością we wszystkich zna-
nych typowych przypadkach i osiąga nienaturalnie dobrą wydajność w pewnych typowych
przypadkach specjalnych. Cała implementacja zapisana została w ponad 500 wierszach skom-
plikowanego kodu w języku C bardzo podobnego do tego prezentowanego w recepturze 5.11.
Przez lata, w których używany był algorytm samplesort, cały czas oferowałem obiad temu, kto
przygotuje szybszy algorytm sortujący dla Pythona. Przez cały ten czas musiałem jadać sam.
Mimo to ciągle śledzę pojawiającą się literaturę, ponieważ pewne aspekty stosowanej w Pytho-
nie hybrydy algorytmów sortujących są nieco irytujące:
·
Co prawda w rzeczywistych zastosowaniach nie pojawiają się przypadki sortowania tablicy
w czasie proporcjonalnym do kwadratu ilości elementów, ale wiem, że takie przypadki
można sobie wyobrazić, natomiast powstanie przypadków, w których sortowanie przebie-
ga dwa do trzech razy wolniej od średniej, jest całkiem realne.
224 |
Rozdział 5. Szukanie i sortowanie
·
Specjalne przypadki przyspieszające sortowanie w sytuacjach wyjątkowych układów da-
nych z całą pewnością były nieocenioną pomocą w normalnej praktyce, ale w czasie moich
prac często spotykałem się z innymi rodzajami losowych układów danych, które można by
było obsłużyć w podobny sposób. Doszedłem do wniosku, że w przypadkach rzeczywistych
praktycznie nigdy nie występują całkowicie losowo ułożone elementy list wejściowych
(a szczególnie poza środowiskami przygotowanymi do testowania algorytmów sortujących).
Nie istnieje praktyczny sposób przygotowania stabilnego algorytmu samplesort bez jed-
·
noczesnego znaczącego powiększenia wykorzystania pamięci.
Kod był niezwykle złożony, a specjalne przypadki komplikowały go jeszcze bardziej.
·
Aktualny algorytm sortowania
Od zawsze było wiadomo, że algorytm mergesort w pewnych przypadkach sprawuje się lepiej,
w tym również w najgorszym przypadku złożoności n log n, a dodatkowo łatwo można
przygotować jego stabilną wersję. Jak się jednak okazało, pół tuzina prób implementowania
tego algorytmu w Pythonie spełzło na niczym, ponieważ przygotowane procedury działały
wolniej (w algorytmie mergesort przenosi się znacznie więcej danych niż w algorytmie sample-
sort) i zajmowały więcej pamięci.
Coraz większa część literatury zaczyna opisywać adaptacyjne algorytmy sortowania, które pró-
bują wykrywać kolejność elementów w różnych danych wejściowych. Sam przygotowałem kilka
takich algorytmów, ale wszystkie okazały się być wolniejsze od pythonowej implementacji
algorytmu samplesort, z wyjątkiem tych przypadków, na obsługę których były specjalnie
przygotowywane. Teoretyczne podstawy tych algorytmów były po prostu zbyt złożone, żeby
na ich bazie można było w praktyce utworzyć efektywny algorytm. Przeczytałem wtedy ar-
tykuł, w którym wskazywano na fakt, że dzięki sprawdzaniu liczby kolejnych „zwycięstw”
poszczególnych danych wejściowych łączenie list w sposób naturalny wykazuje wiele cech po-
rządku częściowego. Ta informacja była bardzo prosta i ogólna, ale w momencie gdy uświado-
miłem sobie, że można by wykorzystać ją w naturalnym algorytmie mergesort, który oczywiście
wykorzystałby wszystkie znane mi rodzaje porządku częściowego, moją obsesją stało się takie
przygotowanie algorytmu, żeby rozwiązać problemy z prędkością sortowania danych losowych
i zminimalizować zajętość pamięci.
Przygotowana „adaptacyjna, naturalna i stabilna” implementacja algorytmu mergesort dla Py-
thona 2.3 była wielkim sukcesem, ale związana była również z wielkim nakładem prac inży-
nieryjnych — po prostu diabeł tkwił w szczegółach. Implementacja ta zajmowała mniej więcej
1200 wierszy kodu w języku C. Jednak w przeciwieństwie do hybrydowej implementacji algo-
rytmu samplesort ten kod nie zawiera obsługi żadnych przypadków specjalnych, ale jego dużą
część zajmuje pewna sztuczka pozwalająca na zmniejszenie o połowę zajętości pamięci w naj-
gorszym z możliwych przypadków. Jestem bardzo dumny z tej implementacji. Niestety, niewiel-
ka ilość miejsca przeznaczona na to wprowadzenie nie pozwala mi na opisanie tu szczegółów
tego rozwiązania. Jeżeli ktoś jest ciekaw, to odsyłam go do opisu technicznego (ostrzegam, że
jest długi), jaki przygotowałem i jaki dostępny jest wśród źródeł dystrybucji Pythona w pliku
Objects/listsort.txt, w katalogu, do którego zainstalowana została dystrybucja Pythona. W poniż-
szej liście podaję przykłady porządków częściowych, jakie wykorzystuje implementacja algo-
rytmu mergesort w Pythonie 2.3. Na liście tej słowo „posortowany” oznacza prawidłową kolej-
ność posortowanych elementów lub ich odwrotną kolejność:
5.0. Wprowadzenie
|
225
Dane wejściowe są już posortowane.
·
Dane wejściowe są w większości posortowane, ale mają dopisane losowe dane na początku
·
i (lub) na końcu albo wstawione w środek.
·
Dane wejściowe są złożeniem dwóch lub więcej list złożonych. Najszybszym sposobem na
połączenie kilku posortowanych list w Pythonie jest teraz złączenie ich w jedną wielką listę
i wywołanie na jej rzecz funkcji list.sort.
·
Dane wejściowe są w większości posortowane, ale pewne elementy nie są ułożone w pra-
widłowej kolejności. Typowym przykładem takiego stanu jest sytuacja, gdy użytkownicy
ręcznie dopisują nowe dane do bazy danych posortowanej według nazwisk. Jak wiemy,
ludzie nie najlepiej radzą sobie z takim dopisywaniem danych i utrzymywaniem ich w po-
rządku alfabetycznym, ale często są bliscy wstawienia elementu we właściwe miejsce.
·
Wśród danych wejściowych znajduje się wiele kluczy o takich samych wartościach. Na
przykład w czasie sortowania bazy danych firm amerykańskich notowanych na giełdzie
większość z takich firm powiązana będzie z indeksami NYSE lub NASDAQ. Taki fakt moż-
na wykorzystać w bardzo ciekawy sposób: klucze o takiej samej wartości są już posorto-
wane, co wynika z faktu, że stosowany jest „stabilny” algorytm sortowania.
·
Dane wejściowe były posortowane, ale zostały rozbite na kawałki, które później poskła-
dano w losowej kolejności, a dodatkowo elementy niektórych kawałków zostały skutecznie
przemieszane. Jest to oczywiście bardzo dziwny przykład, ale w jego wyniku powstaje po-
rządek częściowy danych, co wskazuje na wielką ogólność prezentowanej metody.
Mówiąc krótko, w Pythonie 2.3 funkcja timsort (cóż, musiała dostać jakąś krótką nazwę) jest
rozwiązaniem stabilnym, skutecznym i nienaturalnie szybkim w wielu rzeczywistych przy-
padkach, w związku z czym należy z niej korzystać jak najczęściej!
5.1. Sortowanie słownika
Pomysłodawca: Alex Martelli
Problem
Chcemy posortować słownik. Najprawdopodobniej oznacza to, że chcemy posortować klucze,
a następnie pobierać z niego wartości w tej samej kolejności sortowania.
Rozwiązanie
Najprostsze rozwiązanie tego problemu zostało już wyrażone w opisie problemu: należy po-
sortować klucze i wybierać powiązane z nimi wartości:
def sortedDictValues(adict):
keys = adict.keys()
keys.sort()
return [adict[key] for key in keys]
226
|
Rozdział 5. Szukanie i sortowanie
Analiza
Koncepcja sortowania dotyczy wyłącznie tych kolekcji, których elementy mają jakąś kolejność
(czyli sekwencję). Odwzorowania takie jak słowniki nie mają kolejności, wobec czego nie mogą
być sortowane. Mimo to na listach dyskusyjnych dotyczących Pythona często pojawiają się
całkowicie bezsensowne pytania „Jak mogę posortować słownik?”. Najczęściej takie pytanie
oznacza jednak, że osoba pytająca chciała posortować pewną sekwencję składającą się z kluczy
i (lub) ich wartości pobranych ze słownika.
Jeżeli chodzi o podaną implementację, to co prawda można wymyślić bardziej złożone roz-
wiązania, ale jak się okazuje (w Pythonie nie powinno być to niespodzianką), kod podany
w rozwiązaniu jest rozwiązaniem najprostszym, a jednocześnie najszybszym. Poprawę prędko-
ści działania o mniej więcej 20 można w Pythonie 2.3 uzyskać przez zastąpienie w instrukcji
return listy składanej wywołaniem funkcji map, na przykład:
return map(adict.get, keys)
W Pythonie 2.4 wersja podawana w rozwiązaniu jest jednak o wiele szybsza niż ta w Py-
thonie 2.3, dlatego z takiej zamiany nie zyskamy zbyt wiele. Inne warianty, takie jak na przy-
kład zastąpienie metody adict.get metodą adict.__getitem__ nie powodują już poniesienia
prędkości działania funkcji, a na dodatek mogą spowodować pogorszenie wydajności zarówno
w Pythonie 2.3, jak i w Pythonie 2.4.
Zobacz również
Recepturę 5.4, w której opisywane są sposoby sortowania słowników na podstawie przecho-
wywanych wartości, a nie kluczy.
5.2. Sortowanie listy ciągów znaków
bez uwzględniania wielkości liter
Pomysłodawcy: Kevin Altis, Robin Thomas, Guido van Rossum, Martin V. Lewis, Dave Cross
Problem
Chcemy posortować listę ciągów znaków, ignorując przy tym wszelkie różnice w wielkości li-
ter. Oznacza to, że chcemy, aby litera a, mimo że jest małą literą, znalazła się przed wielką
literą B. Niestety, domyślne porównywanie ciągów znaków uwzględnia różnice wielkości liter,
co oznacza, że wszystkie wielkie litery umieszczane są przed małymi literami.
Rozwiązanie
Wzorzec DSU (decorate-sort-undecorate) sprawdza się tu doskonale, tworząc szybkie i proste
rozwiązanie:
def case_insensitive_sort(string_list):
auxiliary_list = [(x.lower(), x) for x in string_list] # dekoracja
auxiliary_list.sort() # sortowanie
return [x[1] for x in auxiliary_list] # usunięcie dekoracji
5.2. Sortowanie listy ciągów znaków bez uwzględniania wielkości liter
|
227
W Pythonie 2.4 wzorzec DSU obsługiwany jest w samym języku, dlatego (zakładając, że obiekty
listy string_list rzeczywiście są ciągami znaków, a nie na przykład obiektami ciągów zna-
ków Unikodu) można w nim zastosować poniższe, jeszcze szybsze i prostsze rozwiązanie:
def case_insensitive_sort(string_list):
return sorted(string_list, key=str.lower)
Analiza
Dość oczywistą alternatywą dla rozwiązania podawanego w tej recepturze jest przygotowanie
funkcji porównującej i przekazanie jej do metody sort:
def case_insensitive_sort_1(string_list):
def compare(a, b): return cmp(a.lower(), b.lower())
string_list.sort(compare)
Niestety, w ten sposób przy każdym porównaniu dwukrotnie wywoływana jest metoda lower,
a liczba porównań koniecznych do posortowania listy n-elementowej zazwyczaj jest proporcjo-
nalna do n log(n).
Wzorzec DSU tworzy listę pomocniczą, której elementami są krotki, w których każdy element
z oryginalnej listy poprzedzany jest specjalnym „kluczem”. Następnie sortowanie odbywa się
według tych właśnie kluczy, ponieważ Python porównuje krotki leksykograficznie, czyli pierw-
sze elementy krotek porównuje w pierwszej kolejności. Dzięki zastosowaniu wzorca DSU me-
toda lower wywoływana jest tylko n razy w czasie sortowania listy n ciągów znaków, co po-
zwala oszczędzić na tyle dużo czasu, że całkowicie rekompensuje konieczność początkowego
udekorowania listy i końcowego zdjęcia przygotowanych dekoracji.
Wzorzec DSU czasami znany jest też pod (nie do końca poprawną) nazwą transformacji
Schwartza, która jest nieprecyzyjną analogią do znanego idiomu języka Perl. Poprzez zasto-
sowanie takich porównań wzorzec DSU jest bardziej zbliżony do transformacji Guttmana-Roslera
(więcej informacji na stronie http://www.sysarch.com/perl/sort_paper.html).
Wzorzec DSU jest tak ważny, że w Pythonie 2.4 wprowadzono jego bezpośrednią obsługę. Do
metody sort można opcjonalnie przekazać nazywany argument key będący elementem wy-
woływalnym, używanym w czasie sortowania do uzyskania klucza sortowania każdego ele-
mentu listy. Jeżeli do funkcji sort zostanie przekazany taki argument, to automatycznie za-
cznie ona korzystać z wzorca DSU. Oznacza to, że w Pythonie 2.4 wywołanie string_list.sort
(key=str.lower) jest równoważne z wywołaniem funkcji case_insensitive_sort. Jedyna
różnica polega na tym, że metoda sort sortuje listę w miejscu (i zwraca wartość None), a funk-
cja case_insensitive_sort zwraca posortowana kopię listy, nie modyfikując przy tym orygi-
nału. Jeżeli chcielibyśmy, żeby funkcja case_insensitive_sort również sortowała listę w miej-
scu, to wystarczy wynik jej pracy przypisać do ciała wejściowej listy:
string_list[:] = [x[1] for x in auxiliary_list]
Z drugiej strony, jeżeli w Pythonie 2.4 chcielibyśmy uzyskać posortowana kopię listy, bez mo-
dyfikowania oryginału, to możemy skorzystać z wbudowanej funkcji sorted. Na przykład zapis:
for s in sorted(string_list, key=str.lower): print s
w Pythonie 2.4 wypisuje wszystkie ciągi znaków zapisane na liście string_list, która zostaje
posortowana bez uwzględniania różnic w wielkości liter, a jej oryginał pozostaje bez zmian.
228 |
Rozdział 5. Szukanie i sortowanie
Wykorzystanie w Pythonie 2.4 metody str.lower w argumencie key ogranicza nas do sor-
towania wyłącznie ciągów znaków (nie da się tak posortować na przykład ciągów znaków
Unikodu). Jeżeli wiemy, że będziemy sortować obiekty Unikodu, to należy posłużyć się para-
metrem key=unicode.lower. Jeżeli chcielibyśmy uzyskać funkcję, która działałaby tak samo
wobec prostych ciągów znaków i ciągów znaków Unikodu, to można zaimportować moduł
string i posłużyć się argumentem key=string.lower. Ewentualnie można też skorzystać z za-
pisu key=lambda s: s.lower().
Skoro musimy czasem sortować listy ciągów znaków w sposób nieuwzględniający różnic wiel-
kości liter, to równie dobrze możemy potrzebować słowników lub zbiorów stosujących klucze
nieuwzględniające różnic wielkości liter, a także list, w których podobnie zachowują się metody
index oraz count i inne. W takich sytuacjach potrzebny jest nam typ wywiedziony z klasy str,
który nie uwzględniałby różnic wielkości liter w operacjach porównywania i mieszania (ang.
hashing). Jest to zdecydowanie lepsze rozwiązanie w porównaniu z implementowaniem wielu
różnych typów kontenerowych i funkcji obejmujących przedstawioną funkcję. Sposób imple-
mentowania takiego typu podawany był już w recepturze 1.24.
Zobacz również
Zbiór często zadawanych pytań (dostępny na stronie http://www.python.org/cgi-bin/faqw.py?req=
show file=faq04.051.htp. Recepturę 5.3. Podręcznik Library Reference Pythona 2.4 w częściach opi-
sujących wbudowaną funkcję sorted oraz parametr key metod sort i sorted. Recepturę 1.24.
5.3. Sortowanie listy obiektów
na podstawie ich atrybutów
Pomysłodawcy: Yakov Markovitch, Nick Perkins
Problem
Musimy posortować listę obiektów według wartości jednego z atrybutów tych obiektów.
Rozwiązanie
Tutaj również doskonale sprawdza się wzorzec DSU:
def sort_by_attr(seq, attr):
intermed = [ (getattr(x, attr), i, x) for i, x in enumerate(seq) ]
intermed.sort()
return [ x[-1] for x in intermed ]
def sort_by_attr_inplace(lst, attr):
lst[:] = sort_by_attr(lst, attr)
W Pythonie 2.4, w którym wzorzec DSU został wbudowany w język, kod ten może być jeszcze
krótszy i szybszy:
import operator
def sort_by_attr(seq, attr):
return sorted(seq, key=operator.attrgetter(attr))
def sort_by_attr_inplace(lst, attr):
lst.sort(key=operator.attrgetter(attr))
5.3. Sortowanie listy obiektów na podstawie ich atrybutów
|
229
Analiza
Sortowanie listy obiektów według określonego atrybutu najlepiej wykonuje się za pomocą wzor-
ca DSU omawianego w poprzedniej recepturze 5.2. W Pythonie 2.3 i 2.4 nie jest on już po-
trzebny do tworzenia stabilnego sortowania, co było konieczne w poprzednich wersjach ję-
zyka (od wersji 2.3 algorytm sortowania stosowany w Pythonie zawsze jest stabilny), a mimo
to inne zalety wzorca DSU nadal są niepodważalne.
W ogólnym przypadku i z wykorzystaniem najlepszego algorytmu sortowanie ma złożoność
O(n log n) (w formułach matematycznych taki zapis oznacza, że wartości n i log n są mno-
żone). Siła wzorca DSU polega na wykorzystaniu wyłącznie wbudowanych w Pythona (i przez
to najszybszych) mechanizmów porównania, przez co maksymalnie przyspieszana jest ta część
wyrażenia O(n log n), która zabiera najwięcej czasu w operacji sortowania sekwencji o bardzo
dużej długości. Początkowy krok dekorowania, w którym przygotowywana jest pomocnicza lista
krotek, oraz końcowy krok usuwania dekoracji, w którym z posortowanej listy krotek wydo-
bywane są właściwe informacje, oba mają złożoność tylko O(n). Oznacza to, że drobne nie-
dociągnięcia w tych dwóch krokach będą miały nikły wpływ na sortowanie list z wielką liczbą
elementów, a w przypadku niewielkich list wpływ tych kroków również będzie względnie
niewielki.
Notacja O( )
Najbardziej użyteczny sposób określania wydajności danego algorytmu polega na wykorzy-
staniu tak zwanej analizy lub notacji wielkiego O (litera O oznacza po angielsku „order”, czyli
„rząd”). Dokładne objaśnienia dotyczące tej notacji znaleźć można na stronie http://
pl.wikipedia.org/wiki/Notacja_du C5 BCego_O. Tutaj podamy tylko krótkie podsumowanie.
Jeżeli przyjrzymy się algorytmom stosowanym na danych wejściowych o rozmiarze N, to dla
odpowiednio dużych wartości N (duże ilości danych wejściowych sprawiają, że wydajność
danego rozwiązania staje się sprawą krytyczną) czas ich działania może być określany jako
proporcjonalny do pewnej funkcji wartości N. Oznacza się to za pomocą notacji takiej jak
O(N) (czas pracy algorytmu jest proporcjonalny do N; przetwarzanie dwukrotnie większego
zbioru danych zajmuje dwa razy więcej czasu, a przetwarzanie zbioru dziesięciokrotnie więk-
2)
szego zajmuje dziesięć razy więcej czasu; inna nazwa tej notacji to złożoność liniowa), O(N
(czas pracy algorytmu jest proporcjonalny do kwadratu N; przetwarzanie dwukrotnie więk-
szego zbioru danych zajmuje cztery razy więcej czasu, a przetwarzanie zbioru dziesięciokrot-
nie większego zajmuje sto razy więcej czasu; inna nazwa tej notacji to złożoność kwadratowa) itd.
Często będziemy natykać się też na zapis O(N log N), który oznacza algorytm szybszy niż
O(N
2), ale wolniejszy od algorytmu O(N).
Najczęściej ignorowane są stałe proporcji (przynajmniej w rozważaniach teoretycznych), po-
nieważ zazwyczaj zależą one od takich czynników jak częstotliwość zegara w naszym kom-
puterze, a nie od samego algorytmu. Jeżeli zastosujemy dwa razy szybszy komputer, to ca-
łość będzie trwała o połowę krócej, ale nie zmieni to wyników porównań poszczególnych
algorytmów.
W tej recepturze w każdej krotce będącej elementem listy intermed umieszczamy indeks i
przed odpowiadającym mu elementem x (x jest i-tym elementem sekwencji seq). W ten spo-
sób upewniamy się, że dowolne dwa elementy sekwencji seq nie będą porównywane bezpo-
średnio, nawet jeżeli mają taką samą wartość atrybutu attr, ponieważ w takiej sytuacji ich
indeksy będą miały różne wartości. W ten sposób wykonywane w Pythonie leksykograficzne
230 |
Rozdział 5. Szukanie i sortowanie
porównania krotek nigdy nie będą porównywać ostatnich elementów poszczególnych krotek
(czyli właściwych elementów sekwencji seq). Uniknięcie porównywania samych obiektów po-
zwala nam uniknąć wykonywania niezwykle powolnych porównań, a nawet prób wykonania
porównań niedozwolonych. Na przykład moglibyśmy sortować liczby zespolone według ich
części rzeczywistej (atrybut real); przy próbie bezpośredniego porównania takich liczb po-
wstałby wyjątek, ponieważ w liczbach zespolonych nie ma zdefiniowanej takiej operacji. Dzięki
obostrzeniom opisywanym w tym akapicie takie porównanie nigdy nie nastąpi i w związku
z tym sortowanie przebiegnie bezproblemowo.
Jak już wspominaliśmy wcześniej w recepturze 5.2, w Pythonie 2.4 wzorzec DSU obsługiwany
jest w samym języku. Do metody sort można przekazywać opcjonalny argument nazywany
key, który jest wywoływany na rzecz każdego elementu sortowanej listy i ma zwrócić klucz
sortowania. Moduł operator będący częścią biblioteki standardowej udostępnia dwie nowe
funkcje — attrgetter i itemgetter — przeznaczone do zwracania elementów wywoływalnych
nadających się do omówionych wyżej zastosowań. Dzięki temu w Pythonie 2.4 idealnym roz-
wiązaniem naszego problemu staje się poniższy kod:
import operator
seq.sort(key=operator.attrgetter(attr))
Podany kod pozwala posortować listę w miejscu i to z niesamowitą prędkością — na moim
komputerze sortowanie było trzykrotnie szybsze niż ta sama operacja wykonana w Pythonie 2.3
za pomocą funkcji prezentowanej w rozwiązaniu tej receptury. Jeżeli potrzebna jest nam po-
sortowana kopia listy, bez modyfikowania jej oryginału, to w Pythonie 2.4 możemy wyko-
rzystać nową, wbudowaną funkcję sorted.
sorted_copy = sorted(seq, key=operator.attrgetter(attr))
Nie jest to aż tak szybkie jak sortowanie w miejscu, ale ten ostatni kod jest nadal ponad 2,5 razy
szybszy od funkcji przedstawianej w rozwiązaniu receptury. Przekazując opcjonalny argument
nazywany key w Pythonie 2.4, uzyskujemy też pewność, że w czasie sortowania elementy listy
nie zostaną porównane bezpośrednio ze sobą, więc nie musimy tworzyć żadnych dodatkowych
zabezpieczeń. Co więcej, posortowana lista na pewno będzie stabilna.
Zobacz również
Recepturę 5.2. Podręcznik Library Reference z Pythona 2.4 w części opisującej wbudowaną funk-
cję sorted, funkcje attrgetter i itemgetter z modułu operator oraz parametr key funkcji
sort i sorted.
5.4. Sortowanie kluczy lub indeksów
na podstawie związanych z nimi wartości
Pomysłodawcy: John Jensen, Fred Bremmer, Nick Coghlan
Problem
Musimy zliczyć wystąpienia różnych elementów i zaprezentować te elementy w kolejności czę-
stotliwości występowania — na przykład w celu przygotowania histogramu.
5.4. Sortowanie kluczy lub indeksów na podstawie związanych z nimi wartości
|
231
Rozwiązanie
Histogramy niezależnie od swojego zastosowania przy tworzeniu grafiki tworzone są przez
zliczanie wystąpień elementów (co nietrudno jest wykonać w przypadku list lub słowników
w Pythonie) i sortowanie list lub indeksów w kolejności odpowiadającej wyznaczonym warto-
ściom. Oto klasa wywiedziona z klasy dict, która uzupełniona została o dwie metody:
class hist(dict):
def add(self, item, increment=1):
dodaje wartość increment do pozycji elementu item
self[item] = increment + self.get(item, 0)
def counts(self, reverse=False):
zwraca listę kluczy posortowaną zgodnie z odpowiadającymi im wartościami
aux = [ (self[k], k) for k in self ]
aux.sort()
if reverse: aux.reverse()
return [k for v, k in aux]
Jeżeli zliczane elementy mogą być modelowane jako niewielkie liczby całkowite z określone-
go zakresu i wyniki zliczania elementów chcemy przechowywać na liście, to można zastoso-
wać bardzo podobne rozwiązanie:
class hist1(list):
def __init__(self, n):
inicjalizacja listy do zliczania wystąpień n różnych elementów
list.__init__(self, n*[0])
def add(self, item, increment=1):
dodaje wartość increment do pozycji elementu item
self[item] += increment
def counts(self, reverse=False):
zwraca listę indeksów posortowaną zgodnie z odpowiadającymi im wartościami
aux = [ (v, k) for k, v in enumerate(self) ]
aux.sort()
if reverse: aux.reverse()
return [k for v, k in aux]
Analiza
Metoda add klasy hist jest przykładem wykorzystania typowego dla Pythona idiomu prze-
znaczonego do zliczania dowolnych (choć unikalnych) elementów. W klasie hist1, zbudowanej
na podstawie klasy list, stosowane jest inne rozwiązanie, polegające na wpisywaniu w spe-
cjalnej metodzie __init__ wartości 0 do wszystkich elementów listy, dzięki czemu metoda add
może przyjąć prostszą postać.
Metoda counts tworzy listę kluczy lub indeksów posortowanych w kolejności wyznaczanej przez
powiązane z nimi wartości. Problem jest bardzo podobny w obu klasach (hist i hist1), dlatego
podane rozwiązania są niemal identyczne — w obu wykorzystywany jest wzorzec DSU oma-
wiany w recepturach 5.2 i 5.3. Jeżeli w naszym programie chcielibyśmy skorzystać z obu klas,
to możemy wykorzystać ich podobieństwo i wydzielić części wspólne do pomocniczej funkcji
_sorted_keys:
def _sorted_keys(container, keys, reverse):
zwraca listę keys posortowaną zgodnie z wartościami z parametru container
aux = [ (container[k], k) for k in keys ]
aux.sort()
if reverse: aux.reverse()
return [k for v, k in aux]
232
|
Rozdział 5. Szukanie i sortowanie
Następnie metody counts obu klas można zaimplementować jako opakowania zaprezentowanej
funkcji _sorted_keys:
class hist(dict):
## ...
def counts(self, reverse=False):
return _sorted_keys(self, self, reverse)
class hist1(list):
## ...
def counts(self, reverse=False):
return _sorted_keys(self, xrange(len(self)), reverse)
W Pythonie 2.4 wzorzec DSU jest tak ważny, że (jak pokazano w recepturach 5.2 i 5.3) metoda
sort z obiektów list oraz nowa, wbudowana funkcja sorted oferują bardzo szybką implemen-
tację tego wzorca. Dzięki temu w Pythonie 2.4 funkcja _sorted_keys może być jeszcze prostsza
i szybsza:
def _sorted_keys(container,
Pobierz darmowy fragment (pdf)
