DaWei

No question about it -- it can't be universally effective.
I can only imagine it being useful in things like, for instance, statistical analysis of quality control data. Hell, the fall-off from effective to ineffective could serve as a measure of degree of linearity.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

jim mcnamara

As a quick note:

There are other random number functions out there for unix like drand48().

Writing a decent PRNG is hard and rand() usually is not a decent PRNG for most implementations. They usually copy Knuth -- which is fine for playing simple games. There is a LOT of stuff out there on google about PRNG's. (pseudo-random number generator)

rand()*rand() may not be what you want in other words.

DaWei

Well, I wasn't looking for random, just something not quite linear. Sorting kinda plays hell with ultimate randomness. Hi, Jim, good to see ya .

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

EverLearning

Wooooow.... wish i had more spare time for this ...

I also found a paper on precise efficiency analysis of interpolation search (hope to get to reading that soon).

This has been quite interesting...

I know that searches/sorts are chosen depending on data but did anyone of you ever used this search in reality (work place)? just out of curiosity... or would you go with the "safest" bet? like binary search or some other all-time favorite.

__________________
got math? yumm...

"All men by nature desire to know" -Aristotle, Metaphysics

nnxion

For sorting heap-sort is supposed to be really good.

__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates

Ancient Dragon

No. I only use binary search on sorted data sets. interpolation search is only useful when you have a dataset that rarely, if ever, changes.

DaWei

I would use binary search. Bear in mind that the number of elements affects the efficiency opposite to the way it affects a sort, too. It's better to combine multiple sets and search the large set than it is to search the smaller sets.

For grins, you could fill the array with values generated by an exponential function and watch the linear interpolation search go to hell in a handbasket. An exponential interpolation would do well though. An example of an interpolative search is the way most people look up a word in the dictionary. The data are amenable, so that's what we use.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

Ancient Dragon

That's what happed in my post #10.

DaWei

An exponential interpolation would work well on an exponential distribution, just as linear interpolation works well on a linear distribution. I leave it as an exercise for the reader (I just looove to say that!) to show that a random interpolation does NOT work well on a random distribution. That's why we use binary searches .

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

jim mcnamara

In the real world I use a generalized sort - PNMqsort() which is faster on most of the datasets we have. It's still a quiksort, it just swaps pointers instead of data.
It's based on the glibc2.3.3 (GNU) version of qsort.

For large filesorts (>4GB) we use commercial sort routines (SyncSort) and a HPUX box with a LOT of free disk space on /var/adm. These routines mmap the input, output, and tmp files, so they use a lot of memory, and what doesn't fit in memory slops over into the tmp file.