Beispiel von Eric Raymond „intelligenten Datenstrukturen“ -Prinzip

Question

In Eric Raymonds Essay Die Kathedrale und der Basar, stellt er dieses oft zitierte Prinzip:

Intelligente Datenstrukturen und stumm Code funktioniert viel besser als die andere Art und Weise um.

Kann jemand ein starkes Beispiel dafür in einer prozeduralen oder objektorientierten Sprache anbieten?

Answer 1

Hier ist für Sie von MaNGOS:

#if defined(__GNUC__) 
#pragma pack(1) 
#else 
#pragma pack(push,1) 
#endif 

typedef struct AUTH_LOGON_CHALLENGE_C 
{ 
    uint8 cmd; 
    uint8 error; 
    uint16 size; 
    uint8 gamename[4]; 
    uint8 version1; 
    uint8 version2; 
    uint8 version3; 
    uint16 build; 
    uint8 platform[4]; 
    uint8 os[4]; 
    uint8 country[4]; 
    uint32 timezone_bias; 
    uint32 ip; 
    uint8 I_len; 
    uint8 I[1]; 
} sAuthLogonChallenge_C; 

Dies ist ein TCP-Paket. Wenn Sie es betrachten, erfahren Sie alle Algorithmen, die Sie zum Senden und Empfangen von wohlgeformten Paketen benötigen. Sie müssen natürlich noch die gültigen Werte für jedes Feld kennen, aber diese sind in der gleichen Datei definiert.

Jetzt stellen Sie sich vor, wenn die gleiche Logik durch die Decoder-Funktion ausgedrückt wurde und Sie einen Client dafür schreiben mussten, indem Sie nur diesen Code betrachteten.

Answer 2

Die C++ STL ist ein gutes Beispiel dafür.

Algorithmen werden mit einem minimalen Satz von Anforderungen erstellt, die Container (und die darin enthaltenen Werte) erfüllen müssen. Wie sie diese Anforderungen erfüllen, ist für die Algorithmen meistens unwichtig, so dass die Datenstrukturen so schlau sind, wie sie sein müssen, um diese Anforderungen zu erfüllen. Von dort wird der Algorithmus (dumm) weggeworfen, und es kann in einer Vielzahl von Fällen über buchstäblich unzählige Arten von Datenstrukturen verwendet werden.

Answer 3

Das klassische Beispiel ist die Operation remove von einer doppelt verknüpften gegen eine einfach verknüpfte Liste (nicht, dass wir uns viel mehr Sorgen machen müssen, aber es veranschaulicht das Prinzipal).

in einer doppelt verknüpften Liste (mit einem Dummy-Knoten, so dass die Liste immer mindestens einen Knoten) einen Knoten mit nur einem Verweise auf diesen Knoten entfernen:

node.Prev.Next = node.Next; 
node.Next.Prev = node.Prev; 

Contrast dies die gleichen Operation in einer einfach verknüpften Liste, die das Durchlaufen der gesamten Liste erfordert.

Dies veranschaulicht die Idee, dass Algorithmen fast immer die Komplexität der Datenstrukturen widerspiegeln. Dies gilt umso mehr für Datenbankanwendungen, bei denen komplexe Datenbankschemas komplexen Code erstellen und umgekehrt. Ich denke, die meisten erfahrenen Programmierer haben mehr Flüche über lausige Datenmodelle als miesen Code geäußert (obwohl das auch mit dem Grad der Refactoring-Schwierigkeit zwischen Daten und Code zu tun hat).

Aus Wikipedia:

doppelt verkettete Listen erfordern mehr Platz pro Knoten (es sei denn, man verwendet xor Vernetzung) und ihre elementaren Operationen sind teurer; aber sie sind oft einfacher zu manipulieren, weil sie einen sequentiellen Zugriff auf die Liste in beide Richtungen erlauben. Insbesondere kann man einen Knoten in einer konstanten Anzahl von Operationen einfügen oder löschen, wobei nur die Adresse dieses Knotens gegeben ist. Um dasselbe in einer einfach verknüpften Liste zu machen, muss man die Adresse des vorherigen Knotens haben. Einige Algorithmen erfordern Zugriff in beide Richtungen. Auf der anderen Seite erlauben sie keine Tail-Sharing und können nicht als persistente Datenstrukturen verwendet werden.

Answer 4

Das ist wahrscheinlich nicht das, was Sie meinen, aber hier ist eine Idee.

Wenn die Datenstrukturen Qualitätswerkzeuge sind, machen sie den Rest des Codes einfacher und billiger zu schreiben. Mit qualitativ hochwertigen Datenstrukturen reduzieren Sie den Aufwand für den Rest des Codes.

Das Beispiel, das in den Sinn kommt, ist map-reduce. Durch die Einstellung eines kleinen Teams von Super-Genies, die massive Parallelität verstehen, profitiert Ihre gesamte Codebasis von der Fähigkeit, nicht zu iterieren. Der Rest Ihrer nicht-ganz-super-Genie Programmierer schreiben besseren Code nur durch die Verwendung der intelligenten Datenstrukturen.

http://www.joelonsoftware.com/items/2006/08/01.html

Answer 5

@ Rob auf dem richtigen Weg hier ein gutes Beispiel. Sehen Sie sich die Auflistungsobjekte in C# oder Java an.

Ich denke, ich kann ein wenig erweitern, um dies klarer zu machen, warum dies ein gutes Beispiel ist ... Es gibt viele Möglichkeiten, Listen zu erstellen, aber es gibt ein paar grundlegende Operationen, die gemeinsam sind. Diese Operationen variieren alle mit der spezifischen Implementierung, aber der Aufrufer sollte nicht kümmern. Der Anrufer sollte sich darum kümmern, dass die Liste bestimmte Funktionen hat und weiß, wie es geht.

Nehmen wir zum Beispiel an, wir hätten einen Roboter, der unsere Einkäufe erledigt und für uns weggegeben hat.

while there are items in the bag's list 
    remove the next item from the bag 
    put away the item 

put in etwas mehr Code-ish

while (item = bag.NextItem()) 
{ 
    bag.Remove(item); 
    robot.PutAway(item); 
} 

Nun ist es Ihnen, wie die Liste der Elemente in der Tasche umgesetzt wird? Nein überhaupt nicht. Es ist dir nur wichtig, dass du den nächsten Gegenstand findest und ihn aus der Tasche nimmst. Ob die Tasche eine doppelt verkettete Liste ist, eine einzelne verkettete Liste, was auch immer, spielt keine Rolle.

Also, der Entwickler, der diesen abscheulichen PutAway-Algorithmus schreibt, interessiert sich nicht dafür, wie sie Artikel finden, sie kümmern sich nur darum, dass sie den Gegenstand haben. Der Tasche ist es egal, was mit den Gegenständen passiert, es interessiert nur, dass sie sie eine Weile halten können, dann werden sie weggenommen. Und dieser Entwickler wird für das Wochenende nach Hause gehen. :)

Natürlich ist dies ein schmerzlich einfaches Beispiel, es gibt eine ganze Reihe von Löchern, die Sie hineinstecken können.

Answer 6

Der Satz, den Sie zitieren, kommt unmittelbar nach einem guten Beispiel:

Die erste ernsthafte Veränderung, die ich machte, war IMAP-Unterstützung hinzuzufügen. Dazu habe ich die Protokollmaschinen in einen generischen Treiber und drei Methodentabellen (für POP2, POP3 und IMAP) umorganisiert.