znajdowanie domów w promieniu


10

Podczas wywiadu poproszono mnie o następujące informacje: Aplikacja nieruchomości, która zawiera listę wszystkich domów, które są obecnie na rynku (tj. Na sprzedaż) w określonej odległości (np. Użytkownik chce znaleźć wszystkie domy w odległości 20 mil), jak zaprojektowałbyś swoją aplikację (zarówno strukturę danych, jak i alogirithm), aby zbudować ten rodzaj usługi?

Jakieś pomysły? Jak byś to wdrożył? Powiedziałem mu, że nie wiem, ponieważ nigdy wcześniej nie robiłem żadnych rzeczy związanych z geo.

Odpowiedzi:


6

Są prawdopodobnie po odpowiedzi na temat indeksowania przestrzennego , najprawdopodobniej poprzez wybranie bazy danych, która zapewnia indeksowanie przestrzenne po wyjęciu z pudełka , ale możesz również uzyskać kilka punktów, wspominając, że można je zaimplementować w samej aplikacji, jeśli to konieczne, np. Poprzez wdrożenie R -Drzewo (może być przydatne, jeśli wybór DB jest ustalony z innych powodów? Ale pokazuje również, jak wiesz, jak działają przestrzenne bazy danych). Indeksowanie przestrzenne pozwoli ci szybko uzyskać podzbiór lokalizacji, które mieszczą się w polu wyszukiwania, możesz to uściślić, obliczając rzeczywistą odległość (w razie potrzeby sam prostokąt może być wystarczająco dobry) dla każdego z nich, aby zapewnić prawdziwe wyszukiwanie okrąg / elipsa

Biorąc pod uwagę, że odległości wynoszą prawdopodobnie 20 M lub mniej, prawdopodobnie jesteś w porządku, zakładając, że płaska ziemia oblicza odległość, chociaż zaczniesz widzieć zauważalne błędy w kierunku końca 20 M, jeśli dokładnie potrzebne są znacznie większe odległości, musisz również zacząć szukać lepszych modeli odległości dla świata, np. odległość Haversine

istnieją również niezliczone inne szczegóły, które można omówić, np. projektowanie interfejsu użytkownika, schemat DB, które mogą stanowić całe tematy same w sobie


Przy 20 milach błędy wynikające z modelu płaskiej ziemi będą nieistotne. W każdym razie, gdy użytkownik chce zobaczyć listę domów w promieniu 20 mil od swojego biura, nie dba o to, czy w wynikach uwzględniono dom 20 mil i 10 jardów dalej.
kevin cline

1
w rzeczy samej, a jeśli kilka fałszywych trafień nie jest ważnych, równie dobrze możesz całkowicie pominąć obliczenie rzeczywistej odległości i po prostu zwrócić MBR
jk.

Ciekawi mnie jedno: biorąc pod uwagę ogromną liczbę domów na sprzedaż, czy firmy (takie jak Zillo?) Przechowują to wszystko w db i po prostu wybierają z niego? Wyobrażam sobie, że byłby to ogromny hit wydajności i byłoby znacznie szybsze przechowywanie tego wszystkiego w pamięci z reprezentacją graficzną - być może macierzą lub listą sąsiedztwa i używanie algorytmów odległości do znajdowania najbliższych domów. Co myślisz?
Paul Smith

@paulsmith Nie wiem, ale mocno podejrzewam, że jest to przestrzenna baza danych, przestrzenna baza danych prawdopodobnie i tak użyje wewnętrznej reprezentacji wykresu (najprawdopodobniej R-Tree, jak omówiono, ale istnieją inne opcje) klucz jest możliwość wybrania przede wszystkim tylko elementów w minimalnym prostokącie ograniczającym
jk.

8

Ilekroć masz takie pytanie i po prostu nie masz doświadczenia w dziedzinie problemów, dobrze jest zrobić kilka rzeczy.

Po pierwsze, potwierdź, że nie masz specjalistycznej wiedzy w tej dziedzinie problemów.

Po drugie , wyjaśnij, jak byś rozwiązał problem.

Chociaż nie mam specjalnego doświadczenia w pracy z wyszukiwaniem geograficznym, jestem pewien, że istnieją dobrze udokumentowane algorytmy i istniejące technologie rozwiązania problemu. Zbadałbym je, aby uzyskać wiedzę na temat popularnych rozwiązań, które są dla mnie dostępne, i dokonać wyboru wdrożenia w oparciu o wymagania projektu.

Po trzecie , zawsze ograniczaj takie problemy do ich podstawowych komponentów. Wiesz, że lokalizacje na mapie są rozmieszczone w dwóch wymiarach. Wiesz, że jeśli otrzymasz dowolną współrzędną x, y odległość do każdej współrzędnej od innej współrzędnej jest obliczana przez utworzenie trójkąta i rozwiązanie dla nieznanej długości. Mamy nadzieję, że wiesz również, że jeśli zostaniesz poproszony o znalezienie wszystkich współrzędnych w obwiedni, możesz to zrobić, po prostu obliczając zakres tego pola i używając prostej większej niż, mniejszej niż logika wzdłuż obu osi.

Wreszcie , nigdy nie zatrudniłem programisty, który wydawał się rezygnować z pytań. Jeśli zadam pytanie, a osoba powie „nie wiem”, a nawet nie spróbuje go przemówić werbalnie, mam wrażenie, że nie wezmą udziału w sesjach burzy mózgów - co jest niezwykle ważne w organizacjach tworzących oprogramowanie .


wszystkie dobre rady
jk.

@Ben, zdecydowanie zgadzam się ze wszystkimi rzeczami, o których wspomniałeś, jednak ponieważ ankieter wyraźnie powiedział przed rozpoczęciem sesji, że można powiedzieć, że nie wiesz, po prostu zastosowałem się do jego instrukcji i powiedziałem mu z góry, że nie wiem: )
Paul Smith

4

Jest to prawdopodobnie oczywiste, ale dla wielu aplikacji powolne rozwiązanie biedaka może być w porządku.

Mieć tabelę w relacyjnej bazie danych, która przechowuje szerokość i długość geograficzną. Zapytanie dla wszystkich lokalizacji, które mają szerokość geograficzną w odległości 20 mil i długość geograficzną w odległości 20 mil. Daje to prostokąt ograniczający rozmiar najmniejszego prostokąta ograniczającego, który zawiera promień, który naprawdę chcesz wyszukać (i ignoruje również krzywiznę ziemi).

Następnie bierzesz zestaw, który jest zwracany (przez zapytanie za pomocą indeksów), i filtrujesz go, używając dokładnego obliczenia odległości.

Tak więc, nie wydajna wydajność, ale bardzo wydajna w czasie do rozwoju. W przypadku wielu aplikacji może to być lepszy wybór.


2

Prawdopodobnie najłatwiejszym sposobem jest użycie kwadratu do przechowywania lokalizacji domów, przy założeniu, że są rozmieszczone w krajobrazie 2D. Wyszukiwanie powinno być dość proste.

Jeśli używasz RDBMS z obsługą GIS do przechowywania swoich rzeczy, naprawdę nie musisz się tym martwić. Zobacz to pytanie, aby uzyskać informacje na temat wyników głównych graczy.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.