You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by br...@apache.org on 2020/01/13 10:36:58 UTC
[lucene-solr] branch branch_8x updated: LUCENE-9125: Optimize
Automaton.step() with binary search and introduce Automaton.next().
This is an automated email from the ASF dual-hosted git repository.
broustant pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
The following commit(s) were added to refs/heads/branch_8x by this push:
new eb84c04 LUCENE-9125: Optimize Automaton.step() with binary search and introduce Automaton.next().
eb84c04 is described below
commit eb84c04052eef7ab6ebe187c421a4d870f318c41
Author: Bruno Roustant <br...@salesforce.com>
AuthorDate: Mon Jan 13 11:11:35 2020 +0100
LUCENE-9125: Optimize Automaton.step() with binary search and introduce Automaton.next().
---
lucene/CHANGES.txt | 2 +
.../apache/lucene/util/automaton/Automaton.java | 79 ++++++++++++++++++----
.../util/automaton/MinimizationOperations.java | 5 +-
.../apache/lucene/util/automaton/RunAutomaton.java | 5 +-
4 files changed, 77 insertions(+), 14 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 449a893..92648c4 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -42,6 +42,8 @@ Optimizations
* LUCENE-9113: Faster merging of SORTED/SORTED_SET doc values. (Adrien Grand)
+* LUCENE-9125: Optimize Automaton.step() with binary search and introduce Automaton.next(). (Bruno Roustant)
+
Bug Fixes
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java b/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
index 3006940..2758b16 100644
--- a/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
+++ b/lucene/core/src/java/org/apache/lucene/util/automaton/Automaton.java
@@ -656,22 +656,77 @@ public class Automaton implements Accountable {
* @return destination state, -1 if no matching outgoing transition
*/
public int step(int state, int label) {
+ return next(state, 0, label, null);
+ }
+
+ /**
+ * Looks for the next transition that matches the provided label, assuming determinism.
+ * <p>
+ * This method is similar to {@link #step(int, int)} but is used more efficiently
+ * when iterating over multiple transitions from the same source state. It keeps
+ * the latest reached transition index in {@code transition.transitionUpto} so
+ * the next call to this method can continue from there instead of restarting
+ * from the first transition.
+ *
+ * @param transition The transition to start the lookup from (inclusive, using its
+ * {@link Transition#source} and {@link Transition#transitionUpto}).
+ * It is updated with the matched transition;
+ * or with {@link Transition#dest} = -1 if no match.
+ * @param label The codepoint to look up.
+ * @return The destination state; or -1 if no matching outgoing transition.
+ */
+ public int next(Transition transition, int label) {
+ return next(transition.source, transition.transitionUpto, label, transition);
+ }
+
+ /**
+ * Looks for the next transition that matches the provided label, assuming determinism.
+ *
+ * @param state The source state.
+ * @param fromTransitionIndex The transition index to start the lookup from (inclusive); negative interpreted as 0.
+ * @param label The codepoint to look up.
+ * @param transition The output transition to update with the matching transition; or null for no update.
+ * @return The destination state; or -1 if no matching outgoing transition.
+ */
+ private int next(int state, int fromTransitionIndex, int label, Transition transition) {
assert state >= 0;
assert label >= 0;
- int trans = states[2*state];
- int limit = trans + 3*states[2*state+1];
- // TODO: we could do bin search; transitions are sorted
- while (trans < limit) {
- int dest = transitions[trans];
- int min = transitions[trans+1];
- int max = transitions[trans+2];
- if (min <= label && label <= max) {
- return dest;
+ int stateIndex = 2 * state;
+ int firstTransitionIndex = states[stateIndex];
+ int numTransitions = states[stateIndex + 1];
+
+ // Since transitions are sorted,
+ // binary search the transition for which label is within [minLabel, maxLabel].
+ int low = Math.max(fromTransitionIndex, 0);
+ int high = numTransitions - 1;
+ while (low <= high) {
+ int mid = (low + high) >>> 1;
+ int transitionIndex = firstTransitionIndex + 3 * mid;
+ int minLabel = transitions[transitionIndex + 1];
+ if (minLabel > label) {
+ high = mid - 1;
+ } else {
+ int maxLabel = transitions[transitionIndex + 2];
+ if (maxLabel < label){
+ low = mid + 1;
+ } else {
+ int destState = transitions[transitionIndex];
+ if (transition != null) {
+ transition.dest = destState;
+ transition.min = minLabel;
+ transition.max = maxLabel;
+ transition.transitionUpto = mid;
+ }
+ return destState;
+ }
}
- trans += 3;
}
-
- return -1;
+ int destState = -1;
+ if (transition != null) {
+ transition.dest = destState;
+ transition.transitionUpto = low;
+ }
+ return destState;
}
/** Records new states and transitions and then {@link
diff --git a/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java b/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
index 979f7c5..1962731 100644
--- a/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
+++ b/lucene/core/src/java/org/apache/lucene/util/automaton/MinimizationOperations.java
@@ -94,12 +94,15 @@ final public class MinimizationOperations {
}
}
// find initial partition and reverse edges
+ Transition transition = new Transition();
for (int q = 0; q < statesLen; q++) {
final int j = a.isAccept(q) ? 0 : 1;
partition[j].add(q);
block[q] = j;
+ transition.source = q;
+ transition.transitionUpto = -1;
for (int x = 0; x < sigmaLen; x++) {
- final ArrayList<Integer>[] r = reverse[a.step(q, sigma[x])];
+ final ArrayList<Integer>[] r = reverse[a.next(transition, sigma[x])];
if (r[x] == null) {
r[x] = new ArrayList<>();
}
diff --git a/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java b/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
index a425887..e105ac3 100644
--- a/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
+++ b/lucene/core/src/java/org/apache/lucene/util/automaton/RunAutomaton.java
@@ -78,10 +78,13 @@ public abstract class RunAutomaton implements Accountable {
accept = new boolean[size];
transitions = new int[size * points.length];
Arrays.fill(transitions, -1);
+ Transition transition = new Transition();
for (int n=0;n<size;n++) {
accept[n] = a.isAccept(n);
+ transition.source = n;
+ transition.transitionUpto = -1;
for (int c = 0; c < points.length; c++) {
- int dest = a.step(n, points[c]);
+ int dest = a.next(transition, points[c]);
assert dest == -1 || dest < size;
transitions[n * points.length + c] = dest;
}