Quiz

Learn or Teach General Knowledge Related to Coding or Hacking

Moderators: g3nuin3, SpeedWing, WhiteHat, mezzo

Re: Quiz

Postby L. Spiro » Mon Dec 07, 2009 6:55 am

CoMPMStR wrote:Here's another submission:

#4: Isn't the ternary operator much faster than calling the std::max function?
Code: Select all
unsigned long ulMax = 0UL;
for ( size_t I = 0UL; I < vVector.size(); ++I ) {
    ulMax = (ulMax <= vVector[I]) ? vVector[I] : ulMax;
}


std::max() is a templated function so it will resolve to basically the same thing.
Is there something else you could do?


CoMPMStR wrote:#5: If we're just toggling an option on or off (0 or 1), instead of doing ulSwitch=!ulSwitch; just do a simple xor by 1. ulSwitch^=1;, I know for a fact that all bitwise operations are faster than anything else and the logical not (!) is NOT a bitwise operation. :D


Correct.
If you want to switch back and forth between 0 and 1, ^= 1 is the hands-down fastest way to go about it.



troublesh00ter wrote:
Code: Select all
ulX = ulIndex & (16UL - 1UL);   
ulY = (ulIndex - ulX) / 16UL;


As 16 is a power of 2 we can use a bitwise AND instead of %. Something that I learned from this quiz is that the compiler will put 15 instead of 16 - 1, normally I would write 15UL but I suppose this way the intention is clearer.
A thank you to CoMPMStR (if the answer is correct) for sparking a brain cell with the 'bitwise operation' comment.


Is there something more you can do to this?


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Mon Dec 07, 2009 10:47 am

Well after some searching I think I've found the answer to #3:

Code: Select all
for ( int I = static_cast<int>(vVector.size()); I--; ) {
   // Do whatever.
}

Since the conditional will always break on 0, it can be set like this removing the redundant check. Notice that the decrement was switched from pre- to post-. This is because if it's set to pre- (--I) it will be set to 0 BEFORE it has a chance to run the last iteration, which means that vVector[0] would never be accessed! You also don't need the - 1UL for the simple fact that I is set then decreased before entering the loop, so if you set it to size() - 1UL the last element will never be accessed.


This seems like a good solution, so I'd say the same could work for #4: (I was going to suggest a do/while loop but that seems to be the same as a for loop :?).
Code: Select all
for ( size_t I = vVector.size(); I--; ) {
    ulMax = std::max( ulMax, vVector[I] );
}



Also, here's my "improvement" for #6:
Code: Select all
ulX = ulIndex & (16UL - 1UL);
ulY = ulIndex >> 4UL;

Seeing as how troublesh00ter was on the right track using bitwise operations to solve this one, he seemed to miss one vital piece. ;) I figured since it's dividing by a power of 2 (16UL), why not just use the SHR operator. I know that SHL3 (<< 3) is the same as * 8 so SHR4 (>> 4) is the same as / 16. Not sure what the extra subtraction was for though. :P
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Mon Dec 07, 2009 1:28 pm

CoMPMStR wrote:Well after some searching I think I've found the answer to #3:

Code: Select all
for ( int I = static_cast<int>(vVector.size()); I--; ) {
   // Do whatever.
}

Since the conditional will always break on 0, it can be set like this removing the redundant check. Notice that the decrement was switched from pre- to post-. This is because if it's set to pre- (--I) it will be set to 0 BEFORE it has a chance to run the last iteration, which means that vVector[0] would never be accessed! You also don't need the - 1UL for the simple fact that I is set then decreased before entering the loop, so if you set it to size() - 1UL the last element will never be accessed.


Is there something missing from this?



CoMPMStR wrote:This seems like a good solution, so I'd say the same could work for #4: (I was going to suggest a do/while loop but that seems to be the same as a for loop :?).
Code: Select all
for ( size_t I = vVector.size(); I--; ) {
    ulMax = std::max( ulMax, vVector[I] );
}


Correct.


CoMPMStR wrote:Also, here's my "improvement" for #6:
Code: Select all
ulX = ulIndex & (16UL - 1UL);
ulY = ulIndex >> 4UL;

Seeing as how troublesh00ter was on the right track using bitwise operations to solve this one, he seemed to miss one vital piece. ;) I figured since it's dividing by a power of 2 (16UL), why not just use the SHR operator. I know that SHL3 (<< 3) is the same as * 8 so SHR4 (>> 4) is the same as / 16. Not sure what the extra subtraction was for though. :P


Correct.
The subtraction is to set all of the bits below 16 to 1.
0x10 = 10000.
0x0F = 01111.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby troublesh00ter » Mon Dec 07, 2009 1:43 pm

*me goes on a tour to better understand bitwise operations*
troublesh00ter
Sir Hacks-A-Lot
 
Posts: 30
Joined: Mon Jun 01, 2009 2:54 pm
Location: The Netherlands

Re: Quiz

Postby CoMPMStR » Mon Dec 07, 2009 2:21 pm

Did I forget something? Maybe the static_cast conversion? I don't know what its purpose is exactly.

Code: Select all
for ( int I = vVector.size(); I--; ) {
   // Do whatever.
}


Also, the subtraction I was referring to was in troublesh00ter's #6 submission. He put ulY = (ulIndex - ulX) / 16UL; and I didn't understand why the - ulX was included.
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Mon Dec 07, 2009 5:19 pm

You missed one of the most important details.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Tue Dec 08, 2009 4:17 am

After a quick look-over, I noticed one thing that's different from my #4 solution. Should I have used size_t instead of int?

Code: Select all
for ( size_t I = vVector.size(); I--; ) {
   // Do whatever.
}
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Tue Dec 08, 2009 7:58 am

Correct.
#1:
It is encouraged that you use the exact same types for your counter and the type used to indicate the length of the loop. This is the best way to ensure there is no truncation. Here we used size_t only because that is the type returned by vector<>.size(). This actually matters here because size_t changes size per-platform. unsigned long or a typedef of it is most common.
#2:
But even if you violate rule #1 you must at least keep the same signs.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby L. Spiro » Tue Dec 08, 2009 12:28 pm

Be careful of #7.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Tue Dec 08, 2009 3:16 pm

It already seems like a normal way to do things. I'll have to say:

Code: Select all
for ( int I = iTotal; I--; ) {
    // Do something.
}
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Tue Dec 08, 2009 3:58 pm

Is there a better way to write that?


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Tue Dec 08, 2009 5:29 pm

Hmmm.. how about:
Code: Select all
int I = iTotal;
for ( ; I--; ) {
    // Do something.
}

Or is this no different than before?
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Tue Dec 08, 2009 5:51 pm

Worse than before; it leaves the original code with an unused local variable that, for all we know, could later cause binding issues or declaration clashes.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

Re: Quiz

Postby CoMPMStR » Wed Dec 09, 2009 3:03 am

Another shot in the dark, this time I'll go back to the original snippet. There're only so many ways to rewrite a loop:
Code: Select all
for ( int I; I++ < iTotal; ) {
    int index = I - 1;
    // Do something.
}

The only problem with this is that you will have to use I - 1 rather than just I.
Image

______________________________________________________
My Utilities:
CT <-> LSSAVE Converter
LSS Visual Dialog Designer
.NET Trainer Helper Library

~Whether you think you can or you think you can't, you're right.

L. Spiro wrote:In my left hand is a red pill. If you take it I will show you the truth. I lost my right hand in the war, so I’m afraid you’re stuck with the red pill.
User avatar
CoMPMStR
(P)ot (I)n (M)y (P)ipe
 
Posts: 451
Joined: Thu Mar 06, 2008 7:50 am
Location: Best Place

Re: Quiz

Postby L. Spiro » Wed Dec 09, 2009 7:09 am

You seem to be forgetting one of the most trivial of optimization rules you learned years ago.


L. Spiro
Our songs remind you of songs you’ve never heard.
User avatar
L. Spiro
L. Spiro
 
Posts: 3129
Joined: Mon Jul 17, 2006 10:14 pm
Location: Tokyo, Japan

PreviousNext

Return to Knowledge Base

Who is online

Users browsing this forum: No registered users and 0 guests

cron