You need to get rid of the last else-if
else if(addr->getNext()!=nullptr)
{addr=addr->getNext(); ++pos;}^ because this will stop updating addr, once addr->getNext() is null, therefore addr will never be null, and pos will never be updated either. Just get rid of the "if" part
else {addr=addr->getNext(); ++pos;}Now, addr will be set to null when addr->getNext() becomes null, and the while loop will end. The updated code with RulerOfNothing's simplification etc is:
template <class Thing>
Node<Thing>* getNode(Node<Thing>* head, int index=0)
{
Node<Thing>* addr=head;
int pos=1;
while(addr != nullptr)
{
if(pos == index)
return addr;
else if(addr->getNext()==nullptr&&index==0)
return addr;
else
{
addr=addr->getNext(); ++pos;
}
}
return nullptr;
}
The rest of my suggested fixes would include reordering the if statements so that it's not doing tons of unnecessary calculations then throwing them out when a rare condition isn't met. For example, this line:
else if(addr->getNext()==nullptr&&index==0)
is doing a complex calculation first, every time, then checking whether it's even relevant (index==0). Putting "index==0" first would speed this up for cases where index wasn't zero, since it would skip the expensive function call.
Also, it's checking "if pos==index" every time through the loop, without excluding this check in the times when index==0 is true (so pos==index can never be true at the same time index==0, so there's no need to check
both in the same iteration). By reordering things to skip the pos==index check when index==0 then you can save clock cycles in the index==0 cases. e.g.
template <class Thing>
Node<Thing>* getNode(Node<Thing>* head, int index=0)
{
Node<Thing>* addr=head;
int pos=1;
while(addr != nullptr)
{
if(index==0) // it makes sense for the "get the last node" code to be the default branch, because it will by definition need to read more nodes than the index-finders
{
if(addr->getNext()==nullptr) // doing this check after index==0 check means this check is skipped if index!=0, which speeds up
return addr;
}
else // breaking up the preceding if statement allows us to skip the "pos==index" case when we already know index==0
if(pos == index)
return addr;
// getting rid of the "else" here means both branches drop in here unless they returned an address
addr=addr->getNext(); ++pos;
// and we don't have to worry is getNext was null, because it's setting addr to null for us, for free, which ends the loop.
}
return nullptr;
}
Well that's got index==0 case down to two if-checks per loop, one always true, one usually false. That still means the instruction pipeline will be flushed every single iteration (except for the final one, but that is followed by a stack return, so it's not going to help). We can improve that by assuming we didn't find the end of the list, as the default if-branch
template <class Thing>
Node<Thing>* getNode(Node<Thing>* head, int index=0)
{
Node<Thing>* addr=head;
int pos=1;
while(addr != nullptr)
{
if(index==0) // it makes sense for the "get the last node" code to be the default branch, because it will by definition need to read more nodes than the index-finders
{
if(addr->getNext() != nullptr) // doing this check after index==0 check means this check is skipped if index!=0, which speeds up
{
// "true" does nothing
}
else // making the final return on the else branch tells the compiler to assume it's rare
return addr;
}
else // breaking up the preceding if statement allows us to skip the "pos==index" case when we already know index==0
if(pos == index)
return addr;
// getting rid of the "else" here means both branches drop in here unless they returned an address
addr=addr->getNext(); ++pos;
// and we don't have to worry is getNext was null, because it's setting addr to null for us, for free, which ends the loop.
}
return nullptr;
}
So, "index==0" now only hits "true" if statements for all checks until the final one. "Index != 0" still flushes the pipeline every loop due to assuming index==0 is the default. To speed things up any further, the index==0 case should be split off into a separate "getTailNode" function. Also note, that you're creating a "head" variable then only using it once. You don't need to make a separate addr pointer at all, you already have one (because it's a copy of the passed pointer). just pass it as addr.
template <class Thing>
Node<Thing>* getTailNode(Node<Thing>* addr) // reuse the passed pointer in the loop
{
if(addr != null) // use "not null" as default branch. If you're really careful you can exclude this check altogether, but assuming the common case minimizes the costs
{
while(addr->getNext() != nullptr) // use "next node is not null" as default branch
addr = addr->getNext();
}
return addr; // return addr here
}
template <class Thing>
Node<Thing>* getNode(Node<Thing>* addr, int index) // got rid of the "==0 choice", and separate head pointer
{
int pos=1;
while(addr != nullptr)
{
if(pos != index) // update the loop if not found, but we're now assume it's the most likely thing.
{
addr=addr->getNext(); ++pos;
}
else
return addr;
}
return nullptr;
}
EDIT: one final thing that would simplify the getNode function is to do away with "pos" completely, and decrement index each time through the loop. Then you could get it so that you're comparing index to a constant (0) rather than another variable. Which is faster because there's an actual CPU instruction code that branches if something = zero. The trick here is comparing things in a relative sense instead of an absolute sense, so you can compare things to constants, especially zero, which is treated as a special case by the compiler and CPU.
template <class Thing>
Node<Thing>* getNode(Node<Thing>* addr, int index) // got rid of the "==0 choice", and separate head pointer
{
--index; // this is needed if you're calling the first element #1 rather than #0
while(addr != nullptr)
{
if(index != 0) // update the loop if not found, but we're now assume it's the most likely thing.
{
addr=addr->getNext(); --index;
}
else
return addr;
}
return nullptr;
}
Author
Topic: if self.isCoder(): post() #Programming Thread (Read 818121 times)