kmeans-par 1.4.2 → 1.5.0

raw patch · 4 files changed

+22/−12 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• benchmark/Main.lhs +5/−4
• kmeans-par.cabal +1/−1
• src/Algorithms/Lloyd/Sequential.lhs +6/−3
• src/Algorithms/Lloyd/Strategies.lhs +10/−4

@@ -1,7 +1,8 @@ We aim to benchmark each implementation of Lloyd's algorithm:  > import Prelude hiding (take, zipWith)-> import Algorithms.Lloyd.Sequential (Point(..), Cluster(..))+> import Algorithms.Lloyd.Sequential (Point(..), Cluster(..), ExpectDivergent(..))+> import Algorithms.Lloyd.Strategies (Partitions(..)) > import qualified Algorithms.Lloyd.Sequential as Sequential (kmeans) > import qualified Algorithms.Lloyd.Strategies as Strategies (kmeans) > import Data.Metric (Metric(..), Euclidean(..))@@ -35,6 +36,6 @@   > main :: IO () > main = defaultMain->   [ bench "Sequential" $ nf (Sequential.kmeans 80 Euclidean points) clusters->   , bench "Strategies" $ nf (Strategies.kmeans 80 Euclidean 64 points) clusters->   ] +>   [ bench "Sequential" $ nf (Sequential.kmeans expectDivergent Euclidean points) clusters+>   , bench "Strategies" $ nf (Strategies.kmeans expectDivergent Euclidean partitions points) clusters+>   ] where (expectDivergent, partitions) = (ExpectDivergent 80, Partitions 64)

@@ -1,5 +1,5 @@ name:                kmeans-par-version:             1.4.2+version:             1.5.0 synopsis:            Sequential and parallel implementations of Lloyd's algorithm. license:             MIT license-file:        LICENSE

@@ -6,6 +6,7 @@ > module Algorithms.Lloyd.Sequential ( >   Point(..), >   Cluster(..), +>   ExpectDivergent(..), >   kmeans, >   PointSum(..), >   makeNewClusters,@@ -132,9 +133,11 @@ convergence. As the algorithm isn't guaranteed to converge, we cut execution if convergence hasn't been observed after eighty iterations: -> computeClusters :: Metric a => Int -> (Vector Double -> a) -> Vector Point -> Vector Cluster -> Vector Cluster-> computeClusters expectDivergent metric = computeClusters' expectDivergent metric 0 +> newtype ExpectDivergent = ExpectDivergent { expectDivergent :: Int } >+> computeClusters :: Metric a => ExpectDivergent -> (Vector Double -> a) -> Vector Point -> Vector Cluster -> Vector Cluster+> computeClusters (expectDivergent -> expectDivergent) metric = computeClusters' expectDivergent metric 0 +> > computeClusters' :: Metric a => Int -> (Vector Double -> a) -> Int -> Vector Point -> Vector Cluster -> Vector Cluster > computeClusters' expectDivergent metric iterations points clusters  >   | iterations >= expectDivergent = clusters@@ -142,7 +145,7 @@ >   | otherwise                     = computeClusters' expectDivergent metric (succ iterations) points clusters' >   where clusters' = step metric clusters points >-> kmeans :: Metric a => Int -> (Vector Double -> a) -> Vector Point -> Vector Cluster -> Vector (Vector Point)+> kmeans :: Metric a => ExpectDivergent -> (Vector Double -> a) -> Vector Point -> Vector Cluster -> Vector (Vector Point) > kmeans expectDivergent metric points initial = assign metric clusters points >   where clusters = computeClusters expectDivergent metric points initial 

@@ -1,3 +1,5 @@+> {-# LANGUAGE ViewPatterns #-}+ A parallel implementation of Lloyd's algorithm for k-means clustering, adapted from Marlow's _Parallel and Concurrent Programming in Haskell_. Here we use Evaluation Strategies to parallelise the assignment of@@ -6,6 +8,8 @@ > module Algorithms.Lloyd.Strategies ( >   Point(..), >   Cluster(..), +>   ExpectDivergent(..),+>   Partitions(..), >   kmeans > ) where >@@ -17,7 +21,7 @@ > import Data.Semigroup (Semigroup(..)) > import Data.Vector (Vector(..), zipWith, map) > import Data.Vector.Split (chunksOf)-> import Algorithms.Lloyd.Sequential (Cluster(..), Point(..), PointSum(..), makeNewClusters, assignPS, assign)+> import Algorithms.Lloyd.Sequential (Cluster(..), Point(..), ExpectDivergent(..), PointSum(..), makeNewClusters, assignPS, assign)  We can combine two vectors of some same type $t$ provided we know how to combine two $t$s:@@ -43,9 +47,11 @@ are too few items, and those items vary in cost, some of our cores may be unused for part of the computation. -> computeClusters :: Metric a => Int -> (Vector Double -> a) -> Int -> Vector Point -> Vector Cluster -> Vector Cluster-> computeClusters expectDivergent metric = computeClusters' expectDivergent metric 0  ..: chunksOf+> newtype Partitions = Partitions { partitions :: Int } >+> computeClusters :: Metric a => ExpectDivergent -> (Vector Double -> a) -> Partitions -> Vector Point -> Vector Cluster -> Vector Cluster+> computeClusters (expectDivergent -> expectDivergent) metric = computeClusters' expectDivergent metric 0  ..: chunksOf . partitions+> > computeClusters' :: Metric a => Int -> (Vector Double -> a) -> Int -> Vector (Vector Point) -> Vector Cluster -> Vector Cluster > computeClusters' expectDivergent metric iterations points clusters  >   | iterations >= expectDivergent = clusters@@ -53,6 +59,6 @@ >   | otherwise                     = computeClusters' expectDivergent metric (succ iterations) points clusters' >   where clusters' = step metric clusters points >-> kmeans :: Metric a => Int -> (Vector Double -> a) -> Int -> Vector Point -> Vector Cluster -> Vector (Vector Point)+> kmeans :: Metric a => ExpectDivergent -> (Vector Double -> a) -> Partitions -> Vector Point -> Vector Cluster -> Vector (Vector Point) > kmeans expectDivergent metric chunks points initial = assign metric clusters points >   where clusters = computeClusters expectDivergent metric chunks points initial