Häuser in einem Umkreis finden

10

Während eines Interviews wurde ich wie folgt gefragt: Eine Immobilienanwendung, die alle Häuser auflistet, die derzeit auf dem Markt sind (dh zum Verkauf stehen), innerhalb einer bestimmten Entfernung (zum Beispiel, wenn der Benutzer alle Häuser innerhalb von 20 Meilen finden möchte), Wie würden Sie Ihre Anwendung (sowohl Datenstruktur als auch Alogirithmus) entwerfen, um diese Art von Service zu erstellen?

Irgendwelche Ideen? Wie würden Sie es implementieren? Ich sagte ihm, ich wüsste es nicht, weil ich noch nie geo-bezogene Sachen gemacht habe.

Paul Smith
quelle

Antworten:

6

Sie befinden sich wahrscheinlich nach einer Antwort, in der die räumliche Indizierung erwähnt wird , höchstwahrscheinlich durch Auswahl einer Datenbank, die sofort eine räumliche Indizierung bietet. Sie können jedoch auch einige Punkte erhalten, wenn Sie erwähnen, dass sie bei Bedarf in der Anwendung selbst implementiert werden kann, z. B. durch Implementierung eines R. -Baum (kann nützlich sein, wenn die DB-Auswahl aus anderen Gründen festgelegt ist? Zeigt aber auch, dass Sie wissen, wie räumliche Datenbanken funktionieren). Durch die räumliche Indizierung können Sie schnell eine Teilmenge von Positionen abrufen, die in ein Suchfeld passen. Sie können dies weiter verfeinern, indem Sie die tatsächliche Entfernung berechnen (falls erforderlich, kann das Rechteck allein natürlich gut genug sein), damit jede einzelne eine echte Suche ergibt Kreis / Ellipse

Angesichts der Tatsache, dass Entfernungen wahrscheinlich 20 m oder weniger betragen, ist es wahrscheinlich in Ordnung, eine flache Erde anzunehmen, um die Entfernung zu berechnen, obwohl Sie gegen 20 m merkliche Fehler bemerken. Wenn viel größere Entfernungen genau benötigt werden, müssten Sie auch nach besseren Entfernungsmodellen suchen für den Globus zB Haversine Distanz

Es gibt natürlich auch eine Vielzahl anderer Details, die besprochen werden könnten, z. B. UI-Design, DB-Schema, die ganze Themen für sich sein könnten

jk.
quelle
Bei 20 Meilen sind die Fehler aufgrund eines Modells mit flacher Erde vernachlässigbar. Wenn ein Benutzer eine Liste von Häusern innerhalb von 20 Meilen von seinem Büro sehen möchte, ist es ihm egal, ob ein Haus, das 20 Meilen und 10 Meter entfernt ist, in den Ergebnissen enthalten ist.
Kevin Cline
1
In der Tat, und wenn ein paar Fehlalarme nicht wichtig sind, können Sie auch die tatsächliche Entfernungsberechnung überspringen und einfach den MBR
jk zurückgeben.
Eine Sache, auf die ich neugierig bin: Speichern Unternehmen (wie Zillo vielleicht?) Angesichts der großen Anzahl von zum Verkauf stehenden Häusern alles in einer Datenbank und wählen sie einfach weiter aus? Ich stelle mir vor, das wäre ein großer Leistungseinbruch und es wäre viel schneller, alles mit einer grafischen Darstellung im Speicher zu speichern - vielleicht eine Matrix oder eine Adjazenzliste - und Entfernungsalgorithmen zu verwenden, um die nächsten Häuser zu finden. Was denken Sie?
Paul Smith
@paulsmith Ich weiß es nicht, aber ich vermute sehr, dass es sich um eine räumliche Datenbank handelt. Eine räumliche Datenbank wird wahrscheinlich ohnehin intern eine Diagrammdarstellung verwenden (höchstwahrscheinlich ein R-Tree, wie beschrieben, aber es gibt andere Optionen) in erster Linie nur die Elemente in einem minimalen Begrenzungsrechteck auswählen können
jk.
8

Immer wenn Sie mit einer solchen Frage konfrontiert sind und einfach kein Fachwissen in der Problemdomäne haben, ist es gut, ein paar Dinge zu tun.

Zunächst erkennen an, dass Sie nicht spezifisches Know - how in diesem Problembereich verfügen.

Zweitens , erklären , wie Sie über die Lösung des Problems gehen würde.

Obwohl ich keine besonderen Erfahrungen mit der geografischen Suche habe, bin ich zuversichtlich, dass es gut dokumentierte Algorithmen und vorhandene Technologien gibt, um das Problem zu lösen. Ich würde diese untersuchen, um Kenntnisse über gängige Lösungen zu erlangen, die mir zur Verfügung stehen, und anhand der Anforderungen des Projekts eine Entscheidung über die Implementierung treffen.

Drittens : Reduzieren Sie solche Probleme immer auf ihre Grundkomponenten. Sie wissen, dass Standorte auf einer Karte zweidimensional verteilt sind. Sie wissen, dass, wenn Sie beliebige x-, y-Koordinaten erhalten, der Abstand zu jeder Koordinate von einer anderen Koordinate berechnet wird, indem Sie ein Dreieck bilden und nach der unbekannten Länge suchen. Sie wissen hoffentlich auch, dass Sie, wenn Sie aufgefordert werden, alle Koordinaten innerhalb eines Begrenzungsrahmens zu finden, dies einfach tun können, indem Sie die Ausmaße des zu suchenden Felds berechnen und einfach größer als, kleiner als die Logik entlang beider Achsen verwenden.

Zuletzt habe ich noch nie einen Entwickler eingestellt, der Fragen offenbar aufgegeben hat . Wenn ich eine Frage stelle und die Person "Ich weiß nicht" sagt und nicht einmal versucht, sie mündlich zu durchdenken, entsteht der Eindruck, dass sie nicht zu Brainstorming-Sitzungen beiträgt - was bei Organisationen, die Software schreiben, von entscheidender Bedeutung ist .

Ben DeMott
quelle
alles gute ratschläge
jk.
@Ben, ich stimme definitiv allen Dingen zu, die Sie erwähnt haben, aber da der Interviewer vor Beginn der Sitzung explizit gesagt hat, dass es in Ordnung ist zu sagen, dass Sie es nicht wissen, habe ich einfach seine Anweisungen befolgt und ihm im Voraus gesagt, dass ich nicht wusste: )
Paul Smith
4

Dies ist wahrscheinlich offensichtlich, aber für viele Anwendungen kann die langsame Lösung des armen Mannes in Ordnung sein.

Haben Sie eine Tabelle in einer relationalen Datenbank, in der Breiten- und Längengrade gespeichert sind. Abfrage für alle Standorte mit einem Breitengrad innerhalb von 20 Meilen und einem Längengrad innerhalb von 20 Meilen. Auf diese Weise erhalten Sie ein Begrenzungsrechteck in der Größe des kleinsten Begrenzungsrechtecks, das den Radius enthält, nach dem Sie wirklich suchen möchten (und der auch die Erdkrümmung ignoriert).

Anschließend nehmen Sie den zurückgegebenen Satz (durch eine Abfrage unter Verwendung von Indizes) und filtern ihn mithilfe einer genauen Entfernungsberechnung nach unten.

Also keine effiziente Leistung, aber sehr effizient in der Zeit, um sich zu entwickeln. Für viele Anwendungen ist dies möglicherweise die bessere Wahl.

psr
quelle
2

Am einfachsten ist es wahrscheinlich, einen Quadtree zu verwenden, um die Standorte Ihrer Häuser zu speichern, sofern diese in einer 2D-Landschaft verteilt sind. Die Suche sollte ziemlich einfach sein.

Wenn Sie ein GIS-fähiges RDBMS zum Speichern Ihrer Daten verwenden, müssen Sie sich darüber keine Gedanken machen. In dieser Frage finden Sie einige Informationen zur Leistung der Hauptakteure.

vski
quelle