Programming Puzzle

[Julie]

A decent swap function should perform a value equality check both for
safety and run-time efficiency, especially when this does not impose any
space/time concerns, perhaps in the style:

This is purely subjective. Stating preconditions in the functional interface
description is perfectly appropriate.

Sanity checks can be implemented when/where warranted, but mostly serve to
verify that the user is obeying the preconditions.

template<class T>
void swap(T &a, T &b)
{
if(a!=b)
{
// ...
}
}

In any case, we should stick with std::swap and provide specialisations
when necessary.

Yeah, yeah, but that isn't what we are talking about.

 

[Ioannis Vranos]

A decent swap function should perform a value equality check both for
safety and run-time efficiency, especially when this does not impose any
space/time concerns, perhaps in the style:


template<class T>
void swap(T &a, T &b)
{
if(a!=b)
{
// ...
}
}



In any case, we should stick with std::swap and provide specialisations
when necessary.

That said, I would not place the equality/inequality check for the
possibility of the same variable passed in mind, but for efficiency. But
I would use a temporary variable anyway.






Regards,

Ioannis Vranos

 

[Julie]

Thanks!


There is no disagreement on the former, either. Just a difference in the
wording of the problem. To me, two pointers or references that refer to the
same memory location are still two differrent variables. But you are
correct...the memory locations being swapped in such a case are identical,
thus you could rightfuly call them "the same".

The importance, though, as it relates to actually *writing* a swap function,
is that the swap function itself cannot guarantee in advance that the
reference or pointer parameters passed into it will not at some point refer
to the same location in memory. Therefore, it is vital that such a swap
function include a guard against swapping the "same" variable. (Unless, of
course, you clearly document that the function does *not* guard against such
behavior, and declare such usage of the function as a violation of its
contract, generating undefined behavior.)

-Howard

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.

 

[Ioannis Vranos]

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.

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






Regards,

Ioannis Vranos

 

[Mabden]

In <[email protected]> "Mabden"

Chapter and verse, please.

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

 

[Julie]

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

Regards,

Ioannis Vranos

It definitely wouldn't be necessary (or warranted!) if using the xor swap in an
implementation of bubble sort.

There.

 

[Mabden]

Ooops.. return !(x | 0x0001);

Also not correct. That sets bit 1, which still gives you false as the final
result.

I think what you meant was "return !(x & 0x0001);". That test tells you if
bit 1 is set, which is true for any odd number. But, even that test only
checks if it's even (i.e., k*(2^1)) for some integer value k). The question
asks if it's a power of 2, which means 2^n for some integer value n.

A [positive] integer which is exactly a power of two has one and only one
bit set. (i.e., 0001=2^0, 0010=2^1, 0100=2^2, 1000=2^3, for a 4-bit
integer) So you need to loop through the bits, counting how many are set,
and it there is only one bit set, then it's a power of two. (And, you need
to know the size of the integer in bits first, as well as whether negative
numbers are allowed, in which case you also need to know how those are
represented in your system).

You're right I meant "&", but I thought the question was whether the number
was divisible by 2, not a power of 2.

 

[Ioannis Vranos]

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

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






Regards,

Ioannis Vranos

 

[Ioannis Vranos]

It definitely wouldn't be necessary (or warranted!) if using the xor swap in an
implementation of bubble sort.

There.

Why?






Regards,

Ioannis Vranos

 

[Howard]

Why?

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]

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!

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

 

[Default User]

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

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

 

[Xenos]

In any case, an equality check is reasonable to be placed for efficiency
reasons (come on, doesn't this sound natural to you?).

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

 

[Andre Kostur]

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

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]

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)

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]

(For main

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

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.

 

[Tom]

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.

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(1000);
b.push_back(2000);
b.push_back(3000);
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

 

[Branimir Maksimovic]

Owner@buster ~/projects/cxx/quine
$ g++ -o quine-1.5.exe quine-1.5.cpp

Owner@buster ~/projects/cxx/quine
$ ./quine-1.5.exe | cmp - quine-1.5.cpp

Owner@buster ~/projects/cxx/quine
$ ./quine-1.5.exe

well it looks impressive, thanks.

Greetings, Bane.

 

[Gordon Burditt]

Not one, but *two* ways to do it have been

Please describe (in code) a situation where two variables share the same memory
location.

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, &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]

A union?

Nope -- a union is still a single variable, with just different ways to access
it.

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.

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.