| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 851.1 | post it... | CHOVAX::YOUNG | Dumb, Expensive, Dumb ... (Pick Two) | Fri Apr 01 1988 12:14 | 3 |
| Hmmm... I think that your requirements are somewhat ambiguous.
Why don't you post your algorithim if its not too long?
|
| 851.2 | | COOKIE::WAHL | Dave Wahl: Database Systems AD, CX01-2/N22 | Fri Apr 01 1988 16:52 | 6 |
| I can probably mail you some code once I know what you're doing. In
particular, what's the type definition of the matrix and what are you
sorting on?
Dave
|
| 851.3 | Don't move rows, just indices | AKQJ10::YARBROUGH | Why is computing so labor intensive? | Fri Apr 01 1988 17:39 | 8 |
| If the sort is too slow, you are probably doing more data movement than
necessary. Whatever it is you are sorting on, you should consider
constructing an index vector, initially 1..n, which specifies the order of
rows and shuffling that vector to specify in what order the rows should be
moved (ONCE!) into another matrix.
If you were doing the job in FORTRAN, you might be getting hit by page faults
due to FORTRAN's storing matrices by column.
|
| 851.5 | Watch out for Q-sort's worst case | AKQJ10::YARBROUGH | Why is computing so labor intensive? | Tue Apr 05 1988 13:18 | 13 |
| So what you have is actually 26 separate 16000-block sorts. I assume you
want to output the grand sorted list. What I would do is (for first=a..z)
create an index vector of length 1..(actual no of entries in current bucket)
and use a randomized quicksort to shuffle the index vector (to minimize
data moves), then write out the array according to the order given by the
index vector.
NOTE: Quicksort may be the fastest sort *on average*, but its worst-case
behavior is terrible. If the 16000 entries are *already in order* you have
run into the worst-case situation for quicksort, which then becomes an
O(n**2) sort instead of O(nLogn). So unless you are using a randomized
version, you would be better off using a heapsort, which is O(nLogn) in
worst case.
|
| 851.6 | | COOKIE::WAHL | Dave Wahl: Database Systems AD, CX01-2/N22 | Wed Apr 06 1988 02:58 | 8 |
| I know this isn't what you asked for, but I feel like I have to ask
it anyway. Why are you using an unsorted array in the first place?
Is there something about the application which prevents you from
using a persistent order preserving structure like an AVL tree or
binary tree, so the cost of sorting is spread out over the cost of
individual updates to the tree, rather than doing it all at once?
Just asking.
|