Performance improvement for suggestion bolding.
The amount of time spend inside LevenshteinSuggestionFormatter.formatSuggestion is reduced from 72ms to 44ms when runnig the tests. The number of memory allocations is also reduced.
Bug: 2836498
Change-Id: I97826e2499b4647812c58e762336a807f034f1ee
diff --git a/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java b/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java
index c7c5ead..821b6e6 100644
--- a/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java
+++ b/src/com/android/quicksearchbox/LevenshteinSuggestionFormatter.java
@@ -24,7 +24,6 @@
import android.util.Log;
import java.util.ArrayList;
-import java.util.List;
/**
* Suggestion formatter using the Levenshtein distance (minumum edit distance) to calculate the
@@ -42,24 +41,26 @@
public Spanned formatSuggestion(CharSequence query, CharSequence suggestion) {
if (DBG) Log.d(TAG, "formatSuggestion('" + query + "', '" + suggestion + "')");
query = normalizeQuery(query);
- List<Token> queryTokens = tokenize(query);
- List<Token> suggestionTokens = tokenize(suggestion);
- int[] matches = findMatches(queryTokens, suggestionTokens);
+ final Token[] queryTokens = tokenize(query);
+ final Token[] suggestionTokens = tokenize(suggestion);
+ final int[] matches = findMatches(queryTokens, suggestionTokens);
if (DBG){
Log.d(TAG, "source = " + queryTokens);
Log.d(TAG, "target = " + suggestionTokens);
Log.d(TAG, "matches = " + matches);
}
- SpannableString str = new SpannableString(suggestion);
+ final SpannableString str = new SpannableString(suggestion);
- for (int i = 0; i < matches.length; ++i) {
- Token t = suggestionTokens.get(i);
+ final int matchesLen = matches.length;
+ for (int i = 0; i < matchesLen; ++i) {
+ final Token t = suggestionTokens[i];
int sourceLen = 0;
- if (matches[i] >= 0) {
- sourceLen = queryTokens.get(matches[i]).getLength();
+ int thisMatch = matches[i];
+ if (thisMatch >= 0) {
+ sourceLen = queryTokens[thisMatch].length();
}
- applySuggestedTextStyle(str, t.getStart() + sourceLen, t.getEnd());
- applyQueryTextStyle(str, t.getStart(), t.getStart() + sourceLen);
+ applySuggestedTextStyle(str, t.mStart + sourceLen, t.mEnd);
+ applyQueryTextStyle(str, t.mStart, t.mStart + sourceLen);
}
return str;
@@ -79,17 +80,18 @@
* the target token i does not match any source token.
*/
@VisibleForTesting
- int[] findMatches(List<Token> source, List<Token> target) {
- LevenshteinDistance<Token> table = new LevenshteinDistance<Token>(source, target) {
+ int[] findMatches(Token[] source, Token[] target) {
+ final LevenshteinDistance<Token> table = new LevenshteinDistance<Token>(source, target) {
@Override
- protected boolean match(Token source, Token target) {
+ protected boolean match(final Token source, final Token target) {
return source.prefixOf(target);
}
};
table.calculate();
- int[] result = new int[target.size()];
+ final int targetLen = target.length;
+ final int[] result = new int[targetLen];
LevenshteinDistance.EditOperation[] ops = table.getTargetOperations();
- for (int i = 0; i < result.length; ++i) {
+ for (int i = 0; i < targetLen; ++i) {
if (ops[i].getType() == LevenshteinDistance.EDIT_UNCHANGED) {
result[i] = ops[i].getPosition();
} else {
@@ -100,61 +102,72 @@
}
@VisibleForTesting
- List<Token> tokenize(CharSequence seq) {
+ Token[] tokenize(final CharSequence seq) {
int pos = 0;
+ final int len = seq.length();
+ final char[] chars = new char[len];
+ seq.toString().getChars(0, len, chars, 0);
ArrayList<Token> tokens = new ArrayList<Token>();
- while (pos < seq.length()) {
- while (pos < seq.length() && Character.isWhitespace(seq.charAt(pos))) {
+ while (pos < len) {
+ while (pos < len && Character.isWhitespace((int) seq.charAt(pos))) {
pos++;
}
int start = pos;
- while (pos < seq.length() && !Character.isWhitespace(seq.charAt(pos))) {
+ while (pos < len && !Character.isWhitespace((int) seq.charAt(pos))) {
pos++;
}
int end = pos;
if (start != end) {
- Token t = new Token(seq, start, end);
+ Token t = new Token(chars, start, end);
tokens.add(t);
}
}
- return tokens;
+ return tokens.toArray(new Token[tokens.size()]);
}
@VisibleForTesting
- static class Token {
- private final CharSequence mContainer;
- private final int mStart;
- private final int mEnd;
+ static class Token implements CharSequence {
+ private final char[] mContainer;
+ public final int mStart;
+ public final int mEnd;
- public Token(CharSequence container, int start, int end) {
+ public Token(char[] container, int start, int end) {
mContainer = container;
mStart = start;
mEnd = end;
}
- public int getStart() {
- return mStart;
- }
-
- public int getEnd() {
- return mEnd;
- }
-
- public int getLength() {
+ public int length() {
return mEnd - mStart;
}
@Override
public String toString() {
- return getSequence().toString();
+ // used in tests only.
+ return subSequence(0, length());
}
- public CharSequence getSequence() {
- return mContainer.subSequence(mStart, mEnd);
+ public boolean prefixOf(final Token that) {
+ final int len = length();
+ if (len > that.length()) return false;
+ final int thisStart = mStart;
+ final int thatStart = that.mStart;
+ final char[] thisContainer = mContainer;
+ final char[] thatContainer = that.mContainer;
+ for (int i = 0; i < len; ++i) {
+ if (thisContainer[thisStart + i] != thatContainer[thatStart + i]) {
+ return false;
+ }
+ }
+ return true;
}
- public boolean prefixOf(Token that) {
- return that.toString().startsWith(toString());
+ public char charAt(int index) {
+ return mContainer[index + mStart];
+ }
+
+ public String subSequence(int start, int end) {
+ return new String(mContainer, mStart + start, length());
}
}
diff --git a/src/com/android/quicksearchbox/util/LevenshteinDistance.java b/src/com/android/quicksearchbox/util/LevenshteinDistance.java
index f5b99ec..3e61cf0 100644
--- a/src/com/android/quicksearchbox/util/LevenshteinDistance.java
+++ b/src/com/android/quicksearchbox/util/LevenshteinDistance.java
@@ -16,7 +16,6 @@
package com.android.quicksearchbox.util;
-import java.util.List;
/**
* This class represents the matrix used in the Levenshtein distance algorithm, together
@@ -32,21 +31,30 @@
public static final int EDIT_REPLACE = 2;
public static final int EDIT_UNCHANGED = 3;
- private final List<T> mSource;
- private final List<T> mTarget;
- private final Entry[][] mTable;
+ private final T[] mSource;
+ private final T[] mTarget;
+ private final int[][] mEditTypeTable;
+ private final int[][] mDistanceTable;
- public LevenshteinDistance(List<T> source, List<T> target) {
- mTable = new Entry[source.size()+1][target.size()+1];
+ public LevenshteinDistance(T[] source, T[] target) {
+ final int sourceSize = source.length;
+ final int targetSize = target.length;
+ final int[][] editTab = new int[sourceSize+1][targetSize+1];
+ final int[][] distTab = new int[sourceSize+1][targetSize+1];
+ editTab[0][0] = EDIT_UNCHANGED;
+ distTab[0][0] = 0;
+ for (int i = 1; i <= sourceSize; ++i) {
+ editTab[i][0] = EDIT_DELETE;
+ distTab[i][0] = i;
+ }
+ for (int i = 1; i <= targetSize; ++i) {
+ editTab[0][i] = EDIT_INSERT;
+ distTab[0][i] = i;
+ }
+ mEditTypeTable = editTab;
+ mDistanceTable = distTab;
mSource = source;
mTarget = target;
- set(0, 0, EDIT_UNCHANGED, 0);
- for (int i = 1; i <= source.size(); ++i) {
- set(i, 0, EDIT_DELETE, i);
- }
- for (int i = 1; i <= target.size(); ++i) {
- set(0, i, EDIT_INSERT, i);
- }
}
/**
@@ -64,31 +72,37 @@
* @return The Levenshtein distance.
*/
public int calculate() {
- for (int s = 1; s <= mSource.size(); ++s) {
- T sourceToken = mSource.get(s-1);
- for (int t = 1; t <= mTarget.size(); ++t) {
- T targetToken = mTarget.get(t-1);
+ final T[] src = mSource;
+ final T[] trg = mTarget;
+ final int sourceLen = src.length;
+ final int targetLen = trg.length;
+ final int[][] distTab = mDistanceTable;
+ final int[][] editTab = mEditTypeTable;
+ for (int s = 1; s <= sourceLen; ++s) {
+ T sourceToken = src[s-1];
+ for (int t = 1; t <= targetLen; ++t) {
+ T targetToken = trg[t-1];
int cost = match(sourceToken, targetToken) ? 0 : 1;
- Entry e = get(s - 1, t);
- int distance = e.getDistance() + 1;
+ int distance = distTab[s-1][t] + 1;
int type = EDIT_DELETE;
- e = get(s, t - 1);
- if (e.getDistance() + 1 < distance ) {
- distance = e.getDistance() + 1;
+ int d = distTab[s][t - 1];
+ if (d + 1 < distance ) {
+ distance = d + 1;
type = EDIT_INSERT;
}
- e = get(s - 1, t - 1);
- if (e.getDistance() + cost < distance) {
- distance = e.getDistance() + cost;
+ d = distTab[s - 1][t - 1];
+ if (d + cost < distance) {
+ distance = d + cost;
type = cost == 0 ? EDIT_UNCHANGED : EDIT_REPLACE;
}
- set(s, t, type, distance);
+ distTab[s][t] = distance;
+ editTab[s][t] = type;
}
}
- return get(mSource.size(), mTarget.size()).getDistance();
+ return distTab[sourceLen][targetLen];
}
/**
@@ -100,12 +114,13 @@
* token was inserted.
*/
public EditOperation[] getTargetOperations() {
- EditOperation[] ops = new EditOperation[mTarget.size()];
- int targetPos = mTarget.size();
- int sourcePos = mSource.size();
+ final int trgLen = mTarget.length;
+ final EditOperation[] ops = new EditOperation[trgLen];
+ int targetPos = trgLen;
+ int sourcePos = mSource.length;
+ final int[][] editTab = mEditTypeTable;
while (targetPos > 0) {
- Entry e = get(sourcePos, targetPos);
- int editType = e.getEditType();
+ int editType = editTab[sourcePos][targetPos];
switch (editType) {
case LevenshteinDistance.EDIT_DELETE:
sourcePos--;
@@ -126,34 +141,6 @@
return ops;
}
- private void set(int sourceIdx, int targetIdx, int editType, int distance) {
- mTable[sourceIdx][targetIdx] = new Entry(editType, distance);
- }
-
- private Entry get(int sourceIdx, int targetIdx) {
- Entry e = mTable[sourceIdx][targetIdx];
- if (e == null) {
- throw new NullPointerException("No entry at " + sourceIdx + "," + targetIdx +
- "; size: " + (mSource.size() + 1) + "," + (mTarget.size() + 1));
- }
- return e;
- }
-
- private static class Entry {
- private final int mEditType;
- private final int mDistance;
- public Entry(int editType, int distance) {
- mEditType = editType;
- mDistance = distance;
- }
- public int getDistance() {
- return mDistance;
- }
- public int getEditType() {
- return mEditType;
- }
- }
-
public static class EditOperation {
private final int mType;
private final int mPosition;
diff --git a/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java b/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java
index c39e13b..30035ff 100644
--- a/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java
+++ b/tests/src/com/android/quicksearchbox/LevenshteinFormatterTest.java
@@ -21,8 +21,6 @@
import android.test.AndroidTestCase;
import android.text.Spanned;
-import java.util.List;
-
/**
* Tests for {@link LevenshteinSuggestionFormatter}.
*/
@@ -40,10 +38,10 @@
}
private void verifyTokenizeResult(String input, String... output) {
- List<LevenshteinSuggestionFormatter.Token> tokens = mFormatter.tokenize(input);
- assertEquals(output.length, tokens.size());
+ LevenshteinSuggestionFormatter.Token[] tokens = mFormatter.tokenize(input);
+ assertEquals(output.length, tokens.length);
for (int i=0; i<output.length; ++i) {
- assertEquals(output[i], tokens.get(i).toString());
+ assertEquals(output[i], tokens[i].toString());
}
}
@@ -90,18 +88,18 @@
}
private void verifyFindMatches(String source, String target, String... newTokensInTarget) {
- List<LevenshteinSuggestionFormatter.Token> sourceTokens = mFormatter.tokenize(source);
- List<LevenshteinSuggestionFormatter.Token> targetTokens = mFormatter.tokenize(target);
+ LevenshteinSuggestionFormatter.Token[] sourceTokens = mFormatter.tokenize(source);
+ LevenshteinSuggestionFormatter.Token[] targetTokens = mFormatter.tokenize(target);
int[] matches = mFormatter.findMatches(sourceTokens, targetTokens);
- assertEquals(targetTokens.size(), matches.length);
+ assertEquals(targetTokens.length, matches.length);
int newTokenCount = 0;
int lastSourceToken = -1;
- for (int i=0; i<targetTokens.size(); ++i) {
+ for (int i=0; i<targetTokens.length; ++i) {
int sourceIdx = matches[i];
if (sourceIdx < 0) {
- String targetToken = targetTokens.get(i).toString();
+ String targetToken = targetTokens[i].toString();
assertTrue("Unexpected new token '" + targetToken + "'",
newTokenCount < newTokensInTarget.length);
@@ -109,8 +107,8 @@
++newTokenCount;
} else {
assertTrue("Source token out of order", lastSourceToken < sourceIdx);
- LevenshteinSuggestionFormatter.Token srcToken = sourceTokens.get(sourceIdx);
- LevenshteinSuggestionFormatter.Token trgToken = targetTokens.get(i);
+ LevenshteinSuggestionFormatter.Token srcToken = sourceTokens[sourceIdx];
+ LevenshteinSuggestionFormatter.Token trgToken = targetTokens[i];
assertTrue("'" + srcToken + "' is not a prefix of '" + trgToken + "'",
srcToken.prefixOf(trgToken));
lastSourceToken = sourceIdx;
diff --git a/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java b/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java
index d1fa700..282896e 100644
--- a/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java
+++ b/tests/src/com/android/quicksearchbox/util/LevenshteinDistanceTest.java
@@ -20,8 +20,6 @@
import android.test.AndroidTestCase;
-import java.util.Arrays;
-
/**
* Tests for class {@link LevenshteinDistance}.
*/
@@ -36,8 +34,7 @@
int expectedDistance) {
assertEquals("test error", target.length, expectedOps.length);
- LevenshteinDistance<String> distance = new LevenshteinDistance<String>
- (Arrays.asList(source), Arrays.asList(target)){
+ LevenshteinDistance<String> distance = new LevenshteinDistance<String>(source, target){
@Override
protected boolean match(String source, String target) {
return source.equals(target);
