Saturday, May 21, 2016

Digest for comp.lang.c++@googlegroups.com - 7 updates in 4 topics

Paul <pepstein5@gmail.com>: May 21 02:11AM -0700

The URL http://www.infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai seems to contain useful algorithms in C/C++. (By "C/C++", I mean that the author uses C constructs but they're supposed to compile in C++ too. As in the subject title, some of it doesn't compile in either C or C++, though, using gnu).
 
The language of the original text is Romanian/C/C++ (I think) but Google Translate works superbly (which isn't to imply that other online translators aren't equally good or better)>
 
The relevant excerpt begins after "BEGIN QUOTE".
int N, M, G * [N], Deg [N]; doesn't compile, and I wouldn't expect it to compile either.
Can anyone suggest a correction? Also, I am trying to learn from this URL more generally, so I would be very interested if someone disagrees with anything on the URL or in the quote below, even if it isn't pertinent to my non-compilation problem.
 
Many thanks for your help,
 
Paul
 
BEGIN QUOTE
Graphs lists adjacency
It knows (or should know!) That working with pointers is very slow ... so they retain a graph rarely (number of nodes, small number of edges) with pointers (see below) greatly slow the program .
 
struct list
{
int n;
struct list * next;
}
 
typedef struct Lists;
In contiuare we present a method that is 3-4 times faster (ie Browsing DF, BF or other algorithms runs 3-4 times faster when the graph is stored so), but has the disadvantage need to read twice input file.
 
 
#include <stdlib.h>
#include <stdio.h>
 
// BELOW SEEMS WRONG AND IS AN ERROR ON MY COMPILER
// ****************************************************
int N, M, G * [N], Deg [N];
// ************************************************

int main ( void )
{
int i, j;

freopen ( "in.txt" , "r" , stdin);
scanf ( "% d% d" , & N & M);
for (; M> 0; M--)
{
scanf ( "% d% d" , & i, & j);
Deg [i - 1] ++, Deg [j - 1] ++;
}
for (i = 0; i <N; Deg [i ++] = 0)
G [i] = ( int *) malloc (Deg [i] * sizeof ( int ));
fseek (stdin, 0, SEEK_SET);
scanf ( "% d% d" , & N & M);
for (; M> 0; M--)
{
scanf ( "% d% d" , & i, & j);
i--, j--;
G [i] [Deg [i] ++] = j
G [j] [Deg [j] ++] = i;
}

return 0;
}
The speed increase is because the vectors are used instead of pointers and struct sites. If we can avoid reading memory allows twice the file by keeping the edges in a list of edges and then after calculating grades, inserting edges in lists. To demonstrate the effectiveness of this method do the following test: a source deploy and implement struct pointer and a BF, then write the code above with the following changes:
 
 
for (i = 0; i <N; i ++)
{
G [i] = ( int *) malloc ((Deg [i] +1) * sizeof ( int ));
G [i] [Deg [i]] = 1;
Deg [i] = 0;
}
 
and implement BF follows:
 
 
void BF ()
{
int Q [N], ql, qr, * p;
char U [N];
memset (U, 0, sizeof (U));
U [Q [ql = qr = 0] = n] = 1;
for (; ql <= qr; ql ++)
for (p = G [Q [ql]]; * p! = -1; p ++)
if (! U [* i]) U [Q [qr ++] = * p] = 1;
}
Then try to see the time difference between the two programs ... impressive, huh?
END QUOTE
Christian Gollwitzer <auriocus@gmx.de>: May 21 03:04PM +0200

Am 21.05.16 um 11:11 schrieb Paul:
#include <stdio.h>
> // ************************************************
 
> scanf ( "% d% d" , & N & M);
 
> G [i] = ( int *) malloc (Deg [i] * sizeof ( int ));
 
This line suggests that indeed G should be an array of pointers of
length N, and Deg an array of ints of length N. SInce N is only known at
runtime, instead try:
 
int N, M;
scanf ( "% d% d" , & N & M);
 
int **G = (int **) malloc(sizeof(int*)*N);
int *Deg = (int*) malloc(sizeof(int)*N);
 
if you stick to C. Otherwise use either new or std::vector.
There is more to it: Deg[] is not initialized before it's used. I
suppose that the input to the algorithm goes there.
 
Cave: I haven't tried to compile this code.
 
Christian
Ben Bacarisse <ben.usenet@bsb.me.uk>: May 21 05:13PM +0100

> at runtime, instead try:
 
> int N, M;
> scanf ( "% d% d" , & N & M);
 
It's scanf("%d%d",...) or "%d %d" (which does the same) but you can't
have a space after the %.
 
> int **G = (int **) malloc(sizeof(int*)*N);
> int *Deg = (int*) malloc(sizeof(int)*N);
 
> if you stick to C.
 
Though C (in the 1999 version) has variable length arrays and, since C++
does not, you need to use malloc when you *don't* want to stick to C (or
when you need to use old C). To make it work, though, you need to
declare
 
int *G[N], Deg[N];
 
after N has been given a value.
 
For purely C code, the usual idiom is:
 
int *Deg = malloc(N * sizeof *Deg);
 
But your code is clearly the way to go if C and C++ compiling is
required (though why this would be important I can't imagine).
 
> Otherwise use either new or std::vector.
 
Yes, I'd go full C++ for this sort of thing. Much simpler.
 
<snip>
--
Ben.
red floyd <no.spam.here@its.invalid>: May 20 10:33PM -0700

> and free to work to preserve/create a friendly
> place for people of faith interested in C++.
 
> Brian
 
But this group is for EVERYONE interested in C++,
not just "people of faith". Hell, I have my own
religious faith, but I don't push it on anyone
because it's annoying as all hell when someone does
that.
Jerry Stuckle <jstucklex@attglobal.net>: May 21 09:33AM -0400

On 5/20/2016 2:46 PM, David Brown wrote:
> man. The concept simply doesn't make sense.
 
> I guess there is little point in continuing this, since you seem
> incapable or unwilling to read, and I am merely repeating myself.
 
Oh, and one other thing. I notice you want to stop discussing things
right when you challenged me to provide links to archaeological evidence
of stories in Genesis, AND I DID.
 
Once again you just stop discussions rather than admit you are wrong.
But you've done it before, and you'll do it again - because you are
completely unable to admit you just might be wrong about something.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
Paul <pepstein5@gmail.com>: May 21 01:56AM -0700

On Friday, May 20, 2016 at 2:05:40 PM UTC+1, Scott Lurndal wrote:
> rules apply. Static (or file-scope) variables are initialized
> to zero at program load time. Stack (function scope) variables
> are uninitialized and the contents are undefined until assigned.
 
Thanks to all the answerers on this thread. Very helpful!
 
Paul
ram@zedat.fu-berlin.de (Stefan Ram): May 21 12:48AM

>gaping abyss of Ginnungagap. This chaos of perfect silence and darkness
>lay between the homeland of elemental fire, Muspelheim, and the homeland
>of elemental ice, Niflheim.
 
From a physicists point of view, this actually makes sense.
 
Energy always comes from a difference of potentials, like a
difference of temperatures (temperature being one of the
potentials of thermodynamics).
 
In normal life, fire is the hottest thing and ice is the
coldest thing. So the difference of temperature between fire
and ice is the largest possible difference in temperature
one can express with common words. Thus, it corresponds to a
very large difference of potentials which corresponds to a
very large amount of energy.
 
So they say in their words that in the beginning there was
only a very large amount of energy, which seems to
correspond to modern physical theories. For the type of live
the founders of this story must have lived, »elemental fire
and elemental ice« already is a surprisingly abstract way of
description.
 
They then go on to say that the world the evolved due to the
natural course of things that happens when the different
potentials come into contact, which also corresponds to
modern physical theories.
 
PS: While we're at it: I would like to publicly forecast
that in the final season, dragons (»fire« - controlled by
Bran, Tyrion and Daenerys) will fight the white walkers (»ice«).
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)