[
https://issues.apache.org/jira/browse/HADOOP-12185?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14614420#comment-14614420
]
Inigo Goiri commented on HADOOP-12185:
--------------------------------------
I've implemented it with only Map and there is one operation that gets much
more expensive: chooseRandom(). Right now, picking a random node is done
selecting a random index in the list of children which is O(k); however, the
same operation is O(n) for HashMap. I thought about using TreeMap or
LinkedHashMap but both of them have the same issue to some degree.
Given that chooseRandom() is one of the most commonly used operations (e.g.,
block placement in HDFS), I would stick to the addition of the auxiliary map.
To speedup chooseRamdom (which uses indexOf heavily) we can replace my proposed
HashMap<String,Node> by HashMap<String,Integer>. I'm going to do some
performance analysis to see what's better.
> NetworkTopology is not efficient adding/getting/removing nodes
> --------------------------------------------------------------
>
> Key: HADOOP-12185
> URL: https://issues.apache.org/jira/browse/HADOOP-12185
> Project: Hadoop Common
> Issue Type: Improvement
> Affects Versions: 2.7.0
> Reporter: Inigo Goiri
> Assignee: Inigo Goiri
> Attachments: HADOOP-12185-1.patch
>
>
> NetworkToplogy uses nodes with a list of children. The access to these
> children is slow as it's a linear search.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
