Come testare la funzionalità "Ottieni indicazioni" di Google Maps?

13

(Immagino che questo sarebbe un buon domanda dell'intervista , ma nel mio caso è più pragmatica di così.)

Abbiamo large & un'applicazione complessa che modella un processo di reazione chimica estremamente lungo e sofisticato tra dozzine di componenti chimici. Siamo nella fase di progettazione di Acceptance Tests per l'applicazione, ma siamo piuttosto scoraggiati dal numero intrattabile di possibili percorsi da testare. Mi è venuto in mente che la nostra situazione è molto simile a quello che deve aver affrontato il team di sviluppo di Google Maps quando è arrivato il momento di testare l'algoritmo di pianificazione del percorso nella loro funzione "Ottieni indicazioni". Ovviamente non potevano testare (verificare e validare) ogni possibile percorso. Quindi, come hanno avuto la certezza che la loro applicazione avrebbe funzionato in ogni situazione?

E poiché non mi aspetto di scoprire come loro l'hanno fatto, permettimi di chiederti: come farebbe tu a progettare una suite di test con un'adeguata copertura del codice , per soddisfare te stesso che una data applicazione è solida - quando è letteralmente impossibile sondare ogni potenziale percorso attraverso il sistema?

Quello che sto cercando sono i principi che useresti per abbattere un problema intrattabile in parti più piccole e trattabili, la cui somma fornisce una stima soddisfacente del tutto: "Non posso testare tutto, ma io posso testare questo, questo e questo - e questo è abbastanza. " Non sto cercando un approccio che sia "provabilmente corretto", ma piuttosto un prudente , dati i vincoli di budget / tempo del mondo reale.

(Sto usando l'esempio delle mappe di Google come una sorta di pellicola per sollecitare risposte il più specifiche possibile.)

    
posta kmote 13.08.2012 - 01:13
fonte

3 risposte

10

Ho lavorato nel campo della navigazione automobilistica oltre un decennio fa.

Passaggio A) Utilizzare un pacchetto di riferimento e selezionare un ampio set di campioni, eseguire test A / B. Non cercando l'esattezza, alla ricerca di valori anomali - Il set di riferimento ha mostrato Reroute 1234 come 10,34 km e abbiamo calcolato 123,5 km.

Passaggio B) - Affina il nostro software e il software di riferimento - Aggiungi altri campioni e riduci le tolleranze.

Passaggio C)  - Test interni utilizzando le conoscenze locali su set di dati globali.

Passaggio D) UAT ... "Test di accettazione degli utenti" Come in "Vendi questa roba e vedi di cosa si lamentano di più i clienti"

Se hai mai usato prodotti cartografici circa a metà degli anni '90 - 2000, sai cosa intendo, quelli di noi che hanno ancora controllato le indicazioni per svolta ogni volta.

Torna alla domanda di esempio. Quello che ti viene chiesto è come dimostrare che un pezzo di software è corretto. Se vuoi una dimostrazione matematica, è stato dimostrato che può essere fatto - per un software semplice a un prezzo che supera qualsiasi budget realistico, per un pacchetto software complesso, beh, quello è ancora una ricerca ... La NASA ha modelli per scrivere software altamente affidabile a prezzi economicamente gestibili, così come il DoD e l'industria aeronautica - sebbene sia ancora molto più alto di quanto la maggior parte sia disposta a pagare. Alla fine, si tratta di quanto sei disposto a pagare .....

Modifica: Ho appena riletto OP. Sembra che quello che stai cercando sia un modo rapido ed economico per testare la qualità di un software complesso. Non puoi testare in qualità. È necessario disporre di un processo affidabile in modo da sapere che ciò che è costruito funziona correttamente. Se devi pensare a come dimostrare che è corretto e hai già una "applicazione grande e complessa", sei in ritardo.

    
risposta data 13.08.2012 - 06:25
fonte
5

Siamo uno dei concorrenti di Google. La nostra risposta? Fondamentalmente due.

Per prima cosa, calcoliamo la soluzione completa indirizzo-indirizzo. Sì, è una grande matrice. Peggio ancora, lo facciamo per tutte le ore del giorno, tutti i giorni della settimana. C'è abbastanza somiglianza nel dominio di input per memorizzare i risultati intermedi, il che rende il problema trattabile. Ancora, prova a ottenere una tariffa di massa su harddisk.

Si noti che questo calcolo offline viene eseguito utilizzando un algoritmo diverso. Utilizza molta più memoria dell'algoritmo che intendiamo testare, ma non linearmente di più (vale a dire utilizza meno di 1000 volte più memoria quando calcola migliaia di percorsi).

In secondo luogo, gli utenti partecipanti ci forniscono risultati reali. Convalidiamo milioni di percorsi guidati. I percorsi attuali sono veloci come previsto?

E certo, trovi bug in questo modo. Tutte le volte. Per esempio. un tratto di strada che è delimitato su entrambi i lati da una "zona a traffico limitato locale" *. C'è solo un modo;) che scoprirai durante i test, ed è in quel momento che pianifichi un percorso verso quella particolare strada.

* Una "zona di solo traffico locale" può essere utilizzata solo quando stai iniziando o terminando una rotta in tale zona. Il tratto nel mezzo è quindi disconnesso dalla rete stradale principale. Questa è una zonizzazione o un errore di mappa.

    
risposta data 13.08.2012 - 13:59
fonte
3

Non è che Google scrive codice separato per ogni coppia di indirizzi nel mondo. Con l'eccezione dell'euristica che dà il via a una scala più ampia, l'algoritmo per un viaggio a 3 tappe è esattamente lo stesso di un 3000-leg. Testate accuratamente i percorsi più brevi e utilizzate l'induzione per mostrare che il test si applica anche a percorsi più lunghi.

Scegli un campione sano di percorsi del mondo reale e confrontalo con ciò che un umano si avvicina. Paghi un sacco di attenzione al feedback degli utenti finali nelle tue prime uscite e facilita la loro fornitura. Esegui il test delle condizioni al contorno, ad esempio se il percorso migliore richiede effettivamente un allontanamento dalla destinazione per un po 'o se il percorso più breve per distanza ha 18 turni rispetto a un percorso più diretto che è leggermente più lungo. Esegui test negativi, ad esempio se stai provando a guidare dalla California alle Hawaii, e assicurati che siano disponibili uova di pasqua intelligenti.

    
risposta data 13.08.2012 - 05:50
fonte

Leggi altre domande sui tag