Programming Puzzle

[Ioannis Vranos]

Re: Programming Puzzle

Mabden wrote:
[color=blue]
> C:\TEMP>type test.c
> #include <stdio.h>
>
> int main(void) {
> int *foo = NULL;
>
> fprintf(stdout, "%i\n", *foo);
> }
>
>
> C:\TEMP>cl -c test.c
> Microsoft (R) C/C++ Optimizing Compiler Version 8.00c
> Copyright (c) Microsoft Corp 1984-1993. All rights reserved.
>
> test.c
> test.c(7) : warning C4035: 'main' : no return value[/color]


In C90 a return statement is required, in C99 it is not.






Regards,

Ioannis Vranos

[Ioannis Vranos]

Re: Swapping

Julie wrote:
[color=blue]
> It definitely wouldn't be necessary (or warranted!) if using the xor swap in an
> implementation of bubble sort.
>
> There.[/color]


Why?






Regards,

Ioannis Vranos

[Howard]

Re: Swapping


"Ioannis Vranos" <ivr@guesswh.at .grad.com> wrote in message
news:cbq104$k86 $3@ulysses.noc. ntua.gr...[color=blue]
> Julie wrote:
>[color=green]
> > It definitely wouldn't be necessary (or warranted!) if using the xor[/color][/color]
swap in an[color=blue][color=green]
> > implementation of bubble sort.
> >
> > There.[/color]
>
>
> Why?
>
>[/color]

Oooh, I know, I know! If used in a bubble sort, then you're *reducing*
efficiency, because you only call the swap after first determining that two
values are out of order...and that means you've already *done* the
comparison! :-)

-Howard

[Ioannis Vranos]

Re: Swapping

Howard wrote:
[color=blue]
> Oooh, I know, I know! If used in a bubble sort, then you're *reducing*
> efficiency, because you only call the swap after first determining that two
> values are out of order...and that means you've already *done* the
> comparison! :-)[/color]



Yes I realised it myself after pressing the send button, however the
whole topic with xor is really stupid already.


And in this case, using xor for swapping in bubble sort...


I think this xor joke must end sometime now. After all it is a
specialised solution.






Regards,

Ioannis Vranos

[Xenos]

Re: Swapping


"Ioannis Vranos" <ivr@guesswh.at .grad.com> wrote in message
news:cbq0k5$k86 $1@ulysses.noc. ntua.gr...
[color=blue]
> In any case, an equality check is reasonable to be placed for efficiency
> reasons (come on, doesn't this sound natural to you?).[/color]

I don't think so. If I understand you correctly, you are optimizing for
the special (both object are the same), at the expensive of the normal case.
Unless your code is swapping big objects and tried to swap the same object
with itself often, you save nothing. The swap times of the normal case
(objects are different) will increase, although it will probably be
unnoticably small. The point being, the check added nothing for efficiency.

DrX

[Default User]

Re: Programming Puzzle

Mabden wrote:[color=blue]
>
> "Dan Pop" <Dan.Pop@cern.c h> wrote in message
> news:cbp8hp$kgb $17@sunnews.cer n.ch...[color=green]
> > In <zoHDc.3345$cr5 .486@newssvr27. news.prodigy.co m> "Mabden"[/color]
> <mabden@sbc_glo bal.net> writes:[/color]
[color=blue][color=green][color=darkred]
> > >You'll get a warning saying main() has no return value.[/color]
> >
> > Chapter and verse, please.[/color][/color]
[color=blue]
> Microsoft (R) C/C++ Optimizing Compiler Version 8.00c
> Copyright (c) Microsoft Corp 1984-1993. All rights reserved.
>
> test.c
> test.c(7) : warning C4035: 'main' : no return value[/color]


Just because your compiler decides to issue one doesn't mean it is
required (it's not) or that it will happen on other platforms.

Compilers are free to issue whatever diagnostics they wish. Many produce
a warning for things like:

if (a = 1)
{
}


They could issue warnings about misspellings in your comments if they
felt like it.



Brian Rodenborn

[Andre Kostur]

Re: Swapping

Ioannis Vranos <ivr@guesswh.at .grad.com> wrote in
news:cbq0k5$k86 $1@ulysses.noc. ntua.gr:
[color=blue]
> Julie wrote:
>[color=green]
>> Agreed.
>>
>> For me, saying that 'swap operates on two variables' would be
>> sufficient, but for the sake of clarity, it could be documented that
>> references to the same variable leads to undefined behavior.[/color]
>
>
>
> However the whole approach is funny, since an equality check should be
> placed for efficiency reasons anyway.
>
> On the other hand if someone used the swap function passing the same
> object twice explicitly, he would be an idiot (but the operation would
> be safe).
>
>
> In any case, an equality check is reasonable to be placed for
> efficiency reasons (come on, doesn't this sound natural to you?).[/color]

Actually, no. Consider:

1) The comparison of the two objects may be "expensive" (let's assume on
the order of seconds, just to be extreme)
2) The number of times in my own code that I'm going to attempt to swap
two variables that are equal is 0.

This means that I have to pay for this equality check every time I swap
two variables, just on the off chance that they might be the same.

Insert standard quotes about "premature optimization is the root of all
evil" (Knuth), and "More computing sins are committed in the name of
efficiency (without necessarily achieving it) than for any other single
reason - including blind stupidity." (W.A. Wulf)

[Ioannis Vranos]

Re: Swapping

Andre Kostur wrote:
[color=blue]
> Actually, no. Consider:
>
> 1) The comparison of the two objects may be "expensive" (let's assume on
> the order of seconds, just to be extreme)
> 2) The number of times in my own code that I'm going to attempt to swap
> two variables that are equal is 0.
>
> This means that I have to pay for this equality check every time I swap
> two variables, just on the off chance that they might be the same.
>
> Insert standard quotes about "premature optimization is the root of all
> evil" (Knuth), and "More computing sins are committed in the name of
> efficiency (without necessarily achieving it) than for any other single
> reason - including blind stupidity." (W.A. Wulf)[/color]



Indeed regarding this particular swap implementation concerning
integrals with the use of XOR, you are right. There are not efficiency
gains from such a comparison.


However for the general case where a temporary is used, such a
comparison produces efficiency gains (for the general use).


How would you implement the general form of std::swap for example?






Regards,

Ioannis Vranos

[Dik T. Winter]

Re: Programming Puzzle

In article <cbq0t9$k86$2@u lysses.noc.ntua .gr> Ioannis Vranos <ivr@guesswh.at .grad.com> writes:

(For main:)
[color=blue]
> In C90 a return statement is required, in C99 it is not.[/color]

This is wrong. In both a return statement is not required, but in
C90 when the return statement is missing an undefined value is
returned to the environment, in C90 the value is defined. (Note
that it does *not* make it undefined behaviour in C90. It becomes
undefined behaviour when you call the function from within your
program and attempt to use the "returned" value.)

BTW, C90 also allows:
int main(void) { return;}
with the same effect; according to the draft this is not allowed in C99.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Tom]

Re: Swapping Bullshit

JKop wrote:
[color=blue]
> Am I the only person here that thinks it's complete bullshit to think you
> can swap the values of two variables without a temporary variable?! It
> simply cannot be done. Why? Consider this, you have two containers, each of
> capacity 3 litres. Each of them is filled with 2 litres of water. Swap the
> water from the containers. Okay... let's just poor all of one of them into
> the other. Mammy mammy! It was an accident, I didn't realize you can't put 4
> litres of water into a 3 litre container.[/color]

Depends what you mean by "temporary variable." Most or all of the
standard containers (std::vector, std::list, std::map, etc.) have a
swap member function that performs the swap by swapping the internal
pointers behind the scenes - no temporary container is used. The
standard utility function std::swap (in <algorithm>), in turn, is
specialized on the standard containers to use the swap member
function. So at the end of the day, a temporary pointer is used
internally, but no temporary container is used. For example:

std::vector<int > a, b;
a.push_back(1);
a.push_back(2);
b.push_back(100 0);
b.push_back(200 0);
b.push_back(300 0);
std::swap(a, b);

No temporary std::vector is required for the call to std::swap in the
above code. Internally, a's and b's pointers to their respective data
are swapped - no data is actually copied into a temporary. Obviously,
there is a temporary pointer used, though.

The non-specialized version of std::swap uses a temporary.

Best regards,

Tom

[Gordon Burditt]

Re: Swapping Bullshit

>> >Not one, but *two* ways to do it have been[color=blue][color=green][color=darkred]
>> >shown in this thread. Of course it will break down if those variables
>> >happen to share the same memory location, which can be the case if using
>> >pointers and indirecting through them.[/color][/color]
>
>Please describe (in code) a situation where two variables share the same memory
>location.[/color]

A union?

You could also end up calling swap() on to pointers that just happen
to sometimes end up being equal unless you carefully test that it's not.
It may be preferable to make swap() robust enough to deal with this
situation.

#include "card_t.h" /* This is part of the program, NOT the implementation*/
#define DECKSIZE 52
....
int i,j;
card_t deck[DECKSIZE];

/* bogo-shuffle the cards */
for (i = 0; i < DECKSIZE; i++) {
for (j = 0; j < DECKSIZE; j++) {
/*
* DO NOT CHANGE THE LINE OF CODE BELOW.
* Note: rand() % 2 is used here because it is
* a poor random number generator in many
* implementations , and if it isn't possible to
* cheat, *THEY* will break your legs repeatedly
* and cut off your supply of semicolons.
*/
if (rand() % 2) {
swap(&deck[i], &deck[j]);
}
}
}

Now, you can put a "&& i !=j " clause in the if statement, but
some may object to that on efficiency grounds.

Gordon L. Burditt

[Julie]

Re: Swapping

Gordon Burditt wrote:[color=blue]
>[color=green][color=darkred]
> >> >Not one, but *two* ways to do it have been
> >> >shown in this thread. Of course it will break down if those variables
> >> >happen to share the same memory location, which can be the case if using
> >> >pointers and indirecting through them.[/color]
> >
> >Please describe (in code) a situation where two variables share the same memory
> >location.[/color]
>
> A union?[/color]

Nope -- a union is still a single variable, with just different ways to access
it.
[color=blue]
> You could also end up calling swap() on to pointers that just happen
> to sometimes end up being equal unless you carefully test that it's not.
> It may be preferable to make swap() robust enough to deal with this
> situation.[/color]

Yes, I realize all what you said -- however, my point was/is: if you
'implement the xor swap function that operates on two variables', you don't
need the check, because you can't have two variables that share the same memory
location. The check is therefore redundant, and not warranted. If you change
the definition to 'implement an xor swap function' or 'implement an xor swap
function that takes two parameters', then the check *would* be warranted.

In case you still can't see my points:

- The original precondition of two numbers (variables) is sufficient to
eliminate the need for the check.

- Two variables *cannot* share the same memory location.

[Kai-Uwe Bux]

Re: Swapping Bullshit

Gordon Burditt wrote:[color=blue]
> #include "card_t.h" /* This is part of the program, NOT the
> #implementation */ define DECKSIZE 52
> ...
> int i,j;
> card_t deck[DECKSIZE];
>
> /* bogo-shuffle the cards */
> for (i = 0; i < DECKSIZE; i++) {
> for (j = 0; j < DECKSIZE; j++) {
> /*
> * DO NOT CHANGE THE LINE OF CODE BELOW.
> * Note: rand() % 2 is used here because it is
> * a poor random number generator in many
> * implementations , and if it isn't possible to
> * cheat, *THEY* will break your legs repeatedly
> * and cut off your supply of semicolons.
> */
> if (rand() % 2) {
> swap(&deck[i], &deck[j]);
> }
> }
> }[/color]


Hi,

I apologize, for this might not be the topic of this thread, however I feel
compelled to comment on this bogo-shuffle: is that taken from a text on how
*not* to generate a random permutation?

a) The use of rand() % 2 is bad. In a different thread I came across a
random number generator that would produce a strictly alternating sequence
of bits when used this way. The funny comment indicates that the author was
acutally aware of this shortcoming.

b) The method has quadratic runtime in DECKSIZE. Clearly a random-shuffle
can and should be done in linear time.

c) Finally, even with a perfect random number generator, this method is
guaranteed *not* to give equal probabilities to the different permutations.
For small DECKSIZE, the difference is even noticable.


Best

Kai-Uwe

[Risto Lankinen]

Re: Swapping Bullshit


"Julie" <julie@nospam.c om> wrote in message
news:40E040AA.E 6AC3743@nospam. com...[color=blue]
>
> Please describe a situation where two variables share the same memory
> location.[/color]

There is a doubly-linked-list algorithm that uses the same
memory location for both forward and backward pointers.
They are stored as XORred, and given the address of an
anchor node, the chain of nodes can be traversed at either
direction.

- Risto -

[Risto Lankinen]

Re: Swapping thing


"Ioannis Vranos" <ivr@guesswh.at .grad.com> wrote in message
news:cbprc1$6tu $3@ulysses.noc. ntua.gr...[color=blue]
>
> You are right about that, however in reality a decent swap
> implementation would check if the passed arguments have the same value
> so as to avoid unneeded operations.[/color]

There are some algorithms for which the check itself is
an unneeded operation (i.e. which can be proved to be
"correct by construction") become inefficient if the swap
function itself makes such a redundant check. Various
sort algorithms belong to this category, because it is a
characteristic of the sort algorithm [and not a safety net
of swap] to compare items before swapping.

But then there are also some algorithms for which the
check is - if perhaps not redundant - but inefficient as
long as the swap preserves original value in the case of
self-swap.

[I know it's easy to code "more correctly", but] one such
algorithm would be string reversal which might be coded
so that the middle element will be "swapped" with itself
just before the algorithm tests for the termination. Then
you don't need to make an extra check every time before
entering the loop - you just enter the loop every time and
let it do the "right thing" even with strings of length one.

More examples can be found from permutation generation
algorithms, where a straightforward algorithm might benefit
from not having to make the check every time, even given
the cost of occasional self-swap.

- Risto -