rp-tree 0.3.4 → 0.3.5
raw patch · 8 files changed
+38/−46 lines, 8 filesdep −exceptionsdep −mtldep ~conduitdep ~containersdep ~deepseq
Dependencies removed: exceptions, mtl
Dependency ranges changed: conduit, containers, deepseq, serialise, splitmix, splitmix-distributions, transformers, vector, vector-algorithms
Files
- README.md +5/−1
- app/Main.hs +2/−2
- bench/time/Main.hs +3/−5
- rp-tree.cabal +1/−11
- src/Data/RPTree.hs +3/−5
- src/Data/RPTree/Conduit.hs +22/−11
- src/Data/RPTree/Gen.hs +2/−4
- src/Data/RPTree/Internal.hs +0/−7
README.md view
@@ -1,5 +1,9 @@ # rp-tree -+[](https://hackage.haskell.org/package/rp-tree) [](https://github.com/ocramz/rp-tree) Random projection trees for approximate nearest neighbor search in high-dimensional vector spaces.++++
app/Main.hs view
@@ -14,8 +14,8 @@ import qualified Data.Conduit.List as C (chunksOf, unfold, unfoldM) -- containers import qualified Data.IntMap as IM (IntMap, fromList, insert, lookup, map, mapWithKey, traverseWithKey, foldlWithKey, foldrWithKey)--- exceptions-import Control.Monad.Catch (MonadThrow(..))+-- -- exceptions+-- import Control.Monad.Catch (MonadThrow(..)) -- -- mnist-idx-conduit -- import Data.IDX.Conduit (sourceIdxSparse, sBufSize, sNzComponents) -- splitmix-distributions
bench/time/Main.hs view
@@ -17,8 +17,6 @@ import qualified Data.Conduit.Combinators as C (map, mapM, scanl, scanlM, last, print, takeExactly) -- deepseq import Control.DeepSeq (NFData(..), force)--- exceptions-import Control.Monad.Catch (MonadThrow(..)) -- -- mnist-idx-conduit -- import Data.IDX.Conduit (sourceIdxSparse, sBufSize, sNzComponents) -- splitmix-distributions@@ -115,10 +113,10 @@ -- mnist :: MonadResource m => -- FilePath -- path to uncompressed MNIST IDX data file -- -> Int -- number of data items--- -> C.ConduitT a (Embed SVector Double ()) m ()--- mnist fp n = C.takeExactly n src+-- -> C.ConduitT () (Embed SVector Double ()) m ()+-- mnist fp n = src -- where--- src = sourceIdxSparse fp .|+-- src = sourceIdxSparse fp (Just n) .| -- C.map (\r -> fromVectorSv (sBufSize r) (VU.map f $ sNzComponents r)) .| -- C.map (\r -> Embed r ()) -- f (i, x) = (i, toUnitRange x)
rp-tree.cabal view
@@ -1,5 +1,5 @@ name: rp-tree-version: 0.3.4+version: 0.3.5 synopsis: Random projection trees description: Random projection trees for approximate nearest neighbor search in high-dimensional vector spaces .@@ -35,16 +35,10 @@ , conduit >= 1.3.4.1 , containers >= 0.6.2.1 , deepseq >= 1.4.4.0- -- , exceptions- -- , microlens- -- , microlens-th- , mtl- -- , psqueues , serialise >= 0.2.3.0 , splitmix >= 0.1.0.3 , splitmix-distributions >= 0.8 , transformers >= 0.5.6.2- -- , ulid , vector >= 0.12.1.2 , vector-algorithms >= 0.8.0.4 -- -- -- DEBUG@@ -52,7 +46,6 @@ -- , hspec -- , mnist-idx-conduit - test-suite spec default-language: Haskell2010 ghc-options: -Wall@@ -76,9 +69,7 @@ , benchpress , conduit , deepseq >= 1.4.4.0- , exceptions -- , mnist-idx-conduit- , mtl , rp-tree , splitmix >= 0.1.0.3 , splitmix-distributions@@ -93,7 +84,6 @@ build-depends: base , conduit , containers- , exceptions -- , mnist-idx-conduit , rp-tree , splitmix
src/Data/RPTree.hs view
@@ -51,6 +51,8 @@ -- * Construction -- tree, forest+ -- , defaultParams+ -- , ForestParams -- * Query , knn -- * I/O@@ -111,10 +113,6 @@ import qualified Data.Set as S (Set, fromList, intersection, insert) -- deepseq import Control.DeepSeq (NFData(..))--- mtl-import Control.Monad.State (MonadState(..), modify)--- -- psqueues--- import qualified Data.IntPSQ as PQ (IntPSQ, insert, fromList, findMin, minView) -- transformers import Control.Monad.Trans.State (StateT(..), runStateT, evalStateT, State, runState, evalState) import Control.Monad.Trans.Class (MonadTrans(..))@@ -126,7 +124,7 @@ -- vector-algorithms import qualified Data.Vector.Algorithms.Merge as V (sortBy) -import Data.RPTree.Conduit (tree, forest, dataSource, liftC)+import Data.RPTree.Conduit (tree, forest, ForestParams, defaultParams, dataSource, liftC) import Data.RPTree.Gen (sparse, dense, normal2, normalSparse2) import Data.RPTree.Internal (RPTree(..), RPForest, RPT(..), Embed(..), levels, points, Inner(..), Scale(..), scaleS, scaleD, (/.), innerDD, innerSD, innerSS, metricSSL2, metricSDL2, SVector(..), fromListSv, fromVectorSv, DVector(..), fromListDv, fromVectorDv, partitionAtMedian, Margin, getMargin, sortByVG, serialiseRPForest, deserialiseRPForest) import Data.RPTree.Internal.Testing (BenchConfig(..), randSeed, datS, datD)
src/Data/RPTree/Conduit.hs view
@@ -6,7 +6,10 @@ module Data.RPTree.Conduit ( tree,- forest+ forest,+ ForestParams,+ fpMaxTreeDepth,+ defaultParams -- ** helpers , dataSource , liftC@@ -24,10 +27,6 @@ import qualified Data.Conduit.List as C (chunksOf, unfold, unfoldM, mapAccum) -- containers import qualified Data.IntMap.Strict as IM (IntMap, fromList, insert, lookup, map, mapWithKey, traverseWithKey, foldlWithKey, foldrWithKey, intersectionWith)--- -- exceptions--- import Control.Monad.Catch (MonadThrow(..))--- mtl-import Control.Monad.State (MonadState(..), modify) -- splitmix-distributions import System.Random.SplitMix.Distributions (Gen, sample, GenT, sampleT, normal, stdNormal, stdUniform, exponential, bernoulli, uniformR) -- transformers@@ -103,12 +102,12 @@ -- * bounded : we wait until the end of the stream to produce a result forest :: (Monad m, Inner SVector v) => Word64 -- ^ random seed- -> Int -- ^ max tree depth- -> Int -- ^ min leaf size- -> Int -- ^ number of trees- -> Int -- ^ data chunk size- -> Double -- ^ nonzero density of projection vectors- -> Int -- ^ dimension of projection vectors+ -> Int -- ^ max tree depth, \(l > 1\) + -> Int -- ^ min leaf size, \(m_{leaf} > 1\)+ -> Int -- ^ number of trees, \(n_t > 1\)+ -> Int -- ^ data chunk size, \(n_{chunk} > 3\)+ -> Double -- ^ nonzero density of projection vectors, \(p_{nz} \in (0, 1)\)+ -> Int -- ^ dimension of projection vectors, \(d > 1\) -> C.ConduitT () (Embed v Double x) m () -- ^ data source -> m (RPForest Double (V.Vector (Embed v Double x))) forest seed maxd minl ntrees chunksize pnz dim src = do@@ -120,6 +119,18 @@ insertMultiC maxd minl chunksize rvss pure $ IM.intersectionWith RPTree rvss ts +data ForestParams = CP {+ fpMaxTreeDepth :: Int -- ^ max tree depth \(l > 1\) + , fpMinLeafSize :: Int -- ^ min leaf size + , fpNumTrees :: Int -- ^ number of trees \(n_t > 1\)+ , fpDataChunkSize :: Int -- ^ data chunk size+ , fpProjNzDensity :: Double -- ^ nonzero density of projection vectors \(p_{nz} \in (0, 1)\)+ , fpProjDimension :: Int -- ^ dimension of projection vectors \(d > 1\)+ } deriving (Show)++defaultParams :: Int -- ^ dimension of projection vectors \(d > 1\)+ -> ForestParams+defaultParams d = CP 5 10 3 100 0.5 d
src/Data/RPTree/Gen.hs view
@@ -9,13 +9,11 @@ -- containers import qualified Data.IntMap as IM (IntMap, insert, toList)--- mtl-import Control.Monad.Trans.Class (MonadTrans(..))-import Control.Monad.State (MonadState(..), modify) -- splitmix-distribitions import System.Random.SplitMix.Distributions (Gen, GenT, stdUniform, bernoulli, exponential, normal, discrete, categorical) -- transformers-import Control.Monad.Trans.State (StateT(..), runStateT, evalStateT, State, runState, evalState)+import Control.Monad.Trans.Class (MonadTrans(..))+import Control.Monad.Trans.State (StateT(..), get, put, runStateT, evalStateT, State, runState, evalState) -- vector
src/Data/RPTree/Internal.hs view
@@ -33,15 +33,8 @@ import qualified Data.IntMap.Strict as IM (IntMap, fromList) -- deepseq import Control.DeepSeq (NFData(..))--- -- microlens--- import Lens.Micro (Traversal', (.~), (^..), folded)--- import Lens.Micro.TH (makeLensesFor, makeLensesWith, lensRules, generateSignatures)--- mtl-import Control.Monad.State (MonadState(..), modify) -- serialise import Codec.Serialise (Serialise(..), serialise, deserialiseOrFail)--- transformers-import Control.Monad.Trans.State (StateT(..), runStateT, evalStateT, State, runState, evalState) -- vector import qualified Data.Vector as V (Vector, replicateM, fromList) import qualified Data.Vector.Generic as VG (Vector(..), map, sum, unfoldr, unfoldrM, length, replicateM, (!), (!?), take, drop, unzip, freeze, thaw, foldl, foldr, toList, zipWith, last, head, imap)