RadixSort Class Reference

#include <IceRevisitedRadix.h>

Public Member Functions
inline_ udword	GetNbHits () const
	Returns the number of eraly exits due to temporal coherence. More...
inline_ udword	GetNbTotalCalls () const
	Returns the total number of calls to the radix sorter. More...
inline_ const udword *	GetRanks () const
	Access to results. mRanks is a list of indices in sorted order, i.e. in the order you may further process your data. More...
inline_ udword *	GetRecyclable () const
	mIndices2 gets trashed on calling the sort routine, but otherwise you can recycle it the way you want. More...
udword	GetUsedRam () const
	RadixSort ()
RadixSort &	Sort (const udword *input, udword nb, RadixHint hint=RADIX_SIGNED)
RadixSort &	Sort (const float *input, udword nb)
	~RadixSort ()

Private Member Functions
void	CheckResize (udword nb)
bool	Resize (udword nb)

Private Attributes
udword	mCurrentSize
	Current size of the indices list. More...
udword	mNbHits
	Number of early exits due to coherence. More...
udword *	mRanks
	Two lists, swapped each pass. More...
udword *	mRanks2
udword	mTotalCalls
	Total number of calls to the sort routine. More...

Detailed Description

Revisited Radix Sort. This is my new radix routine:

• it uses indices and doesn't recopy the values anymore, hence wasting less ram
• it creates all the histograms in one run instead of four
• it sorts words faster than dwords and bytes faster than words
• it correctly sorts negative floating-point values by patching the offsets
• it automatically takes advantage of temporal coherence
• multiple keys support is a side effect of temporal coherence

• it may be worth recoding in asm... (mainly to use FCOMI, FCMOV, etc) [it's probably memory-bound anyway]

  History:

  • 08.15.98: very first version
  • 04.04.00: recoded for the radix article
  • 12.xx.00: code lifting
  • 09.18.01: faster CHECK_PASS_VALIDITY thanks to Mark D. Shattuck (who provided other tips, not included here)
  • 10.11.01: added local ram support
  • 01.20.02: bugfix! In very particular cases the last pass was skipped in the float code-path, leading to incorrect sorting......
  • 01.02.02: - "mIndices" renamed => "mRanks". That's a rank sorter after all.
    • ranks are not "reset" anymore, but implicit on first calls
  • 07.05.02: - offsets rewritten with one less indirection.
  • 11.03.02: - "bool" replaced with RadixHint enum

\author             Pierre Terdiman
\version    1.4
\date               August, 15, 1998

Definition at line 26 of file IceRevisitedRadix.h.

Constructor & Destructor Documentation

RadixSort()

RadixSort::RadixSort

(

)

~RadixSort()

RadixSort::~RadixSort

(

)

Member Function Documentation

CheckResize()

void RadixSort::CheckResize ( udword  nb )

private

GetNbHits()

inline_ udword RadixSort::GetNbHits ( ) const

inline

Returns the number of eraly exits due to temporal coherence.

Definition at line 47 of file IceRevisitedRadix.h.

GetNbTotalCalls()

inline_ udword RadixSort::GetNbTotalCalls ( ) const

inline

Returns the total number of calls to the radix sorter.

Definition at line 45 of file IceRevisitedRadix.h.

GetRanks()

inline_ const udword* RadixSort::GetRanks ( ) const

inline

Access to results. mRanks is a list of indices in sorted order, i.e. in the order you may further process your data.

Definition at line 37 of file IceRevisitedRadix.h.

GetRecyclable()

inline_ udword* RadixSort::GetRecyclable ( ) const

inline

mIndices2 gets trashed on calling the sort routine, but otherwise you can recycle it the way you want.

Definition at line 40 of file IceRevisitedRadix.h.

GetUsedRam()

udword RadixSort::GetUsedRam

(

)

const

Resize()

bool RadixSort::Resize ( udword  nb )

private

Sort() [1/2]

RadixSort& RadixSort::Sort	(	const udword *	input,
		udword	nb,
		RadixHint	hint = RADIX_SIGNED
	)

Sort() [2/2]

RadixSort& RadixSort::Sort	(	const float *	input,
		udword	nb
	)

Member Data Documentation

mCurrentSize

udword RadixSort::mCurrentSize

private

Current size of the indices list.

Definition at line 54 of file IceRevisitedRadix.h.

mNbHits

udword RadixSort::mNbHits

private

Number of early exits due to coherence.

Definition at line 59 of file IceRevisitedRadix.h.

mRanks

udword* RadixSort::mRanks

private

Two lists, swapped each pass.

Definition at line 55 of file IceRevisitedRadix.h.

mRanks2

udword* RadixSort::mRanks2

private

Definition at line 56 of file IceRevisitedRadix.h.

mTotalCalls

udword RadixSort::mTotalCalls

private

Total number of calls to the sort routine.

Definition at line 58 of file IceRevisitedRadix.h.

---

The documentation for this class was generated from the following file:

• IceRevisitedRadix.h