You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@uima.apache.org by sc...@apache.org on 2013/11/07 19:40:33 UTC
svn commit: r1539756 - in
/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima:
cas/impl/FSBagIndex.java cas/impl/FSVectorIndex.java
internal/util/IntVector.java
Author: schor
Date: Thu Nov 7 18:40:33 2013
New Revision: 1539756
URL: http://svn.apache.org/r1539756
Log:
[UIMA-3413] add a faster indexOf method, call it from the Bag Index. (FSVectorIndex I think is no longer used)
Modified:
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSBagIndex.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSVectorIndex.java
uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntVector.java
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSBagIndex.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSBagIndex.java?rev=1539756&r1=1539755&r2=1539756&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSBagIndex.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSBagIndex.java Thu Nov 7 18:40:33 2013
@@ -332,15 +332,11 @@ public class FSBagIndex extends FSLeafIn
* @see org.apache.uima.cas.impl.FSLeafIndexImpl#deleteFS(org.apache.uima.cas.FeatureStructure)
*/
public void deleteFS(FeatureStructure fs) {
- final int addr = ((FeatureStructureImpl) fs).getAddress();
- final int pos = this.index.indexOf(addr);
- if (pos >= 0) {
- this.index.remove(pos);
- }
+ remove( ((FeatureStructureImpl) fs).getAddress());
}
public void remove(int fsRef) {
- final int pos = this.index.indexOf(fsRef);
+ final int pos = this.index.indexOfOptimizeAscending(fsRef);
if (pos >= 0) {
this.index.remove(pos);
}
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSVectorIndex.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSVectorIndex.java?rev=1539756&r1=1539755&r2=1539756&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSVectorIndex.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/cas/impl/FSVectorIndex.java Thu Nov 7 18:40:33 2013
@@ -274,11 +274,7 @@ public class FSVectorIndex<T extends Fea
* @see org.apache.uima.cas.impl.FSLeafIndexImpl#deleteFS(org.apache.uima.cas.FeatureStructure)
*/
public void deleteFS(FeatureStructure fs) {
- final int addr = ((FeatureStructureImpl) fs).getAddress();
- final int pos = this.index.indexOf(addr);
- if (pos >= 0) {
- this.index.remove(pos);
- }
+ remove(((FeatureStructureImpl) fs).getAddress());
}
/*
@@ -296,7 +292,7 @@ public class FSVectorIndex<T extends Fea
* @see org.apache.uima.cas.impl.FSLeafIndexImpl#remove(int)
*/
void remove(int fs) {
- final int pos = this.index.indexOf(fs);
+ final int pos = this.index.indexOfOptimizeAscending(fs);
if (pos >= 0) {
this.index.remove(pos);
}
Modified: uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntVector.java
URL: http://svn.apache.org/viewvc/uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntVector.java?rev=1539756&r1=1539755&r2=1539756&view=diff
==============================================================================
--- uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntVector.java (original)
+++ uima/uimaj/trunk/uimaj-core/src/main/java/org/apache/uima/internal/util/IntVector.java Thu Nov 7 18:40:33 2013
@@ -365,15 +365,46 @@ public class IntVector implements Serial
* @return the index or <code>-1</code> if the element was not found.
*/
public int indexOf(int element) {
- int index = -1;
for (int i = 0; i < this.pos; i++) {
if (element == this.array[i]) {
- index = i;
- break;
+ return i;
}
}
+ return -1;
+ }
- return index;
+ /**
+ * Returns the index of the first or last occurrence of the element specified in this vector.
+ * optimization:
+ * this is used only in bag index implementations
+ * Other optimizations for that are done for the major use case
+ * that the order of adding elements results in the elements being
+ * more-or-less ordered, ascending.
+ *
+ * Exploit this by assuming ascending, and testing if the
+ * element is above or below the mid-element, and ordering the
+ * direction of the search.
+ *
+ * @return the index or <code>-1</code> if the element was not found.
+ */
+ public int indexOfOptimizeAscending(int element) {
+// return indexOf(element);
+ final int midValue = this.array[this.pos >>> 1];
+ if (element > midValue) {
+ for (int i = this.pos - 1; i >=0; i--) {
+ if (element == this.array[i]) {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ for (int i = 0; i < this.pos; i++) {
+ if (element == this.array[i]) {
+ return i;
+ }
+ }
+ return -1;
}
/**