[jira] [Resolved] (GIRAPH-243) EdgeListVertex performance is sub-optimal

["Alessandro Presta (JIRA)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/GIRAPH-243?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Alessandro Presta resolved GIRAPH-243.
--------------------------------------

    Resolution: Fixed

Fix included in GIRAPH-244
                
> EdgeListVertex performance is sub-optimal
> -----------------------------------------
>
>                 Key: GIRAPH-243
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-243
>             Project: Giraph
>          Issue Type: Improvement
>          Components: graph
>            Reporter: Alessandro Presta
>            Assignee: Alessandro Presta
>
> Iterating over outgoing edges (both vertex id and value) in an EdgeListVertex is O(n log n): you have to iterate over getOutEdgesIterator and call getEdgeValue (which is logarithmic) at each iteration.
> If we store the edge list as a list of Edge<I, E> (instead of the current two lists), iteration becomes linear time (which I think is what most people expect from an adjacency-list representation).
> Furthermore, I think we can avoid sorting the list by ID: addEdge and removeEdge are currently linear-time because we are using an ArrayList, so the binary search doesn't help much. If we don't sort, at least addEdge becomes amortized constant-time.
> This improvement would require an API change: getOutEdgesIterator should iterate over Edge<I, E> as opposed to just I.
> What I propose is to have both iterators (the current one could be called getNeighborsIterator), with a default implementation of the neighbors iterator in terms of the edges iterator, and optimizations left to implementors (e.g. IntIntNullIntVertex).

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira