More optimizations
We don't merge tails anyway, and we can't do it any more
because that would break the bigram lookup algorithm.
The speedup is about 20%, and possibly double this if
there are no bigrams.
Bug: 6394357
Change-Id: I9eec11dda9000451706d280f120404a2acbea304
diff --git a/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java b/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java
index 3c818cc..bb10423 100644
--- a/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java
+++ b/java/src/com/android/inputmethod/latin/makedict/BinaryDictInputOutput.java
@@ -489,10 +489,17 @@
// Merging tails can only be done if there are no attributes. Searching for attributes
// in LatinIME code depends on a total breadth-first ordering, which merging tails
// breaks. If there are no attributes, it should be fine (and reduce the file size)
- // to merge tails, and the following step would be necessary.
- // If eventually the code runs on Android, searching through the whole array each time
- // may be a performance concern.
- list.remove(node);
+ // to merge tails, and removing the node from the list would be necessary. However,
+ // we don't merge tails because breaking the breadth-first ordering would result in
+ // extreme overhead at bigram lookup time (it would make the search function O(n) instead
+ // of the current O(log(n)), where n=number of nodes in the dictionary which is pretty
+ // high).
+ // If no nodes are ever merged, we can't have the same node twice in the list, hence
+ // searching for duplicates in unnecessary. It is also very performance consuming,
+ // since `list' is an ArrayList so it's an O(n) operation that runs on all nodes, making
+ // this simple list.remove operation O(n*n) overall. On Android this overhead is very
+ // high.
+ // For future reference, the code to remove duplicate is a simple : list.remove(node);
list.add(node);
final ArrayList<CharGroup> branches = node.mData;
final int nodeSize = branches.size();