Algorithms - I

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)

Dynamic connectivity - 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...

quick-find

  • Datastruktur: array med N stycken "integers".
  • Initiera varje element med sitt eget index.
  • Två element anses vara "ihopkopplade" om de har samma "värde"

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)


True
True
False
True
True
[2 2 2 2 2 5 6 7 9 9]

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)!

quick-union

Vi har sett att det finns ett problem med "union" metoden i quick-find, den skalar inte! Vi gör en ny ansats.

  • Datastrukturen är den samma, dvs en vektor med "integers" där varje element talar om vilken som den är kopplad till men nu är det bara en som är kopplad till den andra dvs vi har inte dubbelriktad relation längre. Detta gör det lite lättare att koppla ihop två element MEN det blir betydligt svårare att ta reda på om två element är sammankopplade eller ej.

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)


True
True
False
True
True
[1 4 2 2 2 5 6 7 9 9]

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)


True
True
False
True
[1 1 1 2 1 5 6 7 9 9]
[ 1.  5.  2.  1.  1.  1.  1.  1.  1.  2.]

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))


Loading BokehJS ...
True 981.0 0.613125

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)


Loading BokehJS ...

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)


Loading BokehJS ...

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)

Analys av komplexitet:

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.