You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@uima.apache.org by "Branimir Lambov (JIRA)" <ui...@incubator.apache.org> on 2009/06/02 18:15:07 UTC
[jira] Created: (UIMA-1366) Binary heap annotation iterator
implementation
Binary heap annotation iterator implementation
----------------------------------------------
Key: UIMA-1366
URL: https://issues.apache.org/jira/browse/UIMA-1366
Project: UIMA
Issue Type: Improvement
Components: Core Java Framework
Reporter: Branimir Lambov
The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Closed: (UIMA-1366) Binary heap annotation iterator
implementation
Posted by "Branimir Lambov (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Branimir Lambov closed UIMA-1366.
---------------------------------
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Assignee: Thilo Goetz
> Fix For: 2.3
>
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Commented: (UIMA-1366) Binary heap annotation iterator
implementation
Posted by "Thilo Goetz (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12715940#action_12715940 ]
Thilo Goetz commented on UIMA-1366:
-----------------------------------
Forgot to say: please check that everything is ok and then close the issue (or reopen, as the case may be). Thanks.
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Assignee: Thilo Goetz
> Fix For: 2.3
>
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (UIMA-1366) Binary heap annotation iterator
implementation
Posted by "Thilo Goetz (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Thilo Goetz resolved UIMA-1366.
-------------------------------
Resolution: Fixed
Fix Version/s: 2.3
Assignee: Thilo Goetz
Hi Branimir, I have committed your patch, thanks. It's great to see somebody working on this code, it needs it!
I made one small change: I called your ll_leafIterator() ll_rootIterator(), as you're getting an iterator for the root type of the index. Hope that's ok with you.
If you plan to contribute more (and I hope you do), please send in an ICLA (if you haven't done so already).
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Assignee: Thilo Goetz
> Fix For: 2.3
>
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (UIMA-1366) Binary heap annotation iterator
implementation
Posted by "Branimir Lambov (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Branimir Lambov updated UIMA-1366:
----------------------------------
Attachment: (was: BinaryHeapIteratorPatch.txt)
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Issue Comment Edited: (UIMA-1366) Binary heap annotation
iterator implementation
Posted by "Branimir Lambov (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12715876#action_12715876 ]
Branimir Lambov edited comment on UIMA-1366 at 6/3/09 2:09 AM:
---------------------------------------------------------------
Updated patch with the latest version (two unnecessary validity checks removed from is_before).
was (Author: barnie):
Removed two unnecessary validity checks.
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (UIMA-1366) Binary heap annotation iterator
implementation
Posted by "Branimir Lambov (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Branimir Lambov updated UIMA-1366:
----------------------------------
Attachment: BinaryHeapIteratorPatch.txt
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (UIMA-1366) Binary heap annotation iterator
implementation
Posted by "Branimir Lambov (JIRA)" <ui...@incubator.apache.org>.
[ https://issues.apache.org/jira/browse/UIMA-1366?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Branimir Lambov updated UIMA-1366:
----------------------------------
Attachment: BinaryHeapIteratorPatch.txt
Removed two unnecessary validity checks.
> Binary heap annotation iterator implementation
> ----------------------------------------------
>
> Key: UIMA-1366
> URL: https://issues.apache.org/jira/browse/UIMA-1366
> Project: UIMA
> Issue Type: Improvement
> Components: Core Java Framework
> Reporter: Branimir Lambov
> Attachments: BinaryHeapIteratorPatch.txt
>
>
> The attached patch is a logarithmic complexity implementation of FSIndexRepositoryImpl.PointerIterator. The implementation maintains a binary heap of indexes and a short sorted section before the start of the heap to avoid spending more time than the old UIMA iterator when a couple of types completely dominate the heap.
> It offers small advantage when iterating over a small number of types and should be significantly faster for large numbers of types, as well as in situations where moveToNext() is not the only operation used on the iterator.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.