Die erste Implementation ist mittels einer verketteten Liste. Die put Operation stellt fest, ob der Schlüssel bereits in der Liste vorhanden ist. Falls nicht wird er am Anfang eingefügt. Falls der Schlüssel bereits vorhanden ist, wird der Wert überschrieben.
Bei der get Methode wird einfach der Wert in der Liste zurückgegeben.
class SequentialSearchST:
class Node:
def __init__(self, key, value, next = None):
self.key = key
self.value = value
self.next = next;
def __init__(self):
self._first = None
self._numberOfNodesInList = 0
def put(self, key, value):
if self._first == None:
self._first = SequentialSearchST.Node(key, value)
self._numberOfNodesInList += 1
else:
nodeWithKey = self._findNodeWithKey(key)
if nodeWithKey == None:
self._first = SequentialSearchST.Node(key, value, self._first)
self._numberOfNodesInList += 1
else:
nodeWithKey.value = value
def get(self, key):
nodeWithKey = self._findNodeWithKey(key)
if nodeWithKey == None:
return None
else:
return nodeWithKey.value
def delete(self, key):
if self._first == None:
return
if (self._first.key == key):
self._numberOfNodesInList = 0
self._first = self._first.next
return
current = self._first
while (current.next != None):
if current.next.key == key:
current.next = current.next.next
self._numberOfNodesInList -= 1
current = current.next
def contains(self, key):
return self._findNodeWithKey(key) == None
def isEmpty(self):
return self.size() == 0
def size(self):
return self._numberOfNodesInList
def _findNodeWithKey(self, key):
current = self._first
while (current != None):
if current.key == key:
return current
current = current.next
return None # not found
def keys(self):
if (self._first == None):
yield current.key
current = self._first
while (current != None):
yield current.key
current = current.next
In unserer zweiten Implementation, wir nutzen Binary search. Wir schauen uns als erstes die Implementation von Binary search an.
def binarySearch(sequence , value ):
lo = 0
hi = len(sequence) - 1
while lo <= hi:
mid = (lo + hi) // 2
if sequence[mid] < value:
lo = mid + 1
elif value < sequence[mid]:
hi = mid - 1
else:
return mid
return None
binarySearch([1, 3, 6, 7, 11, 19], 6)
2
binarySearch([1, 3, 7, 11, 19], 18)
Eine ähnliche Funktion, genannt rank, bildet das Rückgrat unserer nächsten Implementation. Die Funktion rank basiert auf dem Prinzip von Binarysearch und gibt die Anzahl der Schlüssel kleiner als ein gegebener Wert an.
class BinarySearchST:
def __init__(self):
self._keys = []
self._values = []
def _rank(self, value):
lo = 0
hi = len(self._keys) - 1
while lo <= hi:
mid = (lo + hi) // 2
if self._keys[mid] < value:
lo = mid + 1
elif value < self._keys[mid]:
hi = mid - 1
else:
return mid
return lo
def get(self, key):
if self.isEmpty():
return None
rank = self._rank(key)
if rank < len(self._keys) and self._keys[rank] == key:
return self._values[rank]
else:
return None
def put(self, key, value):
rank = self._rank(key)
if rank < len(self._keys) and self._keys[rank] == key:
self._values[rank] = value
else:
self._keys.insert(rank, key)
self._values.insert(rank, value)
def delete(self, key):
rank = self._rank(key)
if rank < len(self._keys) and self._keys[rank] == key:
del self._keys[rank]
del self._values[rank]
def contains(self, key):
rank = self._rank(key)
return rank < len(self._keys) and self._keys[rank] == key
def isEmpty(self):
return self.size() == 0
def size(self):
return len(self._keys)
def keys(self):
return self._keys
Unser erster Client nimmt jeden Buchstaben von einem String als Key und die Position des Buchstabens im String als Wert.
string = "SEARCHEXAMPLE"
st = SequentialSearchST()
for (pos, char) in enumerate(string):
st.put(char, pos)
st.delete('L')
for key in st.keys():
print(key, st.get(key))
P 10 M 9 X 7 H 5 C 4 R 3 A 8 E 12 S 0
Unser zweiter Client zählt, wie oft ein bestimmes Wort in einem Text vorkommt.
testdataRaw = """ Alice was beginning to get very tired of
sitting by her sister on the bank, and of having nothing to
do: once or twice she had peeped into the book her sister
was reading, but it had no pictures or conversations in it, `and what is the use of a book,'
thought Alice `without pictures or conversation?'
So she was considering in her own mind (as well as she could,
for the hot day made her feel very sleepy and stupid), whether
the pleasure of making a daisy-chain would be worth the trouble
of getting up and picking the daisies, when suddenly a White
Rabbit with pink eyes ran close by her.
There was nothing so VERY remarkable in that; nor did Alice
think it so VERY much out of the way to hear the Rabbit say to
itself, `Oh dear! Oh dear! I shall be late!' (when she thought
it over afterwards, it occurred to her that she ought to have
wondered at this, but at the time it all seemed quite natural);
but when the Rabbit actually TOOK A WATCH OUT OF ITS WAISTCOAT-
POCKET, and looked at it, and then hurried on, Alice started to
her feet, for it flashed across her mind that she had never
before seen a rabbit with either a waistcoat-pocket, or a watch to
take out of it, and burning with curiosity, she ran across the
field after it, and fortunately was just in time to see it pop
down a large rabbit-hole under the hedge.
"""
import string
translator = str.maketrans('', '', string.punctuation)
testdata = testdataRaw.translate(translator).lower()
st = BinarySearchST()
for word in testdata.split():
if len(word) > 5:
if st.contains(word):
st.put(word, st.get(word) + 1)
else:
st.put(word, 1)
Wir können nun das Wort, welches am meisten vorkommt, ganz einfach auslesen. Beachten Sie, dass wir uns dazu eine Variable max führen, die immer auf das wort mit den meisten Einträgen zeigt. Am Anfang wird dies auf ein nicht existierendes Wort, mit 0 Einträgen gesetzt.
max = ""
st.put("", 0)
for word in st.keys():
if st.get(word) > st.get(max):
max = word
print(max, st.get(max))
rabbit 4
st.keys()
['', 'across', 'actually', 'afterwards', 'before', 'beginning', 'burning', 'considering', 'conversation', 'conversations', 'curiosity', 'daisies', 'daisychain', 'either', 'flashed', 'fortunately', 'getting', 'having', 'hurried', 'itself', 'looked', 'making', 'natural', 'nothing', 'occurred', 'peeped', 'picking', 'pictures', 'pleasure', 'pocket', 'rabbit', 'rabbithole', 'reading', 'remarkable', 'seemed', 'sister', 'sitting', 'sleepy', 'started', 'stupid', 'suddenly', 'thought', 'trouble', 'waistcoat', 'waistcoatpocket', 'whether', 'without', 'wondered']