Während des aktuellen Google Code Jam- Wettbewerbs (2013) gab es ein Problem, bei dem mehr als 200 Codezeilen für C ++ und Java benötigt wurden, im Vergleich zu Python-Anwendern, die dasselbe Problem nur mit 40 Codezeilen lösten.

Python ist nicht direkt mit C ++ und Java vergleichbar, aber der Unterschied in der Ausführlichkeit, von dem ich dachte, dass er möglicherweise einen Einfluss auf die Effizienz des Algorithmus hat.

Wie wichtig ist es, den richtigen Algorithmus im Vergleich zur Wahl der Sprache zu kennen? Könnte ein exzellent implementiertes Python-Programm besser in C ++ oder Java implementiert werden (unter Verwendung des gleichen Algorithmus) und hat dies irgendeine Beziehung zur natürlichen Ausführlichkeit bestimmter Programmiersprachen?

Wenn Sie diese Frage im Zusammenhang mit etwas wie Google Code Jam betrachten, ist algorithmisches Denken offensichtlich wichtiger, wenn Sie algorithmische Probleme lösen müssen.

Im Alltag müssen aber noch rund eine Million andere Faktoren berücksichtigt werden, was die Frage viel weniger schwarz als weiß macht.

Nur ein Gegenbeispiel: Wenn Sie in Java 200 weitere Zeilen benötigen, aber jeder in Ihrem Unternehmen Java kennt, ist dies keine große Sache. Wenn Sie es in 5 Zeilen Python oder einer anderen Sprache schreiben könnten, aber Sie wären der einzige im Unternehmen, der diese Sprache kennt - es ist eine große Sache. In der Tat eine so große Sache, dass Sie das gar nicht dürfen und stattdessen in Java schreiben müssen.

Aus Sicht eines Handwerkers versuchen wir immer, mit dem richtigen Werkzeug für den Job umzugehen, aber das Wort genau dort ist so schwierig, dass man es leicht falsch verstehen kann.

Im Gegenteil, ich fand, dass algorithmisches Denken in Unternehmen fast nicht vorhanden ist. Nur wenige ausgewählte Personen besitzen es, während der Durchschnittsmensch oft bereits Probleme hat, die Laufzeitkomplexität von Schleifen, Suchen usw. abzuschätzen.

In Bezug auf algorithmische Wettbewerbe sagt mir meine persönliche Erfahrung aus mehreren Jahren, dass Sie sich an eine Sprache halten sollten. Geschwindigkeit ist ein wichtiger Faktor und Sie können es sich einfach nicht leisten, Zeit mit Ihren Werkzeugen zu verschwenden, wenn Sie es darauf verwenden sollten, die Probleme innerhalb der vorgegebenen Zeit zu lösen. Bedenken Sie auch, dass das Schreiben von 200 Zeilen Java-Code ohne Nachdenken immer noch viel schneller ist als das manuelle Erstellen von 50 Zeilen kompliziertem Python-Code, der viel Nachdenken erfordert, wobei beide mehr oder weniger dasselbe Problem lösen.

Stellen Sie sicher, dass Sie die Hauptunterschiede zwischen dem algorithmischen Wettbewerbscode und dem Produktionscode des Unternehmens verstehen. Ich habe fantastische algorithmische Codierer gesehen, die schrecklichen Code geschrieben haben, den ich in einem Produkt niemals akzeptieren würde.

Ich würde argumentieren, dass selbst außerhalb von Wettbewerben algorithmisches Denken wichtiger ist, als jeden Trick für eine bestimmte Sprache zu kennen.

Natürlich möchten Sie die Sprache, mit der Sie arbeiten, so gut wie möglich kennen, aber Sprachen kommen und gehen, während die Fähigkeit, in Algorithmen abstrakt zu denken, eine hochgradig übertragbare Fähigkeit ist.

Ein typisches Beispiel: Wenn ich mich recht erinnere, gab es vor einiger Zeit hier einen Beitrag über Programmierer, in dem sich jemand darüber beschwerte, dass FizzBuzz in einem Interview versagt habe, und sein mangelndes Wissen über Javas Modulo-Operator dafür verantwortlich machte. Diese Schlussfolgerung ist falsch - der Mangel an Wissen über die Funktionsweise von modulo machte es ihm unmöglich, algorithmisch über das Problem nachzudenken und es zu lösen, selbst wenn kein dedizierter Modulo-Operator vorhanden war. Weiter gehen: Java hat eine Tree-Klasse - was ist, wenn Sie in Zukunft mit einer Sprache arbeiten müssen, die diese Klasse nicht implementiert? Auch hier übertrumpft die Fähigkeit, über das Problem nachzudenken, sprachspezifische Details.

Ich gebe zu, dass die Beispiele vereinfachend sind, aber sie helfen, den Punkt zu verdeutlichen.

Sprache ist wichtig.

DARPA und die US - Marine haben ein shootout Experiment vor fast 20 Jahren. Der Sieger der Dark Horse Runaway war Haskell. Ada und C ++ waren beide vertreten; Java war nicht.

Etwa zur gleichen Zeit führte Pratt & Whitney eine Data-Mining-Studie zu Düsentriebwerkssteuerungsprojekten durch, in der Timecard- und Bug-Tracker-Daten untersucht wurden. Sie stellten fest, dass Ada die Produktivität des Programmierers verdoppelt und die Fehlerdichte jeder anderen Sprache, die sie verwendeten, um ein Viertel erhöht.

Atari verwendete FORTH, um Videospiele zu entwickeln, und die Tatsache, dass sie FORTH verwendeten, galt als äußerst geschützt.

Paul Grahams Kommentare zur Verwendung von LISP sind allgemein bekannt. Erann Gats Kommentare zu LISP bei JPL sind ebenso schlüssig, wenn auch nicht so bekannt.

Die Avionik-Software Boeing 777 ist so ziemlich alles von Ada. Ihre Erfahrung war sehr gut, obwohl ein großer Zulieferer mitten im Strom von vorne anfangen musste.

Sprache ist wichtig.

Ein paar Punkte:

• Die oberen Positionen sind in der Regel C ++ / C / Java, unabhängig von der Anzahl der Codezeilen, in denen der Unterschied zu einer anderen Sprache besteht. Dies mag eher darauf zurückzuführen sein, dass die Top-Programmierer diese Sprachen eher auswählen als einige andere, wahrscheinlich aufgrund ihrer Geschwindigkeit.
  Leider ist die Programmiersprache bei Google Code Jam nicht leicht zu erkennen, aber ich habe einige der besten heruntergeladen und soweit ich mich erinnere, handelt es sich hauptsächlich um C / C ++. TopCoder (eine beliebte Hosting-Site für Online-Programmierwettbewerbe) erzielt meist ähnliche Ergebnisse.

• Da sie ziemlich niedrig sind, bin ich mir ziemlich sicher, dass Sie C / C ++ in Bezug auf die unbearbeitete Laufzeit nicht leicht schlagen werden (und Javas Rückstand ist nicht allzu groß). Nach meiner Erfahrung sind dynamisch typisierte Sprachen in der Regel erheblich langsamer als statisch typisierte Sprachen. Die optimale Lösung ist in einigen Sprachen möglicherweise nicht schnell genug, dies sollte jedoch keine allgemeine Regel sein.

• Der richtige Algorithmus ist entscheidend. Wenn Sie von Anfang an alle Probleme (im Detail) gelöst haben und ein guter, schneller Programmierer sind, werden Sie höchstwahrscheinlich gewinnen, unabhängig davon, in welcher Sprache Sie programmieren (vorausgesetzt, Sie haben die optimale Lösung in dieser Sprache ist schnell genug).

• Gerade Anzahl von Linien ist keine so große Sache. Sobald Sie genug Programmiererfahrung haben, werden Sie wissen, dass Sie 10 Minuten damit verbringen können, 10 Zeilen oder 200 Zeilen zu programmieren. Dies hängt alles davon ab, wie komplex die Zeilen sind. Wenn Sie hunderte Male ähnlichen Code geschrieben haben, können Sie dies auch ziemlich schnell tun. Ganz zu schweigen von den Makros, mit denen C / C ++ - Programmierer häufig ihre Codierungszeit optimieren.

• Frank macht einen guten Punkt - (außerhalb von Programmierwettbewerben) Sie können nicht in Python für Ihr Unternehmen programmieren, wenn die gesamte Codebasis in C ist oder was auch immer, Sie müssen sich an ihre Sprache anpassen.

• Es ist einigermaßen einfach, zwischen Sprachen zu wechseln, und es ist nicht einfach, jahrelanges Wissen über algorithmisches Denken aufzubauen. Ich bin bereit zu wetten, dass fast jeder exzellente Programmierer in einer Woche zu einer anderen (undeutlich ähnlichen) Sprache wechseln kann. Vielleicht wird er / sie nicht gut genug sein, um Programmierwettbewerbe in dieser Sprache zu gewinnen (geben Sie ihm noch 2 Wochen), aber er / sie wird die Grundlagen haben.

Kann die gleiche Logik besser in C ++ implementiert werden? Natürlich kann es, wenn mit besser gemeint ist, schneller und speichereffizienter. Problem ist, dass der Aufwand dafür deutlich höher ist. Darüber hinaus könnten Sie theoretisch noch tiefer gehen und es in reinem C oder sogar ASM implementieren, was noch länger dauern würde, aber Sie könnten noch optimierten Code haben.

Natürlich ist es bei Wettbewerben wie Code Jam oder TopCoder kein Problem, da es nur 40 Zeilen gegen 200 Zeilen sind. Auf der anderen Seite ist bei dieser Art von Wettbewerb die zeitliche / räumliche Komplexität des Algorithmus am wichtigsten. In der realen Anwendung schlägt YMMV bei diesen Arten von Wettbewerben den in der langsamsten Sprache geschriebenen O (n) -Algorithmus immer den in der schnellsten Sprache geschriebenen O (n²) . Insbesondere, dass es mehrere Tests geben wird, die den schlimmsten Fall darstellen.

Aber abgesehen von den Wettbewerben, wenn es sich um echte Großprojekte handelt, sind es nicht mehr 40 Zeilen gegenüber 200 Zeilen. In großen Projekten wird die große Codebasis zum Problem. An welchem ​​Punkt kommen Sie zu:

C ++ gegen Python?

Pure Python ist langsam. Aus diesem Grund ist der Standard-Python-Interpreter (CPython) in C geschrieben. Praktisch alle mit integrierten Funktionen, die als hochoptimiertes C geschrieben wurden. Python kann auch problemlos in Verbindung mit C-Bibliotheken (über C- Typen oder als native C-Python- Module ) und mit C ++ - Bibliotheken verwendet werden über Boost :: Python . Auf diese Weise können Sie Ihre übergeordnete Logik in Python schreiben, einer flexiblen Sprache, die ein schnelles Prototyping und eine schnelle Anpassung ermöglicht (was bedeutet, dass Sie mehr Zeit für das Optimieren und Verbessern Ihres Algorithmus aufwenden können). OTOH, Sie können Ihre untergeordneten Bibliotheksfunktionen in C- oder C ++ - Modul schreiben. Ein gutes Beispiel für einen solchen Ansatz ist SciPy, eine Python-Bibliothek. Unter der Haube werden jedoch hochoptimierte numerische Bibliotheken wie ATLAS, LAPACK, Intel MKL oder AMDs ACML verwendet.

Was die Leute umgangssprachlich als "Programmiersprachen" bezeichnen, sind meiner Meinung nach eigentlich drei verschiedene Dinge:

1. Sprachtyp und Syntax
2. Sprach-IDE
3. Verfügbare Bibliotheken für eine Sprache

Wenn zum Beispiel jemand C # in einer Diskussion aufruft, denken Sie vielleicht, er / sie spricht über die Sprachsyntax (1), aber es ist zu 95% sicher, dass die Diskussion das .Net-Framework (3) beinhalten wird. Wenn Sie keine neue Sprache entwerfen, ist es schwierig und normalerweise sinnlos, (1) zu isolieren und (2) und (3) zu ignorieren. Das liegt daran, dass IDE und Standardbibliothek "Komfortfaktoren" sind, die sich direkt auf die Erfahrung mit einem bestimmten Tool auswirken.

In den letzten Jahren habe ich auch an Google Code Jam teilgenommen. Zum ersten Mal habe ich mich für C ++ entschieden, weil es eine gute Unterstützung für das Lesen der Eingabe bietet. Das Lesen von drei Ganzzahlen aus einer Standardeingabe in C ++ sieht beispielsweise folgendermaßen aus:

int n, h, w;
cin >> n >> h >> w;

Während in C # das gleiche wie folgt aussehen würde:

int n, h, w;
string[] tokens = Console.ReadLine().Split(' ');
n = int.Parse(tokens[0]);
h = int.Parse(tokens[1]);
w = int.Parse(tokens[2]);

Das ist viel mehr Aufwand für eine einfache Funktionalität. In C # wird es mit mehrzeiligen Eingaben noch komplizierter. Vielleicht habe ich damals einfach keinen besseren Weg gefunden. Wie auch immer, ich habe die erste Runde nicht bestanden, weil ich einen Fehler hatte, den ich vor dem Ende der Runde nicht korrigieren konnte. Ironischerweise hat die Methode zum Lesen von Eingaben den Fehler verschleiert. Das Problem war einfach, die Eingabe enthielt eine Zahl, die für 32-Bit-Ganzzahlen zu groß war. In C # int.Parse(string)würde eine Ausnahme ausgelöst, aber in C ++ würde der Dateieingabestream ein bestimmtes Fehlerflag setzen und im Hintergrund fehlschlagen, sodass der ahnungslose Entwickler kein Problem bemerkt.

Beide Beispiele zeigen, wie die Bibliothek anstelle der Sprachsyntax verwendet wurde. Der eine zeigt die Ausführlichkeit und der andere die Zuverlässigkeit. Viele Bibliotheken sind auf mehrere Sprachen portiert, und einige Sprachen können Bibliotheken verwenden, die nicht speziell für sie erstellt wurden (siehe @ vartecs Antwort zu Python mit C-Bibliotheken).

Um dies zusammenzufassen, hilft es, den richtigen Algorithmus zu kennen. Bei Codierungswettbewerben ist dies von entscheidender Bedeutung, insbesondere wenn Ressourcen wie Ausführungszeit und Arbeitsspeicher absichtlich begrenzt sind. In der Anwendungsentwicklung ist es willkommen, aber im Allgemeinen nicht entscheidend. Dort ist die Wartbarkeit wichtiger. Dies kann durch die Anwendung korrekter Entwurfsmuster, einer guten Architektur, lesbarem Code und relevanter Dokumentation erreicht werden. Alle diese Methoden hängen stark von internen Bibliotheken und Bibliotheken von Drittanbietern ab. Umso wichtiger finde ich es, zu wissen, welche Arten von Rädern bereits erfunden wurden und wie sie passen, um meine eigenen zu bauen.

Wenn Sie an zeitgesteuerten Programmierwettbewerben teilnehmen möchten, sollten Sie die ausdrucksstärkste Sprache lernen, die der Wettbewerb zulässt. Perl wäre wahrscheinlich am besten, gefolgt von Ruby oder Python. Sie werden immer noch gute Möglichkeiten mit Algorithmen brauchen, aber zumindest werden Sie sich beim Schreiben von so etwas nicht verzetteln

Integer prev = b.get(k)
if (prev == null) prev = 0
Integer v = a.get(k);
if (v == null) v = 0;
b.put(prev + v);

anstatt

b[k] += a[k]

Machen Sie sich keine Sorgen, wenn Sie mehrere Bibliotheken lernen möchten. Sie sind alle sehr ähnlich und die Dokumentation ist online. Wenn Sie in ausdrucksstärkeren Sprachen fließend sprechen, werden Sie zu einem besseren (aber möglicherweise frustrierten) Programmierer in weniger ausdrucksstarken Sprachen. Das Gegenteil ist nicht der Fall.

NB

Der Unterschied zwischen 200 Codezeilen und 40 Codezeilen ist enorm und noch größer, wenn es sich um den Unterschied zwischen einem Programm mit 200.000 Zeilen und einem Programm mit 40.000 Zeilen handelt. Dann ist es der Unterschied zwischen einem Team von fünf und einem Manager und einem oder zwei Teams.

Jeder Algorithmus kann in jeder Programmiersprache implementiert werden. Schließlich ist es nicht die Syntax, die zählt. Die Verwendung einer höheren Programmiersprache wie Python hat jedoch ihre eigenen Vorteile. Weniger Arbeit und weniger Programmieraufwand. Um einen Algorithmus in Python zu implementieren, benötigen Sie weniger Zeilen als in einer einfachen Sprache wie C erforderlich.

In Python sind die meisten Datenstrukturen in die Bibliothek integriert. Aber in C müssen wir bei Null anfangen und eine Struktur verwenden, um alles aufzubauen. Natürlich gibt es Unterschiede zwischen der Hochsprache und der Niedrigsprache, aber die Sprache sollte Sie nicht davon abhalten, einen Algorithmus zu implementieren.

Während die Extrapolation des Beispiels "40 LoC vs 200 LoC" mit der Aussage "gut, nur ein Fünftel der gesamten LoC ist offensichtlich schneller zu schreiben, also muss es besser sein" verlockend erscheint, denke ich wirklich, dass dort wenig Wahrheit zu finden ist.

Die Optimierung auf die wenigsten LoCs ist meiner Meinung nach fast nie eine gute Idee. Ja, jede geschriebene LoC birgt die Gefahr von Fehlern, und Sie müssen niemals das debuggen, was Sie noch nie geschrieben haben. Es geht darum, die Lesbarkeit und Entkopplung zu optimieren. Es spielt keine Rolle, ob Sie ein Problem mit einem 20 Zeilen großen regulären Ausdruck lösen, im Gegensatz zum Schreiben eines Moduls mit 1 KB LoC. Der Regex wird eine undurchsichtige Wand sein, die extrem anfällig für Fehler ist, schwer zu verstehen ist und sich durch Albträume verändert, ohne sein Verhalten auf unverbesserliche Weise zu ändern.

Das Boilerplate und die Ausführlichkeit loszuwerden, die keinen Mehrwert bringen, ist alles in allem gut, aber auf der anderen Seite können Sie so viel Flexibilität bei der Umgestaltung des Codes gewinnen, wenn Sie Java oder C # verwenden und Kenntnisse über Entwurfsmuster und Tools wie Resharper haben Es wäre einfach VIEL schwieriger, wenn Sie es als viel kleineres Python-Skript oder Ruby-App geschrieben hätten.

Ein sehr aussagekräftiger Vergleich: Ich hätte lieber 100.000 LoC von testbedecktem entkoppeltem C # -Code, gefüllt mit "Overkill" -Stoff wie Strategiemuster, Fabriken usw., als eine 20.000-Python-App, die nur "erledigt". 5 mal mehr Code oder nicht, die Architektur gewinnt jeden Tag.

Ich stimme voll und ganz zu, dass einige Arten von Arbeit in einigen Sprachen einfacher und bequemer sind, aber ich glaube eher, dass Sie Ihre Sprache basierend auf den von Ihnen benötigten Tools und den Anforderungen (und möglicherweise in naher Zukunft) auswählen müssen.