Comments (20)
Yep you were right, it boost a bit performances, but nothing extraordinary:
foldgWithoutEmpty' :: (a -> b) -> (Operator -> [b] -> b) -> Graph a -> b
foldgWithoutEmpty' f h = go
where
go (Leaf a) = f a
go (Node co xs) = h co $ map go xs
induce :: (a -> Bool) -> Graph a -> Graph a
induce p = foldgWithoutEmpty' (\x -> if p x then Vertex x else Empty) (\co t -> Node co $ filter k t)
where
k (Node _ []) = False -- Constant folding to get rid of Empty leaves
k _ = True
removeVertex
Description: Remove a vertex of the graph
Mesh
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 38.59 ns | 1.350 μs | 19.11 μs | 207.2 μs |
AlgaOld | 41.80 ns | 1.072 μs | 14.01 μs | 170.5 μs |
Clique
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 39.35 ns | 4.519 μs | 539.3 μs | 60.47 ms |
AlgaOld | 41.96 ns | 3.419 μs | 445.9 μs | 155.9 ms |
Circuit
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 112.6 ns | 1.039 μs | 10.68 μs | 104.9 μs |
AlgaOld | 82.09 ns | 857.2 ns | 7.770 μs | 79.26 μs |
SUMMARY:
- AlgaOld was the fastest 17 times
- Alga was the fastest 4 times
There was 3 ex-aequo
ABSTRACT:
(Based on an average of the ratio between largest benchmarks)
- Alga was 1.03 times faster than AlgaOld
from alga.
@nobrakal Interesting! Yes, of course you can represent graphs (or any algebraic expressions) simply by trees labelled with operators. In fact, this is similar to what I plan to use for labelled graphs :-)
See here: https://github.com/snowleopard/alga/blob/edge-labels/src/Algebra/Graph/Labelled.hs#L62-L71
There is one important advantage of the current data type that you didn't mention: its constructors exactly correspond to the algebra of graphs.
This also brings us back to the question: do we need to export the constructors? Maybe we shouldn't. Then we'll be free to choose whatever internal representation we like, including yours.
However, I still prefer to keep the 'vanilla' version of the data type in the library simply because it emerges so naturally from the underlying mathematics.
If the goal is, however, to find the most efficient representation possible, I'm quite sure it will actually be something else and it will be complex -- more complex than what you suggest. There is also a relevant discussion here: #61.
from alga.
In fact, this is similar to what I plan to use for labelled graphs :-)
Haha, I missed this!
This also brings us back to the question: do we need to export the constructors?
Finally, maybe exporting constructors is not the right idea to have.
With some GHC hack, we can allow pattern-matching without constructors, using for example ViewPatterns
from alga.
Yes, ViewPatterns
may be the way to go.
from alga.
An other option is PatternSynonyms. It is much more like what we need to hide constructors, it provide synonyms.
There is a naming problem: A pattern cannot have the same name as the constructor... But one can pose:
data Graph a = EmptyG
| VertexG a
| OverlayG (Graph a) (Graph a)
| ConnectG (Graph a) (Graph a)
deriving (Foldable, Functor, Show, Traversable)
pattern Empty :: Graph a
pattern Empty = EmptyG
pattern Vertex :: a -> Graph a
pattern Vertex a = VertexG a
pattern Overlay :: Graph a -> Graph a -> Graph a
pattern Overlay a b = OverlayG a b
pattern Connect :: Graph a -> Graph a -> Graph a
pattern Connect a b = ConnectG a b
{-# COMPLETE Empty, Vertex, Overlay, Connect #-}
Some advantages:
- They can be used to construct graphs effectively, so they can even replace lower-cased aliases.
- They can be a part of the Graph class definition.
from alga.
Yes, this is a promising approach.
While we're thinking about a more efficient internal representation, I think it is also important to consider packing arguments to multi-way +
and *
into lists. You then end up with something like this:
data Operator = Overlay | Connect
data Graph a = Leaf a | Node Operator [Graph a]
empty = Node Overlay []
vertex = Leaf
overlays = Node Overlay
connects = Node Connect
This works thanks to the associativity of both operators.
from alga.
I played a bit this afternoon and came to:
data Operator = OverlayG | ConnectG deriving (Eq,Show)
data Graph a = Leaf a | Node Operator [Graph a]
deriving (Foldable, Functor, Show, Traversable)
pattern Empty :: Graph a
pattern Empty <- Node _ [] where
Empty = Node OverlayG []
pattern Vertex :: a -> Graph a
pattern Vertex a = Leaf a
pattern Overlay :: Graph a -> Graph a -> Graph a
pattern Overlay a b <- (view -> Node OverlayG [a,b]) where
Overlay a b = Node OverlayG [a,b]
pattern Connect :: Graph a -> Graph a -> Graph a
pattern Connect a b <- (view -> Node ConnectG [a,b]) where
Connect a b = Node ConnectG [a,b]
{-# COMPLETE Empty, Vertex, Overlay, Connect #-}
{-# COMPLETE Empty, Vertex, Node #-}
view :: Graph a -> Graph a
view (Node c [a,b]) = Node c [a,b]
view (Node c (x:xs)) = Node c [x,Node c xs]
view g = g
This is passing tests, combining view patterns and patterns synonyms can lead to some interesting results ^^.
Sadly, I think this will slow down the whole thing, since the traditional foldg will not be so efficient !
from alga.
The results of the bench suite, even using custom foldg like the don't require the Connect of Overlay information, for example, I redefined hasVertex
with
foldg'' :: b -> (a -> b) -> ([b] -> b) -> Graph a -> b
foldg'' e v o = go
where
go Empty = e
go (Vertex x ) = v x
go (Node _ xs) = o $ map go xs
hasVertex :: Eq a => a -> Graph a -> Bool
hasVertex x = foldg'' False (==x) or
The result of the benchmarking suite
isEmpty: 0.97
vertexList: 2.33
vertexCount: 2.25
hasVertex: 1.58
edgeCount: 1.94
edgeList: 1.45
hasEdge: 1.63
addEdge: 2.03
addVertex: 2.68
removeVertex: 1.50
from alga.
foldg''
We might call such folds "blindfolds" :-)
Are numbers > 1 good? I'm sure I'll keep forgetting that :D Maybe should add (good)
, (bad)
to the table!
By the way, have you also done overlays = Node Overlay
and connects = Node Connect
? That should give a good speed up.
from alga.
I added a small reminder:
Comparing Alga to AlgaOld . It means that the displayed number will be k such that Alga = k * AlgaOld
So these are very bad values ^^. I just saw that I haven't changed rnf
, so maybe when I used pattern matching, it slowed down the whole thing.
I tired with more specialized foldg
but I am not able to obtain descent results
I have pushed the try here: https://github.com/nobrakal/alga/tree/betterRepresentation
A bench is running: https://travis-ci.com/nobrakal/alga/jobs/130222270
from alga.
It means that the displayed number will be k such that Alga = k * AlgaOld
I'm afraid this doesn't help me, still takes me a while to understand =) Why not add obvious (good)
/(bad)
labels instead? If you want to get fancy, you could also add (OK)
when 0.9 < k < 1.1
.
vertexList: 1.92
It's quite surprising to see such a slowdown here. We should be doing less work to traverse a tree and find all vertices -- do you have any ideas why this happens? By the way, it may be useful to test the whole Algebra.Graph
API in the regression suite.
from alga.
Why not add obvious (good)/(bad) labels instead?
It is done now :)
do you have any ideas why this happens?
Corrected now, it was again a problem with foldl :) Now vertexList
is a bit faster:
vertexList
Description: Produce a list of the vertices in the graph
Mesh
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 42.71 ns | 312.1 ns | 314.5 ns | 736.2 ns |
AlgaOld | 45.18 ns | 368.3 ns | 371.9 ns | 695.7 ns |
Clique
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 42.62 ns | 1.977 μs | 341.9 μs | 68.43 ms |
AlgaOld | 45.30 ns | 2.367 μs | 442.3 μs | 99.67 ms |
SUMMARY:
- Alga was the fastest 5 times
There was 3 ex-aequo
ABSTRACT:
(Based on an average of the ratio between largest benchmarks)
- Alga was 1.15 times faster than AlgaOld
My induce
is still not convincing:
foldgWithoutEmpty' :: (a -> b) -> ([b] -> b) -> ([b] -> b) -> Graph a -> b
foldgWithoutEmpty' f o c = go
where
go (Leaf a) = f a
go (Node co xs) = case co of
OverlayG -> o $ map go xs
_ -> c $ map go xs
induce :: (a -> Bool) -> Graph a -> Graph a
induce p = foldgWithoutEmpty' (\x -> if p x then Vertex x else Empty) (overlays . filter k) (connects . filter k)
where
k (Node _ []) = False -- Constant folding to get rid of Empty leaves
k _ = True
removeVertex
Description: Remove a vertex of the graph
Mesh
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 33.06 ns | 522.7 ns | 529.2 ns | 1.395 μs |
AlgaOld | 35.66 ns | 368.3 ns | 362.4 ns | 925.7 ns |
Clique
1 | 10 | 100 | 1000 | |
---|---|---|---|---|
Alga | 32.52 ns | 4.863 μs | 561.3 μs | 61.48 ms |
AlgaOld | 34.27 ns | 3.098 μs | 456.6 μs | 172.5 ms |
SUMMARY:
- AlgaOld was the fastest 10 times
- Alga was the fastest 2 times
There was 4 ex-aequo
ABSTRACT:
(Based on an average of the ratio between largest benchmarks)
- Alga was 1.07 times faster than AlgaOld
By the way, it may be useful to test the whole Algebra.Graph API in the regression suite.
Yeah of course. I don't really now where to do that (because I need to extend the configuration file in haskell-perf/graph
). Here ? In nobrakal/benchAlgaPr
(I am not satisfied with this repo).
from alga.
Thanks @nobrakal!
Perhaps, for foldgWithoutEmpty'
you need to use parameter Operator -> [b] -> b
instead? That might lead to a more efficient code.
from alga.
Ooops, I spent some time to figure out the the bench-suite was broken. A mesh wasn't a real mesh !
Here is the corrected times:
removeVertex
Description: Remove a vertex of the graph
Mesh
1000 | |
---|---|
Alga | 195.8 μs |
AlgaOld | 185.9 μs |
Clique
1000 | |
---|---|
Alga | 55.75 ms |
AlgaOld | 163.2 ms |
Circuit
1000 | |
---|---|
Alga | 98.39 μs |
AlgaOld | 89.24 μs |
SUMMARY:
- Alga was the fastest 2 times
- AlgaOld was the fastest 2 times
There was 2 ex-aequo
ABSTRACT:
(Based on an average of the ratio between largest benchmarks)
- Alga was 1.20 times faster than AlgaOld
So there is a surprising drop for clique. Again, strangely,
induce :: (a -> Bool) -> Graph a -> Graph a
induce p = go
where
go (Leaf a) = if p a then Leaf a else Empty
go (Node co xs) = Node co $ filter k $ map go xs
k (Node _ []) = False -- Constant folding to get rid of Empty leaves
k _ = True
Is not faster, it is worse:
removeVertex
Description: Remove a vertex of the graph
Mesh
1000 | |
---|---|
Alga | 224.7 μs |
AlgaOld | 169.3 μs |
Clique
1000 | |
---|---|
Alga | 68.39 ms |
AlgaOld | 169.2 ms |
Circuit
1000 | |
---|---|
Alga | 116.9 μs |
AlgaOld | 80.39 μs |
SUMMARY:
- AlgaOld was the fastest 4 times
- Alga was the fastest 2 times
ABSTRACT:
(Based on an average of the ratio between largest benchmarks)
- AlgaOld was 1.06 times faster than Alga
Perhaps, for foldgWithoutEmpty' you need to use parameter Operator -> [b] -> b instead? That might lead to a more efficient code.
What do you mean ?
from alga.
What do you mean?
I mean the function signature should be:
foldgWithoutEmpty' :: (a -> b) -> (Operator -> [b] -> b) -> Graph a -> b
foldgWithoutEmpty' v op g = ...
The function op
here deals with both types of nodes, so one of the conditionals (checking the operator of the current node) disappears/is pushed inside the function.
from alga.
Again, this is a problem with edges
. Maybe I should change the comparing script to use the alga representation instead of edges
, but edges
is what users will use.
The same code benchmarked using alga's clique:
Clique
1000 | |
---|---|
Alga | 29.79 μs |
AlgaOld | 34.93 μs |
from alga.
I agree: edges
is very often used to construct graphs, so we shouldn't assume graph expressions are coming in a better shape.
from alga.
So I don't know if we can make a better induce
here (and because all the graphs structures are similar when building with edges, our induce is faster on very big lists nested inside a Node
)
from alga.
Note that the implementation described in #84 (comment) shows great results here
### Clique
#### 1000
##### (0,1)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 76.30 ns | 1.000 |
| AlgaOld || 93.11 ms | 0.898 |
+---------++----------+-------+
##### (292,820)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 18.99 ms | 0.971 |
| AlgaOld || 95.07 ms | 0.970 |
+---------++----------+-------+
##### (997,999)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 45.77 ms | 0.996 |
| AlgaOld || 88.05 ms | 0.974 |
+---------++----------+-------+
##### (0,0)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 32.41 ms | 0.999 |
| AlgaOld || 90.33 ms | 0.978 |
+---------++----------+-------+
##### (1,0)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 45.26 ms | 1.000 |
| AlgaOld || 92.34 ms | 0.979 |
+---------++----------+-------+
##### (1,1)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 31.54 ms | 1.000 |
| AlgaOld || 90.06 ms | 0.980 |
+---------++----------+-------+
Even with an algebraic clique:
### Clique
#### 1000
##### (0,1)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 71.73 ns | 0.995 |
| AlgaOld || 48.15 μs | 1.000 |
+---------++----------+-------+
##### (292,820)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 16.92 μs | 1.000 |
| AlgaOld || 53.08 μs | 1.000 |
+---------++----------+-------+
##### (997,999)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 33.32 μs | 0.999 |
| AlgaOld || 53.66 μs | 1.000 |
+---------++----------+-------+
##### (0,0)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 26.77 μs | 1.000 |
| AlgaOld || 48.66 μs | 1.000 |
+---------++----------+-------+
##### (1,0)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 28.30 μs | 1.000 |
| AlgaOld || 48.14 μs | 1.000 |
+---------++----------+-------+
##### (1,1)
+---------++----------+-------+
| || Time | R² |
+=========++==========+=======+
| Alga || 95.58 ns | 0.996 |
| AlgaOld || 48.75 μs | 1.000 |
+---------++----------+-------+
from alga.
Interesting, that's an impressive speed up.
from alga.
Related Issues (20)
- How to handle goodness inherited from other libraries HOT 2
- Bump upper bound for base-compat for version 0.4 on Hackage HOT 4
- Unable to use ghcid HOT 6
- Algorithms should be in terms of typeclasses not data structures HOT 15
- Acyclic graphs with Int labels HOT 5
- Tests failed to build with QuickCheck 2.14.2
- Multitree HOT 3
- Monoid instance HOT 6
- support for GraphViz "HTML strings" for node or edge labels HOT 1
- Add benchmarks to CI HOT 2
- Supporting different node and edge types HOT 7
- v0.6 fails to build with GHC 8.0 and 8.2 HOT 3
- Doubt about decorating a Graph HOT 4
- Compatibility with mtl-2.3 HOT 2
- Smart constructor for Symbol rather than requiring -XOverloadedLists HOT 1
- Proposal : foldgM HOT 2
- Algebra.Graph.Labelled.AdjacencyMap.edges appears to be broken HOT 2
- Semigroup version of Algebra.Graph.Labelled.AdjacencyMap HOT 7
- Bump "deepseq" dependency bounds to 1.5.0.0 HOT 2
- Warnings when building with ghc-9.10
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from alga.