Dobre praktyki pisania algorytmów


22

Chodzi o to, jak skutecznie możemy wyrazić algorytm. Potrzebuję tego do moich studiów licencjackich.

Rozumiem, że nie ma czegoś takiego jak standardowy sposób pisania pseudo kodu. Różni autorzy stosują różne konwencje.

Byłoby pomocne, gdyby ludzie tutaj wskazywali, w jaki sposób podążają i myślą najlepiej.

Czy jest jakaś książka, która zajmuje się tym szczegółowo.


9
„najlepszy” jest bardzo subiektywny, myślę, że powinieneś zmodyfikować tytuł, a zamiast prosić o „najlepszy”, zapytaj o to, co ludzie robią w praktyce. Może coś w rodzaju „jak przedstawiać algorytmy” lub „dobre praktyki w zakresie przedstawiania algorytmów”. Możesz także być bardziej szczegółowy, ponieważ przedstawianie algorytmów: 1. uczniom w klasie licencjackiej 2. w podręczniku 3. w dokumencie konferencyjnym są bardzo różne zadania.
Kaveh

1
Możesz także sprawdzić odpowiednie sekcje pisania matematycznego Knutha, Larrabee i Robertsa.
Kaveh,

Odpowiedzi:


26

Pisanie pseudokodu przypomina pisanie kodu: nie jest szczególnie ważne, którego standardu przestrzegasz, o ile ty (i ludzie, z którymi piszesz) faktycznie przestrzegasz jakiegoś standardu.

Ale dla przypomnienia, oto idiosynkratyczny standard, którego używam w moich notatkach z wykładów, artykułach naukowych i nadchodzącej książce.

  • Użyj standardowej składni imperatywnej do sterowania przepływem i dostępu do pamięci - if, while, for, return, array [index], function (arguments). Przeliteruj „else if”.

    • Ale użyj zamiast lubfield(record)record.fieldrecord->field
  • Używać standardowego zapisu matematycznej matematycznych - zapis zamiast , a mod b zamiast , s T zamiast , Ź p zamiast , xyx*yamodba%bsts <= t¬p!p zamiast,πzamiast,zamiastitp.xsqrt(x)πPIMAX_INT

    • Ale użyj do przypisania, aby uniknąć problemu.xy==

    • Ale unikaj notacji (i pseudokodu!) Całkowicie, jeśli angielski jest wyraźniejszy.

      • Symetrycznie, unikaj angielskiego, jeśli notacja jest wyraźniejsza!
  • Minimalizuj cukier składniowy - Wskaż strukturę bloku poprzez spójne wcięcie (à la Python). Pomiń słodkie słowa kluczowe, takie jak „początek / koniec”, „do / od” lub „fi”. Pomiń numery linii. Czy nie podkreślać słowa kluczowe jak „za” lub „a” lub „jeśli”, ustawiając je w inny typefacelub stylu . Zawsze. Po prostu nie.

    • Ale nazwy i stałe algorytmów składu w \ textsc {Small Caps}, nazwy zmiennych kursywą i ciągi literalne w sans serif.

    • Dodaj jednak niewielką ilość pionowej „oddychającej” przestrzeni ( \\[0.5ex]) między znaczącymi fragmentami kodu.

  • Nie podawaj nieistotnych szczegółów. Jeśli nie ma znaczenia, w jakiej kolejności odwiedzasz wierzchołki, powiedz „dla wszystkich wierzchołków”.

Na przykład, tutaj jest rekurencyjne sformułowanie algorytmu minimalnego drzewa opinającego Borůvki . Wcześniej zdefiniowałem jako wykres otrzymany z G przez skurczenie wszystkich krawędzi w zestawie L , a Spłaszcz jako podprogram, który usuwa pętle i równoległe krawędzie.G/LGL

Algorytm Borůvka

Używam własnego, lekkiego algorithmśrodowiska LaTeX do pisania pseudokodu. (To tylko tabbingśrodowisko wewnątrz \fbox.) Oto mój kod źródłowy algorytmu Borůvka:

\begin{algorithm}
	\textul{$\textsc{Borůvka}(G)$:}\+
\\	if $G$ has no edges\+
\\		return $\varnothing$\-
\\[0.5ex]
	$L \gets \varnothing$
\\	for each vertex $v$ of $G$\+
\\		add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
	return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}

fj(v)jthv

@SureshVenkat: Tak zazwyczaj robisz w językach funkcjonalnych, a także notacja w TAoCP. (Oczywiście nie wiem, czy właśnie dlatego Jɛ ff E używa tej notacji.)
Radu GRIGore 10.11.11

5
Głównym powodem, dla którego należy uważać na pseudo-kod, jest to, że łatwo jest pomylić się z algorytmem, dlatego ważne jest podkreślenie niektórych rzeczy. Powyższy przykład Jeffa dotyczący Boruvki ilustruje to. W kodzie L jest traktowany jako zestaw. Krawędź uv może być najlżejszym zdarzeniem krawędzi u, a także v, więc jest dodawana dwukrotnie w pętli, ale nie ma znaczenia, czy myślisz o L jako zestawie. Nie jest to jednak oczywiste i ktoś, kto to zaimplementuje, może łatwo zostać wyzwolony, jeśli zaimplementuje L jako listę.
Chandra Chekuri,

2
@ChandraChekuri: Tak, niepoprawne wdrażanie zestawów może powodować problemy w algorytmach manipulujących zestawami.
Jeffε

1
@SureshVenkat: Och, to. Nie mogę tego znieść. Odważne słowa kluczowe powodują płacz małego Jezusa. Dijkstra powinien stracić nagrodę Turinga za wprowadzenie tej wykonalnej konwencji typograficznej.
Jeffε

11

Zwykle używam czegoś przypominającego składnię Pythona. Python jest już na tyle blisko pseudokodu, że w niektórych przypadkach mój pseudokod może zacienić się na faktyczny działający kod.


Ja też, ale w Ruby. Dzięki github gists możesz łatwo udostępniać wykonywalne fragmenty, aby mogli się nimi bawić. gist.github.com/chadbrewbaker/7202412
Chad Brewbaker

Python nie jest jednak dobry do reprezentowania algebry liniowej. Myślę, że oktawa jest lepszym rozwiązaniem w tym przypadku (bliżej pseudokodu).
gaboryczny

3

Jeśli chcesz mieć określony kod (tj. Mało lub nie matematyki, blisko prawdziwego programowania), możesz rozważyć kod, który faktycznie się kompiluje. Ma to kilka zalet:

  • Wszędzie widać podświetlanie składni.
  • Kompilator sprawdza dla Ciebie składnię i wymusza spójność.
  • Możesz testować jednostkowo swoje implementacje, aby poprawić jakość kodu.
  • Możesz uruchomić algorytm i porównać zmierzone środowiska wykonawcze z analizami (motywując w ten sposób zaawansowane techniki analizy).

Profesor na moim uniwersytecie robi to na kursie algorytmów. Jego wybranym językiem jest Modula. Nie sądzę jednak, żeby konkretny wybór języka miał znaczenie. Po prostu trzymaj się jednego (według paradygmatu), który najlepiej pasuje do twojego poziomu abstrakcji.


„Po prostu trzymaj się jednego (według paradygmatu), który najlepiej pasuje do twojego poziomu abstrakcji”. Myślę, że to świetna rada, aby znaleźć alternatywę dla pseudokodu. Istnieje wiele języków i prawie zawsze istnieje co najmniej jeden, który celuje w prostą składnię dla konkretnego paradygmatu: Ada dla współbieżnego projektowania, Octave dla algebry liniowej, Python dla procedur, NetLogo dla systemów wieloagentowych, Prolog dla logiki, CLIPS dla programowanie oparte na regułach itp.
wredny

@gaborous Jeśli możesz mieć czytelny, abstrakcyjny kod - idź do niego. Niestety podejrzewam, że dzięki temu będziesz używać co najmniej trzech języków w jakimkolwiek większym obszarze pracy; to też byłoby niefortunne.
Raphael

oczywiście zgadzam się na większy kod, nie ma języka, ale w przypadku małych, podstawowych algorytmów często można znaleźć język bardzo zbliżony do pseudokodu.
nudny
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.