Reimplementierung von Datenstrukturen in der realen Welt

Question

Das Thema der Algorithmenklasse heute war die Neuimplementierung von Datenstrukturen, insbesondere ArrayList in Java. Die Tatsache, dass Sie eine Struktur auf verschiedene Arten anpassen können, hat mich definitiv interessiert, insbesondere mit Variationen von add() & iterator.remove() Methoden.

Aber reimplementiert und Anpassen einer Datenstruktur etwas, das für die Akademiker vs die realen Programmierer von Interesse ist? Hat jemand seine eigene Version einer Datenstruktur in einer kommerziellen Anwendung/Programm erneut implementiert, und warum haben Sie diesen Weg über die Implementierung Ihrer speziellen Sprache gewählt?

Answer 1

Zu wissen, wie Datenstrukturen implementiert und implementiert werden können, ist definitiv für jeden interessant, nicht nur für Akademiker. Während Sie eine Datenstruktur wahrscheinlich nicht neu implementieren werden, wenn die Sprache bereits eine Implementierung mit geeigneten Funktionen und Leistungsmerkmalen bietet, ist es sehr wahrscheinlich, dass Sie Ihre eigene Datenstruktur erstellen müssen, indem Sie andere Datenstrukturen erstellen ... oder Sie müssen implementieren eine Datenstruktur mit etwas anderem Verhalten als eine bekannte Datenstruktur. In diesem Fall müssen Sie sicher wissen, wie die ursprüngliche Datenstruktur implementiert ist. Alternativ können Sie am Ende eine Datenstruktur benötigen, die nicht existiert oder die einer vorhandenen Datenstruktur ein ähnliches Verhalten verleiht, aber die Art und Weise, in der sie verwendet wird, erfordert, dass sie für eine andere Gruppe von Funktionen optimiert ist. Eine solche Situation würde wiederum erfordern, dass Sie wissen, wie Sie die Datenstruktur implementieren (und ändern), also ist es von Interesse.

bearbeiten
Ich bin nicht, dass Sie bestehenden Datenstrukturen befürworten reimplementieren! Tu das nicht. Was ich sage ist, dass das Wissen praktische Anwendung hat. Beispielsweise müssen Sie möglicherweise eine bidirektionale Kartendatenstruktur erstellen (die Sie implementieren können, indem Sie zwei unidirektionale Kartendatenstrukturen erstellen), oder Sie müssen möglicherweise einen Stapel erstellen, der eine Vielzahl von Statistiken (z. B. min, max, mean) durch Verwendung einer vorhandenen Stack-Datenstruktur mit einem Elementtyp, der den Wert sowie diese verschiedenen Statistiken enthält. Dies sind einige triviale Beispiele für Dinge, die Sie möglicherweise in der realen Welt implementieren müssen.

Answer 2

Ich habe einige der integrierten Datenstrukturen, Funktionen und Klassen einer Sprache mehrfach implementiert. Als Hauptentwickler ist der Hauptgrund, dass ich das tue, Geschwindigkeit oder Effizienz. Die Standardbibliotheken und -typen wurden entwickelt, um in einer Vielzahl von Situationen nützlich zu sein. Es gibt jedoch viele Fälle, in denen ich eine speziellere Version erstellen kann, die auf die Funktionen und Einschränkungen meiner aktuellen Plattform zugeschnitten ist. Wenn die Sprache keine Möglichkeit bietet, existierende Klassen zu öffnen und zu modifizieren (wie Sie es zum Beispiel in Ruby können), dann kann die Wiederverwendung der Klasse/Funktion/Struktur der einzige Weg sein.

Zum Beispiel hat ein System, an dem ich gearbeitet habe, eine MIPS-CPU verwendet, die beim Arbeiten mit 32-Bit-Zahlen schnell, bei kleineren aber langsamer war. Ich habe mehrere Datenstrukturen und Funktionen neu geschrieben, um 32-Bit-Ganzzahlen anstelle von 16-Bit-Ganzzahlen zu verwenden, und außerdem angegeben, dass die Felder an 32-Bit-Grenzen ausgerichtet sind. Das Ergebnis war eine bemerkenswerte Geschwindigkeitssteigerung in einem Codeabschnitt, der andere Teile der Software unter Druck setzte.

Das gesagt, es war kein trivialer Prozess. Ich musste schließlich jede Funktion ändern, die diese Struktur benutzte, und ich musste auch einige Standardbibliotheksfunktionen neu schreiben. In diesem besonderen Fall überwogen die Vorteile die Arbeit. Im allgemeinen Fall ist es jedoch normalerweise nicht die Mühe wert. Es gibt ein großes Potenzial für schwer zu debuggende Probleme, und es ist fast immer mehr Arbeit, als es aussieht. Sofern Sie keine spezifischen Anforderungen oder Einschränkungen haben, die die vorhandenen Strukturen/Klassen nicht erfüllen, würde ich empfehlen, sie nicht erneut zu implementieren.

Wie Michael erwähnt, ist es in der Tat nützlich zu wissen wie Strukturen wieder zu implementieren, auch wenn Sie es nie tun. In der Zukunft könnte ein Problem auftreten, das durch die Anwendung der in bestehenden Datenstrukturen verwendeten Prinzipien und Techniken gelöst werden kann.