Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   How to apply qsort() with a parameter? (http://www.velocityreviews.com/forums/t953742-how-to-apply-qsort-with-a-parameter.html)

none 10-22-2012 05:51 PM

How to apply qsort() with a parameter?
 
How does one apply qsort() if the comparison criterion
depends on a parameter?

Specifically, suppose I wish to sort an array of int,
according to distance from a prescribed value `n':

int compar(const void *aa, const void *bb)
{
int a = *(int *)aa;
int b = *(int *)bb;
return abs(a - n) < abs(b - n);
}

One way to make this work, is to declare n as a global
(file scope) variable. Is there a clever way to do this
without bringing in a global variable?

--
Rouben Rostamian

ImpalerCore 10-22-2012 06:18 PM

Re: How to apply qsort() with a parameter?
 
On Oct 22, 1:51*pm, rouben@shadow.(none) (Rouben Rostamian) wrote:
> How does one apply qsort() if the comparison criterion
> depends on a parameter?
>
> Specifically, suppose I wish to sort an array of int,
> according to distance from a prescribed value `n':
>
> int compar(const void *aa, const void *bb)
> {
> * * * * int a = *(int *)aa;
> * * * * int b = *(int *)bb;
> * * * * return abs(a - n) < abs(b - n);
>
> }
>
> One way to make this work, is to declare n as a global
> (file scope) variable. *Is there a clever way to do this
> without bringing in a global variable?


The best method is to reparameterize the qsort function with a
comparison that takes an external parameter.

void qsort_ext( void* base,
size_t num,
size_t size,
int (*cmp_ext_fn)( const void*, const void*, void* ),
void* ext_data );

Then you write your modified comparison function in this fashion.

int compar(const void *aa, const void *bb, void *nn)
{
int a = *(const int *)aa;
int b = *(const int *)bb;
int n = *(int *)n;
return abs(a - n) < abs(b - n);
}

If you have the source of a 'qsort' you want to use, you can create
'qsort_ext' by simply adding the external parameter to the comparison
function pointer call.

Best regards,
John D.

ImpalerCore 10-22-2012 06:26 PM

Re: How to apply qsort() with a parameter?
 
On Oct 22, 2:18*pm, ImpalerCore <jadil...@gmail.com> wrote:
> int compar(const void *aa, const void *bb, void *nn)
> {
> * int a = *(const int *)aa;
> * int b = *(const int *)bb;
> * int n = *(int *)n;
> * return abs(a - n) < abs(b - n);
> }


The comparison should probably be 'abs(a - n) - abs(b - n)', not '<'
which is a boolean expression.

Best regards,
John D.

tom st denis 10-22-2012 06:38 PM

Re: How to apply qsort() with a parameter?
 
On Oct 22, 1:51*pm, rouben@shadow.(none) (Rouben Rostamian) wrote:
> How does one apply qsort() if the comparison criterion
> depends on a parameter?
>
> Specifically, suppose I wish to sort an array of int,
> according to distance from a prescribed value `n':
>
> int compar(const void *aa, const void *bb)
> {
> * * * * int a = *(int *)aa;
> * * * * int b = *(int *)bb;
> * * * * return abs(a - n) < abs(b - n);
>
> }
>
> One way to make this work, is to declare n as a global
> (file scope) variable. *Is there a clever way to do this
> without bringing in a global variable?


The most portable way is to normalize your input first based on what
you are measuring the distance from then perform your sort.

Tom

Eric Sosman 10-22-2012 06:41 PM

Re: How to apply qsort() with a parameter?
 
On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
> How does one apply qsort() if the comparison criterion
> depends on a parameter?
>
> Specifically, suppose I wish to sort an array of int,
> according to distance from a prescribed value `n':
>
> int compar(const void *aa, const void *bb)
> {
> int a = *(int *)aa;
> int b = *(int *)bb;
> return abs(a - n) < abs(b - n);


Aside: This can't be right, as it doesn't define
a total ordering.

> }
>
> One way to make this work, is to declare n as a global
> (file scope) variable. Is there a clever way to do this
> without bringing in a global variable?


No, nothing clever. You could write multiple comparators,
each hard-wiring a different `n' value:

int compar10(const void *aa, const void *bb) {
... use n=10 ...
}

int compar20(const void *aa, const void *bb) {
... use n=20 ...
}

Or, you could subtract n from all the array elements,
use the equivalent of compar0(), and then add n back again.
(Sounds wasteful, but it only adds O(N) time to an operation
that's probably O(N log N) already.)

Neither alternative strikes me as "clever." You either
live with the qsort() interface or write your own sort.

--
Eric Sosman
esosman@comcast-dot-net.invalid

Eric Sosman 10-22-2012 06:59 PM

Re: How to apply qsort() with a parameter?
 
On 10/22/2012 2:41 PM, Eric Sosman wrote:
> On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
>> How does one apply qsort() if the comparison criterion
>> depends on a parameter?


A further observation: Don't go overboard in parameterizing
your comparators. A comparator may be called a large number of
times during a sort, so it's "in the inner loop" and should be
kept short and swift. A comparator that examines parameters
P1,P2,P3,... in addition to the items it's comparing starts to
stray from the "short and swift" ideal.

A particular abuse that always seems to crop up is trying
to use one comparator to sort on multiple keys:

struct s {
int k1;
char *k2;
double k3;
};

int which_key;

int compare(const void *aa, const void *bb) {
const struct s *a = aa;
const struct s *b = bb;
switch (which_key) {
case 1:
return (a->k1 > b->k1) - (a->k1 < b->k1);
case 2:
return strcmp(a->k2, b->k2);
case 3:
return (a->k3 > b->k3) - (a->k3 < b->k3);
default:
assert(false);
}
}

...
which_key = 2;
qsort(array, count, sizeof array[0], compare);

This setup repeats the switch decision -- which is "just
overhead" -- for every comparison, and there may be a lot of
them. It would almost surely be better to have three short
comparators than one omnibus comparator.

--
Eric Sosman
esosman@comcast-dot-net.invalid

Ben Bacarisse 10-22-2012 07:27 PM

Re: How to apply qsort() with a parameter?
 
ImpalerCore <jadill33@gmail.com> writes:

> On Oct 22, 1:51*pm, rouben@shadow.(none) (Rouben Rostamian) wrote:
>> How does one apply qsort() if the comparison criterion
>> depends on a parameter?
>>
>> Specifically, suppose I wish to sort an array of int,
>> according to distance from a prescribed value `n':
>>
>> int compar(const void *aa, const void *bb)
>> {
>> * * * * int a = *(int *)aa;
>> * * * * int b = *(int *)bb;
>> * * * * return abs(a - n) < abs(b - n);
>>
>> }
>>
>> One way to make this work, is to declare n as a global
>> (file scope) variable. *Is there a clever way to do this
>> without bringing in a global variable?

>
> The best method is to reparameterize the qsort function with a
> comparison that takes an external parameter.
>
> void qsort_ext( void* base,
> size_t num,
> size_t size,
> int (*cmp_ext_fn)( const void*, const void*, void* ),
> void* ext_data );
>
> Then you write your modified comparison function in this fashion.
>
> int compar(const void *aa, const void *bb, void *nn)
> {
> int a = *(const int *)aa;
> int b = *(const int *)bb;
> int n = *(int *)n;
> return abs(a - n) < abs(b - n);
> }
>
> If you have the source of a 'qsort' you want to use, you can create
> 'qsort_ext' by simply adding the external parameter to the comparison
> function pointer call.


Many C libraries already have such a thing. GNU libc has qsort_r and
Microsoft champions qsort_s -- to the extent that it's in C11. The BSD
C library also has qsort_r but with a different argument order (for both
qsort_r and the comparison function). I'll bet there are others.

A mess of #ifdefs can probably render such code reasonably portable, but
maybe the OP wants the code to work in only one of these environments.

--
Ben.

tom st denis 10-22-2012 08:25 PM

Re: How to apply qsort() with a parameter?
 
On Oct 22, 2:59*pm, Eric Sosman <esos...@comcast-dot-net.invalid>
wrote:
> On 10/22/2012 2:41 PM, Eric Sosman wrote:
>
> > On 10/22/2012 1:51 PM, none Rouben Rostamian wrote:
> >> How does one apply qsort() if the comparison criterion
> >> depends on a parameter?

>
> * * *A further observation: Don't go overboard in parameterizing
> your comparators. *A comparator may be called a large number of
> times during a sort, so it's "in the inner loop" and should be
> kept short and swift. *A comparator that examines parameters
> P1,P2,P3,... in addition to the items it's comparing starts to
> stray from the "short and swift" ideal.
>
> * * *A particular abuse that always seems to crop up is trying
> to use one comparator to sort on multiple keys:
>
> * * * * struct s {
> * * * * * * int k1;
> * * * * * * char *k2;
> * * * * * * double k3;
> * * * * };
>
> * * * * int which_key;
>
> * * * * int compare(const void *aa, const void *bb) {
> * * * * * * const struct s *a = aa;
> * * * * * * const struct s *b = bb;
> * * * * * * switch (which_key) {
> * * * * * * case 1:
> * * * * * * * * return (a->k1 > b->k1) - (a->k1 < b->k1);
> * * * * * * case 2:
> * * * * * * * * return strcmp(a->k2, b->k2);
> * * * * * * case 3:
> * * * * * * * * return (a->k3 > b->k3) - (a->k3 < b->k3);
> * * * * * * default:
> * * * * * * * * assert(false);
> * * * * * * }
> * * * * }
>
> * * * * ...
> * * * * which_key = 2;
> * * * * qsort(array, count, sizeof array[0], compare);
>
> * * *This setup repeats the switch decision -- which is "just
> overhead" -- for every comparison, and there may be a lot of
> them. *It would almost surely be better to have three short
> comparators than one omnibus comparator.


But that code is not thread safe and it's not really any simpler than
just calling qsort with a variable as the compare callback that is
determined locally on the stack.

Tom

Eric Sosman 10-22-2012 08:54 PM

Re: How to apply qsort() with a parameter?
 
On 10/22/2012 4:25 PM, tom st denis wrote:
> On Oct 22, 2:59 pm, Eric Sosman <esos...@comcast-dot-net.invalid>
> wrote:
>>[...]
>> This setup repeats the switch decision -- which is "just
>> overhead" -- for every comparison, and there may be a lot of
>> them. It would almost surely be better to have three short
>> comparators than one omnibus comparator.

>
> But that code is not thread safe and it's not really any simpler than
> just calling qsort with a variable as the compare callback that is
> determined locally on the stack.


Since qsort() itself need not be thread-safe (it need not
even be re-entrant within just one thread), the thread-safety
of a comparator scarcely matters. A thread-safe comparator
could be called by qsort() in one thread while another called
it via bsearch(), but that's a bit of a stretch.

My personal parser recognizes all the words in your second
and third lines, but is unable to make sense of them.

In any event, the code I showed was an illustration of
what I consider an inferior pattern; the suggested alternative
could in fact be thread-safe.

--
Eric Sosman
esosman@comcast-dot-net.invalid

Tiib 10-22-2012 10:30 PM

Re: How to apply qsort() with a parameter?
 
On Monday, 22 October 2012 20:51:55 UTC+3, none wrote:
> How does one apply qsort() if the comparison criterion
> depends on a parameter?


Others have already replied that most platforms offer qsort variants
with additional parameter.

Also think over why you need to sort with dynamic criteria.
Maybe you only need to find few items with highest order before
your criteria changes again?
On that case building an heap
http://en.wikipedia.org/wiki/Heap_(data_structure)
can be more efficient solution.


All times are GMT. The time now is 10:31 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.