Har börjat ytterligare en kurs. Den här handlar om algoritmer och hålls på coursera. Kursen hålls utav Robert Sedgewick, professor på Princeton. Han har för övrigt skrivit boken "Algorithms" som jag har i bokhyllan. Det är en 6-veckors kurs som går igenom en hel del intressanta saker...
Vi börjar med: vecka 1 lecture slides (union find)
Vi börjar med en definition:
Anta att "is connected to" är en ekvivalens relation: Reflexive: p is connected to p. Symmetric: if p is connected to q, then q is connected to p. Transitive: if p is connected to q and q is connected to r, then p is connected to r
Vi ska skapa en klass UF som har ett antal olika metoder: UF(int N) // initiera N "objekt" i en array void union(int p, int q) // gör en koppling mellan p och q boolean isConnected(int p, int q) // kolla om p och q är kopplade int find(int p) int count()
(Jag antar att jag skulle kunna göra denna på två olika sätt, dels traditonell objektorienterad samt funktionell...)
Vi kommer nu att analysera lite olika angreppssätt: quick-find quick-union weighted quick-union quick-union + path compression weighted quick-union + path compression
Vi kommer att se att med diverse olika förbättringar så kommer vi gå från O(M x N) till O(N + M lg(N)) vilket är en avsevärd förbättring (N=10^9 går från 30 år till 6 sekunder).
1: modellera problemet 2: hitta en algoritm för att lösa problemet 3: tillräckligt snabb? minnesproblem? 4: om inte, försök förstå varför 5: hitta ett sätt att addressera problemet 6: iterera...
Vi gör ett test:
In [1]:
import numpy as np
N = 10
cf_uf = np.arange(10)
def cf_union(p, q):
# todo: verifiy that p and q within boundaries
pid = cf_uf[p]
qid = cf_uf[q]
for idx in range(N):
if cf_uf[idx] == pid:
cf_uf[idx] = qid
def cf_isConnected(p, q):
return cf_uf[p] == cf_uf[q]
cf_union(0, 1)
cf_union(1, 4)
cf_union(3, 2)
cf_union(1, 3)
cf_union(8, 9)
print(cf_isConnected(1, 0))
print(cf_isConnected(1, 2))
print(cf_isConnected(1, 9))
print(cf_isConnected(4, 2))
print(cf_isConnected(0, 3))
print(cf_uf)
Det går snabbt att avgöra om två stycken element är sammankopplade med varandra MEN det är inte så effektivt att koppla ihop element. Vi har en "for loop" som går igenom varje element varje gång vi gör en koppling: Ordo(M x N)!
Vi har sett att det finns ett problem med "union" metoden i quick-find, den skalar inte! Vi gör en ny ansats.
In [2]:
cu_uf = np.arange(N)
def cu_findRoot(p):
parent = cu_uf[p]
if parent == p:
return p
return cu_findRoot(parent)
def cu_union(p, q):
# todo: verify that p and q are within boundaries
cu_uf[cu_findRoot(p)] = cu_uf[cu_findRoot(q)]
#cu_uf[cu_findRoot(p)] = cu_uf[q] <- we do not use this one either
#cu_uf[p] = cu_uf[q] <- this one is wrong!
def cu_isConnected(p, q):
return cu_findRoot(p) == cu_findRoot(q)
cu_union(0, 1)
cu_union(1, 4)
cu_union(3, 2)
cu_union(1, 3)
cu_union(8, 9)
print(cu_isConnected(1, 0))
print(cu_isConnected(0, 2))
print(cu_isConnected(1, 9))
print(cu_isConnected(4, 2))
print(cu_isConnected(0, 3))
print(cu_uf)
Nå blev "union" metoden snabbare men det tar betydligt längre tid att verifiera om två noder är kopplade eller ej. I värsta fall är det O(N)
Oups! Ovanstående "union" fungerar ju inte... det är ju "rooten" som skall ändras och inte det "objekt" som vi kopplar ihop... jag gör om och hastigt och lustigt blir algoritmen betydligt sämre vad gäller "union". Potentiellt sett måste vi iterera igenom N-1 element för att koppla ihop två: O(N)(?)
Och inte heller denna ska vi använda oss utav...
In [3]:
wcu_uf = np.arange(N)
wcu_sz = np.ones(N)
def wcu_findRoot(p):
parent = wcu_uf[p]
if parent == p:
return p
return wcu_findRoot(parent)
def wcu_union(p, q):
# todo: verify that p and q are within boundaries
p_parent = wcu_findRoot(p)
q_parent = wcu_findRoot(q)
if p_parent != q_parent:
if wcu_sz[p_parent] > wcu_sz[q_parent]:
wcu_uf[q_parent] = wcu_uf[p_parent]
wcu_sz[p_parent] += wcu_sz[q_parent]
else:
wcu_uf[p_parent] = wcu_uf[q_parent]
wcu_sz[q_parent] += wcu_sz[p_parent]
#cu_uf[cu_findRoot(p)] = cu_uf[q] <- we do not use this one either
#cu_uf[p] = cu_uf[q] <- this one is wrong!
def wcu_isConnected(p, q):
return wcu_findRoot(p) == wcu_findRoot(q)
wcu_union(0, 1)
wcu_union(1, 4)
wcu_union(3, 2)
wcu_union(1, 3)
wcu_union(8, 9)
print(wcu_isConnected(1, 0))
print(wcu_isConnected(0, 2))
print(wcu_isConnected(1, 9))
print(wcu_isConnected(4, 2))
print(wcu_uf)
print(wcu_sz)
In [ ]:
ones = np.ones(3)
np.sum(ones)
In [5]:
# percolate:
import numpy as np
from bokeh.plotting import figure
from bokeh.io import push_notebook, output_notebook, reset_output, show
import sys
import random
output_notebook()
p = figure(plot_width=400, plot_height=400, tools='pan,box_zoom,wheel_zoom,save')
N = 40
opened = np.zeros(N*N)
sz = np.ones(N*N+2)
uf = np.arange(N*N+2)
x = [x for r in range(N) for x in range(N)]
y = [N-y for y in range(N) for x in range(N)]
colors = ['olive' for x in range(N*N)]
last_x = []
last_y = []
p.square(x, y, size=(400 // N)*0.75, color = colors, alpha = 0.5)
p.circle(last_x, last_y, size=(400 // N) * 0.5, color = 'red', alpha = 0.5)
t = show(p, notebook_handle=True)
def findRoot(p):
parent = uf[p]
if parent == p:
return p
return findRoot(parent)
def union(p, q):
# todo: verify that p and q are within boundaries
p_parent = findRoot(p)
q_parent = findRoot(q)
if p_parent != q_parent:
if sz[p_parent] > sz[q_parent]:
uf[q_parent] = uf[p_parent]
sz[p_parent] += sz[q_parent]
else:
uf[p_parent] = uf[q_parent]
sz[q_parent] += sz[p_parent]
#cu_uf[cu_findRoot(p)] = cu_uf[q] <- we do not use this one either
#cu_uf[p] = cu_uf[q] <- this one is wrong!
def isConnected(p, q):
return findRoot(p) == findRoot(q)
def openCell(row, col):
if not isOpen(row, col):
idx = row*N + col
opened[idx] = 1
if row == 0:
union(idx, N*N)
elif isOpen(row-1, col):
union(idx, idx-N)
if col > 0 and isOpen(row, col-1):
union(idx, idx-1)
if col < N-1 and isOpen(row, col+1):
union(idx, idx+1)
if row == N-1:
union(idx, N*N+1)
elif isOpen(row+1, col):
union(idx, idx+N)
color = 'white'
if isConnected(idx, N*N):
color = 'blue'
colors[idx] = color
for i in range(N*N):
if isConnected(i, N*N):
colors[i] = 'blue'
push_notebook(handle = t)
def isOpen(row, col):
return opened[row*N+col] == 1
def isFull(row, col):
return opened[row*N+col] == 0
def numberOfOpenSites():
return np.sum(opened)
def percolates():
return isConnected(N*N, N*N+1)
while not percolates():
idx = random.randint(0, N*N-1)
openCell(idx // N, idx % N)
last_x.append(idx % N)
last_y.append(N - (idx // N))
push_notebook(handle = t)
reset_output()
#for i in range(60):
# idx = random.randint(0,N*N-1)
# openCell(idx // N, idx % N)
#openCell(0,2)
#openCell(1,2)
#openCell(2,2)
#openCell(2,1)
#openCell(3,1)
#openCell(4,1)
#openCell(5,1)
#openCell(6,1)
#openCell(7,1)
#openCell(8,1)
#openCell(9,1)
#prevRow = 0
#for i in np.arange(N*N):
# row = i // N
# col = i % N
# mark = '.'
# if isConnected(i, N*N):
# mark = '*'
# elif isOpen(row, col):
# mark = ' '
#
# nl = ''
# if prevRow < row:
# nl = '\n'
#
# sys.stdout.write(nl+mark)
#
# prevRow = row
#sys.stdout.write('\n')
print(percolates(), numberOfOpenSites(), numberOfOpenSites() / (N*N))
In [30]:
from bokeh.plotting import figure
from bokeh.io import output_notebook, show
output_notebook()
p = figure(plot_width=400, plot_height=400, tools='pan,box_zoom,wheel_zoom,save')
percolating_x = []
percolating_y = []
filled_cells_x = []
filled_cells_y = []
open_cells_x = []
open_cells_y = []
last_x = []
last_y = []
prevRow = 0
for i in np.arange(N*N):
row = i // N
col = i % N
if i == idx:
last_x.append(col)
last_y.append(N-row)
if isConnected(i, N*N):
percolating_x.append(col)
percolating_y.append(N-row)
elif isFull(row, col):
filled_cells_x.append(col)
filled_cells_y.append(N-row)
else:
open_cells_x.append(col)
open_cells_y.append(N-row)
p.square(percolating_x, percolating_y, size=(400 // N)*0.75, color = 'blue', alpha = 0.5)
p.square(filled_cells_x, filled_cells_y, size=(400 // N)*0.75, color = 'olive', alpha = 0.5)
p.square(open_cells_x, open_cells_y, size=(400 // N)*0.75, color = 'white', alpha = 0.5)
p.circle(last_x, last_y, size=(400 // N) * 0.5, color = 'red', alpha = 0.5)
show(p)
In [33]:
import plotly
import plotly.plotly as py
import plotly.graph_objs as go
from plotly.graph_objs import Scatter, Layout
plotly.offline.init_notebook_mode()
shapes = []
prevRow = 0
for i in np.arange(N*N):
row = i // N
col = i % N
shape = {
'type' : 'rect',
'x0' : col,
'y0' : N - row,
'x1' : col+1,
'y1' : N - row - 1,
'line' : {'color' : 'rgba(128,0,128,1)'}
}
if i == idx:
shape['fillcolor'] = 'rgba(0,256,128,0.7)'
elif isConnected(i, N*N):
shape['fillcolor'] = 'rgba(128,0,128,0.7)'
elif isFull(row, col):
shape['fillcolor'] = 'rgba(0,0,0,0.7)'
shapes.append(shape)
prevRow = row
trace0 = Scatter(
x=[1],
y=[-1],
text=['Unfilled Rectangle'],
mode='text',
)
data = [trace0]
layout = {
'xaxis': {'range': [0, N], 'showgrid': False,},
'yaxis': {'range': [0, N]},
'shapes': shapes
}
fig = {
'data': data,
'layout': layout,
}
plotly.offline.iplot(fig, filename='shapes-rectangle')
In [42]:
from bokeh.plotting import figure, output_file, show
from bokeh.io import output_notebook
# prepare some data
x = [1, 2, 3, 4, 5]
y = [6, 7, 2, 4, 5]
# output to static HTML file
#output_file("lines.html", title="line plot example")
output_notebook()
# create a new plot with a title and axis labels
p = figure(title="simple line example", x_axis_label='x', y_axis_label='y')
# add a line renderer with legend and line thickness
p.line(x, y, legend="Temp.", line_width=2)
p.square([1, 2, 3, 4, 5], [5, 5, 5, 5, 5], size=20, color="red", alpha=0.5)
p.square(x, y, size=20, color="olive", alpha=0.5)
# show the results
t = show(p, notebook_handle=True)
In [43]:
y[4]=2
push_notebook(handle=t)
reset_output()
In [ ]:
from ipywidgets import widgets
from IPython.display import display
text = widgets.Text()
button = widgets.Button()
display(text)
display(button, description='Button!')
def on_button_clicked(b):
print('Button clicked')
if text.value is not None:
print(text.value)
button.on_click(on_button_clicked)
Under vecka 1 går vi även igenom olika algoritmers komplexitet: lecture slides. Vi tittar dels på hur lång tid en algoritm tar samt även hur mycket minne den konsumerar.