Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #147755
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: One works, the other doesn't? |
| Date | 2019-11-08 00:02 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87y2wrgrr3.fsf@bsb.me.uk> (permalink) |
| References | (1 earlier) <qppdj2$52q$1@dont-email.me> <0EgwF.8082$kt1.6599@fx46.iad> <qq0nfg$1hk0$1@gioia.aioe.org> <87imnvj2v6.fsf@bsb.me.uk> <qq1m1g$55b$1@gioia.aioe.org> |
jak <nospam@please.ty> writes:
> Il 07/11/2019 13:19, Ben Bacarisse ha scritto:
>> This is a very odd function. What problem are you trying to solve by
>> writing is this way? The usual reason to have a loop in such a function
>> is to remove the bias that can occur when RAND_MAX is small and not a
>> multiple of the length of the range of values being chosen. But here
>> you could simply add a number in the right range to min and have no loop
>> at all.
>>
>> IIRC the comp.lang.c FAQ has a reasonable discussion on the bias
>> problem.
>>
>> Note also that the OP's function could generate a value of max. In your
>> version, the range of returned results is min to max-1. Nothing wrong
>> with that, but it's a non-obvious change that can trip up the unwary.
>>
>> On the plan of maintaining a sorted list, it's likely to be costly. You
>> will be doing, in effect, a quadratic sort. You could, instead, just
>> all every string to the list and do an O(n log n) merge sort, followed
>> by a count of equal strings. Even then, the cost of all the small
>> allocations might be significant.
>
> You're right about the sort. I had already changed the algorithm with
> unbalanced btree.
A merge sort will be O(n log n) but an unbalanced tree can still be
O(n^2). On average it will be better, but not in the worst case.
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <time.h>
>
> unsigned int rndNum(int min, int max)
> {
> int hi = 0;
> int rnd;
> if (min < max)
> hi = max;
> else
> hi = min;
> do
> {
> rnd = rand() % hi;
> }
> while(rnd < min);
> return rnd;
> }
This is still an odd function. See my comments above.
> char *rndStr()
> {
> static char charset[] = "AaBbCcDdEeFfGgHhIiLlMmNnOoPpQqRrSsTtUuVvZz";
> int charsetLen = strlen(charset);
> int i, rndLen = rndNum(3, 30);
> static char *rndStr;
>
> if((rndStr = malloc(sizeof(char) * (rndLen + 1))) != NULL)
> {
> for(i = 0; i < rndLen; i++)
> rndStr[i] = charset[rndNum(0, charsetLen)];
> rndStr[rndLen] = '\0';
> }
> return rndStr;
> }
I'd write a function with this prototype:
char *rndStr(char *str_buffer, int min_len, int max_len, const char *alphabet);
so as to avoid allocating and freeing every string twice. The main
function can then call this function to fill a buffer with a random
string and the buffer can be reused. Of course if you need this
function for other things, then it's a good idea to return an allocated
string, but it looks like a special-case function with it's hard-wired
alphabet and sizes.
> typedef struct LIST
> {
> char *str;
> int count;
> struct LIST *pMin, *pMaj;
> } Lista;
>
> Lista *BuildList(char *str)
> {
> Lista *lRet = malloc(sizeof(Lista));
> if(lRet != NULL)
> {
> lRet->str = malloc((strlen(str) + 1) * sizeof(str[0]));
You could avoid doing two allocation by using a C99 flexible array
member:
typedef struct LIST
{
int count;
struct LIST *pMin, *pMaj;
char str[];
} Lista;
You then
lRet = malloc(sizeof *lRet + strlen(str) + 1);
> if(lRet->str != NULL)
> {
> strcpy(lRet->str, str);
> lRet->count = 1;
> lRet->pMin = lRet->pMaj = NULL;
> }
> else
> {
> free(lRet);
> lRet = NULL;
> }
> }
> return lRet;
> }
>
> int InsertList(Lista **next, char *str)
> {
> static Lista *iNxt;
> static int cmp;
Eek! When I see static data I start to worry. But in fact, neither of
these needs to be static. If you are worried about the stack usage, a
good compiler (like gcc) will turn this function into a loop. If you
are worried about other compilers, it's very simple to write it as a
loop.
> if(*next == NULL)
> {
> if(!(*next = BuildList(str)))
> return 0;
> }
> else
> {
> iNxt = *next;
> cmp = strcmp(str, iNxt->str);
> if(cmp < 0)
> {
> return InsertList(&(iNxt->pMin), str);
> }
> else if(cmp > 0)
> {
> return InsertList(&(iNxt->pMaj), str);
> }
> else
> {
> iNxt->count++;
> }
> }
> return 1;
> }
>
> int PrintList(Lista *l)
> {
> static unsigned int i = 0;
> if(l == NULL)
> return 1;
> PrintList(l->pMin);
> i++;
> // if(l->count > 1) /* print duplicates */
> printf("%5d: %5d: %s\n", i, l->count, l->str);
> PrintList(l->pMaj);
> return 0;
> }
>
> void KillList(Lista *l)
> {
> if(l != NULL)
> {
> KillList(l->pMin);
> KillList(l->pMaj);
You don't free l->str. Not that it matters in this case, but you are
careful about freeing storage so you probably want to to free it all.
If you didn't free it here because the tree does not "own" the string,
then I would argue that the tree insert function should not have taken a
copy.
> free(l);
> }
> }
>
> int main(int argc, char *argv[])
> {
> char *str;
> int i;
> Lista *root = NULL;
> srand(time(0));
> for(i = 0; i < 3000; i++)
> {
> if((str = rndStr()) == NULL)
> {
> perror("Allocation failure!");
> exit(1);
> }
> if(str[0] != '\0')
> if(!InsertList(&root, str))
> {
> printf("Error adding list\n");
> exit(1);
> }
> free(str);
> }
> PrintList(root);
> KillList(root);
> exit(0);
> }
>
--
Ben.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-03 17:39 -0500
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-04 00:20 +0000
Re: One works, the other doesn't? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-04 06:53 +0000
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-04 09:45 -0500
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 10:34 -0500
Re: One works, the other doesn't? mark.bluemel@gmail.com - 2019-11-05 07:45 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 10:53 -0500
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-05 08:04 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 11:29 -0500
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-05 23:24 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-05 23:06 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 12:31 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-05 23:43 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 12:54 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 01:35 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-06 15:16 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 11:11 +0000
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 01:59 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 11:35 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 08:57 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:24 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 22:59 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 14:37 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 00:58 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 02:08 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 15:43 +0100
Re: One works, the other doesn't? Robert Wessel <robertwessel2@yahoo.com> - 2019-11-07 16:15 -0600
Re: One works, the other doesn't? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-11-10 20:01 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-11 15:26 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-11 12:37 +0100
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:21 +1300
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 10:39 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 07:47 +1300
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-07 08:14 +1300
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-06 12:30 -0800
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 21:04 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 01:37 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-09 01:38 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-10 08:32 +1300
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 16:09 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-29 11:33 +0100
Re: One works, the other doesn't? Öö Tiib <ootiib@hot.ee> - 2019-11-30 14:20 -0800
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-12-01 12:15 +1300
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 10:07 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 10:58 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 10:05 +0100
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 09:52 +0100
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-06 00:56 -0800
Re: One works, the other doesn't? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2019-11-06 01:00 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 11:32 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-06 23:11 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-06 23:22 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 01:04 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 01:13 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 10:22 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 11:51 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 15:58 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 16:34 +0000
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-07 12:40 -0500
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 17:57 +0000
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-07 21:14 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-08 09:45 +0000
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-08 09:56 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-08 19:47 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:14 +1300
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-08 19:10 -0800
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-09 12:24 +0000
Like an old married couple... (Was: One works, the other doesn't?) gazelle@shell.xmission.com (Kenny McCormack) - 2019-11-08 20:25 +0000
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 19:58 +0100
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 19:31 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 08:56 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 20:06 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 09:21 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 21:20 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-08 10:28 +1300
Re: One works, the other doesn't? Bart <bc@freeuk.com> - 2019-11-07 22:35 +0000
Re: One works, the other doesn't? Ian Collins <ian-news@hotmail.com> - 2019-11-09 09:22 +1300
Re: One works, the other doesn't? jadill33@gmail.com - 2019-11-07 08:37 -0800
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-07 08:52 -0800
Re: One works, the other doesn't? jadill33@gmail.com - 2019-11-07 09:52 -0800
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-07 20:04 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 19:50 -0800
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 18:05 +0100
Re: One works, the other doesn't? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2019-11-05 09:28 -0800
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 19:02 +0100
Re: One works, the other doesn't? David Brown <david.brown@hesbynett.no> - 2019-11-05 23:21 +0100
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-06 18:36 +0100
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-05 12:51 -0500
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 18:35 -0500
Re: One works, the other doesn't? Barry Schwarz <schwarzb@delq.com> - 2019-11-05 17:53 -0800
Re: One works, the other doesn't? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-11-06 09:33 -0500
Re: One works, the other doesn't? Barry Schwarz <schwarzb@delq.com> - 2019-11-05 13:36 -0800
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-07 10:17 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-07 12:19 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-07 18:59 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-08 00:02 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-20 10:54 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-20 11:14 +0000
Re: One works, the other doesn't? jak <nospam@please.ty> - 2019-11-20 13:22 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 15:54 -0800
Re: One works, the other doesn't? Keith Thompson <kst-u@mib.org> - 2019-11-20 08:42 -0800
Re: One works, the other doesn't? Manfred <noname@add.invalid> - 2019-11-21 18:56 +0100
Re: One works, the other doesn't? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-11-22 01:07 +0000
Re: One works, the other doesn't? Manfred <noname@add.invalid> - 2019-11-22 15:27 +0100
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-28 15:47 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-07 18:41 -0500
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 17:39 +0100
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-05 11:47 -0500
Re: One works, the other doesn't? Bonita Montero <Bonita.Montero@gmail.com> - 2019-11-05 17:54 +0100
Re: One works, the other doesn't? luser droog <luser.droog@gmail.com> - 2019-11-05 09:00 -0800
Re: One works, the other doesn't? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-11-08 21:02 -0800
Re: One works, the other doesn't? DFS <nospam@dfs.com> - 2019-11-09 02:09 -0500
csiph-web