|
From: H.N. de R. <hnr...@gr...> - 2016-04-09 18:31:07
|
On Fri, Apr 08, 2016 at 02:36:37AM -0700, John Sichi wrote:
> Regarding short-lived VertexPairs: long ago I learned to stop worrying and
> love the Eden approach of the garbage collector. Think about how many
> iterators are created and forgotten during a typical algorithm execution...
But iterators typically are used more than once, here the new pair is used
only for a single hash lookup.
Several years ago I ran into the same performance issue with JgraphT and as a
quick hack created a wrapper class like this (and then forget about it until
this discussion):
public class CacheGraph<V,E> extends ListenableDirectedGraph<V,E>
implements GraphListener<V,E> {
private DirectedGraph<V,E> graph; /** The graph we're caching */
private HashMap<V,V> nodeCache;
private HashMap<Pair,E> edgeCache;
private Pair reusablePair; /** For looking up edges */
The rest of the class is about as you'd expect. Note that Pair, different from
org.jgrapht.util.VertexPair, is modifiable. I used this class to time the
impact of allocating a new Pair() when performing an edge lookup and in my
application it adds about 9% to the running time. And this is when there is no
shortage of memory. When there is, the shit can really hit the fan. So I
suggest using a reusable pair object and not reallocating one for every test.
Regards,
Ernst
>
> On Wed, Apr 6, 2016 at 4:18 PM, Joris Kinable <de...@gm...> wrote:
>
> > John,
> >
> > If I understand you correct, you would propose to do the following:
> > To the Specifics class, you would add:
> > Map<VertexPair<V,V>,Set<E>> vertexPairToEdgeMap=....;
> >
> > Then in DirectedSpecifics.addEdgeToTouchingVertices(E e) you would *add*:
> > VertexPair<V,V> pair=new VertexPair<>(source, target);
> > if(!vertexPairToEdgeMap.containsKey(pair)) vertexPairToEdgeMap.put(pair,
> > new LinkedHashSet<>());
> > vertexPairToEdgeMap.get(pair).put(e);
> >
> > And then the current DirectedSpecifics.getEdge(V source, V target) would
> > be *replaced* by:
> > VertexPair<V,V> pair=new VertexPair<>(source, target);
> > if(!vertexPairToEdgeMap.containsKey(pair) ||
> > vertexPairToEdgeMap.get(pair).isEmpty()) return null;
> > else return vertexPairToEdgeMap.get(pair).iterator().next();
> >
> > This would be possible, but then the SimpleIdentityDirectedGraphTest would
> > fail. (In this test, the Vertex objects are changed *after* they are
> > created and added to graph, so an IdentityHashMap is required, see the test
> > for details). I'm not sure how to resolve this. An application can indeed
> > override createDirectedSpecifics, but both Specifics and
> > DirectedSpecifics are resp. private and protected, so you cannot provide a
> > custom DirectedSpecifics implementation which avoid this issue.
> >
> > Also, would the frequent construction of short-lived VertexPair objects
> > not be an issue, i.e. a new VertexPair would be created each time getEdge(V
> > source, V target) is invoked.
> >
> > Joris
> >
> > On Wed, Apr 6, 2016 at 5:25 PM, John Sichi <js...@gm...> wrote:
> >
> >> Per the last option mentioned by Joris, I don't think any equals/hashCode
> >> override is required for any object.
> >>
> >> My preference is a hybrid of his second and third options.
> >>
> >> We would add an additional graph-level map inside of Specifics (not
> >> vertex-level inside of EdgeContainer), where the key is VertexPair, and the
> >> value is Edge (or Set<Edge> for multigraphs). When adding an edge, we add
> >> a corresponding entry. When removing an edge, we remove the entry (or
> >> remove the edge from the set for multigraphs, deleting the entry once the
> >> set is empty). This allows us to optimize both containsEdge and getEdge
> >> (which is slightly different depending on directed vs undirected).
> >>
> >> The default implementation would be this new indexing. If an application
> >> wants to revert to the old approach to save memory, this would be possible
> >> by overriding the createDirectedSpecifics and createUndirectedSpecifics
> >> methods.
> >>
> >>
> >> On Wed, Apr 6, 2016 at 2:01 PM, Rushang Karia <rus...@ho...>
> >> wrote:
> >>
> >>>
> >>> Wouldn't this be solved by checking for references as well in addition
> >>> to the equals()?
> >>>
> >>> ----- Reply message -----
> >>> From: "Aidan Delaney" <ai...@on...>
> >>> To: "jgr...@li..." <
> >>> jgr...@li...>
> >>> Subject: [jgrapht-users] some potential speed improvements for
> >>> containsEdge(u, v) and getEdge(u, v)
> >>> Date: Wed, Apr 6, 2016 01:33
> >>>
> >>>
> >>> Dear all,
> >>> As far as I recall (and I'm happy to be wrong) overriding hash code for
> >>> Edge leads to Bad Things (tm). JGraphT is a general graph
> >>> implementation. As such, it doesn't assume that you're graph is not a
> >>> multigraph.
> >>> In the JGraphT implementation, if we add edge e between vertex
> >>> v1 and v2 we -- unsurprisingly -- have an edge between v1 and v2. If I
> >>> create another edge, e', which is between v1 and v2 and identical to e
> >>> in all other respects, then my graph has two edges, e and e', between
> >>> v1 and v2. By overriding hashCode, e and e' would be equal edges and
> >>> you'd only have one edge between v1 and v2.
> >>> I hope the above helps. I'll read it again after my first
> >>> coffee to see if it's actually intelligible.
> >>>
> >>> --
> >>> Dr Aidan Delaney
> >>> Principal Lecturer
> >>> Computing, Engineering & Maths
> >>> University of Brighton
> >>>
> >>> @aidandelaney
> >>>
--
Information System on Graph Classes and their Inclusions (ISGCI)
http://www.graphclasses.org
|
