You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucy.apache.org by "Marvin Humphrey (JIRA)" <ji...@apache.org> on 2009/09/14 23:36:58 UTC
[jira] Created: (LUCY-49) Context-aware mergesort and quicksort
Context-aware mergesort and quicksort
-------------------------------------
Key: LUCY-49
URL: https://issues.apache.org/jira/browse/LUCY-49
Project: Lucy
Issue Type: Improvement
Components: Core
Reporter: Marvin Humphrey
Assignee: Marvin Humphrey
Priority: Blocker
The only sort routine you can count on the system providing is qsort. Some
systems provide a qsort_r which takes a context argument in addition to the
items being compared, but not all, and the function signature differs on the
systems that do provide it (with context being either the first or the last
argument to the comparison function).
Lucy::Util::SortUtils provides a context-aware quicksort and a context-aware
mergesort. The mergesort also exposes merge routines which are optimized for
use by an external sorter, as they minimize copying.
The quicksort implementation guards against the classic quicksort worst-case
behavior with careful pivot selection. One popular quicksort optimization is
still TODO: using insertion sort for array slices of 10 or fewer elements.
Implementing that optimization may be worthwhile, as this quicksort will
probably be used for the first level of token-sorting at index time.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (LUCY-49) Context-aware mergesort and quicksort
Posted by "Marvin Humphrey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCY-49?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marvin Humphrey updated LUCY-49:
--------------------------------
Attachment: SortUtils.c
SortUtils.bp
> Context-aware mergesort and quicksort
> -------------------------------------
>
> Key: LUCY-49
> URL: https://issues.apache.org/jira/browse/LUCY-49
> Project: Lucy
> Issue Type: Improvement
> Components: Core
> Reporter: Marvin Humphrey
> Assignee: Marvin Humphrey
> Priority: Blocker
> Attachments: SortUtils.bp, SortUtils.c
>
>
> The only sort routine you can count on the system providing is qsort. Some
> systems provide a qsort_r which takes a context argument in addition to the
> items being compared, but not all, and the function signature differs on the
> systems that do provide it (with context being either the first or the last
> argument to the comparison function).
> Lucy::Util::SortUtils provides a context-aware quicksort and a context-aware
> mergesort. The mergesort also exposes merge routines which are optimized for
> use by an external sorter, as they minimize copying.
> The quicksort implementation guards against the classic quicksort worst-case
> behavior with careful pivot selection. One popular quicksort optimization is
> still TODO: using insertion sort for array slices of 10 or fewer elements.
> Implementing that optimization may be worthwhile, as this quicksort will
> probably be used for the first level of token-sorting at index time.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Resolved: (LUCY-49) Context-aware mergesort and quicksort
Posted by "Marvin Humphrey (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/LUCY-49?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Marvin Humphrey resolved LUCY-49.
---------------------------------
Resolution: Fixed
Committed as r815563.
> Context-aware mergesort and quicksort
> -------------------------------------
>
> Key: LUCY-49
> URL: https://issues.apache.org/jira/browse/LUCY-49
> Project: Lucy
> Issue Type: Improvement
> Components: Core
> Reporter: Marvin Humphrey
> Assignee: Marvin Humphrey
> Priority: Blocker
> Attachments: SortUtils.bp, SortUtils.c
>
>
> The only sort routine you can count on the system providing is qsort. Some
> systems provide a qsort_r which takes a context argument in addition to the
> items being compared, but not all, and the function signature differs on the
> systems that do provide it (with context being either the first or the last
> argument to the comparison function).
> Lucy::Util::SortUtils provides a context-aware quicksort and a context-aware
> mergesort. The mergesort also exposes merge routines which are optimized for
> use by an external sorter, as they minimize copying.
> The quicksort implementation guards against the classic quicksort worst-case
> behavior with careful pivot selection. One popular quicksort optimization is
> still TODO: using insertion sort for array slices of 10 or fewer elements.
> Implementing that optimization may be worthwhile, as this quicksort will
> probably be used for the first level of token-sorting at index time.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.