search_and_destroy_drohnenkrieg_3.0

import math
import random
import time

def splitList(ls):
    n = len(ls)
    comp = ls[math.floor(n / 2)]
    l = 0
    r = n - 1
    while l < r:
        while ls[l] < comp:
            l += 1
        while ls[r] > comp:
            r -= 1
        if l < r:
            ls[r], ls[l] = ls[l], ls[r]
            l += 1
            r -= 1
        else:
            if l == r:
                l += 1
    return ls[:r], ls[l-1:]

def quickSort(ls):
    n = len(ls)
    if n > 2:
        left, right = splitList(ls)
        left = quickSort(left)
        right = quickSort(right)
        return left + right
    elif n == 2:
        if ls[0] > ls[1]:
            return [ls[1], ls[0]]
    return ls

def parseInput():
    sourceFile = open("staedte_laender.txt", 'r')
    list = []
    for line in sourceFile:
        town = line.replace("\n", "").rsplit(" ", 1)
        town[1] = town[1].replace("(", "")
        town[1] = town[1].replace(")", "")
        town = tuple(town)
        list.append(town)
    return list

BUNDESLAENDER = ["BB", "TH", "RP", "MV", "SN", "ST", "BY", "SH", "NW", "NI", "HE", "HH", "BW", "SL", "HB"]
ALPHABET = "abcdefghijklmnopqrstuvwxyz"
def expandList(liste, n = 10000):
    while len(liste) < n:
        townName = ""
        for i in range(8):
            townName += ALPHABET[random.randint(0, 25)]
        land = BUNDESLAENDER[random.randint(0, 14)]
        liste.append((townName, land))

def linearSearch(liste, key):
    i = 0
    for element in liste:
        if element == key:
            return i
        i += 1
    return -1

def binarySearch(liste, key):
    n = int(len(liste) / 2)
    lastStep = n
    while True:
        if liste[n] == key:
            return n

        if lastStep == 0:
            return -1

        lastStep =  int(lastStep / 2)
        if liste[n] < key:
            n += lastStep
        else:
            n -= lastStep
    
def keyToIndex(key):
    try:
        return BUNDESLAENDER.index(key)
    except:
        return 0

def indexToKey(idx):
    return BUNDESLAENDER[idx]

def createHashedList(list):
    hashed = []
    for i in range(len(BUNDESLAENDER)):
        hashed.append([])
    for key in list:
        hashed[keyToIndex(key[1])] = i
    return hashed

def hashSearch(liste, key):
    smallList = liste[keyToIndex(key[1])]
    return linearSearch(smallList, key)

randomList = parseInput()
print("Liste ist jetzt", len(randomList), "lang")
expandList(randomList, n = 10000)
print(randomList)

print("Searching [binary] ...")
t1 = time.time()
for i in range(1000):
    random.shuffle(randomList)
    quickSort(randomList)
    binarySearch(randomList, ('Weil am Rhein', 'BW'))

print(time.time() - t1)


print("Searching [linear] ...")
t1 = time.time()
for i in range(1000):
    random.shuffle(randomList)
    linearSearch(randomList, ('Weil am Rhein', 'BW'))

print(time.time() - t1)


print("Searching [hashing]...")
t1 = time.time()
for i in range(1000):
    random.shuffle(randomList)
    hashedList = createHashedList(randomList)
    hashSearch(randomList, ('Weil am Rhein', 'BW'))

print(time.time() - t1)


print("Testing how long shuffling takes")
t1 = time.time()
for i in range(100000):
    random.shuffle(randomList)
print(time.time() - t1)