Reversing a linked list

J

jacob navia

Le 17/09/11 17:47, jacob navia a écrit :
The same analysis for 3: also a cost of 1/16 makes 1/8 cycle for
a pipeline depth of 32.

No, (3) is done only N / 2 times since the pointer is incremented twice
as fast. Its cost is not 1/16 but 1/32.

We would have then 1/16 + 1/32 --> 3/32 approx 1/11 --> 0.1 cycle
 
J

jacob navia

Le 17/09/11 09:09, Tony a écrit :
What are the statistics?
How many new C programmers are there each year?
Is the total number of C programmers increasing or decreasing?

1) Here you acknowledge that you have absolutely NO DATA for your
assertion that C is in a "black hole" and in complete decline.

2) If you take a random statistical programming language rating like
(for instance) the TIOBE rating at

http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

that has been running for years you will see that the order is
more like:


Pos. Pos. Programming
Sep11 Sep10 Language Ratings Delta

1 1 Java 18.761% +0.85%
2 2 C 18.002% +0.86%
3 3 C++ 8.849% -0.96%
4 6 C# 6.819% +1.80%

All other programming languages come AFTER those.

If you look at the long term history of that rating
(further down that page) you will see has held that
position for MANY YEARS.

OK?

Next time, before you make those blanket statements turn on
your brain before writing anything.
 
K

Keith Thompson

Tony said:
By "implementation", Ian meant "the compiler". That is what is typically
understood as "the implementation". As in, "the implementation of the
language".

The "implementation" includes the compiler, the standard library, the
linker, and probably some other things.
(Aside: Isn't a single underscore suggested for use by libraries?).

The simple rule is to avoid defining *any* identifier starting with an
identifier, unless you're writing a C implementation.

It's not quite that simple. Identifiers starting with two underscores,
or with an underscore followed by an upper case letter, are reserved for
all purposes. Identifiers starting with an underscore *not* followed by
another underscore or by an upper case letter are reserved in fewer
contexts. So you *can* use such identifiers in your own code, but it's
easier not to.
 
H

henry eshbaugh

The "implementation" includes the compiler, the standard library, the
linker, and probably some other things.


The simple rule is to avoid defining *any* identifier starting with an
identifier, unless you're writing a C implementation.

It's not quite that simple.  Identifiers starting with two underscores,
or with an underscore followed by an upper case letter, are reserved for
all purposes.  Identifiers starting with an underscore *not* followed by
another underscore or by an upper case letter are reserved in fewer
contexts.  So you *can* use such identifiers in your own code, but it's
easier not to.

K.

With my compiler, symbols are _[name]. So, it comes out to be
___reverse_list(), which isn't too bad.

But it's a coding style issue anyway, and is trivial.
 
T

Tony

BartC said:
Documentation ensures

Welll when you write a book on that, maybe your theories will have some
worth? I stop you mid sentence. "Documentation ensures"... what! I dare
you! Make me!
 
T

Tony

Keith said:
The "implementation" includes the compiler, the standard library, the
linker, and probably some other things.

Bah! I'm supposed to feel sorry for you?
The simple rule is

Don't you EVEN dare me. "Bring your 'simple rule' before me, so that I
can "judge", what is right and what is wrong, as if there was ever
confusion, I assure you that I am appointed by the highest (er, uh, ...)

I owe you what?! You have a "president". Don't you dare graft poliitics
upon me. Because you will be "pushing my buttons".

to avoid defining *any* identifier starting with an
identifier, unless you're writing a C implementation.

It's not quite that simple.

Don't you dare put that "star of simplicity" on me, because I do know
what you did.
 
T

Tony

Ben said:
I hope you now accept that that is not what I was saying. In case
there is any doubt: I am not saying that.

If that's "walking the line" and trying to suck me into your politics,

It's not going to ever happen, bitch.
 
J

jacob navia

Le 18/09/11 07:11, Tony a écrit :
BITCH, you tell what "I acknowlege" on more time, .. you don't want to
war with me.


I challenged you to do what?


It is.


I didn't say that.
You said:
<quote>
The truth is surely that C/C++ are well within the
black hole now with no chance of escaping its mighty pull.
<end quote>

And I see that you snipped the data I presented to substantiate my
claim:

C is today a very popular programming langage.
 
S

Seebs

If that's not the implementation of the algorithm, then what is it?

The phrase "the implementation" refers to the compiler and standard
library.

If you are not the person who is responsible for implementing printf()
and fopen(), you are not working on the implementation.

-s
 
S

Seebs

BITCH, you tell what "I acknowlege" on more time, .. you don't want to
war with me.

I suspect you'll find that he does, for the following reasons:
1. He's sometimes pretty ready to take up an offered fight.
2. He's not dumb enough to be scared of Internet tough guys.

BTW: *plonk*

-s
 
J

jacob navia

Le 18/09/11 09:03, Seebs a écrit :
I suspect you'll find that he does, for the following reasons:
1. He's sometimes pretty ready to take up an offered fight.

Maybe but I presented hard data to substaintiate my claims,
and didn't resort to any insults.

We are constantly being harassed by the "C is dead" crowd, and
I think that enough is enough: the facts tell another story.
 
K

Keith Thompson

henry eshbaugh said:
The "implementation" includes the compiler, the standard library, the
linker, and probably some other things.


The simple rule is to avoid defining *any* identifier starting with an
identifier, unless you're writing a C implementation.

It's not quite that simple.  Identifiers starting with two underscores,
or with an underscore followed by an upper case letter, are reserved for
all purposes.  Identifiers starting with an underscore *not* followed by
another underscore or by an upper case letter are reserved in fewer
contexts.  So you *can* use such identifiers in your own code, but it's
easier not to.
[...]

With my compiler, symbols are _[name]. So, it comes out to be
___reverse_list(), which isn't too bad.

What do you mean, it "isn't too bad"?
But it's a coding style issue anyway, and is trivial.

It's not merely coding style. The identifier "__reverse_list" is
reserved to the implementation. Using it in your own code makes your
program's behavior undefined.
 
K

Keith Thompson

Seebs said:
I suspect you'll find that he does, for the following reasons:
1. He's sometimes pretty ready to take up an offered fight.
2. He's not dumb enough to be scared of Internet tough guys.

BTW: *plonk*

FYI, I just realized I had already plonked him some time ago,
but he's using a different fake e-mail address (he previously used
<[email protected]>).
 
J

James Kuyper

FYI, I just realized I had already plonked him some time ago,
but he's using a different fake e-mail address (he previously used
<[email protected]>).

It seems to me we've had several assaults recently, quite probably all
from the same person, which all followed the same general pattern. They
started with reasonable messages, not easily distinguishable from the
general background of newbie questions. Then the poster starts
obstinately standing by his own opinions in conflict with the
information he's been given by many other people; regrettably, that's
also not all that unusual a pattern in this newsgroup. Then, he suddenly
degenerates into incoherent rage, ranting and raving about something
that seems completely unrelated to the topics being discussed in the
messages he's nominally responding to. One of the more unusual features
is that these rants are much shorter than is usual for this newsgroup.

I can understand ordinary trolling - it takes a lot less work and a lot
less intelligence to "show" that you're "smarter" than other people by
trying to fool them, than by actually demonstrating a superior
understanding of a subject. This feels like something quite different to
me. One could almost imagine that the rage being expressed during the
terminal stages of one of these infestations is sincere. The last time
this happened, several people suggested that the change in mood was due
to drug abuse, which seems plausible. But does anyone have any clue as
to what this guy thinks he's getting angry about when he's high? Insofar
as there's any pattern to his ranges, he seems to think it's something
political, and that's about as far as I can get in understanding it.
It's probably not worth thinking about, but I just can't form a
plausible mental model of the person who bothers perpetrating this nonsense.
 
N

Nick Keighley

It seems to me we've had several assaults recently, quite probably all
from the same person, which all followed the same general pattern. They
started with reasonable messages, not easily distinguishable from the
general background of newbie questions. Then the poster starts
obstinately standing by his own opinions in conflict with the
information he's been given by many other people; regrettably, that's
also not all that unusual a pattern in this newsgroup. Then, he suddenly
degenerates into incoherent rage, ranting and raving about something
that seems completely unrelated to the topics being discussed in the
messages he's nominally responding to. One of the more unusual features
is that these rants are much shorter than is usual for this newsgroup.

I can understand ordinary trolling - it takes a lot less work and a lot
less intelligence to "show" that you're "smarter" than other people by
trying to fool them, than by actually demonstrating a superior
understanding of a subject. This feels like something quite different to
me. One could almost imagine that the rage being expressed during the
terminal stages of one of these infestations is sincere. The last time
this happened, several people suggested that the change in mood was due
to drug abuse, which seems plausible. But does anyone have any clue as
to what this guy thinks he's getting angry about when he's high? Insofar
as there's any pattern to his ranges, he seems to think it's something
political, and that's about as far as I can get in understanding it.
It's probably not worth thinking about, but I just can't form a
plausible mental model of the person who bothers perpetrating this nonsense.

I think he doesn'tlike being contradicted. How this works in the real
world I can't imagine. Maybe he just bottles up his real world rage
and spews it out on usenet.
 
H

henry eshbaugh

HENRY Eshbaugh wrote:

)> Readable, elegant, correct: pick any two!
)
) I just noticed the bug. My bad.
)
)
) void reverse_list(ListElement *head)
) {
)         if (head == NULL) return;
)         __reverse_list(head->next, head);
)         return;
) }
)
) void __reverse_list(ListElement *this, ListElement *next)
) {
)         if (this == NULL) return;
)
)         if (next->next) __reverse_list(next, next->next);
)
)         next->next = this;
) }
)
) Now it works.

Doesn't that effectively push the entire linked list up the stack first,
and then go down the stack again to build the reversed list ?
Seems wasteful to me, when it can be done in O(1) space.

SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Yeah. It's impossible to do it in O(1) time, considering that for
every node in the list, there's a pointer to change. Ramming it up the
stack and popping it off runs in O(n) time, which is acceptable, but
could cause a stack overflow.
 

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

Forum statistics

Threads
473,769
Messages
2,569,579
Members
45,053
Latest member
BrodieSola

Latest Threads

Top