Mengukur kecepatan dalam methode hashing

Siapakah yang paling cepat antara Open Address dengan Close Address :

Source Code :

from __future__ import print_function

import time

import random

waktu = time.time() 

print ("Waktu sekarang :", waktu)

print("=".center(80,"="))

print("Tugas Praktikum 4".center(80))

print("=".center(80,"="))

print()

print("=".center(80,"="))

print("No.1 Linear Probbing".center(80))

print("=".center(80,"="))

table = [None]*110

def Linear(x):

    return x % 11

def insert(table,keys,value):

    index = Linear(keys)

    if table[index]==None:

        table[index]=value

    else:

        tumbukan=index

        found = False

        ind = tumbukan + 1

        if ind >= len(table)-1:

            ind = 0

        while (ind<=len(table)-1) and not(found):

            if table[ind]== None:

                found = True

                table[ind]=value

            ind +=1

    return table

keys = []

for i in range (0,100):

    keys.append(random.randint(11,111))

value = list(keys)

for j in range(0,100):

    linear = insert(table,keys[j],value[j])

print (linear)

waktu1 = time.time() 

print ("Waktu sekarang :", waktu1)

print("=".center(80,"="))

print("Quadratic Probbing".center(80))

print("=".center(80,"="))

table1 = [None]*100

def Quadrat(x):

    return x% 11

def insert1(table1,keys1,value1):

    index = Quadrat(keys1)

    if table1[index]==None:

        table1[index]=value1

    else:

        tumbukan=index

        found = False

        ind = tumbukan + 1

        if ind >= len(table1)-1:

            ind = 0

        i = 1

        while (ind<=len(table1)-1) and not(found):

            i+=1

            if table1[ind]== None:

                found = True

                table1[ind]=value1

            ind = (ind+(i**2))

    return table1

keys1 = list(keys)

value1 = list(keys)

for j in range(0,100):

    quadratic=insert1(table1,keys1[j],value1[j])

print (quadratic)

waktu2 = time.time() 

print ("Waktu sekarang :", waktu2)

print("=".center(80,"="))

print("Chaining(Close Address)".center(80))

print("=".center(80,"="))

table2 = [[]]*20

def Chaining(x):

    return x % 11

def insert2(table2,keys2,value2):

    index = Chaining(keys2)

    if table2[index]==[]:

        table2[index]=[value2]

    else:

        table2[index].append(value2)

    return table2

keys2 = list(keys)

value2 = list(keys)

for j in range(0,100):

    chaining = insert2(table2,keys2[j],value2[j])

print (chaining)

waktu3 = time.time() 

print ("Waktu sekarang :", waktu3)

print("=".center(80,"="))

print("No.2 Methode yang Paling Cepat".center(80))

print("=".center(80,"="))

if waktu2-waktu1 > waktu3-waktu2 < waktu1-waktu :

    print ("Metode Chaining Yang Paling Cepat".upper().center(80))

elif waktu2-waktu1 == waktu3-waktu2:

    print ("Methode Chaining dengan Quadratic sama-sama cepat".upper().center(80))

else:

    print ("Methode Quadratic Paling Cepat".upper().center(80))

Silahkan Mencoba dan tentukan mana yang paling cepat...

Hashing Python

Hashing pada Python

Hashing adalah proses pengindeksan dan pengambilan elemen (data) dalam sebuah datastructure untuk menyediakan cara yang lebih cepat dalam menemukan elemen menggunakan kunci hash.

Collision = Ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua dalam tabel hash.
Memecahkan:

A. Open Address: dalam hal itu mencoba untuk menemukan slot atau alamat terbuka berikutnya di tabel hash.

1. Linear Probbing: kita melihat secara berurutan, slot demi slot, sampai kita menemukan posisi terbuka.

Source Code :

table = [None]*110
def Linear(x):
    return x % 11
def insert(table,keys,value):
    index = Linear(keys)
    if table[index]==None:
        table[index]=value
    else:
        tumbukan=index
        found = False
        ind = tumbukan + 1
        if ind >= len(table)-1:
            ind = 0
        while (ind<=len(table)-1) and not(found):
            if table[ind]== None:
                found = True
                table[ind]=value
            ind +=1
    return table
keys = []
for i in range (0,100):
    keys.append(random.randint(11,111))
value = list(keys)
for j in range(0,100):
    linear = insert(table,keys[j],value[j])

print (linear)

2. Qudratic Probbing: Ini berarti bahwa jika nilai hash pertama adalah h, nilai berturut-turut adalah h + 1, h + 4, h + 9, h + 16. seterusnya

Source code :

table1 = [None]*100 def Quadrat(x): return x% 11 def insert1(table1,keys1,value1): index = Quadrat(keys1) if table1[index]==None: table1[index]=value1 else: tumbukan=index found = False ind = tumbukan + 1 if ind >= len(table1)-1: ind = 0 i = 1 while (ind<=len(table1)-1) and not(found): i+=1 if table1[ind]== None: found = True table1[ind]=value1 ind = (ind+(i**2)) return table1 keys1 = list(keys) value1 = list(keys) for j in range(0,100): quadratic=insert1(table1,keys1[j],value1[j]) print (quadratic)

B. Close Address

Chaining = memungkinkan banyak item ada di lokasi yang sama dalam tabel hash. Ketika tabrakan terjadi, item tersebut masih ditempatkan di slot yang tepat dari tabel hash.

Source Code :

table2 = [[]]*20
def Chaining(x):
    return x % 11
def insert2(table2,keys2,value2):
    index = Chaining(keys2)
    if table2[index]==[]:
        table2[index]=[value2]
    else:
        table2[index].append(value2)
    return table2
keys2 = list(keys)
value2 = list(keys)
for j in range(0,100):
    chaining = insert2(table2,keys2[j],value2[j])
print (chaining)

Selamat Mencoba...

Infix To Prefix + Evaluasi

Infix To Prefix pada Python

class Stack:

    def __init__(self):

        self.items = []

    def isEmpty(self):

        return self.items==[]

    def push(self,items):

        self.items.append(items)

    def pop(self):

        return self.items.pop()

    def peek(self):

        return self.items[len(self.items)-1]

    def size(self):

        return len(self.items)

def replace(data):

    for i in range(len(data)):

        if data[i]=='(':

            data[i]=')'

        elif data[i]==')':

            data[i]='('

    return data

def infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr 

    for token in tokenList:

        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":

            postfixList.append(token)

        elif token == '(':

            opStack.push(token)

        elif token == ')':

            topToken = opStack.pop()

            while topToken != '(':

                postfixList.append(topToken)

                topToken = opStack.pop()

        else:

            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]) :

                postfixList.append(opStack.pop())

            opStack.push(token)

    while not opStack.isEmpty():

        postfixList.append(opStack.pop())

    return " ".join(postfixList)

def postfixEval(postfixExpr):

    operandStack = Stack()

    tokenList = postfixExpr

    for token in tokenList:

        if token in "0123456789":

            operandStack.push(int(token))

        else:

            operand2 = operandStack.pop()

            operand1 = operandStack.pop()

            result = doMath(token,operand1,operand2)

            operandStack.push(result)

    return operandStack.pop()

def doMath(op, op1, op2):

    if op == "*":

        return op1 * op2

    elif op == "/":

        return op1 / op2

    elif op == "+":

        return op1 + op2

    else:

        return op1 - op2

#Main Program

infix = input("Masukan : ")

a = infix.split()

Data = []

for i in range (len(a)):

    Data.append(a[i])

data2= Data[::-1]

hasil = replace(data2)

total1 = infixToPostfix(hasil)

total = total1[::-1]

print (total)

Preval = input("Masukan : ")

b = Preval.split()

Data2 = []

for i in range (len(b)):

    Data2.append(b[i])

Datum = Data2[::-1]

eval1 = postfixEval(Datum)

print (eval1)

Infix To Postfix + Evaluasi

Infix To Postfix pada Python

from __future__ import print_function

class Stack:

    def __init__(self):

        self.items = []

    def isEmpty(self):

        return self.items==[]

    def push(self,items):

        self.items.append(items)

    def pop(self):

        return self.items.pop()

    def peek(self):

        return self.items[len(self.items)-1]

    def size(self):

        return len(self.items)

def infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr.split()  

    print (tokenList)

    for token in tokenList:

        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":

            postfixList.append(token)

        elif token == '(':

            opStack.push(token)

        elif token == ')':

            topToken = opStack.pop()

            while topToken != '(':

                postfixList.append(topToken)

                topToken = opStack.pop()

        else:

            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]) :

                postfixList.append(opStack.pop())

            opStack.push(token)

    while not opStack.isEmpty():

        postfixList.append(opStack.pop())

    return " ".join(postfixList)

def postfixEval(postfixExpr):

    operandStack = Stack()

    tokenList = postfixExpr.split()

    for token in tokenList:

        if token in "0123456789":

            operandStack.push(int(token))

        else:

            operand2 = operandStack.pop()

            operand1 = operandStack.pop()

            result = doMath(token,operand1,operand2)

            operandStack.push(result)

    return operandStack.pop()

def doMath(op, op1, op2):

    if op == "*":

        return op1 * op2

    elif op == "/":

        return op1 / op2

    elif op == "+":

        return op1 + op2

    else:

        return op1 - op2

# Infix To Postfix

data = input("Masukan Infix (Dalam bentuk String dan tambahan spasi): ")

postfix = infixToPostfix(data)

print (postfix)

# Postfix Evaluasi

data2 = input("Masukan Postfix (Dalam bentuk Angka dan tambahan spasi): ")

infix = postfixEval(data2)

print (infix)

Implementasi Stack terhadap Infix, Prefix, dan Postfix

Infix To Postfix + Evaluasi

Dalam struktur data yang kita pelajari secara umum ada 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika,yaitu Prefix,Infix,dan postfix.Dan untuk mengetahui notasi-notasi yang diatas itu,sebelumnya kita harus mengenal dan mengetahui indikator yang ada di notasi itu tersebut.

Notasi ini terbentuk dari Operand dan Operator.
Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses.

contohnya:
A+B*C
2 + 5 * 3
Keterangan: A ,B ,C ,2 ,3 ,5 adalah Operand.
+,*  adalah Operator.

   Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:
-( ) (Kurung).
- ^ (Pangkat).
- * / (Perkalian / Pembagian).
- + - (Penjumlahan / Pengurangan).

Notasi ada 3 jenis, yaitu Prefix,Infix dan Postfix yang seperti kita ketahui di atas:

1.Prefix adalah notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.
   contoh: A + B * C (infix).
   maka notasi prefixnya adalah: +A*BC.

   Pemecahannya:

                A+B*C

        Diketahui ada 3 operand yaitu: A, B, C dan 2 operand yaitu: +, *.proses dimulai dengan melihat dari hirarkhi oprator.Contoh diatas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC.

Sehingga hasil sementara dari notasi prefix adalah:
      A+*BC

        Selanjutnya mencari prefix untuk operator yang berikutnya yaitu  +, cara yang dilakukan sama seperti diatas, operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir menjadi :
     +A*BC.


2.Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.
   Contoh :           
                 - A + B * C
                 - (A + B) * C
                 - A - (B + C) * D ^ E


3.Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.
   Contoh : A + B * C ( infix).
maka notasi postfix adalah ABC*+.

Stack, Queue, dan Dequeue Python

Stack, Queue, dan Dequeue pada Python

Stack (disebut pula “push-down stack”) adalah koleksi berurut dari item-item dimana
penambahan item baru dan penghapusan item yang telah ada selalu terjadi di ujung yang
sama. Ujung ini dinamakan sebagai “top.” Ujung berlawanan dari top dikenal sebagai “base.”
Stack diurutkan mengikuti konsep LIFO (last in first out). Berikut ini adalah beberapa operasi
terhadap stack:

- stack() membuat suatu stack baru yang kosong. Tidak memerlukan parameter dan
mengembalikan suatu stack kosong.
- push(item) menambahkan suatu item baru ke atas (top) dari stack. Perlu item dan
tidak mengembalikan apapun.
- pop() menghapus item teratas dari stack. Tidak perlu parameter dan mengembalikan
item. Stack berubah.
- peek() mengembalikan top item dari stack tetapi tidak menghapusnya. Tidak
memerlukan parameter dan stack tidak berubah.
- isEmpty() memeriksa apakah stack dalam keadaan kosong. Tidak memerlukan
parameter dan mengembalikan nilai boolean.
- size() mengembalikan jumlah item di dalam stack. Tidak memerlukan parameter dan
mengembalikan suatu integer.

Contoh Source code Stack():

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items==[]

    def push(self,items):
        self.items.append(items)

    def pop(self):
        return self.items.pop()

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)
print ("=".center(42,"="))       
print ("Stack")
print ("=".center(42,"="))
print()
s = Stack()
s.push("Hello")
s.push("World")

while not s.isEmpty():
    print(s.pop())

Queue atau antrian adalah suatu koleksi item berurut dimana penambahan item baru terjadi
di satu ujung bernama “ekor” (rear) dan penghapusan terjadi pada ujung lainnya yang
dinamakan “kepala” (front). Queues menggunakan pengurutan FIFO. Berikut ini adalah
beberapa operasi Queue:

- queue() membuat suatu antrian baru yang kosong. Tidak memerlukan parameter dan
mengembalikan suatu antrian kosong.
- enqueue(item) menambahkan suatu item baru ke ujung saru antrian. Perlu item dan
tidak mengembalikan sesuatu.
- dequeue() menghapus item depan dari antrian. Tidak memerlukan parameter dan
mengembalikan itemnya. Antrian termodifikasi.
- isEmpty() menguji untuk melihat apakah antrian dalam keadaan kosong. Tidak
memerlukan parameter dan mengembalian nilai boolean.
- size() mengembalikan jumlah item yang ada di dalam antrian. Tidak memerlukan
parameter dan mengembalikan suatu integer.

Contoh Source code Queue():

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items==[]

    def enqueue (self,items):
        self.items.insert(0,items)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)
     
print("Queue")
print ("=".center(42,"="))
print ()
q = Queue()
q.enqueue("Hello")
q.enqueue("World")
q.enqueue("Python3")

while not q.isEmpty():
    print(q.dequeue())

Deque (Deantrian), dikenal juga sebagai antrian berujung dua (double-ended), adalah suatu koleksi item terurut serupa dengan queue. Perbedaannya? Sifat tidak terikat untuk penambahan dan penghapusan item-item dari antrian. Item baru dapat ditambahkan ke depan atau belakang. Karena itu, item yang ada dapat dihapuskan dari salah satu ujung. Struktur linier hibrida ini menyediakan semua kapabilutas stack dan antrian dalam satu struktur data.

- deque() membuat suatu deque baru yang kosong. Tidak perlu parameter dan mengembalikan suatu deque kosong.
- addFront(item) menambahkan suatu item baru ke depan dari deque. Perlu item dan tidak mengembalikan apapun.
- addRear(item) menambahkan suatu item baru ke ekor dari deque. Perlu item dam tidak mengembalikan sesuatu.
- removeFront() menghapus item depan dari deque. Tidak perlu parameter dan mengembalikan item. Deque termodifikasi.
- removeRear() menghapus item ujung (ekor) dari deque. Tidak perlu parameter dan mengembalikan item. Deque berubah.
- viewFront() menampilkan item depan dari deque.
- viewRear() menampilkan ujung (ekor) dari deque.
- isEmpty() menguji apakah deque dalam kondisi kosong. Tidak perlu parameter dan mengembalikan suatu

Contoh Source Code dequeue():

class Dequeu:
    def __init__(self):
        self.items = []
       
    def isEmpty(self):
        return self.items == []
       
    def addFront(self,items):
        self.items.insert(0,items)
       
    def addRear(self,items):
        self.items.append(items)
       
    def removeFront(self):
        return self.items.pop()
       
    def removeRear(self):
        return self.items.pop(0)
       
    def vievFront(self):
        return self.items[0]
       
    def viewRear(self):
        return self.items[len(self.items)-1]
       
print ("=".center(42,"="))
print ("Dequeu")
print ("=".center(42,"="))
d = Dequeu()
d.isEmpty()
d.addFront("d")
d.addFront("a")
d.addFront("s")
d.addFront("r")
d.addFront("I")

while not d.isEmpty():
    print(d.removeRear())

Pahami dan banyak-banyaklah mencoba...

Shell Sort Python

Shell Sort pada Pyhton

Hal ini dapat dilihat sebagai generalisasi penyortiran dengan pertukaran (bubble sort) atau penyortiran dengan penyisipan (semacam penyisipan). Metode ini dimulai dengan menyortir pasangan elemen yang berjauhan satu sama lain, lalu secara progresif mengurangi jarak antar elemen yang akan dibandingkan. Dimulai dengan elemen yang berjauhan, ia dapat memindahkan beberapa elemen di luar tempat ke posisi lebih cepat daripada pertukaran tetangga terdekat yang sederhana.

N = 8

Gap : 8/2 = 4

Compare:

0-4

1-5

2-6

3-7

Gap : 4/2 = 2

Compare:

0-2    4-6

1-3    5-7

2-4

3-5

Gap : 2/2 = 1

Insertion Sort

Contoh Source Code Shell Sort :

from __future__ import print_function

def shellSort(alist):

    sublistcount = len(alist)//2

    while sublistcount > 0:

      for startposition in range(sublistcount):

        gapInsertionSort(alist,startposition,sublistcount)

      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):

    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]

        position = i

        while position>=gap and alist[position-gap]>currentvalue:

            alist[position]=alist[position-gap]

            position = position-gap

        alist[position]=currentvalue

alist = [35,33,42,10,14,19,27,44]

shellSort(alist)

print(alist)

Selamat Mencoba...