In der Ortsdatenbank möchten wir alle Orte finden, deren Bevölkerung grösser oder kleiner als ein beliebiger Schwellenwert ist. Wir wollen einen Index erstellen, der für alle möglichen Schwellenwerte funktioniert und schnell ist.
Implementiert eine effiziente Abfrage für Range Queries. In allCountries.zip gibt es 95 Entitäten, die zw. 10M-15M Einwohner haben, davon 12 Städte.
Hinweise
Könnte Binärsuche helfen?
Wie würde der Index dafür aussehen?
Schreibe eine Funktion def build_integer_range_index(dataset, attribute), die einen Index erstellt!
Schreibe eine Funktion def query_numeric_index(dataset, idx, lower, upper), die den Index durchsucht und die richtigen Einträge aus dem Dataset liefert!
Wenn alles funktioniert, sollte das folgende Snippet die gewünschten Einträge liefern:
%%time
for place in query_numeric_index(places, population_idx, 10e6, 15e6):
print(place['name'], place['population'])
Lösung
from tqdm.auto import tqdm
# Create the index.
def build_integer_range_index(dataset, attribute):
index = []
for id, entity in tqdm(dataset.items()):
# Only include entities that specify a population (no mountains and lakes, please)
try:
value = int(entity[attribute])
if value > 0:
index.append((value, id))
except ValueError:
pass
index.sort() # Sort first by population, then id
return index
def query_numeric_index(dataset, idx, lower, upper):
# Use bisect instead of implementing binary search ourselves:
import bisect
# Use operator.itemgetter(0) to extract the population from the (pop, id) tuple.
import operator
# The index of the smallest entity in idx greater or equal than lower.
lower_index = bisect.bisect_left(idx, lower, key=operator.itemgetter(0))
# The index of the smallest entity in population_idx greater than upper.
upper_index = bisect.bisect_right(idx, upper, key=operator.itemgetter(0))
for index_key in range(lower_index, upper_index):
yield dataset[idx[index_key][1]]
%time population_idx = build_integer_range_index(places, 'population')
Statt Binärsuche könnten wir auch einen Binären Suchbaum (Binary Search Tree - BST) verwenden. Jeder Knoten (Node) des Baums speichert eine Stadt mit ihrer Bevölkerungszahl als Schlüssel (Key) und der dazugehörigen geonameid als Wert (Value). Dazu hat jeder Knoten noch zwei Unterknoten: Im Knoten left werden alle Knoten mit kleineren Keys gespeichert, im Knoten right werden alle Knoten mit grösseren Keys gespeichert.
Ein Knoten sieht in Python zum Beispiel so aus:
class Node:
"""A tree node, also represents an entire (sub-)tree."""
def __init__(self, key, value):
self.key = key
self.value = value
self.left = None
self.right = None
Aufgabe: Schreibe eine Funktion def build_tree(sorted_tuples, left_idx, right_idx), die aus einer sortierten Liste von Tupeln (population, geonameid) einen Baum baut, der den obigen Bedingungen genügt.
Hinweise
Das Wurzel-Element ist idealerweise das Element in der Mitte zwischen left_idx und right_idx (Median), dann sind beide Subtrees ungefähr gleich gross, der Baum ist balanciert.
Rekursion ist praktisch: Schaffe einen neuen Knoten node = Node(key, value), anschliessend rufe die Funktion für den linken und rechten Subtree auf:
node.left = build_tree(sorted_tuples, left_idx, ...)
node.right = build_tree(sorted_tuples, ..., right_idx)
Lösung
def build_tree(sorted_tuples, left=None, right=None):
"""Builds a binary search tree from a sorted tuple list."""
left = left if left is not None else 0
right = right if right is not None else len(sorted_tuples) - 1
# Stop when the given range is empty.
if left > right:
return None
median = (left + right) // 2
element = sorted_tuples[median]
node = Node(element[0], element[1])
node.left = build_tree(sorted_tuples, left, median - 1)
node.right = build_tree(sorted_tuples, median + 1, right)
return node
population_tree = build_tree(population_idx)
Suche im BST
Wie können wir im Suchbaum ein Element finden? Wir steigen im Baum vom Wurzelknoten her ab, und wenden uns jeweils links oder rechts, je nachdem, ob der Key kleiner oder grösser als der gewünschte Wert ist.
Schreibe eine Funktion bst_search(node, key), die den Value des gewünschten Knotens zurückgibt. Wie sieht die rekursive Variante davon aus?
Wie könnte eine (rekursive) Funktion aussehen, die alle Values zurückgibt, die zwischen zwei Grenzen stehen (range query)?
Hinweise:
Lösung
def tree_search(node, lower, upper):
"""Traverses tree in-order from lower to upper key."""
if node is None:
return # reached the bottom of the tree
if lower <= node.key:
# return elements on our left
yield from tree_search(node.left, lower, upper)
if lower <= node.key <= upper:
yield node.value # return this node's value
if node.key <= upper:
# return elements on our right
yield from tree_search(node.right, lower, upper)
import time
start = time.time()
for geonameid in tree_search(population_tree, 10e6, 15e6):
entity = places[geonameid]
print(entity['name'], entity['population'])
elapsed = time.time() - start
print(f"took {elapsed:.2g}s")
Visualisiere einen von dir gebauten Baum mit Graphviz. Experimentiere zuerst mit dem Online-Editor, um ein Gefühl dafür zu kriegen, wie ein Baum aussehen könnte. Verwende anschliessend das graphviz Package in Python wie folgt.
Beachte:
Einen neuen Graph erzeugen wir mit graph = graphviz.Digraph('Graph Title').
In Graphviz werden zuerst Knoten (nodes) erstellt
graph.node('A')
graph.node('B')
Kanten (edges) werden zwischen zwei Knoten eingefügt, diese werden über ihre Id identifiziert:
Rekursion wäre wieder mal hilfreich…
Lösung:
def render_tree(graph, node, nuller=""):
"""Renders the tree in graphviz."""
if node is None:
# In order to have separate Nil-nodes, we need to create artificially
# named nodes with unique names. We use the 'nuller' parameter to create
# these, which is the left/right-path down from the root.
graph.node(nuller, "", shape="point")
return nuller
id = str(node.key)
graph.node(id, f"< <B>key:</B> {id}<BR/><B>id:</B> {str(node.value)}<BR/><B>town:</B> {towns[node.value]['name']} >")
left_key = render_tree(graph, node.left, nuller + "l")
graph.edge(id, left_key)
right_key = render_tree(graph, node.right, nuller + "r")
graph.edge(id, right_key)
return id
dot = graphviz.Digraph("Population Search Tree")
render_tree(dot, tree)
dot
Bevölkerungszahl, Geburtstage etc. sind einfach, weil die Bevölkerungszahl und Zeit skalare, also eindimensionale Grössen sind. Aber wie können wir einen zweidimensionalen Index schaffen, der uns alle Elemente liefert, die innerhalb eines Rechtecks von Längen- und Breitengraden liegen?
