Darmowy fragment publikacji:
Tytuł oryginału: Beautiful Code: Leading Programmers Explain How They Think
Tłumaczenie: Łukasz Piwko (wstęp, rozdz. 1 – 16),
Marcin Rogóż (rozdz. 17 – 33),
Projekt okładki: Radosław Pazdrijowski i Mateusz Obarek
ISBN: 978-83-283-3477-9
© Helion SA 2008, 2017
Authorized translation of the English edition of Beautiful Code © 2007 O’Reilly Media, Inc.
This translation is published and sold by permission of O’Reilly Media, Inc., the owner of all rights to
publish and sell the same.
All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,
electronic or mechanical, including photocopying, recording or by any information storage retrieval system,
without permission from the Publisher.
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,
fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje
naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich
właścicieli.
Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były
kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane
z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION
nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji
zawartych w książce.
Fotografia na okładce została wykorzystana za zgodą iStockPhoto Inc.
Wydawnictwo HELION
ul. Kościuszki 1c, 44-100 GLIWICE
tel. 032 231 22 19, 032 230 98 63
e-mail: helion@helion.pl
WWW: http://helion.pl (księgarnia internetowa, katalog książek)
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie/szpppv
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
Pliki z przykładami omawianymi w książce można znaleźć pod adresem:
ftp://ftp.helion.pl/przyklady/szpppv.zip
Printed in Poland.
• Kup książkę
• Poleć książkę
• Oceń książkę
• Księgarnia internetowa
• Lubię to! » Nasza społeczność
Słowo wstępne
Wstęp
1. Wyrażenia regularne
Programowanie w praktyce
Implementacja
Omówienie
Alternatywy
Rozszerzanie
Podsumowanie
2. Edytor delty w Subversion — interfejs jako ontologia
Kontrola wersji i transformacja drzewa
Prezentacja różnic pomiędzy drzewami
Interfejs edytora delty
Ale czy to jest sztuka?
Abstrakcja jako sport widowiskowy
Wnioski
3. Najpiękniejszy kod, którego nigdy nie napisałem
Najpiękniejszy kod, jaki kiedykolwiek napisałem
Coraz więcej za pomocą coraz mniejszych środków
Perspektywa
Co to jest pisanie
Zakończenie
Podziękowania
4. Wyszukiwanie
Na czas
Problem — dane z pamiętnika sieciowego
Problem — kto zażądał, czego i kiedy
Wyszukiwanie na dużą skalę
Podsumowanie
S P I S T R E Ś C I
13
15
19
20
21
22
24
25
27
29
30
34
35
40
43
45
47
47
49
54
57
57
59
61
61
62
70
75
77
5
Poleć książkęKup książkę5. Poprawny, piękny, szybki (w takiej kolejności)
— lekcje z projektowania weryfikatorów XML
Znaczenie walidacji XML
Problem
Wersja 1. Naiwna implementacja
Wersja 2. Imitacja gramatyki BNF O(N)
Wersja 3. Pierwsza optymalizacja O(log N)
Wersja 4. Druga optymalizacja — nie sprawdzaj dwa razy
Wersja 5. Trzecia optymalizacja O(1)
Wersja 6. Czwarta optymalizacja — buforowanie
Morał
6. Framework for Integrated Test — piękno poprzez delikatność
Acceptance Testing Framework w trzech klasach
Wyzwanie zaprojektowania środowiska
Otwarte środowisko
Jak prosty może być parser HTML
Podsumowanie
7. Piękne testy
To niesforne wyszukiwanie binarne
Wstęp do JUnit
Rozprawić się z wyszukiwaniem binarnym
Podsumowanie
8. Generowanie w locie kodu do przetwarzania obrazów
9. Kolejność wykonywania operatorów
JavaScript
Tablica symboli
Tokeny
Kolejność
Wyrażenia
Operatory wrostkowe
Operatory przedrostkowe
Operatory przypisania
Stałe
Zakres
Instrukcje
Funkcje
Literały tablicowe i obiektowe
Rzeczy do zrobienia i przemyślenia
10. Poszukiwanie szybszych metod zliczania bitów w stanie wysokim
Podstawowe metody
Dziel i zwyciężaj
Inne metody
6
S P I S T R E Ś C I
79
79
80
82
83
84
85
87
91
93
95
96
98
99
100
103
105
106
109
111
122
125
147
148
149
150
151
152
152
154
155
155
156
157
160
161
162
163
164
165
167
Poleć książkęKup książkęSuma i różnica liczb ustawionych bitów w dwóch słowach
Porównywanie liczby ustawionych bitów w dwóch słowach
Zliczanie jedynek w tablicy
Zastosowania
11. Bezpieczna komunikacja — technologia wolności
Początki
Rozwikłać tajemnicę bezpiecznego przesyłania wiadomości
Klucz to użyteczność
Podstawa
Zestaw testów
Działający prototyp
Oczyść, podłącz i używaj
Hakowanie w Himalajach
Niewidoczne ruchy ręką
Prędkość ma znaczenie
Prywatność komunikacji dla praw jednostki
Hakowanie cywilizacji
12. Hodowanie pięknego kodu w języku BioPerl
BioPerl i moduł Bio::Graphics
Proces projektowania modułu Bio::Design
Rozszerzanie modułu Bio::Graphics
Wnioski i lekcje
13. Projekt programu Gene Sorter
Interfejs użytkownika programu Gene Sorter
Podtrzymywanie dialogu z użytkownikiem przez internet
Nieco polimorfizmu
Filtrowanie w celu znalezienia odpowiedniego genu
Ogólna teoria pięknego kodu
Podsumowanie
14.
Jak elegancki kod ewoluuje wraz ze sprzętem — przypadek eliminacji Gaussa
Wpływ architektury komputerów na algorytmy macierzowe
Metoda dekompozycyjna
Prosta wersja
Podprocedura DGEFA biblioteki LINPACK
Procedura LAPACK DGETRF
Rekursywna dekompozycja LU
Procedura ScaLAPACK PDGETRF
Wielowątkowość w systemach wielordzeniowych
Słowo na temat analizy błędów i liczby operacji
Przyszłe kierunki badań
Literatura zalecana
169
169
170
175
177
178
180
181
184
188
189
190
194
199
201
202
203
205
206
210
228
232
235
236
237
239
242
243
246
247
248
250
251
252
255
257
260
265
267
268
269
S P I S T R E Ś C I
7
Poleć książkęKup książkę15. Długoterminowe korzyści z pięknego projektu
Moje wyobrażenie o pięknym kodzie
Wprowadzenie do biblioteki CERN
Zewnętrzne piękno
Piękno wewnętrzne
Podsumowanie
16. Model sterowników jądra systemu Linux — korzyści płynące ze współpracy
17.
18.
Skromne początki
Redukcja do jeszcze mniejszych rozmiarów
Skalowanie do tysięcy urządzeń
Małe, luźno połączone obiekty
Inny poziom pośredniości
Od kodu do wskaźników
Od argumentów funkcji do wskaźników argumentów
Od systemów plików do warstw systemów plików
Od kodu do języka konkretnej domeny
Multipleksacja i demultipleksacja
Na zawsze warstwy?
Implementacja słownika w Pythonie — być wszystkim dla wszystkich
Wewnątrz słownika
Warunki specjalne
Kolizje
Zmiana rozmiaru
Iteracje i zmiany dynamiczne
Podsumowanie
Podziękowania
19. Wielowymiarowe iteratory w NumPy
Kluczowe wyzwania w operacjach na N-wymiarowych tablicach
Modele pamięci dla tablicy N-wymiarowej
Początki iteratora NumPy
Interfejs iteratora
Wykorzystanie iteratora
Podsumowanie
20. System korporacyjny o wysokim stopniu niezawodności dla misji Mars Rover NASA
Misja i Collaborative Information Portal
Wymagania misji
Architektura systemu
Studium przypadku — usługa strumieniowa
Niezawodność
Solidność
Podsumowanie
8
S P I S T R E Ś C I
271
271
272
273
278
284
285
286
290
293
294
297
297
300
303
305
307
308
311
313
314
316
317
318
319
319
321
322
323
324
331
332
336
337
338
339
340
343
346
353
355
Poleć książkęKup książkę21. ERP5 — projektowanie maksymalnej giętkości
Ogólne cele ERP
ERP5
Podstawowa platforma Zope
Założenia ERP5 Project
Pisanie kodu dla ERP5 Project
Podsumowanie
22.
Łyżka dziegciu
23. Programowanie rozproszone z zastosowaniem MapReduce
Motywujący przykład
Model programistyczny MapReduce
Inne przykłady MapReduce
Implementacja rozproszonego MapReduce
Rozszerzenia modelu
Wnioski
Literatura zalecana
Podziękowania
Dodatek: przykład algorytmu zliczającego słowa
24. Piękna współbieżność
Prosty przykład: konta bankowe
Pamięć transakcyjna STM
Problem Świętego Mikołaja
Refleksje na temat Haskella
Wnioski
Podziękowania
25. Abstrakcja składniowa — rozszerzenie syntax-case
Krótkie wprowadzenie do syntax-case
Algorytm rozwijania
Przykład
Wnioski
26. Architektura oszczędzająca nakłady
— obiektowy framework dla oprogramowania sieciowego
Przykładowa aplikacja — usługa rejestrowania
Zorientowany obiektowo projekt frameworku serwera rejestrowania
Implementacja sekwencyjnych serwerów rejestrowania
Implementacja współbieżnych serwerów rejestrowania
Wnioski
27.
Integracja partnerów biznesowych z wykorzystaniem architektury REST
Tło projektu
Udostępnianie usług klientom zewnętrznym
357
358
358
360
364
365
368
371
389
389
392
393
394
398
399
400
400
400
403
404
406
414
422
423
424
425
429
431
443
445
447
449
451
457
461
467
469
470
470
S P I S T R E Ś C I
9
Poleć książkęKup książkęPrzekazywanie usługi za pomocą wzorca fabryki
Wymiana danych z użyciem protokołów e-biznesowych
Wnioski
28. Piękne debugowanie
Debugowanie debugera
Systematyczny proces
Szukany problem
Automatyczne wyszukiwanie przyczyny awarii
Debugowanie delta
Minimalizacja wejścia
Polowanie na usterkę
Problem prototypu
Wnioski
Podziękowania
Literatura zalecana
29. Traktując kod jako esej
30. Gdy ze światem łączy cię tylko przycisk
Podstawowy model projektu
Interfejs wejściowy
Wydajność interfejsu użytkownika
Pobieranie
Przyszłe kierunki rozwoju
31. Emacspeak — kompletne dźwiękowe środowisko pracy
Tworzenie wyjścia mówionego
Włączanie mowy w Emacsie
Bezbolesny dostęp do informacji online
Podsumowanie
Podziękowania
32. Kod w ruchu
O byciu „podręcznikowym”
Podobne wygląda podobnie
Niebezpieczeństwa wcięć
Poruszanie się po kodzie
Wykorzystywane przez nas narzędzia
Burzliwa przeszłość DiffMerge
Wnioski
Podziękowania
Literatura zalecana
1 0
S P I S T R E Ś C I
473
475
480
481
482
483
485
486
488
490
490
493
493
494
494
495
501
502
505
518
518
519
521
522
523
534
541
544
545
546
547
548
549
550
552
554
554
554
Poleć książkęKup książkę33. Pisanie programów dla Księgi
Niekrólewska droga
Ostrzeżenie dla nawiasofobów
Trzy w rzędzie
Śliskie nachylenie
Nierówność trójkąta
Meandrowanie
„No przecież!”, znaczy się „Aha!”
Wnioski
Zalecana literatura
Posłowie
Autorzy
Skorowidz
557
558
558
559
561
563
565
566
567
568
571
573
583
S P I S T R E Ś C I
1 1
Poleć książkęKup książkę1 2
S P I S T R E Ś C I
Poleć książkęKup książkęR O Z D Z I A Ł 3 .
NajpiÚkniejszy kod,
którego nigdy nie napisaïem
Jon Bentley
K
IEDY¥ SYSZAEM, ¿E PEWIEN MISTRZ PROGRAMOWANIA dawał taką oto pochwałę: „On dodaje funkcje
poprzez usuwanie kodu”. Antoine Saint-Exupéry, francuski pisarz i lotnik, wyraził tę myśl bardziej
ogólnie: „Projektant może uznać, że osiągnął perfekcję, nie wtedy, kiedy nie pozostało już nic do
dodania, ale wtedy, gdy nie można już nic odjąć”. W oprogramowaniu najpiękniejszego kodu, naj-
piękniejszych funkcji i najpiękniejszych programów czasami w ogóle nie ma.
Oczywiście trudno dyskutować o rzeczach, których nie ma. Ten rozdział jest próbą wykonania tego
przytłaczającego zadania poprzez zaprezentowanie nowatorskiej analizy czasu pracy klasycznego
programu Quicksort. Pierwszy podrozdział zawiera ogólny opis programu z osobistego punktu
widzenia. Następny — to już treść właściwa tego rozdziału. Zaczniemy od dodania jednego licznika
do programu, a następnie będziemy manipulować kodem, żeby stawał się coraz mniejszy i potęż-
niejszy, aż tylko kilka wierszy kodu w pełni będzie pokrywać jego średni czas działania. Trzeci pod-
rozdział podsumowuje techniki i zawiera niezwykle zwięzłą analizę kosztów binarnych drzew po-
szukiwań. Wskazówki znajdujące się w dwóch ostatnich podrozdziałach, oparte na spostrzeżeniach
zawartych w tym tekście, pomogą nam pisać bardziej eleganckie programy.
NajpiÚkniejszy kod, jaki kiedykolwiek napisaïem
Kiedy Greg Wilson przedstawił mi pomysł na tę książkę, zadałem sobie pytanie, jaki był najpięk-
niejszy kod, który napisałem. Po prawie całym dniu kołatania się tego pytania w mojej głowie zda-
łem sobie sprawę, że ogólna odpowiedź jest niezwykle prosta: Quicksort. Jednak w zależności od
tego, jak precyzyjnie sformułuje się to pytanie, można odpowiedzieć na nie na trzy sposoby.
4 7
Poleć książkęKup książkęTematem mojej rozprawy naukowej były algorytmy typu „dziel i zwyciężaj”. Dzięki niej odkryłem,
że algorytm Quicksort napisany przez programistę o nazwisku C. A. R. Hoare (Quicksort, „Com-
puter Journal” nr 5) jest niezaprzeczalnie dziadkiem ich wszystkich. Jest to piękny algorytm roz-
wiązujący podstawowy problem, który można zaimplementować w eleganckim kodzie. Zawsze go
uwielbiałem, ale trzymałem się z dala od jego najgłębiej zagnieżdżonej pętli. Kiedyś spędziłem dwa
dni na debugowaniu programu opartego na niej i całymi latami kopiowałem skrupulatnie kod za
każdym razem, kiedy musiałem wykonać podobne zadanie. Rozwiązywał moje problemy, ale nigdy
tak naprawdę go nie rozumiałem.
W końcu nauczyłem się od Nico Lomuto eleganckiej metody dzielenia i nareszcie mogłem napisać
program Quicksort, który byłby dla mnie zrozumiały, a nawet umiałbym udowodnić, że jest popraw-
ny. Spostrzeżenie Williama Strunka Jr., że „piszący szybko piszą zwięźle”, ma zastosowanie zarów-
no do kodu, jak i języka angielskiego. W związku z tym, idąc za jego radą, „pomijałem zbędne sło-
wa” (The Elements of Style). Udało mi się zredukować 40 wierszy kodu do równo 12. A więc jeśli
pytanie brzmi: „Jaki jest najpiękniejszy mały fragment kodu, jaki w życiu napisałem?”, moja odpo-
wiedź to: Quicksort z mojej książki pod tytułem Perełki oprogramowania1. Ta funkcja Quicksort, na-
pisana w języku C, została przedstawiona na listingu 3.1. W następnym podrozdziale zajmiemy się
dalszym dostrajaniem i badaniem tego kodu.
L I S T I N G 3 . 1 . Funkcja Quicksort
void quicksort(int l, int u)
{ int i, m;
if (l = u) return;
swap(l, randint(l, u));
m = l;
for (i = l+1; i = u; i++)
if (x[i] x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
Kod ten sortuje globalną tablicę x[n], kiedy jest wywoływany z argumentami quicksort(0, n-1).
Oba argumenty tej funkcji są indeksami podtablicy, która ma być posortowana. l oznacza dolną
granicę (ang. lower), a u — górną (ang. upper). Wywołanie funkcji swap(i,j) powoduje zamianę
zawartości elementów x[i] i x[j]. Pierwsza funkcja swap losowo wybiera element podziału, który
w taki sam sposób jest wybierany spomiędzy l i u.
Książka Perełki oprogramowania zawiera szczegółowy opis i dowód poprawności funkcji quick-
sort. Zakładam, że Czytelnik zna algorytm Quicksort na poziomie tamtego opisu i najbardziej
podstawowych książek o algorytmach.
Jeśli zmienimy pytanie na: „Jaki jest najpiękniejszy powszechnie używany fragment kodu, który
napisałeś?”, moja odpowiedź ponownie będzie brzmieć Quicksort. W artykule napisanym razem
1 Jon Bentley, Perełki oprogramowania, wyd. 2, Wydawnictwa Naukowo-Techniczne, Warszawa 2001 — przyp. red.
4 8
R O Z D Z I A Ł 3 .
Poleć książkęKup książkęz M. D. McIlroyem2 omawiamy poważny błąd związany z wydajnością w nieco sędziwej już funkcji
systemu Unix — qsort. Wzięliśmy się za pisanie nowej funkcji sort dla biblioteki języka C, biorąc
pod uwagę wiele różnych algorytmów do wykorzystania, w tym Merge Sort i Heap Sort. Po porów-
naniu kilku możliwości implementacji zdecydowaliśmy się na wersję z algorytmem Quicksort. We
wspomnianym artykule wyjaśniamy, w jaki sposób napisaliśmy nową funkcję, która była bardziej
przejrzysta, szybsza i solidniejsza niż jej konkurentki — po części z racji swoich niewielkich roz-
miarów. Mądra rada Gordona Bella okazała się słuszna: „Najtańsze, najszybsze i najbardziej nieza-
wodne komponenty systemu komputerowego to te, których nie ma”. Funkcja ta jest już powszech-
nie używana od ponad dziesięciu lat i nie zgłoszono jeszcze żadnych błędów.
Biorąc pod uwagę korzyści płynące ze zmniejszania objętości kodu, zadałem sobie w końcu trzeci
wariant pytania zamieszczonego na początku tego rozdziału: „Jaki jest najpiękniejszy fragment kodu,
którego nigdy nie napisałem?”. Jak udało mi się osiągnąć bardzo dużo za pomocą tak małych środ-
ków? Odpowiedź i tym razem jest związana z Quicksort, a konkretnie z analizą jego wydajności.
O tym opowiadam w kolejnym podrozdziale.
Coraz wiÚcej za pomocÈ coraz mniejszych Ărodków
Quicksort to bardzo elegancki algorytm, który nadaje się do wykonywania wnikliwych analiz. Około ro-
ku 1980 odbyłem wspaniałą rozmowę z Tonym Hoarem na temat historii jego algorytmu. Powiedział
mi, że kiedy go opracował, wydawało mu się, iż jest on zbyt prosty do opublikowania. Napisał więc
tylko swój klasyczny artykuł Quicksort, kiedy udało mu się przeanalizować jego oczekiwany czas
wykonywania.
Łatwo się zorientować, że posortowanie tablicy zawierającej n elementów algorytmowi Quicksort
może w najgorszym przypadku zająć około n2 czasu. W najlepszym natomiast przypadku wybiera
on wartość średnią jako element dzielący, dzięki czemu sortuje tablicę za pomocą około
po-
równań. A więc ilu średnio porównań potrzebuje w przypadku losowej tablicy n różnych wartości?
lg(n
n u
)
Analiza tego problemu dokonana przez Hoare’a jest piękna, ale niestety wykraczająca poza wiedzę
matematyczną wielu programistów. Kiedy uczyłem zasady działania algorytmu Quicksort studen-
tów, martwiło mnie, że wielu z nich nie mogło zrozumieć dowodu, nawet mimo mojego szczerego
wysiłku. Spróbujemy teraz podejść do tego zagadnienia w eksperymentalny sposób. Zaczniemy od
programu Hoare’a i stopniowo dojdziemy do analizy zbliżonej do jego własnej.
Naszym zadaniem jest zmodyfikować kod z listingu 3.1 przedstawiającego randomizujący kod
Quicksort, aby drogą analizy sprawdzał średnią liczbę porównań potrzebnych do posortowania ta-
blicy zawierającej unikatowe elementy. Spróbujemy też uzyskać jak najwięcej przy użyciu jak naj-
mniejszej ilości kodu, czasu i miejsca.
Aby określić średnią liczbę porównań, najpierw rozszerzymy funkcjonalność programu o możli-
wość ich zliczania. W tym celu inkrementujemy zmienną comps przed porównaniem w wewnętrznej
pętli (listing 3.2).
2 J. Bentley, M. D. McIlroy, Engineering a sort function, „Software-Practice and Experience”, Vol. 23, No. 11 — przyp. red.
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
4 9
Poleć książkęKup książkęL I S T I N G 3 . 2 . WewnÚtrzna pÚtla algorytmu Quicksort przystosowana do zliczania porównañ
for (i = l+1; i = u; i++) {
comps++;
if (x[i] x[l])
swap(++m, i);
}
Jeśli uruchomimy program tylko dla jednego n, dowiemy się, ile porównań to jedno uruchomienie
potrzebuje. Jeśli powtórzymy tę operację wielokrotnie dla wielu wartości n i przeprowadzimy
statystyczną analizę wyników, uzyskamy wartość średnią. Algorytm Quicksort potrzebuje około
1,4
porównań do posortowania n elementów.
ng
(
n u
)
l
Nie jest to wcale zły sposób na uzyskanie wglądu w działanie programu. Dzięki 13 wierszom kodu
i kilku eksperymentom można sporo odkryć. Znane powiedzenie przypisywane pisarzom takim jak
Blaise Pascal i T. S. Eliot brzmi: „Gdybym miał więcej czasu, napisałbym Ci krótszy list”. My mamy
czas, więc poeksperymentujemy trochę z kodem, aby napisać krótszy (i lepszy) program.
Zagramy w przyspieszanie eksperymentu, próbując zwiększyć statystyczną dokładność i wgląd w dzia-
łanie programu. Jako że wewnętrzna pętla wykonuje dokładnie u-l porównań, możemy nieco przy-
spieszyć działanie programu, zliczając te porównania za pomocą pojedynczej operacji poza pętlą.
Po tej zmianie algorytm Quicksort wygląda jak na listingu 3.3.
L I S T I N G 3 . 3 . Algorytm Quicksort po przeniesieniu inkrementacji na zewnÈtrz pÚtli
comps += u-l;
for (i = l+1; i = u; i++)
if (x[i] x[l])
swap(++m, i);
Program ten sortuje tablicę i jednocześnie sprawdza liczbę potrzebnych porównań. Jeśli jednak na-
szym celem jest tylko zliczenie porównań, nie musimy sortować tablicy. Na listingu 3.4 zostało
usunięte prawdziwe sortowanie i pozostał tylko szkielet różnych wywołań wykonywanych przez
program.
L I S T I N G 3 . 4 . Szkielet algorytmu Quicksort zredukowany do zliczania
void quickcount(int l, int u)
{ int m;
if (l = u) return;
m = randint(l, u);
comps += u-l;
quickcount(l, m-1);
quickcount(m+1, u);
}
Program ten działa dzięki losowemu wybieraniu przez Quicksort elementu dzielącego i dzięki za-
łożeniu, że wszystkie elementy są unikatowe. Jest on wykonywany w czasie proporcjonalnym do n.
Podczas gdy program z listingu 3.3 wymagał proporcjonalnej do n ilości miejsca, teraz została ona
zredukowana do stosu rekurencji, który średnio jest proporcjonalny do
ng
(
.
)
l
5 0
R O Z D Z I A Ł 3 .
Poleć książkęKup książkęMimo że indeksy (l i u) tablicy są niezbędne w prawdziwym programie, w tej wersji szkieletu nie
mają znaczenia. Można je zastąpić jedną liczbą całkowitą (n), która będzie określała rozmiar pod-
tablicy do posortowania (listing 3.5).
L I S T I N G 3 . 5 . Szkielet algorytmu Quicksort z jednym argumentem okreĂlajÈcym rozmiar
void qc(int n)
{ int m;
if (n = 1) return;
m = randint(1, n);
comps += n-1;
qc(m-1);
qc(n-m);
}
Bardziej naturalne teraz będzie przetworzenie tej procedury do postaci funkcji zliczającej porów-
nania (ang. comparison count — cc), która zwraca liczbę porównań użytych przez jedno wykona-
nie algorytmu Quicksort. Funkcję tę przedstawia listing 3.6.
L I S T I N G 3 . 6 . Szkielet algorytmu Quicksort zaimplementowany jako funkcja
int cc(int n)
{ int m;
if (n = 1) return 0;
m = randint(1, n);
return n-1 + cc(m-1) + cc(n-m);
}
Przykłady zamieszczone na listingach 3.4, 3.5 i 3.6 rozwiązują ten sam podstawowy problem i po-
trzebują na to tyle samo czasu i pamięci. Każda kolejna wersja ma poprawioną formę, dzięki czemu
jest nieco bardziej przejrzysta i zwięzła od poprzedniej.
Definiując paradoks wynalazcy (ang. inventor’s paradox), George Pólya oznajmia, że: „Bardziej
ambitny plan może mieć więcej szans na powodzenie”3. Spróbujemy teraz wykorzystać ten para-
doks w analizie Quicksort. Do tej pory zadawaliśmy sobie pytanie, ile porównań potrzebuje algorytm
Quicksort do posortowania tablicy zawierającej n elementów. Teraz zadamy bardziej ambitne pytanie:
ile średnio porównań potrzebuje algorytm Quicksort do posortowania losowej tablicy o rozmiarze
n? Możemy rozszerzyć kod z listingu 3.6, aby uzyskać pseudokod widoczny na listingu 3.7.
L I S T I N G 3 . 7 . ¥rednia liczba porównañ algorytmu Quicksort jako pseudokod
float c(int n)
if (n = 1) return 0
sum = 0
for (m = 1; m = n; m++)
sum += n-1 + c(m-1) + c(n-m)
return sum/n
Jeśli dane wejściowe zawierają maksymalnie jeden element, Quicksort nie wykonuje żadnych porów-
nań, jak w przykładzie z listingu 3.6. W przypadku n o większej wartości kod ten bierze pod uwagę każ-
dą wartość dzielącą (od pierwszego do ostatniego elementu — każdy jest równie prawdopodobny)
3 George Pólya, How to solve it, Princeton University Press, 1945 — przyp. red.
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
5 1
Poleć książkęKup książkęi określa koszt podziału w każdym z tych miejsc. Następnie kod oblicza sumę tych wartości (w ten
sposób rekursywnie rozwiązując jeden problem rozmiaru m-1 i jeden problem rozmiaru n-m) i dzieli
ją przez n, uzyskując średnią.
Gdybyśmy mogli obliczyć tę liczbę, nasze eksperymenty byłyby znacznie bardziej potężne. Zamiast
przeprowadzać wiele eksperymentów z jedną wartością n w celu oszacowania średniej, jeden ekspery-
ment wystarczyłby do uzyskania prawdziwej średniej. Niestety, ta potęga ma swoją cenę: program
działa w czasie proporcjonalnym do 3n (interesującym ćwiczeniem jest analiza tego czasu przy użyciu
technik opisanych w tym rozdziale).
Kod z listingu 3.7 potrzebuje właśnie tyle czasu, ponieważ oblicza pododpowiedzi wielokrotnie.
W takim przypadku można zastosować programowanie dynamiczne w celu zapisywania tych po-
dodpowiedzi, co pozwoli na uniknięcie ich ponownego obliczania. W tym przypadku wprowadzimy
tablicę t[N+1], w której element t[n] przechowuje c(n), i obliczymy jej wartości w kolejności ro-
snącej. N będzie oznaczać maksymalną wartość n, czyli rozmiar tablicy do posortowania. Rezultat
jest widoczny na listingu 3.8.
L I S T I N G 3 . 8 . Obliczenia algorytmu Quicksort przy uĝyciu programowania dynamicznego
t[0] = 0
for (n = 1; n = N; n++)
sum = 0
for (i = 1; i = n; i++)
sum += n-1 + t[i-1] + t[n-i]
t[n] = sum/n
Program ten jest z grubsza transkrypcją kodu z listingu 3.7, w której zastąpiono c(n) zapisem t[n]. Je-
go czas wykonywania jest proporcjonalny do N2, a ilość zajmowanego miejsca do N. Jedną z jego
zalet jest to, że po zakończeniu wykonywania tablica t zawiera rzeczywiste wartości średnie (a nie
przybliżoną wartość przykładowych średnich) dla elementów tablicy od 0 do N. Dzięki analizie tych
liczb można uzyskać informacje na temat funkcjonalnej formy spodziewanej liczby porównań wy-
konanych przez algorytm Quicksort.
Teraz uprościmy nasz program jeszcze bardziej. Najpierw przeniesiemy człon n-1 poza pętlę, jak
widać na listingu 3.9.
L I S T I N G 3 . 9 . Obliczenia Quicksort z kodem przeniesionym na zewnÈtrz pÚtli
t[0] = 0
for (n = 1; n = N; n++)
sum = 0
for (i = 1; i = n; i++)
sum += t[i-1] + t[n-i]
t[n] = n-1 + sum/n
Dalsze dostrajanie kodu będzie polegało na użyciu symetrii. Jeśli na przykład n wynosi 4, we-
wnętrzna pętla oblicza następującą sumę:
t[0]+t[3] + t[1]+t[2] + t[2]+t[1] + t[3]+t[0]
W tym szeregu par pierwsze elementy zwiększają się, podczas gdy mniejsze zmniejszają. Możemy
zatem sumę tę zapisać tak:
5 2
R O Z D Z I A Ł 3 .
Poleć książkęKup książkę2 * (t[0] + t[1] + t[2] + t[3])
Za pomocą tej symetrii otrzymamy algorytm widoczny na listingu 3.10.
L I S T I N G 3 . 1 0 . Obliczenia Quicksort przy uĝyciu symetrii
t[0] = 0
for (n = 1; n = N; n++)
sum = 0
for (i = 0; i n; i++)
sum += 2 * t[i]
t[n] = n-1 + sum/n
Kod ten jednak również nie jest w pełni efektywny, ponieważ wielokrotnie oblicza tę samą sumę.
Zamiast dodawać wszystkie poprzednie człony, możemy zmienną sum zainicjalizować poza pętlą
i dodać następny człon. Rezultat jest widoczny na listingu 3.11.
L I S T I N G 3 . 1 1 . Obliczenia Quicksort z usuniÚtÈ wewnÚtrznÈ pÚtlÈ
sum = 0; t[0] = 0
for (n = 1; n = N; n++)
sum += 2*t[n-1]
t[n] = n-1 + sum/n
Ten niewielki program jest naprawdę użyteczny. W czasie proporcjonalnym do N tworzy tabelę
rzeczywistych spodziewanych czasów wykonania algorytmu Quicksort dla każdej liczby całkowitej
od 1 do N.
Kod z listingu 3.11 jest łatwy do użycia w arkuszu kalkulacyjnym, w którym wartości są natych-
miast dostępne do dalszej analizy. Tabela 3.1 przedstawia początkowe wiersze.
T A B E L A 3 . 1 . Wynik implementacji kodu z listingu 3.11 w arkuszu kalkulacyjnym
N
0
1
2
3
4
5
6
7
8
Suma
0
0
0
2
7.333
17
31.8
52.4
79.371
t[n]
0
0
1
2.667
4.833
7.4
10.3
13.486
16.921
Pierwszy wiersz liczb w tej tabeli jest inicjalizowany za pomocą trzech stałych z kodu. W notacji
arkuszy kalkulacyjnych kolejny wiersz liczb (trzeci wiersz arkusza) jest obliczany przy użyciu na-
stępujących zależności:
A3 = A2+1
B3 = B2 + 2*C2
C3 = A3-1 + B3/A3
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
5 3
Poleć książkęKup książkęKopiując poprzez przeciągnięcie te (względne) odwołania w dół, można uzupełnić arkusz. Ten arkusz
jest moim poważnym kandydatem na „najpiękniejszy kod, jaki kiedykolwiek napisałem” w kategorii
osiągania jak najwięcej za pomocą tylko kilku wierszy kodu.
Co jednak, jeśli nie potrzebujemy tych wszystkich wartości? Gdybyśmy na przykład woleli prze-
analizować tylko kilka z wartości (na przykład wszystkie potęgi cyfry 2 od 20 do 232)? Mimo że kod
z listingu 3.11 tworzy pełną tablicę t, używa on tylko jej najnowszej wartości.
Możemy zatem zastąpić liniową przestrzeń tablicy t[] stałą przestrzenią zmiennej t, jak na listingu 3.12.
Listing 3.12. Obliczenia Quicksort — ostateczna wersja
sum = 0; t = 0
for (n = 1; n = N; n++)
sum += 2*t
t = n-1 + sum/n
Można następnie wstawić dodatkowy wiersz kodu w celu sprawdzenia trafności n i w razie potrzeby
wydrukować wyniki.
Ten niewielki program jest ostatnim etapem naszej podróży. Dobrą konkluzją w odniesieniu do niej
mogą być słowa Alana Perlisa: „Prostota nie występuje przed złożonością, ale jest jej następstwem”4.
Perspektywa
Tabela 3.2 zawiera zestawienie programów analizujących Quicksort, prezentowanych w tym rozdziale.
T A B E L A 3 . 2 . Ewolucja programu analizujÈcego pracÚ algorytmu Quicksort
Numer
przykĥadu
2
Liczba
odpowiedzi
1
Liczba
wierszy
13
Czas trwania
n
lu
( ng
)
Typ
odpowiedzi
Przykĥadowa
Dokĥadna
Dokĥadna
N
N
n
3N
N2
N
N
Przestrzeħ
)
N
( ngl
N
N
1
3
4
5
6
7
8
9
10
11
12
13
8
8
6
6
6
6
6
4
4
4 Alan Perlis, Epigrams on Programming, „Sigplan Notices”, Vol. 17, Issue 9 — przyp. red.
5 4
R O Z D Z I A Ł 3 .
Poleć książkęKup książkęKażdy etap ewolucji naszego kodu był bardzo prosty. Przejście od przykładu zamieszczonego na li-
stingu 3.6 do dokładnej odpowiedzi na listingu 3.7 jest prawdopodobnie najbardziej subtelne. Kod
w miarę kurczenia się stawał się coraz szybszy. W połowie XIX wieku Robert Browning zauważył,
że „mniej oznacza więcej”. Ta tabela umożliwia ilościowe określenie jednego z przykładów tamtej
minimalistycznej filozofii.
Widzieliśmy trzy zasadniczo różniące się typy programów. Przykłady z listingów 3.2 i 3.3 są dzia-
łającymi algorytmami Quicksort przystosowanymi do zliczania porównań w trakcie sortowania
prawdziwej tablicy. Listingi 3.4 do 3.6 implementują prosty model Quicksort — imitują jedno uru-
chomienie algorytmu, w rzeczywistości nie wykonując żadnego sortowania. Listingi 3.7 do 3.12
implementują bardziej wyrafinowany model — obliczają rzeczywistą średnią liczbę porównań, nie
badania jakiegoś konkretnego uruchomienia algorytmu.
Oto podsumowanie technik zastosowanych do uzyskania każdego z programów:
x Listingi 3.2, 3.4, 3.7 — fundamentalna zmiana definicji problemu.
x Listingi 3.5, 3.6, 3.12 — nieduża zmiana definicji funkcji.
x Listing 3.8 — nowa struktura danych implementująca programowanie dynamiczne.
Techniki te są typowe. Program często można uprościć poprzez odpowiedzenie sobie na pytanie,
jaki problem tak naprawdę trzeba rozwiązać oraz czy jest funkcja lepiej nadająca się do rozwiązania
tego problemu.
Kiedy po raz pierwszy przedstawiłem tę analizę studentom, program w końcu skurczył się do 0 wierszy
kodu i zniknął w tumanie matematycznego kurzu. Kod z listingu 3.7 można przedstawić za pomo-
cą następującej zależności rekurencyjnej:
¦
1
0
/1
n
C
C
n
C
0
n
C
1
i
in
dd
ni
1
Jest to dokładnie metoda zastosowana przez Hoare’a i później przedstawiona przez D. E. Knutha
w jego klasycznej monografii Sztuka programowania. Tom 3: Sortowanie i wyszukiwanie5. Sztuczki
programistyczne polegające na wprowadzaniu odpowiedników i zastosowaniu symetrii, dzięki któ-
rym powstał kod zaprezentowany na listingu 3.10, umożliwiły uproszczenie części rekursywnej do
następującej postaci:
C
n
n
1
/2
¦
n
C
0
dd
ni
1
i
Technika Knutha polegająca na usunięciu symbolu sumy daje w wyniku (mniej więcej) kod wi-
doczny na listingu 3.11, który można zastąpić układem dwóch zależności rekurencyjnych z dwiema
niewiadomymi.
C
0
0
S
0
0
S
n
S
n
C
1 2
n
1
C
n
1
n
nS
/
n
5 Wydawnictwa Naukowo-Techniczne, Warszawa 2002 — przyp. red.
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
5 5
Poleć książkęKup książkęKnuth uzyskuje wynik dzięki zastosowaniu matematycznej techniki czynnika sumującego (ang.
summing factor):
21
n
n
ln
~
386,1
n
H
n
C
n
2
n
1
2
gdzie Hn oznacza n-tą liczbę harmoniczną — 1 + ½ + ⅓+ … 1/n. W ten sposób gładko przeszliśmy
od eksperymentowania na programie poprzez wzbogacanie go dogłębną analizą do kompletnie
matematycznej analizy jego działania.
Na tej formule kończymy naszą przygodę. Poszliśmy za słynną radą Einsteina, która brzmi: „Upraszczaj
wszystko jak to tylko możliwe i ani trochę bardziej”.
Dodatkowa analiza
Słynne stwierdzenie Goethego mówi, że architektura to zamrożona muzyka. W dokładnie tym samym
sensie twierdzę, że struktury danych to zamrożone algorytmy. Jeśli zamrozimy algorytm Quicksort,
otrzymamy strukturę danych binarnego drzewa poszukiwań. Struktura ta jest zaprezentowana w pu-
blikacji Knutha. Czas jej wykonania został przeanalizowany za pomocą relacji rekurencyjnej podob-
nej do tej występującej w Quicksort.
Gdybyśmy chcieli przeanalizować średni koszt wstawienia elementu do binarnego drzewa wyszu-
kiwania, moglibyśmy zacząć od kodu, który następnie wzbogacilibyśmy o zliczanie porównań. Po-
tem moglibyśmy przeprowadzić eksperymenty na zgromadzonych danych. Następnie moglibyśmy
uprościć kod (i zwiększyć jego funkcjonalność) w sposób bardzo podobny do tego z poprzedniego
podrozdziału. Prostsza metoda polega na zdefiniowaniu nowego algorytmu Quicksort z użyciem
metody idealnego podziału pozostawiającej elementy w tej samej względnej kolejności po obu stro-
nach. Taki algorytm Quicksort jest izomorficzny z binarnymi drzewami poszukiwań, co widać na
rysunku 3.1.
Rysunek 3.1. Algorytm Quicksort z idealnym podziaïem i odpowiadajÈce mu drzewo binarne poszukiwañ
Ramki po lewej stronie prezentują algorytm Quicksort z idealnym podziałem w trakcie działania.
Graf po prawej stronie przedstawia odpowiadające mu drzewo binarne, które zostało zbudowane
z tych samych danych wejściowych. Oba te procesy wykonują nie tylko tę samą liczbę porównań,
ale dokładnie takie same ich zestawy. A zatem nasza poprzednia analiza w celu sprawdzenia średniej
efektywności randomizującego algorytmu Quicksort, działającego na zestawie unikatowych elementów,
daje nam średnią liczbę porównań do wstawienia do binarnego drzewa wyszukiwań losowo usta-
wionych unikatowych elementów.
5 6
R O Z D Z I A Ł 3 .
Poleć książkęKup książkęCo to jest pisanie
Tworząc kody z listingów od 3.2 do 3.12, najpierw zapisałem je w swoich notatkach, następnie na
tablicy dla studentów i w końcu na kartkach tego rozdziału. Programy te powstawały stopniowo.
Spędziłem dużą ilość czasu nad ich analizą i jestem przekonany o tym, że nie zawierają błędów.
Jednak poza implementacją w arkuszu kalkulacyjnym przykładu z listingu 3.11 nigdy nie urucho-
miłem żadnego z tych programów jako programu komputerowego.
W ciągu dwudziestu lat pracy w Bell Labs miałem okazję uczyć się od wielu nauczycieli (zwłaszcza
od Briana Kernighana, którego rozdział o nauczaniu programowania pojawia się jako pierwszy
w tej książce). Nauczono mnie, że pisanie programu do użytku publicznego to coś więcej niż tylko
wpisywanie symboli. Po napisaniu kodu programu uruchamia się go w kilku przypadkach testo-
wych, następnie buduje szczegółowe rusztowanie, sterowniki i bibliotekę przypadków systema-
tycznie na nim uruchamianych. W idealnej sytuacji skompilowany kod źródłowy jest „włączany
w tekst” bez interwencji człowieka. Przykład z listingu 3.1 (i wszystkie kody w książce Perełki pro-
gramowania) napisałem właśnie w tym duchu.
Punktem honoru dla mnie było trzymanie się tytułu i nieimplementowanie przykładów z listingów
3.2 do 3.12. Prawie czterdzieści lat programowania komputerów nauczyło mnie głębokiego sza-
cunku dla trudności tego rzemiosła (mówiąc dokładniej, panicznego strachu przed błędami). Ska-
pitulowałem, implementując kod z listingu 3.11 w arkuszu kalkulacyjnym, i dorzuciłem dodatkową
kolumnę, która dała zamkniętą formę rozwiązania. Wyobraź sobie moją radość, kiedy zobaczyłem,
że dokładnie do siebie pasują! Tak więc prezentuję światu te piękne nienapisane programy z pewną
dozą pewności, że są poprawne, ale w głębi będąc boleśnie świadom, że mogą zawierać jakieś nie-
odkryte błędy. Mam nadzieję, że głębokie piękno, które w nich widzę, nie zostanie przekreślone
przez jakieś powierzchowne skazy.
Prezentując niepewnie te nienapisane programy, pocieszam się spostrzeżeniem Alana Perlisa, który
powiedział: „Czy jest możliwe, że oprogramowanie nie jest podobne do niczego innego, że jest ska-
zane na wyrzucenie, że cała filozofia polega na tym, aby postrzegać je jako mydlaną bańkę?”.
Zakoñczenie
Piękno ma wiele źródeł. Ten rozdział koncentruje się na pięknie zdobywanym dzięki prostocie,
elegancji i zwięzłości. Poniższe stwierdzenia wyrażają tę najistotniejszą myśl:
x Staraj się dodawać funkcje poprzez usuwanie kodu.
x Projektant może uznać, że osiągnął perfekcję, nie wtedy, kiedy nie pozostało już nic do doda-
nia, ale wtedy, gdy nie można już nic odjąć (Saint-Exupéry).
x W oprogramowaniu najpiękniejszego kodu, najpiękniejszych funkcji i najpiękniejszych pro-
gramów czasami w ogóle nie ma.
x Piszący szybko piszą zwięźle. Pomijają niepotrzebne słowa (Strunk i White).
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
5 7
Poleć książkęKup książkęx Najtańsze, najszybsze i najbardziej niezawodne komponenty systemu komputerowego to te,
których nie ma (Bell).
x Dąż do robienia coraz więcej za pomocą coraz mniejszej ilości kodu.
x Gdybym miał więcej czasu, napisałbym Ci krótszy list (Pascal).
x Paradoks wynalazcy: bardziej ambitny plan może mieć więcej szans na powodzenie (Pólya).
x Prostota nie występuje przed złożonością, ale jest jej następstwem (Perlis).
x Mniej oznacza więcej (Browning).
x Upraszczaj wszystko jak to tylko możliwe i ani trochę bardziej (Einstein).
x Oprogramowanie powinno być czasami postrzegane jako mydlana bańka (Perlis).
x Szukaj piękna w prostocie.
Na tym kończy się ta lekcja. Idź zatem i postępuj, jak tu napisano.
Dla tych, którzy potrzebują bardziej konkretnych wskazówek, poniżej przedstawiam listę koncepcji
podzielonych na trzy kategorie.
Analiza programów
Jednym ze sposobów na zyskanie wglądu w działanie programu jest odpowiednie wyposażenie go
i uruchomienie na reprezentatywnej próbce danych, jak w przykładzie z listingu 3.2. Często
jednak bardziej niż całym programem zajmujemy się jednym jego fragmentem. W tym przy-
padku zajmowaliśmy się tylko średnią liczbą porównań wykonywanych przez Quicksort, a pomija-
liśmy wiele innych aspektów. Sedgewick6 bada takie zagadnienia, jak wymagana przez niego
przestrzeń i wiele innych komponentów wykonywania różnych wariantów Quicksort. Koncentru-
jąc się na najważniejszych problemach, możemy (przez chwilę) zapomnieć o innych aspektach
programu. W jednym z moich artykułów, A Case Study In Applied Algorithm Design7, opisuję,
jak zetknąłem się z problemem oszacowania wydajności heurystyki paskowej (ang. strip heuri-
stic) do znalezienia przybliżonej drogi akwizytora przez N punktów w określonym kwadracie.
Oceniłem, że kompletny program do rozwiązania tego zadania zajmie około 100 wierszy kodu.
Po kilku etapach podobnych do tych opisanych powyżej uzyskałem dwunastowierszową symulację
o znacznie większej dokładności (a po zakończeniu mojej małej symulacji odkryłem, że Beardwood
i inni autorzy8 wyrazili moją symulację w postaci podwójnej liczby całkowitej, a więc rozwiązali
matematycznie ten problem około dwudziestu lat wcześniej).
6 Robert Sedgewick, The Analysis of Quicksort programs, „Acta Informatica”, Vol. 7 — przyp. red.
7 „IEEE Computer”, Vol. 17, No. 2 — przyp. red.
8 J. Beardwood, J. H. Halton, J. M. Hammersley, The Shortest Path Through Many Points, „Proc. Cambridge Philosophical
Soc.”, Vol. 55 — przyp. red.
5 8
R O Z D Z I A Ł 3 .
Poleć książkęKup książkęMałe fragmenty kodu
Uważam, że programowanie komputerów to umiejętność praktyczna, i zgadzam się z Pólyą, iż
„zdolności praktyczne nabywamy poprzez naśladownictwo i praktykę”. Programiści, którzy pragną
pisać piękny kod, powinni zatem czytać piękne programy i naśladować zastosowane w nich
techniki we własnych. Według mnie do takich ćwiczeń najlepiej nadają się niewielkie fragmenty
kodu, składające się z 10 do 25 wierszy kodu. Przygotowywanie drugiego wydania książki Perełki
programowania wymagało mnóstwa pacy, ale było też bardzo zabawne. Implementowałem każdy
fragment kodu i pracowałem nad nim, aby zredukować jego rozmiar do niezbędnego minimum.
Mam nadzieję, że inni będą mieli tyle samo radości z czytania tego kodu co ja z jego pisania.
Systemy oprogramowania
Opisałem niezwykle szczegółowo jedno małe zadanie. Wydaje mi się, że świetność tych zasad nie
bierze się z małych fragmentów kodu, a z dużych programów i wielkich systemów kompute-
rowych. Parnas opisuje techniki redukcji systemu do niezbędnego minimum9. Stosując je, nie
zapomnij rady Toma Duffa: „Podkradaj kod, kiedy tylko jest taka możliwość”.
PodziÚkowania
DziĊkujĊ za wnikliwe komentarze Danowi Bentleyowi, Brianowi Kernighanowi, Andy’emu
Oramowi i Davidowi Weissowi.
9 David L. Parnas, Designing software for ease of extension and contraction, „IEEE T. Software Engineering”, Vol. 5, No. 2
— przyp. red.
N A J P I Ę K N I E J S Z Y K O D , K T Ó R E G O N I G D Y N I E N A P I S A Ł E M
5 9
Poleć książkęKup książkę6 0
R O Z D Z I A Ł 3 .
Poleć książkęKup książkęS K O R O W I D Z
.NET Common Language Runtime, 132
__dict__, 315
A
abstrakcja, 43
iterator, 324
abstrakcja składniowa, 425
makra Lisp, 426
makra preprocesora C, 425
syntax-rules, 428
warunek higieniczności dla rozszerzania makr, 427
Acceptance Testing Framework, 96
ACE, 448, 454
ACE_Handle_Set, 459
Adapter, 448
adnotacje, 206
adresowanie otwarte, 316
advice, 524
AFL, 529
Agile methodologies, 110
algorytmy
algebra liniowa, 248
binarySearch, 116
dziel i zwyciężaj, 48
Euklidesa, 558
filtr cyfrowy, 136
gęsta algebra liniowa, 253
higieniczne rozszerzanie makr, 428
macierzowe, 248
ogólne, 146
podzielone na bloki, 248
Quicksort, 48
rozwijanie, 431
rsync, 29
współliniowość, 566
wyszukujące, 67
zliczające słowa, 400
analiza błędów, 267
analiza programów, 58
analizator składniowy, 306
AND, 126
annotation, 206
Ant, 89
Apache Log4J, 347
API, 45
API JavaMail, 98
API JDOM, 79, 80
API JDOM 3, 86
API Perl XS, 184
aplikacje sieciowe, 228, 447
Application Programming Interface, 447
apply_textdelta(), 41
architektura
komputer, 248
oszczędzająca nakłady, 447
REST, 469
RISC, 79, 249
sieciowe usługi rejestrowania, 449
wielokrotnego użytku, 448
zorientowana na usługi, 340
argumenty funkcji, 300
arkusze właściwości, 361
ArrayIndexOutOfBoundsException, 108
Arrays, 116
AS/400, 469, 470
asembler, 126
asercje
blokady, 306
JUnit, 120
ASSERT_VOP_ELOCKED(), 306
ASSERT_VOP_UNLOCKED(), 306
assignment, 155
AsTeR, 529
AsTeR, Audio System For Technical Readings, 521
asymetria w przepływie danych, 503
Atom, 540
atomically act, 410
Audio Formatting Language, 529
audyt modułu, 197
Aural CSS, 529, 530, 535
automatyczne wyszukiwanie przyczyny awarii, 486
awk, 20, 70
5 8 3
Poleć książkęKup książkęB
backtick operator, 198
badania użyteczności, 182
base pair, 206
Basic Linear Algebra Communication Subprograms, 261
Basic Multilingual Plane, 89
baton, 36
baza danych, 277
Benchmark, 201
bezpieczna komunikacja, 177
bezpieczne przesyłanie wiadomości, 180
białe znaki, 550
biblioteki
CERN, 272
LAPACK, 272
binarySearch, 113, 116, 121
binarySearchComparisonCount, 121
Bio::Graphics, 206
dodawanie nowych glifów, 231
fabryki glifów, 219
gęstość własności, 209
historyjka, 210
interaktywne aplikacje sieciowe, 209
klasy obiektowe, 216
niezależność od formatu graficznego, 209
niezależność od schematów baz danych, 210
obsługa obrazów nadających się do publikacji, 230
opcje dynamiczne, 224
otwarta natura problemu, 208
powiększanie semantyczne, 225
proces projektowania, 210
projektowanie sposobu interakcji dewelopera
z modułem, 210
przetwarzanie opcji, 218
rozszerzanie modułu, 228
skala, 209
ścieżki, 212
ustawianie opcji, 214
wspieranie programistów sieciowych, 228
wymagania, 208
wywołanie zwrotne, 227
zwracane dane, 207
Bio::Graphics::Glyph, 232
Bio::Graphics::Glyph::Factory, 219
Bio::Graphics::Panel, 210, 216
Bio::Graphics::Track, 216
Bio::SeqFeature::Generic, 224
Bio::SeqFeatureI, 224
bioinformatyka, 205
BioMoby, 471
BioPerl, 205, 206, 213
BitBlt, 126, 128, 132
BLACS, 261
BLAS, 253
5 8 4
S K O R O W I D Z
block, 158
block-partitioned algorithms, 248
blokady, 404, 405, 423
rogatkowa, 376
wątki, 375
blokowanie, 413
wątki, 372
zasoby, 372
błędy wyczerpania pamięci, 277
BMP, 89
BNF, 81
boundary testing, 106
bramki, 416
branch, 140
branch if less than, 142
branching, 140
brush, 128
BT Trade, 364
bufor wpisywania, 515
buforowanie, 91
Business Template, 364
bycie podręcznikowym, 547
C
C#, 131
CA, 180
Carry Save Adder, 171
CAS, 412
cd9660_read(), 299
cele ERP, 358
cele projektowe, 185
CERN, 272
algorytmy, 273
Certification Authority, 180
CGI, 237
chaining, 249
Character, 82
isDigit(), 82, 83
isLetterOrDigit(), 82, 83
checkXMLName(), 82, 83, 86
CIP, 337
CIP Middleware Monitor Utility, 352
cmaild, 188
CMF, 357, 358, 360
CMF Types, 360
Collaborative Information Portal, 337, 338
Commercial off-the-shell, 340
Common Lisp, 425
commoning, 172
Compare-And-Swap, 412
constant, 155
container_of(), 289
Content Management Framework, 358
cookie, 238
Poleć książkęKup książkęcore dump, 378
corner cases, 112
COTS, 340
CPAN, 184
CreateProcess(), 464
Crypt::PGP5, 189
Cryptonite, 178, 182
audyt modułu Crypt::GPG, 197
bezpieczne przesyłanie wiadomości, 180
cele projektowe, 185
cmaild, 188
Crypt::GPG, 191
Crypt::PGP, 190
Cryptonite::Mail::Config, 196
Cryptonite::Mail::Service, 196
DBD::Replication, 192
decyzje, 185
deszyfracja, 192
działający prototyp, 189
Edit Key, 194
folder cieni, 192
IMAP, 192
IPC::Run, 198
Mail::Cclient, 201
Mail::Folder, 192
Mail::Folder::Shadow, 192, 200
Mail::Folder::SQL, 192
mbox, 189
OpenPGP, 198
Params::Validate, 196
Persistence::Database::SQL, 190
Persistence::Object::Postgres, 190, 191
Persistence::Object::Simple, 190, 191
początkowy projekt systemu, 186
poczta odbierana, 189
projekt systemu, 186
prywatność komunikacji, 202
przechowywanie wiadomości e-mail, 191
przejście od prototypu do skalowalnego produktu, 190
reorganizacja kontenera wiadomości, 191
Replication::Recall, 192, 201
replikacja wiadomości e-mail, 192
serializacja, 187
szybkość działania, 201
trwałość deszyfracji, 192
uwierzytelnienie z kluczem, 180
użyteczność, 181
zabezpieczanie kodu, 195
zarządzanie kluczami, 194
zestaw testów, 188
Cryptonite Mail Daemon, 188
Cryptonite::Mail::Service, 186
CSA, 171
cyberpunki, 202
cyfrowe filtry obrazu, 132
cykl życia grup procesów, 465
czas trwania testów, 118
czynnik sumujący, 56
czytanie programów, 495
czytelność kodu, 114, 309
czytnik kanałów, 540
D
dane, 125
dane z pamiętnika sieciowego, 62
data display debugger, 482
DAXPY, 254
DBD::SQLite, 189
DBI, 189
DCOM, 391
dd(), 488
ddchange, 493
ddd, 482
debuger, 482
ddd, 482
debugowanie, 378, 481
automatyczne wyszukiwanie przyczyny awarii, 486
dd(), 488
ddd, 482
debuger, 482, 485
efektywność, 481
gdb, 482
hipoteza przyczyny awarii, 484
in situ, 378
metoda naukowa, 483
odtworzenie awarii, 490
poawaryjne, 378
post mortem, 378
przewidywania, 484
systematyczny proces, 483
wyszukiwanie przyczyn, 483
zasady, 484
debugowanie delta, 488
ddchange, 493
minimalizacja wejścia, 490
porównanie stanów programu, 491
problem prototypu, 493
różnice między dwoma stanami, 491
stan programu, 491
wyszukiwanie przyczyn w danych wejściowych, 490
DECTalk, 522
DECTalk Express, 522
definiowanie interfejsu usługi, 471
dekompozycja LU, 248, 280
delta debugging, 488
delta editor, 29
demarshalling, 391
demultipleksacja, 307
dentry, 294
S K O R O W I D Z
5 8 5
Poleć książkęKup książkędepot, 374
deskryptor tablicy, 263
deszyfracja, 192
devfs, 286
device, 286, 291
DGEFA, 252, 254
DGEMM, 257
DGETF2, 257, 258
DGETRF, 255
dialog z użytkownikiem przez internet, 237
dictionary, 67
DiffMerge, 546, 547, 550, 552
digital filters, 132
długie kliknięcie, 507
długość wierszy tekstu, 547
DNA, 206
dobry projekt, 29
Document, 86
document-centric, 357
dodawanie funkcji poprzez usuwanie kodu, 47
dokumenty
XHTML, 91
XML, 79, 479
DOM, 479
Domain Specific Language, 498
doPost(), 472
dostarczanie informacji, 61
dostęp do informacji online, 534
do-while, 23
DRY, 497
DSCAL, 254
DTRSM, 257
Duff’s Device, 29
DynamicMethod, 139, 146
dynamiczna rekonfiguracja, 354
dynamiczne obiekty, 149
dynamiczne wybieranie funkcji przechowującej, 315
dynamiczne zasiedlanie drzewa, 510
działający prototyp, 189
dziedziczenie priorytetów, 373
dziedziczenie prototypowe, 149
dziel i zwyciężaj, 48, 164, 283
zliczanie bitów w stanie wysokim, 165
dziennik transakcji, 412
dźwiękowe środowisko pracy, 521
Emacspeak, 521
wyjście mówione, 522
E
ed, 20
EDEADLK, 382
edytor delty, 29, 41
interfejs, 35
efekty uboczne, 407, 409
5 8 6
S K O R O W I D Z
efektywność debugowania, 481
egrep, 20
EJB, 341, 344
eksponowanie obiektów OpenPGP, 182
ekspresywna notacja obiektowa, 148
ekstremalne przypadki testowe, 112
elastyczność kodu, 499
elegancki kod, 48
element, 359
eliminacja Gaussa, 247
analiza błędów, 267
DGETRF, 255
faktoryzacja dla wykonywania wielowątkowego, 265
język MATLAB, 251
LAPACK, 256
liczba operacji, 267
LINPACK, 253
metoda dekompozycyjna, 250
PBLAS, 263
rekursywna dekompozycja LU, 257
ScaLAPACK, 260, 261
eliminacja niepotrzebnych transferów danych przez sieć, 29
eLocutor, 501
asymetria w przepływie danych, 503
bufor wpisywania, 515
Common Words, 514
częste słowa, 514
długie kliknięcie, 507
drzewo, 506
dynamiczne zasiedlanie drzewa, 510
edycja, 515
Favorites, 514
grupowanie słów, 504
implementacja pamięci podręcznej, 513
interfejs wejściowy, 505
makra, 517
model projektu, 502
następne słowo, 511
Next Word, 511
pamięć podręczna, 513
pobieranie, 518
proste wpisywanie, 511
przewidywanie, 511
przewijanie, 515
Replace, 512
schowek, 517
szablony, 512
śledzenie ścieżek, 515
Templates, 512
TreeView, 506
układ ekranu, 503
ulubione, 514
uzupełnianie słów, 511
wejście binarne, 506
Word Completion, 511
Poleć książkęKup książkęwydajność interfejsu użytkownika, 518
wyszukiwanie, 517
zastępowanie, 512
Emacs Calendar, 532
Emacs W3, 535
Emacspeak, 521
advice, 524
Aural CSS, 529
czytnik kanałów, 540
dostęp do informacji online, 534
emacspeak-auditory-icon, 532
emacspeak-calendar, 533
emacspeak-calendar-speak-date, 533, 534
emacspeak-minibuffer-setup-hook, 531
emacspeak-speak-line, 524
emacspeak-url-template, 539
emacspeak-w3-extract-table-by-match, 537
emacspeak-websearch, 535, 536, 539
formatowane dźwięku, 526
formatowanie wyjścia dźwiękowego na podstawie
słuchowych list wyświetlania, 528
generowanie bogatego wyjścia mówionego, 525
gramatyka zawartości bufora, 525
ikony dźwiękowe, 530
implementacja, 523
internetowy wiersz poleceń, 539
kalendarz, 532
minibuffer-setup-hook, 531
odtwarzanie ikon dźwiękowych podczas wypowiadania
zawartości, 532
personality, 527
put-text-property, 526
RSS, 540
semantyka zależna od kontekstu, 532
serwer mowy, 522
stylizowanie wyjścia mówionego, 529
szablony URL, 539
tts-format-text-and-speak, 528, 529
tts-speak, 528
tworzenie dźwiękowych list wyświetlania, 526
voice-lock, 526
włączanie mowy w Emacsie, 523
wyszukiwanie zorientowane na zadania, 535
emacspeak-auditory-icon, 532
emacspeak-calendar, 533
emacspeak-calendar-speak-date, 533, 534
emacspeak-minibuffer-setup-hook, 531
emacspeak-url-template, 539
emacspeak-w3-extract-table-by-match, 537
emacspeak-websearch, 535, 536, 539
emacspeak-websearch-yahoo-map-directions-get-locations,
537
embedded systems, 293
Enterprise, 293
Enterprise JavaBeans, 341
Enterprise Resource Planning, 357
EPR5 RAD, 366
ERP5, 357, 358
arkusze właściwości, 361
BT Trade, 364
CMF, 357, 358, 360
CMF Types, 360
DCWorkflow, 358
egzemplarz zasobu, 359
element, 359
GUI, 366
implementacja zachowania zadań, 367
Item, 359
kategorie podstawowe, 363
Movement, 359
Node, 359
obieg Task, 367
obieg Task Report, 369
Path, 359
pisanie kodu, 365
Portal, 362
przemieszczenie, 359
Resource, 359
szablon biznesowy, 364
ścieżka, 359
Task, 367
UBM, 359
węzeł, 359
XML, 358
założenia projektu, 364
zasób, 359
ZODB, 358, 359
Zope, 360
ZPT, 358
zunifikowany model biznesowy, 359
ERP5 Project, 364
eseje, 495
evaluation stack, 139
ewoluowanie kodu wraz ze sprzętem, 247
Exclusive-OR, 129
exec*(), 464
executeQuery(), 477
expression, 152
eXtreme Programming, 110
fabryka, 473
faktoryzacja
LU, 279
panelowa, 265
fałszywe zakleszczenie, 382
fasada, 448, 454
ACE, 455
features, 208
ffs, 300
F
S K O R O W I D Z
5 8 7
Poleć książkęKup książkęfgrep, 20
file baton, 41
FilterMethodCS(), 134, 135, 137, 146
FilterMethodTL(), 134, 138, 145, 146
filtry, 242
grafika cyfrowa, 132
wyostrzające, 133
FIT, 95
fixture, 96
Fixture, 99
folder cieni, 192
fork(), 464
forkIO(), 408
format XML, 358
formatowane dźwięku, 526
formaty wpisów dziennika, 450
Fortran, 252
fragmentowanie, 321
Framework for Integrated Test, 95
ActionFixture, 97
architektura, 98
dokumenty, 96
fixture, 96
Fixture, 97, 99
otwarte środowisko, 99
Parse, 97
parser HTML, 100
projektowanie środowiska, 98
przetwarzanie kodu HTML, 100
rdzeń, 97
testy, 96
TypeAdapter, 97
frameworki, 448, 452
free(), 318
FreeBSD, 307
funkcja partycjonująca, 398
funkcje, 160, 245
funkcjonalność interfejsu użytkownika, 182
G
gałęzie wydań DiffMerge, 552
Gate, 416
GBrowse, 229
GD, 230
gdb, 482
Gene Sorter, 235
advFilter, 242
filterControls, 242
filtry, 242
interfejs użytkownika, 236
podtrzymywanie dialogu z użytkownikiem
przez internet, 237
polimorfizm, 239
teoria pięknego kodu, 243
5 8 8
S K O R O W I D Z
generator XML, 479
generowanie
bogate wyjście mówione, 525
kod do przetwarzania obrazów, 125
kod w locie, 126
Genes, 209
genom, 206
getResponseXML(), 479
gęstość własności, 209
GHC, 421
Glasgow Haskell Compiler, 421
głęboko wcięty kod, 548
gniazda, 447
GNU debugger, 482
Google, 75, 76
Google Maps, 537, 538
goto, 140
graficzny interfejs użytkownika, 503
grafika, 209
SVG, 230
gramatyka BNF, 81, 83
Grand Unified Debugger Emacs, 532
grep, 20, 393
grupowanie słów, 504
GUI, 366
gwarancje kolejności, 399
H
haker, 202
Hash, 67
hash table, 67
hash(), 399
HashMap, 67
Haskell, 404, 406, 422
akcje, 407, 409, 422
atomically act, 410
efekty uboczne, 407, 409
forkIO(), 408
kompilacja programu, 421
operacje STM, 414
pamięć transakcyjna, 423
STM, 410
struktury sterujące, definiowane przez użytkownika, 409
transakcje, 410
uruchamianie programu, 421
wątki, 408
wejście-wyjście, 407
Heap Sort, 49
Hello World, 496
heurystyka paskowa, 58
higieniczne rozszerzanie makr, 427
hook methods, 453
hot swapping, 355
Poleć książkęKup książkęHotkeyAdaptor, 474
HotkeyAdaptorFactory, 474
HTML, 100
HttpClient, 475
I
IDAMAX, 254
IDE, 185, 497
idealny podział, 56
identyfikator URI, 92
IETF, 180
if-else, 140
if-then-else, 548
ikony dźwiękowe, 530
IL Disassembler, 135, 137
ILGenerator, 139, 146
ILP, 174
image filters, 132
ImageClip, 134
ImageFilter, 135, 138
IMAP, 192, 199
imitacja gramatyki BNF O(N), 83
implementacja, 386
kod, 272
pamięć podręczna, 513
pamięć transakcyjna, 412
rozproszony MapReduce, 394
sekwencyjny serwer rejestrowania, 457
słownik, 311
Święty Mikołaj, 420
wyszukiwanie binarne, 109
infix, 153, 156
infixr, 155
informacje pośrednie, 323
informacyjny RNA, 236
information retrieval, 76
informowanie o postępie, 29
infrastruktura klucza publicznego, 180, 203
infrastruktura warstwy pośredniczącej, 448
inode, 294
Instruction-Level Parallelism, 174
instrukcje, 157
rozgałęziające, 140
integracja partnerów biznesowych, 469
interakcja dewelopera z modułem, 210
interaktywne aplikacje sieciowe, 209
interfejs, 29
interfejs edytora delty, 35
interfejs usługi systemu zaplecza, 472
interfejs wejściowy, 505
internetowy wiersz poleceń, 539
inventor’s paradox, 51
inwersja priorytetów, 373
IPC, 449, 450, 454
IPC::Run, 198
ISO X.509, 180
isXMLCombiningChar(), 83
isXMLExtender(), 83
isXMLLetter(), 83
isXMLNameCharacter(), 83
isXMLNameStartCharacter(), 83
Item, 359
iteracyjny serwer rejestrowania, 457
Iterative_Logging_Server, 457, 461
iterator NumPy, 324, 335
iteratory, 323
J
J2EE, 340
Java, 26
Java(), 26
JavaMail, 98
JavaScript, 148
jądro
Linux, 285
Solaris, 372
JDOM, 79, 80, 84
JDOM 1.0, 85
język
BioPerl, 205
funkcyjny, 409, 422
Haskell, 404, 422
imperatywny, 422
Java, 26
JavaScript, 148
konkretnej domeny, 305
LISP, 148
MATLAB, 251
Python, 311
Rexx, 498
Ruby, 64, 497
TCL, 522
XML, 80
JIT, 79, 132
JPL, 338
JSON, 149
jump, 140
JUnit, 109, 120
asercje, 120
dokumentacja, 110
Just-In-Time compiler, 132
Jython, 315
K
kanały RSS, 540
Key Ring, 183
KFFD, 428, 445
S K O R O W I D Z
5 8 9
Poleć książkęKup książkęKleene, Stephen, 19
klient mowy Emacspeak, 523
klient poczty e-mail, 184
klient-serwer, 522
klucz, 66
kobject, 291
kod, 125, 305, 496
generowanie w locie, 126
XML, 79
zarządzany, 131
kolejność wykonywania operatorów, 147
funkcje, 160
instrukcje, 157
JavaScript, 148
literały obiektowe, 161
literały tablicowe, 161
operator trójargumentowy, 153
operatory przedrostkowe, 154
operatory przypisania, 155
operatory wrostkowe, 152
podejmowanie decyzji, 151
stałe, 155
tablica symboli, 149
technika parsowania, 147
technika Pratta, 148
tokeny, 150
zakres, 156
kolizje, 316
komentarze, 549
kompilacja, 26
kompilatory, 492
język C#, 131
JIT, 79, 132, 139
komponenty EJB, 344
komunikacja, 177
między procesami, 449
konstruktor danych MkGate, 417
konstrukty pętli, 425
konstrukty warunkowe, 425
konta bankowe, 404
blokady, 404
zmienne warunkowe, 404
kontrola wersji, 30
konwencje pisania kodu, 546
konwersja niedeterministycznego automatu skończonego
na automat deterministyczny, 25
kopia robocza, 34
kopiowanie binarnej tablicy wyszukiwania, 89
kref, 292
kref_put(), 292
krótki kod, 279
kryptografia, 202
kryptografia z kluczem publicznym, 180
Księga, 557
5 9 0
S K O R O W I D Z
L
LAPACK, 248, 256, 272
left denotation, 151
Level-1 BLAS, 253
lex, 306
liczba operacji, 267
licznik referencji, 293
LINPACK, 248, 252, 253, 255
Linux, 285
Lisp, 541
LISP, 148
list comprehension, 419
lista, 318
listy składane, 419
literały
obiektowe, 149, 161
tablicowe, 149, 161
Logging_Server, 450
lokalność, 398
lookdict(), 319
lookdict_string(), 319
losowanie, 115
ludzki genom, 235
luźne powiązania, 342
Ł
ładowanie
binarne tablice wyszukiwania, 90
wielkie tablice asocjacyjne, 71
łańcuch blokowań, 374
łatwość użycia, 179
łączenie operacji w łańcuchy, 249
M
m4, 425
macierz
gęsta, 247
rzadka, 247
magazines, 374
magazyn, 374
Mail::Cclient, 201
Mail::Folder::Shadow, 192, 200
Mail::Folder::SQL, 192
Mail::IMAPClient, 201
MailVault beta 2, 178
make, 498
makra, 425, 517
makroprocesor m4, 425
malloc(), 318
małe fragmenty kodu, 59
Poleć książkęKup książkęmałe systemy wbudowane, 293
małe, luźno połączone obiekty, 294
Map(), 392, 395
MAPICS, 470, 477
Maple, 67
mapowanie, 313
MapReduce, 389, 392
funkcja partycjonująca, 398
gwarancje kolejności, 399
implementacja, 394
kopia robocza, 396
lokalność, 398
Map(), 392, 395
model programistyczny, 392
odporność na błędy, 397
odwrócony graf odnośników internetowych, 393
odwrócony indeks, 394
pomijanie złych rekordów, 399
program główny, 396
przepustowość sieci, 398
Reduce(), 392
relacje między procesami, 396
rozproszone grep, 393
rozproszone sortowanie, 394
rozszerzenia modelu, 398
wektor terminów dla hosta, 394
wyważenie obciążenia, 397
zadania rezerwowe, 398
Mars Exploration Rover, 337, 338
architektura CIP, 341
architektura systemu, 340
architektura usługi strumieniowej, 344
CIP Middleware Monitor Utility, 352
Collaborative Information Portal, 338
doFileDownload(), 348
dynamiczna rekonfiguracja, 354
funkcjonalność, 343
getDataFile(), 350
Jet Propulsion Laboratory, 338
monitorowanie, 352
niezawodność, 343, 346
przesyłanie plików, 346
readDataBlock(), 348, 351
registerNewReader(), 349
rejestrowanie, 347, 352
removeReader(), 349
SOA, 341
solidność, 353
StreamerServiceBean, 347
usługa strumieniowa, 343
usługi, 341
warstwa kliencka, 340
wymagania misji, 339
wymiana podczas pracy, 355
zarządzanie czasem, 339
zarządzanie danymi, 340, 343
zarządzanie personelem, 340
marshalling, 391
match(), 22
Matcher, 26
matchhere(), 23, 24
matchstar(), 23, 24
MATLAB, 251
mbox, 189
meandry, 565
MER, 338
Merge Sort, 49
messenger RNA, 236
metaznaki, 19
metoda dekompozycyjna, 250
metoda szablonu, 448, 453
metody abstrakcyjne, 453
metody zsynchronizowane, 404
metodyki Agile, 110
Microsoft .NET Framework, 131
miejsca DNA, 224
MIMD, 260
MIME, 191
minibuffer-setup-hook, 531
minimalizacja wejścia, 490
MkGate, 417
MLB, 539
model sterowników jądra systemu Linux, 285
model współbieżności, 450
modularność, 342, 423
modyfikowalne zmienne, 408
monitorowanie, 352
mostkowanie, 172
Movement, 359
mRNA, 236
Multiple Instruction Multiple Data, 260
multipleksacja, 307
mutable, 408
mutex, 372
mutex_vector_exit(), 383
N
następne słowo, 511
National Public Radio, 539
nawiasofobia, 558
nawracanie, 25
Neomailbox, 199
Next Word, 511
NFS, 303
nierówność trójkąta, 563
nieustanne testowanie, 485
niezależność od formatu graficznego, 209
niezależność od języka, 342
niezależność od schematów baz danych, 210
S K O R O W I D Z
5 9 1
Poleć książkęKup książkęniezawodność, 343, 346
Node, 359
notacja
#{}, 68
Backusa-Naura, 81
nowy SMP, 268
NPR, 539
ntz(), 175
null denotation, 151
null_bypass, 302, 303
nullfs, 302
NullPointerException, 112
NUMA, 395
numer wersji, 30
NumPy, 321
fragmentowanie, 321
generator liczb losowych, 335
implementacja rozgłaszania, 327
interfejs iteratora, 331
iteracja przez wszystkie wymiary oprócz jednego, 332
iteracje, 323
iteratory, 324
modele pamięci, 323
obiekt multi-iteratora, 334
operacje, 322
projekt iteratora, 325
przerwanie iteratora, 326
PyArray_IterAllButAxis(), 333
PyArrayIterObject, 330
rozgłaszanie, 334
rozwój iteratora, 325
struktura iteratora, 329
śledzenie licznika iteratora, 328
tablice nieciągłe, 323
ustawianie iteratora, 327
wiele iteracji, 333
wykorzystanie iteratora, 332
N-wymiarowe tablice, 321
iteratory, 323
modele pamięci, 323
operacje, 322
O
obciążenie, 386
obiekt fixture, 96
obiektowy framework dla oprogramowania sieciowego, 447
obiekty generyczne, 148
Object Oriented, 449
obliczanie powierzchni, 567
obsługa obrazów nadających się do publikacji,
Pobierz darmowy fragment (pdf)