Dobre praktyki pisania algorytmów

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.

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 lub$field(record)$record.fieldrecord->field

• Używać standardowego zapisu matematycznej matematycznych - zapis zamiast , a mod b zamiast , s ≤ T zamiast , Ź p zamiast , $xy$x*y$a\bmod b$a%b$s\le t$s <= t$\lnot p$!p zamiast,πzamiast,∞zamiastitp.$\sqrt{x}$sqrt(x)$\pi$PI$\infty$MAX_INT

  • Ale użyj do przypisania, aby uniknąć problemu.$x\gets y$==

  • 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 / L$$G$$L$

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}

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.

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.