Open letter to Ian Collins

I

Ike Naar

Suppose you're delving into a random scene, (or have an extract for use
elsewhere), and want to be reminded who a character is, you have to start
ploughing through from page one first until you encounter their first
mention?

It depends.
When a variable is declared on first use, the active scope of the variable
is sometimes reduced to a few lines of code. So, to find the declaration, one
has to plough backward for a few lines. That may take less ploughing than
when the declaration is at the beginning of the function.
 
B

BartC

ccl version:

To sort 85.6384S

C++ version (std::list.sort()):

To sort 18.7927S

Iteration was closer:

To access 2.80655S (ccl)
To access 1.82896S

What does iteration measure, in terms of the example program? Just the same
thing, but without the sort?
 
K

Keith Thompson

Ian Collins said:
On 05/27/12 09:12 PM, jacob navia wrote: [...]
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.

Especially for values like a==INT_MIN, b==INT_MAX.
 
I

Ian Collins

That's another thing; uses of i, j and k for loop indices is fairly
standard. They probably will be ints, and the formality of having to declare
them can be kept out of the way instead of making for-loops even longer.
(Alternatively for-loop variables could be implicitly declared.)

Declaring loop indexes in the loop makes it clear that's what they are
and that they won't spill out.
What do you mean by a const? If it is a name that is to be used in several
places, then it can also benefit from splitting declaration (and
initialisation) from it's use.

const in t n = some_expression;
 
J

jacob navia

Le 27/05/12 19:55, pete a écrit :
I think there's about a zillion combinations of (a) and (b),
where (a - b) has problems.

Sure.

You want to say then that it is not a good idea in C to write

a - b

??

If you think that overflow could be a problem in a comparison you can
write something more complicated, expressions can be of any length, it
is only important that they be consequent.

You can of course test for overflow, and for any other conditions you
wish. If your integers are 32 bit you can force them into 64 bits for
doing the comparisons, for instance
 
B

BartC

jacob navia said:
Le 27/05/12 19:55, pete a écrit :

Sure.

You want to say then that it is not a good idea in C to write

a - b

??

If you think that overflow could be a problem in a comparison you can
write something more complicated, expressions can be of any length, it
is only important that they be consequent.

Maybe he means there might be more problems using:

(a-b<=0)

than just using:

(a<=b)

for example. Especially when a and b are unsigned. (Assuming the way
comparisons will be done is along the lines of that former expression.)
 
K

Keith Thompson

BartC said:
Maybe he means there might be more problems using:

(a-b<=0)

than just using:

(a<=b)

for example. Especially when a and b are unsigned. (Assuming the way
comparisons will be done is along the lines of that former expression.)

My point is simply that "a - b" is not a reliable way to *compare*
two arbitrary integer values. Using a wider type is not a general
solution.

If you *don't* think that overflow could be a problem in a
comparison, then you've probably missed something.

The language doesn't have a built-in 3-way comparison operator,
but it does have < and >. Just use them.
 
P

Philip Lantz

pete said:
What I want to say, is that what you wrote:

"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"

doesn't correspond to any notion
of what "generic qsort function" could possibly mean.

You misunderstood. The qsort function is generic. The comparison macro
isn't generic, it is specific to the data being sorted. "a - b" could be
a valid comparison macro for some data sets where the range of the data
is known. However, Jacob did overgeneralize a bit when he said that it
would be appropriate "for integers", without further qualification.
 
S

Sarah Wren

jacob navia said:

Are you not ashamed of yourself for asking what you are asking (you've a
history here, not just the one proverbial question)?

At some point, you'll become as wise as me, and I'll become as old as you.
To note, I am older and you are just taking your toys apart and figuring
them out. Hmm?
 
J

jacob navia

Le 28/05/12 21:44, io_x a écrit :
#define N 10_000_000
in your pc; here with my little pc, and with my implementation
of list
is too much for me... i get a result only until N=190_000
because if more big, it would
be Malloc_m return 0 in the first loop ...

Did the library catch correctly the error?

Thanks
 
M

Malcolm McLean

בת×ריך ×™×•× ×©×œ×™×©×™, 29 במ××™ 2012 09:58:50 UTC+1, מ×ת io_x:
"nodes" in my little english dictionary not exist
pehraps better "knots"
The words have the same root, but now they mean different things.
 
J

jacob navia

Le 14/06/12 03:25, pete a écrit :
/*
** Would you please run this program
** and let me know what the output is?
** I'm of the opinion that the QSORT function
** which is currently in listgen.c, at
** http://code.google.com/p/ccl/downloads/detail?name=ccl.zip&can=2&q=
** has approximately zero chance of correctly sorting
** a data set of as many as 10000000 psuedorandom keys.
*/
#include<stdlib.h>

#include "containers.h"
#include "intlist.h"

#define N 10000000

int
main(void)
{
intList *L1;
size_t i;
int d;
long unsigned sum=0,newSum=0;
Iterator *it;
int *pint, last_pint;

L1 = iintList.Create(sizeof(int));
iintList.UseHeap(L1,NULL); // Use specialized Heap
// Add N random numbers to the integer list
for (i=0; i<N;i++) {
d = rand();
sum += d;
iintList.Add(L1,d);
}
// Sort it
iintList.Sort(L1);
// Go through the sorted list using an iterator
it = iintList.NewIterator(L1);
i=0;
pint = it->GetFirst(it);
while (pint != NULL) {
last_pint = *pint;
newSum += last_pint;
pint = it->GetNext(it);
if (pint != NULL&& last_pint> *pint) {
puts("\n\nThe data is not sorted.\n\n");
iintList.Finalize(L1);
exit(EXIT_SUCCESS);
}
}
// Verify that both sums are identical
if (sum != newSum) {
printf("Failed\n");
} else {
printf("Sum = %lu\n",sum);
}
// Destroy the list
iintList.Finalize(L1);
return 0;
}

Hi Pete

The output is:
Sum = 10737818730605039

Maybe because I incorporated the changes you proposed to the quick sort
template after the last discussion.

You get another output? Have you tried with the latest sources?

Thanks for your help.

jacob
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top