Das mag naiv klingen, aber gibt es irgendwelche Datenstrukturen / Algorithmen, die nicht in C konstruiert werden können, wenn man genug Code hat? Ich verstehe das Argument, Turing sei vollständig. Ich weiß auch, dass es vorteilhaft ist, eine elegante Lösung zu haben, und dass die zeitliche Komplexität wichtig ist (d. H. Expressiver oder prägnanter, wenn sie in Ruby / Java / C # / Haskell / Lisp implementiert wird). Alle Sprachen, die ich erforscht oder verwendet habe, scheinen alle in C-basierten Compilern, Interpretern und / oder virtuellen Maschinen erstellt oder nachträglich refaktoriert worden zu sein. Sind einige komplexe Datenstrukturen nur mit einem Interpreter und / oder einer virtuellen Maschine implementierbar? Wenn diese virtuelle Maschine oder dieser Interpreter C-basiert ist, ist das nicht nur eine weitere Datenstrukturabstraktion des zugrundeliegenden C-Codes? h. C hat ein einfaches System, dient aber als Grundlage für ein dynamisches System. Ich war überrascht zu erfahren, dass Metaprogrammierung in C mit dem Präprozessor ( ioccc.org Immanuel Herrmann ) möglich erscheint. Ich habe auch einige faszinierende C-Algorithmen gesehen, die das Gleichzeitigkeitsmodell von Erlang nachahmen, aber nicht an die Quelle erinnern.
Was diese Frage inspirierte, war der StackOverflow-Beitrag ( Lesser Known) Nützliche Datenstrukturen ) und das Patrick-Dussud-Interview auf channel9 ( Garbage Collection - Vergangenheit, Gegenwart und Zukunft ) - erklären, wie sie den ersten CLR Garbage Collector (geschrieben in Lisp für die JVM, kompiliert von Lisp nach C ++ für die CLR) geschrieben haben.
Also, am Ende des Tages, nachdem ich mit dem Ausstanzen meiner Karten fertig bin, frage ich mich, ob diese Frage wahrscheinlich eher das C-Programmiersprachen-Design als die Bequemlichkeit der Programmierung und die zeitliche Komplexität betrifft. Zum Beispiel könnte ich einen sehr komplexen Algorithmus in Prolog implementieren, der sehr elegant und ziemlich schwierig zu verstehen ist, anders ausgedrückt, aber ich bin immer noch eingeschränkt durch die Montageanweisungen und die Computerarchitektur (an / aus) am anderen Ende von der Stock, also wäre ich die ganze Nacht hier.
Shors Algorithmus zum Faktorisieren von ganzen Zahlen in O((log n)^3) polynomialer Zeit kann nicht in C implementiert werden, weil die Computer Es kann weiterlaufen, noch nicht offiziell existieren. Vielleicht wird es irgendwann eine vollständige Version von C geben, und ich muss meine Antwort überarbeiten.
Spaß beiseite, ich glaube nicht, dass irgendjemand Ihnen eine befriedigende Antwort geben kann. Ich werde versuchen, einige Aspekte zu behandeln:
Jede Turing-vollständige Maschine oder Sprache kann jede andere Turing-vollständige Sprache implementieren, was bedeutet, dass sie jedes Programm implementieren kann in jeder anderen Turing-vollständigen Sprache durch Interpretation, wenn kein anderer Weg. Die Frage, die Sie stellen, ist schlecht formuliert. Das Problem ist nicht, ob Aufgaben erledigt werden können, sondern wie sehr Sie daran arbeiten müssen.
Insbesondere funktioniertC fast wie eine "Assemblersprache auf hoher Ebene", da es Ihnen viele Dinge ermöglicht, die neuere Sprachen nicht bieten, und somit Lösungen ermöglichen, die in einem größeren Umfang schwieriger zu implementieren wären stark geprüfte Sprache.
Das bedeutet nicht, dass C die beste Sprache für all diese Zwecke ist. Es zwingt Sie, in vielen Bereichen viel mehr auf Details zu achten, von der Speicherverwaltung über die Überprüfung der Grenzen bis hin zur Objektorientierung (Sie können OO-Code in C schreiben, aber Sie müssen es von Grund auf implementieren). Sie müssen Bibliotheken explizit für Dinge laden und aufrufen, die in andere Sprachen eingebaut werden können. C-Datentypen können unglaublich verworren sein (obwohl Typedefs und Makros einen Großteil dieser Komplexität verbergen können). Und so weiter.
Das beste Werkzeug für jede Aufgabe ist diejenige, mit der Sie vertraut sind oder werden können; (b) das ist gut für die Aufgabe geeignet und (c) die Sie zur Verfügung haben.
Werfen Sie einen Blick auf Turing Vollständigkeit: Turing Vollständigkeit
Grundsätzlich kann jede Sprache, die Turing vollständig ist, alle Turing-berechenbaren Funktionen ausführen. C ist eine vollständige Turing-Sprache, daher können Sie in der Theorie jeden bekannten lösbaren Algorithmus in C implementieren (auch wenn er sehr ineffizient ist).
Tags und Links algorithm c data-structures