4
\$\begingroup\$

I have a flat data that represent the hierarchical relationship as below:

ID    Name    PID
0     A       NULL
1     B       0
2     C       0
4     D       1
5     E       1
6     F       4
3     G       0

This table represents the 'data table', where PID indicates the parent element. For example, in the first row we see that A has PID null whereas B has PID 0, which means that B’s parent is A, because 0 is the ID of A, and A is the root element, because it does not have a PID. Similarly, C has parent A because C too has PID 0, and 0 is the ID of A.

I create a class RecordHolder to represent the above table. I also implement the method processRecordHolder

public Map<String, List<String>> processRecordHolder()

The returned map uses element as keys, and holds collections of descendant nodes as values. For example, the first item in the map corresponds to element A, which has many descendants, whereas element C has no descendant. The order of members in the output is not important.

public static void main(String[] args) {

     RecordHolder dt = newRecordHolder();

     dt.addRow(0, "A", null);
     dt.addRow(1, "B", 0);
     dt.addRow(2, "C", 0);
     dt.addRow(4, "D", 1);
     dt.addRow(5, "E", 1);
     dt.addRow(6, "F", 4);
     dt.addRow(3, "G", 0);

     System.out.println("Output:");
     System.out.println(dt.processRecordHolder());
 }

Output:
{D=[F], A=[B, C, G, D, E, F], B=[D, E, F]}
or
{D=[F], E=null, F=null, G=null, A=[B, C, G, D, E, F], B=[D, E, F], C=null}

Below is my implementation of RecordHolder:

public class RecordHolder {

    private List<Record> records = new ArrayList<>();
    private Map<Integer, Integer> indexes = new HashMap<>();
    private static final int PROCESSORS = Runtime.getRuntime().availableProcessors();

    /**
     * Add new record into RecordHolder.
     * 
     * @param id
     * @param name
     * @param parentId
     */
    public void addRow(Integer id, String name, Integer parentId) {
        if (indexes.get(id) == null) {
            Record rec = new Record(id, name, parentId);
            records.add(rec);
            indexes.put(id, records.size() - 1);
        }
    }

    public List<Record> getRecords() {
       return records;
    }

    /**
     * Process RecordHolder and return a Map of all keys and its children. The
     * main algorithm here is to divide big record set into multiple parts, compute
     * on multi threads and then merge all result together.
     * 
     * @return
     */
    public Map<String, List<String>> processRecordHolder() {
       long start = System.currentTimeMillis(); 
       int size = size();

       // Step 1: Link all nodes together
       invokeOnewayTask(new LinkRecordTask(this, 0, size));

       Map<String, List<String>> map = new ConcurrentHashMap<>();

       // Step 2: Get result
       invokeOnewayTask(new BuildChildrenMapTask(this, 0, size, map));

       long elapsedTime = System.currentTimeMillis() - start;

       System.out.println("Total elapsed time: " + elapsedTime + " ms");

       return map;
    }

    /**
     * Invoke given task one way and measure the time to execute.
     * 
     * @param task
     */
    private void invokeOnewayTask(ForkJoinTask<?> task) {
        long start = System.currentTimeMillis();
        ForkJoinPool pool = new ForkJoinPool(PROCESSORS);
        pool.invoke(task);
        long elapsedTime = System.currentTimeMillis() - start;
        System.out.println(task.getClass().getSimpleName() + ":" + elapsedTime + " ms");
    }

    /**
     * Find record by id.
     * 
     * @param id
     * @return
     */
    public Record getRecordById(Integer id) {
        Integer pos = indexes.get(id);
        if (pos != null) {
            return records.get(pos);
        }
        return null;
    }

    /**
     * Find record by row number.
     * 
     * @param rownum
     * @return
     */
    public Record getRecordByRowNumber(Integer rownum) {
       return (rownum < 0 || rownum > records.size() - 1) ? null:records.get(rownum);
    }

    public int size() {
       return records.size();
    }

    /**
     * A task link between nodes
     */
    private static class LinkRecordTask extends RecursiveAction {

    private static final long serialVersionUID = 1L;
    private RecordHolder dt;
    private int start;
    private int end;
    private int limit = 100;

    public LinkRecordTask(RecordHolder dt, int start, int end) {
        this.dt = dt;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        if ((end - start) < limit) {
        for (int i = start; i < end; i++) {
            Record r = dt.records.get(i);
            Record parent = dt.getRecordById(r.parentId);
            r.parent = parent;
            if(parent != null) {
               parent.children.add(r);
            }
        }
        } else {
           int mid = (start + end) / 2;
           LinkRecordTask left = new LinkRecordTask(dt, start, mid);
           LinkRecordTask right = new LinkRecordTask(dt, mid, end);
           left.fork();
           right.fork();
           left.join();
           right.join();
        }
    }

    }

    /**
     * Build Map<String, List<String>> result from given RecordHolder.
     */
    private static class BuildChildrenMapTask extends RecursiveAction {

        private static final long serialVersionUID = 1L;
        private RecordHolder dt;
        private int start;
        private int end;
        private int limit = 100;
        private Map<String, List<String>> map;

        public BuildChildrenMapTask(RecordHolder dt, int start, int end, Map<String, List<String>> map) {
            this.dt = dt;
            this.start = start;
            this.end = end;
            this.map = map;
        }

        @Override
        protected void compute() {
            if ((end - start) < limit) {
               computeDirectly();
            } else {
                int mid = (start + end) / 2;
                BuildChildrenMapTask left = new BuildChildrenMapTask(dt, start, mid, map);
                BuildChildrenMapTask right = new BuildChildrenMapTask(dt, mid, end, map);
                left.fork();
                right.fork();
                left.join();
                right.join();
           }
        }

        private void computeDirectly() {  
            for (int i = start; i < end; i++) {
                Record rec = dt.records.get(i);
                List<String> names = new ArrayList<String>();

                loadDeeplyChildNodes(rec, names);

                if(!names.isEmpty()) {
                    map.put(rec.name, names);
                }
            }
        }

        private void loadDeeplyChildNodes(Record r, List<String> names) {
             Collection<Record> children = r.children;
             for(Record rec:children) {
                if(!names.contains(rec.name)) {
                   names.add(rec.name);
                }
                loadDeeplyChildNodes(rec, names);
             }
        }

    }

}

My Record class:

/**
 * Represents a structure of a record in RecordHolder.
 */
public class Record {

    public Integer id;
    public String name;
    public Integer parentId;
    public Record parent;
    public Collection<Record> children;

    public Record(Integer id, String name, Integer parentId) {
        this();
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }

    public Record() {
       children = Collections.newSetFromMap(new ConcurrentHashMap<Record, Boolean>())
    }

    public Collection<Record> getChildren() {
       return children;
    }

    public Record getParent() {
       return parent;
    }

    public Integer getParentId() {
       return parentId;
    }

    @Override
    public String toString() {
        return "Record{" + "id=" + id + ", name=" + name + ", parentId=" + parentId + '}';
    }

    /* (non-Javadoc)
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
       final int prime = 31;
       int result = 1;
       result = prime * result + ((id == null) ? 0 : id.hashCode());
       result = prime * result + ((name == null) ? 0 : name.hashCode());
       result = prime * result  + ((parentId == null) ? 0 : parentId.hashCode());
       return result;
    }

    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @Override
    public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj == null) {
        return false;
    }
    if (!(obj instanceof Record)) {
        return false;
    }
    Record other = (Record) obj;
    if (id == null) {
        if (other.id != null) {
        return false;
        }
    } else if (!id.equals(other.id)) {
        return false;
    }
    if (name == null) {
        if (other.name != null) {
        return false;
        }
    } else if (!name.equals(other.name)) {
        return false;
    }
    if (parentId == null) {
        if (other.parentId != null) {
        return false;
        }
    } else if (!parentId.equals(other.parentId)) {
        return false;
    }
    return true;
    }    
}

The algorithm is like this:

  • Link all parent and child of each record
  • Build the map

On each step I apply fork join to divide the dataset into smaller parts and run in parallel. How can we simplify this algorithm?

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Don't do half the job if you can do it all

        protected void compute() {
            if ((end - start) < limit) {
               computeDirectly();
            } else {
                int mid = (start + end) / 2;
                BuildChildrenMapTask left = new BuildChildrenMapTask(dt, start, mid, map);
                BuildChildrenMapTask right = new BuildChildrenMapTask(dt, mid, end, map);
                left.fork();
                right.fork();
                left.join();
                right.join();
           }
        }

You recursively divide the task in half until it is small enough to be under the limit. Why? You know the total size and the limit from the beginning.

        protected void compute() {
            if ((end - start) < limit) {
               computeDirectly();
            } else {
                List<BuildChildrenTask> subtasks = new ArrayList<>();

                for (int current = start; current < end; current += limit - 1) {
                    BuildChildrenMapTask subtask = new BuildChildrenMapTask(dt, current, Math.min(current + limit - 1, end), map));
                    subtask.fork();
                    subtasks.add(subtask);
                }

                for (BuildChildrenMapTask subtask : subtasks) {
                    subtask.join();
                }
            }
        }

Note that the new ArrayList<>() notation requires newer versions of Java. Stick to your original notation if you're actually using an older version that requires it.

For large ranges, this will do far fewer forks and joins. Consider the case where start is 0 and end equals 16 * limit.

  1. 2 of 8 * limit
  2. 4 of 4 * limit
  3. 8 of 2 * limit
  4. 16 of limit
  5. 32 of limit / 2

So that's 62 forks and joins total in the original code. In this code, it will do 17. That's an extreme case, but it illustrates the principle.

Use a Set to hold a list of unique elements

                if(!names.contains(rec.name)) {
                   names.add(rec.name);
                }

In this case, names is a List, particularly an ArrayList. To do a contains on a List, you have to do a scan which takes linear time. If you change this to a Set implemented as a HashSet, then you can do this in constant time.

               names.add(rec.name);

You don't have to do the contains at all, since a Set does this implicitly.

Note that you also have to change things like

        public BuildChildrenMapTask(RecordHolder dt, int start, int end, Map<String, List<String>> map) {

to something like

        public BuildChildrenMapTask(RecordHolder dt, int start, int end, Map<String, Set<String>> map) {

and

                List<String> names = new ArrayList<String>();

to

                Set<String> names = new HashSet<>();

Reuse when you can

You call

                loadDeeplyChildNodes(rec, names);

every time, but you should only need to calculate this once per record. The rest of the time, you should be able to use the already calculated value. Something like

        private Set<String> getDescendants(Record r) {
            Set<String> names = new HashSet<>();
            for (Record rec : r.children) {
                Set<String> descendants = map.get(rec.name);
                if (descendants == null) {
                    descendants = getDescendants(rec);
                    map.put(rec.name, descendants);
                }

                names.addAll(descendants);
            }

            return names;
        }

Note that I renamed loadDeeplyChildNodes to getDescendants as more in tune with what the revised method does.

Also in computeDirectly change

                List<String> names = new ArrayList<String>();

                loadDeeplyChildNodes(rec, names);

                if(!names.isEmpty()) {
                    map.put(rec.name, names);
                }

to

                if (!map.containsKey(rec.name)) {
                    map.put(rec.name, getDescendants(rec));
                }

If you really need to output null, you could iterate over your map afterwards and replace all the empty entries. But I would actually prefer to see the empty lists there as better reflecting what you are saying.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your suggestion. When I tried with your suggestion, it doesn't work. My output is all coming as empty but earlier it used to work. Any thoughts why is it so? \$\endgroup\$
    – david
    Commented Jun 11, 2015 at 19:45
3
\$\begingroup\$

I think what you're missing here is an algorithmic change to improve the way you load data, ranter than the way you compute the results.

One way to do this would be to build a tree to store your Records. A tree is really not that complicated to do, but, there's an in-between thing you can do which will really help.

Create a Map<Integer,List<Integer>> as part of the constructor of your class. Call it tree for want of a better name. Then, each time you add a record, ensure that the tree is modified as well. Here's your current method:

public void addRow(Integer id, String name, Integer parentId) {
    if (indexes.get(id) == null) {
        Record rec = new Record(id, name, parentId);
        records.add(rec);
        indexes.put(id, records.size() - 1);
    }
}

If we change that to be:

private final Map<Integer, List<Integer>> tree = new HashMap<>();

public void addRow(Integer id, String name, Integer parentId) {
    if (indexes.get(id) == null) {
        Record rec = new Record(id, name, parentId);

        records.add(rec);
        indexes.put(id, records.size() - 1);

        // Special note here!!!
        tree.put(id, new ArrayList<>());
        if (parentId != null) {
            tree.get(parentId).add(Id);
        }

    }
}

Note how we simply add the data to the tree structure. The special note I have there is that the above code only supports input data where the parentID is always added before any child Id's that use that parent. If the data comes in a different order, it will fail with a NullPointerException. There are ways to alter the code to create a "phantom" record for parents that have not been added before, though. Since your example data is compatible with my suggestion, though, I'll leave that up to you.

Now, once you have that tree structure right, the way to get all the descendents of a node, is simple:

List<Integer> children = new ArrayList<>();
children.addAll(tree.get(id));
for (int i = 0; i < children.size(); i++) {
    children.addAll(tree.get(children.get(i)));
}

That style of loop is needed because we modify the children List while iterating over it (so the children.size() keeps on increasing).

I hope that gives you some ideas.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.