Wörterbücher im Pseudocode

8

Was ist eine gute, übliche Methode, um Wörterbücher (= Karten) im Pseudocode auszudrücken? Das heißt, Datenstrukturen, die es grundsätzlich ermöglichen, Werte für Schlüssel zu speichern, über alle Schlüssel / Wert-Paare zu iterieren, auf die Aufnahme eines bestimmten Schlüssels zu testen usw. Ich denke an den folgenden (in diesem Fall sinnlosen) Python-Code:

D = {}
D[1] = 2
for key, value in D.items():
    # do something with key and value
if key in D:
    # do something

Und ich möchte es als Pseudocode in einer Publikation ausdrücken. Mathematisch denken, Wörterbücher sind Funktionen, Beziehungen sind Mengen von Paaren, also schreiben Sie so etwas wie

D ← ∅
D[1] ← 2
for all (k, v) ∈ D

würde eigentlich Sinn machen. Aber ist es verständlich? Und für den Test würde ich verwenden

if k ∈ keys(D)

Oder ist es sicherer, wörtlicher zu sein, z

D ← empty dictionary
for all key-value pairs (k, v) in D

Gibt es bewährte Verfahren / Hinweise zum Schreiben eines allgemein verständlichen Pseudocodes?

Jan Pöschko
quelle
Ich denke, dies sollte auf Stackoverflow verschoben werden.
David Ketcheson
Ich habe auch über Stack Overflow nachgedacht, war aber im Zweifel, weil es nicht um die eigentliche Programmierung geht, sondern nur darum, wie man sie präsentiert, was sicherlich mit der Computerwissenschaft zusammenhängt. Wenn Sie jedoch das Gefühl haben, dass es bewegt werden sollte, kann jemand das für mich tun? (Ich selbst kann nicht, kann ich?)
Jan Pöschko
Ich habe gerade eine Diskussion über Meta unter meta.scicomp.stackexchange.com/questions/205/… begonnen
Jan Pöschko
@DavidKetcheson: Wenn Sie der Meinung sind, dass die Frage in Zukunft migriert werden sollte, markieren Sie sie bitte für die Migration. In diesem Fall hat Jan recht; Es geht nicht um die eigentliche Programmierung, daher geht es bei Stack Overflow nicht um ein Thema. Es kann jedoch ein Thema für Programmierer oder Theorie sein. Ich müsste mit den cstheory-Mods über die gewünschten Änderungen sprechen, da einer ihrer Mods erwähnte, dass die Frage für ihre Site optimiert werden müsste.
Geoff Oxberry
In der Zwischenzeit kann dieser Link zu einer Frage zur Theorie im Meta-Thread (mit freundlicher Genehmigung von Theorie Kaveh) für Personen von Interesse sein, die an dieser Frage interessiert sind.
Geoff Oxberry

Antworten:

7

Es sieht so aus, als würden Sie bereits einige der Konzepte von Corwin, Leiserson, Rivest und Stein , die ich immer als "Standard" -Einführungstext für Algorithmen angesehen habe, beim Schreiben Ihres Pseudocodes verwenden. Ich glaube nicht, dass es mehr Standardreferenzen für Pseudocode gibt.

Ich würde jedoch argumentieren, dass ein guter Pseudocode darin besteht, das Problem in seine repräsentativen mathematischen und logischen Funktionen zu zerlegen. Welche Bedingungen müssen erfüllt sein, um den Code auszuführen? Welche Zweige gibt es? Welche Daten sind für die Bestimmung des Verhaltens wirklich wichtig?

Darüber hinaus besteht das Ziel eines guten Pseudocodes darin, dem Programmierer mitzuteilen, was zu tun ist - und nicht unbedingt, wie es implementiert werden soll. Möglicherweise möchten Sie beispielsweise verschachtelte Schleifen in einer einzigen Anweisung zusammenfassen:

For all elements x in 2-D array A
    x ← max(0, x)

wäre wahrscheinlich besser als zu sagen

For all i in 1:m
   For all j in 1:n
       A(i,j) ← max(0, A(i,j)

da letzterer bereits einige Annahmen über die verwendete Sprache macht (Zeilenmajor versus Spaltenmajor usw.).

aeismail
quelle
4

Ich denke, es hängt vom Kontext der Veröffentlichung, dem beabsichtigten Publikum und davon ab, wie "allgemein" Sie "allgemein verständlich" sein müssen. Ich denke, Ihre letzte Option ist wahrscheinlich am sichersten, dh so wörtlich / explizit und so nah wie möglich an "einfachem Englisch". Wenn Ihre Zielgruppe jedoch mit der Mengenlehre, Python, Java, C #, JavaScript usw. vertraut ist, ist eine ähnliche Notation möglicherweise besser.

Ich mache diesen Vorschlag als jemand, der Vorstellungsgespräche führt, bei denen vom Kandidaten erwartet wird, dass er Code oder Pseudocode schreibt. Die meisten Kandidaten (sowohl gute als auch schlechte) tendieren dazu, sich der Sprache zuzuwenden, mit der sie am besten vertraut sind, um ihren Pseudocode für sich und mich so verständlich wie möglich zu machen. Leute, die mit Java vertraut sind, schreiben Map<K,V>. Leute, die mit Python vertraut sind, schreiben Tupel oder ein Wörterbuch, wie Sie es in Ihrem ersten Code-Snippet getan haben. Mit C vertraute Personen schreiben Arrays. Leute mit weniger Programmierhintergrund neigen dazu, Pseudocode zu schreiben, der eher wie einfaches Englisch aussieht - aber oft wie Python aussieht. :-)

Ich kann Ihre letzte Frage leider nicht beantworten - ich kenne keine Referenz oder allgemeinen Empfehlungen zum Schreiben von Pseudocode.

Paul Karlin
quelle