Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4FC20CB5.2AD3@mindspring.com> (permalink) |
|---|---|
| Date | 2012-05-27 07:15 -0400 |
| From | pete <pfiland@mindspring.com> |
| Organization | PF |
| Newsgroups | comp.lang.c |
| Subject | Re: Open letter to Ian Collins |
| References | (1 earlier) <a2dkjvF7faU2@mid.individual.net> <jpsl62$h39$1@speranza.aioe.org> <a2e8hgF7faU3@mid.individual.net> <jpsr5k$utq$1@speranza.aioe.org> <a2ea1oF7faU4@mid.individual.net> |
Ian Collins wrote:
>
> On 05/27/12 09:12 PM, jacob navia wrote:
> > Le 27/05/12 10:56, Ian Collins a écrit :
> >> As I expected, the big difference was in sorting:
> >>
> >> ccl version:
> >>
> >> To sort 85.6384S
> >>
> >> C++ version (std::list.sort()):
> >>
> >> To sort 18.7927S
> >
> > Yes. But I am not finished yet. I am writing a generic
> > qsort module that will avoid the function call overhead of
> > the current solution.
> >
> > As it is now, qsort calls a user defined sort function, that makes a
> > memcmp of the data...
> >
> > With the generic qsort function you would directly compare
> > the data (without function calls) by specifying a macro
> > for comparing your data. For integers it would be simply
> >
> > a - b
>
> That will be interesting to see.
For generic array sorting functions that I've written,
I've had to #define 3 macros.
One E_TYPE macro for the element type,
a GT(A, B) macro for "greater than" comparison
and a MOV(A, B) macro for copying an element.
The MOV(A, B) macro is always #defined as either
((void)(*(A) = *(B)))
or
((void)memcpy((A), (B), sizeof *(A))
depending on whether or not the element is an array type.
/* BEGIN output from ia_sort.c */
Arrays of element type (int),
are being sorted into ascending order.
This is the original order of the test array:
7
8
6
Sorted by simple selection sort:
6
7
8
Sorted by stable insertionsort:
6
7
8
Arrays of element type (char [sizeof "seven"]),
are being sorted by string length.
This is the original order of the test array:
seven
eight
six
Sorted by simple selection sort:
six
eight
seven
Sorted by stable insertionsort:
six
seven
eight
/* END output from ia_sort.c */
/* BEGIN ia_sort.c */
/*
** ia_sort.c shows how to
** sort an array of int and also how to
** sort an array of array of six char,
** from within the same file,
** using sort functions with the e_type interface.
*/
#include "ia_init.h"
#include <stdio.h>
#include <string.h>
#define NMEMB(A) (sizeof (A) / sizeof *(A))
int main(void)
{
size_t sort, element;
char *description[] = {
{"This is the original order of the test array:"},
{"Sorted by simple selection sort:"},
{"Sorted by stable insertionsort:"}
};
const int integer[] = {7,8,6};
int arrayint[NMEMB(integer)];
void (*sort_int[])(int *, size_t) = {
no_sorti,
ssorti,
sisorti,
};
const char string[][sizeof "seven"] = {"seven","eight","six"};
char arraychar[NMEMB(string)][NMEMB(*string)];
void (*sort_char[])(char (*)[NMEMB(*string)], size_t) = {
no_sorta,
ssorta,
sisorta,
};
puts("/* BEGIN output from ia_sort.c */");
puts("\nArrays of element type (int),\n"
"are being sorted into ascending order.\n");
for (sort = 0; sort != NMEMB(sort_int); ++sort) {
memcpy(arrayint, integer, sizeof arrayint);
sort_int[sort](arrayint, NMEMB(arrayint));
puts(description[sort]);
for (element = 0; element != NMEMB(arrayint); ++element) {
printf("%d\n", arrayint[element]);
}
putchar('\n');
}
puts("\nArrays of element type (char [sizeof \"seven\"]),\n"
"are being sorted by string length.\n");
for (sort = 0; sort != NMEMB(sort_char); ++sort) {
memcpy(arraychar, string, sizeof arraychar);
sort_char[sort](arraychar, NMEMB(arraychar));
puts(description[sort]);
for (element = 0; element != NMEMB(arraychar); ++element) {
printf("%s\n", arraychar[element]);
}
putchar('\n');
}
puts("/* END output from ia_sort.c */");
return 0;
}
/* END ia_sort.c */
/* BEGIN ia_init.h */
#ifndef H_IA_INIT_H
#define H_IA_INIT_H
#include <stddef.h>
void no_sorti(int *array, size_t nmemb);
void ssorti(int *array, size_t nmemb);
void sisorti(int *array, size_t nmemb);
void no_sorta(char (*array)[sizeof"seven"], size_t nmemb);
void ssorta(char (*array)[sizeof"seven"], size_t nmemb);
void sisorta(char (*array)[sizeof"seven"], size_t nmemb);
#endif
/* END ia_init.h */
/* BEGIN ia_init.c */
#include "ia_init.h"
#include <string.h>
#define SWAP(N, A, B, T) \
(MOV##N((T), (A)), MOV##N((A), (B)), MOV##N((B), (T)))
#define SORT_INIT(N) \
typedef E_TYPE##N; \
void no_sort##N(e_type##N *array, size_t nmemb) \
{ \
array, nmemb; \
} \
void ssort##N(e_type##N *array, size_t nmemb) \
{ \
e_type##N *first, *middle, temp; \
size_t counter; \
\
while (nmemb-- > 1) { \
first = middle = array + 1; \
counter = nmemb; \
while (--counter != 0) { \
++middle; \
if (GT##N(first, middle)) { \
first = middle; \
} \
} \
if (GT##N(array, first)) { \
SWAP(N, array, first, &temp); \
} \
++array; \
} \
} \
void sisort##N(e_type##N *array, size_t nmemb) \
{ \
e_type##N *base, *low, *high, temp; \
\
if (nmemb-- > 1) { \
base = array; \
do { \
low = array++; \
if (GT##N(low, array)) { \
high = array; \
MOV##N(&temp, high); \
do { \
MOV##N(high, low); \
if (--high == base) { \
break; \
} \
--low; \
} while (GT##N(low, &temp)); \
MOV##N(high, &temp); \
} \
} while (--nmemb != 0); \
} \
}
#define E_TYPEi int e_typei
#define MOVi(A, B) ((void)(*(A) = *(B)))
#define GTi(A, B) (*(A) > *(B))
#define E_TYPEa char e_typea[sizeof "seven"]
#define MOVa(A, B) ((void)memcpy((A), (B), sizeof *(A)))
#define GTa(A, B) (strlen(*(A)) > strlen(*(B)))
SORT_INIT(i)
SORT_INIT(a)
/* END ia_init.c */
--
pete
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 00:22 +0200
Re: Open letter to Ian Collins Ike Naar <ike@sverige.freeshell.org> - 2012-05-26 22:36 +0000
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 01:13 +0200
Re: Open letter to Ian Collins Barry Schwarz <schwarzb@dqel.com> - 2012-05-26 16:53 -0700
Re: Open letter to Ian Collins Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-26 16:41 -0700
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-26 22:43 -0400
Re: Open letter to Ian Collins Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-26 15:41 -0700
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 01:14 +0200
Re: Open letter to Ian Collins MelissA <melis@a.com> - 2012-05-27 00:52 +0200
Re: Open letter to Ian Collins Stephen Sprunk <stephen@sprunk.org> - 2012-05-26 20:40 -0500
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 09:32 +0200
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 07:18 -0400
Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 14:24 +1200
Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 10:36 +0100
Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 22:33 +1200
Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 12:25 +0100
Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-28 07:17 +1200
Re: Open letter to Ian Collins Ike Naar <ike@sverige.freeshell.org> - 2012-05-27 13:03 +0000
Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 15:16 +1200
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 09:30 +0200
Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 20:56 +1200
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 11:12 +0200
Re: Open letter to Ian Collins Ian Collins <ian-news@hotmail.com> - 2012-05-27 21:22 +1200
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 07:15 -0400
Re: Open letter to Ian Collins Keith Thompson <kst-u@mib.org> - 2012-05-27 07:49 -0700
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 13:55 -0400
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 22:24 +0200
Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 22:09 +0100
Re: Open letter to Ian Collins Keith Thompson <kst-u@mib.org> - 2012-05-27 14:33 -0700
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 17:49 -0400
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-27 17:31 -0400
Re: Open letter to Ian Collins Philip Lantz <prl@canterey.us> - 2012-05-28 01:38 -0700
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-05-28 08:18 -0400
Re: Open letter to Ian Collins "BartC" <bc@freeuk.com> - 2012-05-27 15:46 +0100
Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-06-13 21:25 -0400
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-06-13 21:52 -0400
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-06-14 04:00 +0200
Re: Open letter to Ian Collins pete <pfiland@mindspring.com> - 2012-06-14 00:04 -0400
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-27 09:42 +0200
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-28 12:39 +0200
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-28 21:44 +0200
Re: Open letter to Ian Collins jacob navia <jacob@spamsink.net> - 2012-05-29 09:46 +0200
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 10:06 +0200
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 10:37 +0200
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 10:58 +0200
Re: Open letter to Ian Collins "Joachim Schmitz" <nospam.jojo@schmitz-digital.de> - 2012-05-29 11:34 +0200
Re: Open letter to Ian Collins Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-05-29 03:02 -0700
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 09:59 +0200
Re: Open letter to Ian Collins "io_x" <a@b.c.invalid> - 2012-05-29 20:09 +0200
Re: Open letter to Ian Collins "Sarah Wren" <swreb@ameritech.net> - 2012-05-29 01:40 -0600
csiph-web