Re: "Sorting" assignment

On Feb 10, 2:34 pm, spinoza1111 <spinoza1...@xxxxxxxxx> wrote:
On Feb 10, 2:16 pm,spinoza1111<spinoza1...@xxxxxxxxx> wrote:





On Feb 10, 8:33 am, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:

Malcolm McLean said:

"spinoza1111" <spinoza1...@xxxxxxxxx> wrote in message
On Feb 9, 2:42 am, Richard Heathfield <r...@xxxxxxxxxxxxxxx> wrote:

<snip>

memcpy(buf, left, BUF_LEN);

Of course, if memcpy is (1) implemented in C itself and (2) byte by
byte, Heathfield has just wasted our time.

Yes.

No.

In actual fact memcpy() is sometimes implemented as a rather slow
byte by byte loop. It's the only thing you can do, if you write it in C.

In actual fact memcpy() is typically implemented as a heavily optimised and
astoundingly fast copying routine that uses the target platform's fastest

...and strlen() isn't. How convenient that is for you!

possible way of copying data around the place. Whilst the C Standard
doesn't require this, it is clearly a very desirable thing to do, and so
sensible implementors will do it if it is possible to do it. In the rare
circumstances where only a byte-by-byte copy is available on the target
platform, c'est la vie - you can't implement something that the hardware

...as the French would say?

won't support, but the code I showed will still behave, on that platform,
as fast as can reasonably be expected of portable code. So where there's

But it will be a Complete Waste of Time, since the memcpys doing the
exchange are byte by byte by byte.

nothing to gain from using memcpy, you gain nothing but at least you lose
nothing significant either - and where there is something to gain from

Save your understanding of the truth of Malcolm's claim. Oh well...

using memcpy, you gain that something. Sounds like a win-draw to me. Not
quite as good as a win-win, but the best you can get without writing code
specific to each platform.

No, the best solution would be a simple for loop that XORs each byte
(the following is extempore and written in a C based pseudo code and
not C; it is untested):

for (int intIndex1 = 0; intIndex1 < length; intIndex1++)
*(ptrToA+intIndex1) = *(ptrToA+intIndex1)  ^ *(ptrToB+intIndex1);

WRONG : my error. The body of the for loop should be

{
*(ptrToA+intIndex1) ^= *(ptrToB+intIndex1);
*(ptrToB+intIndex1) ^= *(ptrToA+intIndex1);
*(ptrToA+intIndex1) ^= *(ptrToB+intIndex1);





}

The above solution is definitive since it won't use, once recoded in
C, any library functions therefore its efficiency is independent of
the library.

The next optimization step is not to use a "buffer". It is to SEARCH
AHEAD starting at a and to SEARCH AHEAD starting at b for a pair of
characters that are different so that we avoid unnecessary XOR.

The following is untested, theory-based C based pseudocode and not C.
As above we assume that a and b are safely known to be the same
length.

int intIndex1 = 0;
while(intIndex1 < length)
{
intIndex1 =
mininum(phonycspn(ptrToA+intIndex1, *(ptrToB+intIndex1)),
phonycspn(ptrToB+intindex1, *(ptrToA+intIndex1)));
*(ptrToA+intIndex1) = *(ptrToA+intIndex1) ^ *(ptrToA+intIndex1);
intIndex1++;

WRONG : my error. The body of the for loop should be

{
*(ptrToA+intIndex1) ^= *(ptrToB+intIndex1);
*(ptrToB+intIndex1) ^= *(ptrToA+intIndex1);
*(ptrToA+intIndex1) ^= *(ptrToB+intIndex1);

}

The point I've made remains unchanged: that you don't need to
unnecessarily move data around unlike you like that sort of thing as
does the concentration camp guard like shoving people around.





}

IF strcspn in the library is implemented fast it may replace phonycspn
for a solution which avoids all unnecessary data movement. The use of
"mininum" can of course be replaced by the ternary operator ?:. The
"buffer" solution does not. On many if not most computers, scanning is
cheaper than data movement.

I have deliberately used "extempore untested C based pseudo code"
rather than running code examples on my nice lccwin32 C compiler
because given the utter randomness of C libraries, the goal needs to
be first getting a pseudo code template that avoids as much bull ***
as possible, starting with the use of "buffers". I am certain that it
will be flamebait for incompetents, but hey what the hell.

The hypostatization and reification of the very word "buffer" means
that the programmer, once deciding, d'oh me need use buffer me need
use buffer must use buffer, the goal becomes neither truth nor
efficiency but instead Homer's using the goddamn buffer.

<snip>

If memcpy stays in C and moves byte
by byte, you've written code with no meaning while starting to make
nasty remarks about yet another person.

I'm used to having nasty remarks made about me.

We all are. I have noticed, however, that the frequency of nasty remarks I
read about myself has dropped significantly since I dropped Mr Nilges into
my killfile.

Bite my ass. All you do is conduct third party discussions and
threaten to trash others if they don't agree with you. You've posted
code which typically is NOT appreciated by hard working maintenance
programmers that snarl in disgust at your cleverness, because it's not
minimized anything in the general case, which happens to be the only
interesting case.

I've shown that the process of code development CAN, in a sense, be
driven, not by "efficiency" per se (where that's an engineering ratio
properly understood) but by an elegant desire, to see if we could
eliminate the overlarge memory footprint taken by your less than
totally useful code, and all unnecessary operations, without assuming
a goddamn thing about the artifact INCLUDING the C library.

<snip>

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -

Sorry for screwing up the exchange in the untested extempore C based
pseudocode. I last used it in IBM mainframe assembler circa 1980: it
was a well known trick at the time. Today I primarily use exchange in
the context of atomic operations in .Net which set semaphores and the
three step exchange is useless for this purpose, since it can be
interrupted at any step.

Of course, I could have CLAIMED that my "untested extempore C based
pseudocode" redefines and overloads ^ as exchange, but that would have
been a lie.

Wikipedia appears to have an excellent article including a correctness
proof for exchange: http://en.wikipedia.org/wiki/Xor_swap_algorithm.
.

Quantcast