Jak przetestowałbyś funkcję „Uzyskaj wskazówki” w Mapach Google?

(Wyobrażam sobie, że byłoby to dobre pytanie do rozmowy kwalifikacyjnej , ale w moim przypadku jest bardziej pragmatyczne).

Mamy dużą i złożoną aplikację, która modeluje wyjątkowo długi i wyrafinowany proces reakcji chemicznej między dziesiątkami składników chemicznych. Jesteśmy na etapie projektowania testów akceptacyjnych dla aplikacji, ale nieco zniechęca nas nieuchronna liczba możliwych ścieżek do przetestowania. Przyszło mi do głowy, że nasza sytuacja jest bardzo podobna do tego, z czym musiał się zmierzyć zespół programistów Google Maps, gdy przyszedł czas na przetestowanie algorytmu planowania trasy w funkcji „Uzyskaj wskazówki”. Oczywiście nie mogli przetestować (zweryfikować i zweryfikować) każdej możliwej trasy. Jak więc uzyskali pewność, że ich aplikacja będzie działać w każdej sytuacji?

A ponieważ nie oczekujemy, aby dowiedzieć się, jak oni zrobili to, pozwól mi zapytać: Jak byś ty go o zaprojektowanie zestawu testowego z odpowiedniego pokrycia kodu, aby zadowolić siebie, że dana aplikacja jest solidna - kiedy to jest dosłownie niemożliwe zbadać każdą potencjalną ścieżkę przez system?

To, czego szukam, to zasady, których użyłbyś do rozbicia nierozwiązywalnego problemu na mniejsze, dające się traktować kawałki, których suma zapewnia satysfakcjonujące oszacowanie całości: „Nie mogę przetestować wszystkiego, ale mogę to przetestować , to i to - i to wystarczy ”. Nie szukam podejścia, które byłoby „możliwe do udowodnienia”, ale raczej ostrożne , biorąc pod uwagę rzeczywiste ograniczenia budżetowe / czasowe.

(Używam przykładu z mapami Google jako czegoś w rodzaju folii, aby uzyskać odpowiedzi, które są jak najbardziej szczegółowe).

Pracowałem w dziedzinie nawigacji samochodowej ponad dziesięć lat temu.

Krok A) Użyj pakietu referencyjnego i wybierz duży zestaw próbek, uruchom testy A / B. Nie szukając dokładności, szukając wartości odstających - zestaw referencyjny pokazał Reroute 1234 jako 10,34 km, a my obliczyliśmy 123,5 km.

Krok B) - Udoskonal nasze oprogramowanie i oprogramowanie referencyjne - Dodaj więcej próbek i zmniejsz tolerancje.

Krok C) - Testy wewnętrzne z wykorzystaniem lokalnej wiedzy w globalnych zestawach danych.

Krok D) UAT ... „Test akceptacji użytkownika” Jak w „Sprzedawaj te rzeczy i zobacz, na co klienci najbardziej narzekają”

Jeśli kiedykolwiek używałeś produktów do mapowania około połowy lat 90. - 2000, wiesz, co mam na myśli, tych z nas, którzy za każdym razem sprawdzali zakręt po zakręcie.

Pytanie przykładowe do Ciebie Pytamy Cię, jak udowodnić, że oprogramowanie jest poprawne. Jeśli potrzebujesz matematycznego dowodu, pokazano, że można to zrobić - dla prostego oprogramowania w cenie przekraczającej wszelkie realistyczne budżety, dla złożonego pakietu oprogramowania, cóż, to wciąż badania… NASA ma modele do pisania wysoce niezawodnego oprogramowania w przystępnych cenach, podobnie jak DoD i branża lotnicza - choć wciąż znacznie wyższe niż większość chętnych do zapłaty. Ostatecznie wszystko sprowadza się do tego, ile jesteś gotów zapłacić .....

Edycja: Właśnie przeczytałem ci OP. Wygląda na to, że szukasz szybkiego i taniego sposobu na sprawdzenie jakości złożonego oprogramowania. Nie możesz przetestować jakości. Musisz mieć solidny proces, abyś wiedział, że to, co jest zbudowane, działa poprawnie. Jeśli musisz pomyśleć o tym, jak udowodnić, że jest poprawny, a masz już „dużą i złożoną aplikację”, spóźniasz się.

Jesteśmy jednym z konkurentów Google. Nasza odpowiedź Zasadniczo dwa.

Po pierwsze, obliczamy kompletne rozwiązanie adres-adres. Tak, to wielka matryca. Co gorsza, robimy to o każdej porze dnia, we wszystkie dni tygodnia. W domenie wejściowej istnieje wystarczające podobieństwo do buforowania wyników pośrednich, co sprawia, że ​​problem jest możliwy do rozwiązania. Mimo to spróbuj uzyskać masową stawkę na dyskach twardych.

Pamiętaj, że obliczenia offline są wykonywane przy użyciu innego algorytmu. Zużywa znacznie więcej pamięci niż algorytm, który zamierzamy przetestować, ale nie liniowo więcej (tzn. Zużywa mniej niż 1000 razy więcej pamięci podczas obliczania tysiąca tras).

Po drugie, uczestniczący użytkownicy zapewniają nam rzeczywiste wyniki. Sprawdzamy miliony przejechanych tras. Czy rzeczywiste trasy są tak szybkie, jak przewidywano?

I na pewno znajdziesz w ten sposób błędy. Cały czas. Np. Odcinek drogi, który jest obustronnie ograniczony „strefą wyłącznie ruchu lokalnego” *. Jest tylko jeden sposób;) znajdziesz to w testach i wtedy planujesz trasę do tej konkretnej drogi.

_{* „Strefa tylko dla ruchu lokalnego” może być używana tylko podczas rozpoczynania lub kończenia trasy w takiej strefie. Dlatego odcinek pośrodku jest odłączony od głównej sieci drogowej. Jest to błąd strefowy lub błąd mapy.}

To nie jest tak, że Google pisze osobny kod dla każdej pary adresów na świecie. Z wyjątkiem heurystyki, która rozpoczyna się na większą skalę, algorytm dla podróży na 3 nogach jest dokładnie taki sam, jak na 3000 nogach. Dokładnie testujesz krótsze ścieżki i używasz indukcji, aby pokazać, że testy dotyczą również dłuższych ścieżek.

Wybierasz zdrową próbkę rzeczywistych tras i porównujesz ją z tym, co wymyśli człowiek. Zwracasz dużą uwagę na opinie użytkowników końcowych w swoich pierwszych wydaniach i ułatwiasz im ich dostarczanie. Testujesz warunki brzegowe, np. Jeśli najlepsza trasa rzeczywiście wymaga dłuższej podróży z miejsca docelowego lub jeśli najkrótsza trasa według odległości ma 18 zakrętów w porównaniu z bardziej bezpośrednią, nieco dłuższą trasą. Wykonujesz testy negatywne, na przykład jeśli próbujesz pojechać z Kalifornii na Hawaje i upewnij się, że są sprytne pisanki.