Wie würden Sie die Funktion "Route berechnen" von Google Maps testen?

13

(Ich stelle mir vor, das wäre eine gute Interviewfrage , aber in meinem Fall ist es pragmatischer.)

Wir haben eine große und komplexe Anwendung , die einen extrem langen und ausgeklügelten chemischen Reaktionsprozess zwischen Dutzenden chemischer Komponenten modelliert. Wir sind gerade dabei, Abnahmetests für die Anwendung zu entwerfen, sind jedoch etwas entmutigt über die unlösbare Anzahl möglicher Testpfade. Mir ist aufgefallen, dass unsere Situation der Situation des Google Maps-Entwicklerteams sehr ähnlich ist, als es darum ging, den Routenplanungsalgorithmus in der Funktion "Route berechnen" zu testen. Offensichtlich konnten sie nicht jede mögliche Route testen (verifizieren und validieren). Wie kamen sie zu der Gewissheit, dass ihre Anwendung in jeder Situation funktionieren würde?

Und da ich nicht damit rechne, herauszufinden, wie sie es geschafft haben, möchte ich Sie fragen: Wie würden Sie eine Testsuite mit angemessener Codeabdeckung entwerfen , um sich davon zu überzeugen, dass eine bestimmte Anwendung robust ist - wenn es buchstäblich unmöglich ist jeden möglichen Weg durch das System zu sondieren?

Was ich suche, sind die Prinzipien, die Sie verwenden würden, um ein hartnäckiges Problem in kleinere, handhabbare Teile zu zerlegen, deren Summe eine zufriedenstellende Schätzung des Ganzen liefert: "Ich kann nicht alles testen, aber ich kann dies testen , dies und das - und das ist genug. " Ich suche nicht einen Ansatz, der "nachweislich richtig" ist, sondern einen , der angesichts realer Budget- / Zeitbeschränkungen umsichtig ist.

(Ich verwende das Google Maps-Beispiel als eine Art Folie, um Antworten zu erhalten, die so spezifisch wie möglich sind.)

kmote
quelle
Google Maps hat in der Vergangenheit versucht, mich nur auf Busstraßen zu lenken, auf Einbahnstraßen in die falsche Richtung und an Kreuzungen, die es nicht gibt (z. B. eine Überführung mit nur einer Abzweigung). Ich glaube, sie haben eine Funktion zum Melden falscher Richtungen, aber das ist wahrscheinlich nicht das, was in Ihrer Situation funktionieren würde. Die Antwort auf die Frage, ob sie alles testen? Sie taten es nicht und sie brauchten es auch nicht wirklich.
John Lyon
Wie immer bei Fragen dieser Art empfehle ich Ihnen, die Bücher und Artikel von Nassim Nicholas Taleb zu lesen. Hier ist ein technischer Artikel , der sich mit Mathematik befasst, aber ich empfehle dringend, seine Bücher zu lesen.
Jfrankcarr
Ich glaube nicht, dass Sie einen Test entwerfen können, der alle Fälle für etwas abdeckt, das ausreichend komplex ist. Wenn Sie wissen, wie das Innere funktioniert, können Sie Tests für jeden offensichtlichen Weg erstellen, aber es wird immer Dinge geben, an die niemand jemals gedacht hat. Sie denken nur an so viele wie möglich und hoffen, dass die, die Sie verpassen, kein allzu großes Problem sind.
Loren Pechtel
2
@jozzas: Alles, was Sie beschreiben, sind Datenbankfehler, kein Problem mit dem Richtungsalgorithmus von Google. Ein Äquivalent wäre heute Morgen, wenn mein Navi versucht hätte, mich auf eine unbefestigte Straße zu lenken. Auf der anderen Seite war es ein echter Bug, als ich eine Spurensperrungsmeldung über eine Straße erhielt, die ich gerade verlassen wollte. (Der
Hinweis bezieht sich
1
Nenne es "Beta". Erledigt. Dies ist der Google-Weg.
Paystey

Antworten:

10

Ich habe vor über einem Jahrzehnt in der Autonavigation gearbeitet.

Schritt A) Verwenden Sie ein Referenzpaket und wählen Sie einen großen Probensatz aus. Führen Sie A / B-Tests durch. Keine Suche nach Genauigkeit, keine Suche nach Ausreißern - Im Referenzsatz wurde die Route 1234 mit 10,34 km angegeben, und wir berechneten 123,5 km.

Schritt B) - Verfeinern Sie unsere Software und die Referenzsoftware. - Fügen Sie weitere Muster hinzu und reduzieren Sie die Toleranzen.

Schritt C) - In-House-Tests mit lokalem Wissen über globale Datensätze hinweg.

Schritt D) UAT ... "User Acceptance Test" Wie in "Verkaufe dieses Zeug und schau, worüber sich die Kunden am meisten beschweren"

Wenn Sie jemals Mapping-Produkte zwischen Mitte der 1990er und 2000 verwendet haben, wissen Sie, was ich meine, diejenigen von uns, die noch jedes Mal die Abbiegehinweise überprüft haben.

Zurück zu Ihrer Beispielfrage. Was Sie gefragt werden, ist, wie Sie beweisen können, dass eine Software korrekt ist. Wenn Sie einen mathematischen Beweis benötigen, ist nachgewiesen, dass dies möglich ist - für einfache Software zu einem Preis, der jedes realistische Budget übersteigt, für ein komplexes Softwarepaket, das noch in der Forschung steckt. Die NASA verfügt über Modelle zum Schreiben von hochzuverlässiger Software innerhalb wirtschaftlich überschaubarer Preise, ebenso wie DoD und die Luftfahrtindustrie - obwohl immer noch viel höher als die meisten bereit sind zu zahlen. Am Ende kommt es darauf an, wie viel Sie bereit sind zu zahlen .....

Edit: Ich habe gerade das OP neu gelesen. Was Sie suchen, ist anscheinend eine schnelle und kostengünstige Möglichkeit, die Qualität einer komplexen Software zu testen. Sie können nicht in der Qualität testen. Sie benötigen einen robusten Prozess, damit Sie wissen, dass das, was erstellt wird, richtig funktioniert. Wenn Sie darüber nachdenken müssen, wie Sie die Richtigkeit beweisen können und bereits eine "große und komplexe Anwendung" haben, sind Sie zu spät.

mattnz
quelle
5

Wir sind einer der Konkurrenten von Google. Unsere Antwort? Grundsätzlich zwei.

Zunächst berechnen wir die vollständige Adress-zu-Adress-Lösung. Ja, das ist eine große Matrix. Schlimmer noch, wir tun dies zu jeder Tageszeit, an allen Tagen der Woche. In der Eingabedomäne gibt es genügend Ähnlichkeiten, um Zwischenergebnisse zwischenzuspeichern, wodurch das Problem behoben werden kann. Versuchen Sie dennoch, eine Bulk-Rate für Festplatten zu ermitteln.

Beachten Sie, dass diese Offline-Berechnung mit einem anderen Algorithmus durchgeführt wird. Es verwendet viel mehr Speicher als der Algorithmus, den wir testen möchten, aber nicht linear mehr (dh es verwendet weniger als das 1000-fache an Speicher, wenn tausend Routen berechnet werden).

Zweitens liefern uns die teilnehmenden Benutzer reale Ergebnisse. Wir validieren Millionen von gefahrenen Strecken. Sind die tatsächlichen Routen so schnell wie vorhergesagt?

Und natürlich finden Sie auf diese Weise Fehler. Jedesmal. ZB ein Straßenabschnitt, der auf beiden Seiten von einer "Nur-Nahverkehrszone" * begrenzt wird. Es gibt nur einen Weg;), den Sie beim Testen finden werden, und dann planen Sie eine Route zu dieser bestimmten Straße.

* Eine "Zone nur für lokalen Verkehr" kann nur verwendet werden, wenn Sie eine Route in einer solchen Zone starten oder beenden. Die Strecke in der Mitte ist daher vom Hauptstraßennetz getrennt. Dies ist entweder ein Zonen- oder ein Kartenfehler.

MSalters
quelle
3

Es ist nicht so, als würde Google für jedes Adresspaar der Welt einen eigenen Code schreiben. Mit Ausnahme von Heuristiken, die in größerem Maßstab eingesetzt werden, ist der Algorithmus für eine Reise mit drei Etappen genau derselbe wie für eine Reise mit 3000 Etappen. Sie testen die kürzeren Pfade gründlich und verwenden die Induktion, um zu zeigen, dass der Test auch für längere Pfade gilt.

Sie wählen eine gesunde Stichprobe realer Routen aus und vergleichen sie mit den Vorstellungen eines Menschen. Sie legen großen Wert auf das Feedback der Endbenutzer in Ihren ersten Releases und erleichtern ihnen die Bereitstellung. Sie testen die Randbedingungen, zum Beispiel, ob die beste Route tatsächlich eine Weile vom Ziel entfernt sein muss oder ob die kürzeste Route nach Entfernung 18 Umdrehungen aufweist, verglichen mit einer direkteren Route, die etwas länger ist. Sie machen negative Tests, wenn Sie versuchen, von Kalifornien nach Hawaii zu fahren, und stellen sicher, dass clevere Ostereier vorhanden sind.

Karl Bielefeldt
quelle
Ich bin sicher, dass alles, was Sie vorgeschlagen haben, korrekt ist, aber ich kann nicht anders, als das Gefühl zu haben, dass es immer noch nicht ausreichend streng ist. "Eine gesunde Stichprobe von Routen auswählen" klingt eher so, wie ich es für ein Semesterprojekt am College tun könnte, als wie es sich ein erstklassiges Entwicklungsteam ausdenken würde. Und obwohl ich Ihrer Beobachtung zu den 3-Strecken-Routen im Vergleich zu den 3000-Strecken-Routen zustimme, scheint es immer noch recht ehrgeizig, auch einen großen Teil der 3-Strecken-Routen zu testen. Ich habe das Gefühl, dass uns hier noch etwas Grundlegendes fehlt.
kmote
@kmote: "Aber ich kann nicht anders, als das Gefühl zu haben, dass es immer noch nicht ausreichend streng ist." Warum nicht, es hat eine Generation lang für die Softwareindustrie funktioniert und es gibt kein wirkliches Anzeichen dafür, dass es bald abgelöst wird. Wir werden dafür bezahlt, Code zu schreiben, der Geld verdient, und nicht dafür, Code zu schreiben, der perfekt ist. Wenn Sie sich das vorstellen, ist es das, was in der Medizin, im Ingenieurwesen und in praktisch allen Berufen verwendet wird, und es scheint, dass es diese Industrien angemessen gut macht.
Mattnz