Skip to content

LeslieK/UnionFind33

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

8 Commits
 
 
 
 
 
 
 
 
 
 

Repository files navigation

usage:
$ python performanceTest.py

performanceTest.py
This is the top level program.
Enter the test to run:
0: compares 2 algorithms (Enter the 2 algorithms)
1: tests a single algorithm(Enter the algorithm)

Enter the number of trials (for each trial, N is doubled)
Enter the initial number of sites (N)

Results:
test 0: print the ratio of running times of algo1 : algo2
test 1: print the ratio of current and previous running times

Here is a blog post about running these experiments:
http://lesliebklein.tumblr.com/post/76189280783/im-feeling-like-a-better-programmer-via-union-find


randomGrid.py
generates random pairs of connections for an N x N grid

ErdosRenyi.py
reads in N (number of sites) and algorithm (algo) from standard input
returns the number of random connections needed to connect the N sites
returns both the number calculated by theory and the number generated by experiment

WeightedQuickUF.py
contains the implementations of the algorithms as classes:
QuickFind (QF)
QuickUnion (QU)
WeightedQuickUnionUF (WQU)
WeightedQuickUnionUFHeight (WQUH)
WeightedQuickUnionUFPC (with path compression) (WQUPC)

About

Experiments with union find algos for python 3.3

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages