{ Snipperize } /algorithm

Rsync Algorithm In Python

An implementation of the rsync algorithm in Python. As my rolling checksum, I just summed all of the ascii byte values in a given window. Even with this simple weak rolling checksum, computing and comparing the produced rolling checksums is still terribly slow. I'm fairly certain the speed could be reduced a fair amount but I haven't decided what the most efficient manner of doing this in Python alone would be.

Python / algorithm, delta, diff, rsync / by ThePeppersStudio (144 days, 3.68 hours ago)

Efficient Algorithm for computing a Running Median

Maintains sorted data as new elements are added and old one removed as a sliding window advances over a stream of data. Running time per median calculation is proportional to the square-root of the window size.

Python / algorithm, indexable, median, running, skiplist, statistics / by ThePeppersStudio (144 days, 3.79 hours ago)

K-means clustering

Hierarchical clustering gives a nice tree as a result, but it has a couple of disadvan- tages. The tree view doesn’t really break the data into distinct groups without additional work, and the algorithm is extremely computationally intensive. Because the relationship between every pair of items must be calculated and then recalculated when items are merged, the algorithm will run slowly on very large datasets. An alternative method of clustering is K-means clustering. This type of algorithmis quite different from hierarchical clustering because it is told in advance how many distinct clusters to generate. The algorithm will determine the size of the clusters based on the structure of the data. K-means clustering begins with k randomly placed centroids (points in space that represent the center of the cluster), and assigns every item to the nearest one. After the assignment, the centroids are moved to the average location of all the nodes assigned to them, and the assignments are redone. This process repeats until the assignments stop changing.

Python / clustering, K-means, algorithm / by ThePeppersStudio (400 days, 14.58 hours ago)