Open letter to Ian Collins

[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.

 

[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?

 

[Keith Thompson]

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.

 

[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;

 

[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

 

[BartC]

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.)

 

[Keith Thompson]

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.

 

[Philip Lantz]

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.

 

[Sarah Wren]

Hi Ian

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?

 

[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

 

[Joachim Schmitz]

"nodes" in my little english dictionary not exist
pehraps better "knots"

I guess it is "punto nodale"

 

[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.

 

[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