0

I was working on a code related to reversing parts of linked lists. For the reversal part, the algorithm I was using was to push the nodes of the list onto a stack, and then keep popping the stack and correct the next pointer of each node. The question that I had was that would using the STL stack provide a better performance over the function call stack, or vice-versa.

I had expected the STL stack to perform better because there are other overheads with calling a function stack, but from the submission details it seems otherwise. Did I miss something, or does the function stack somehow perform better?

Thanks for any help provided.

Attaching the code also, in case someone wants a look. The parameters to the reverse between function are the head of the list, and the two indexes (1 based, inclusive), between which the nodes should be reversed. I don't think you need to go through the code though:

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <stack>

using namespace std;

 struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n)
{
    int counter = 1;
    stack<ListNode*> holder;
    ListNode* current = head;
    ListNode* pre_flip = NULL;
    ListNode* to_return = head;
    while (counter < m)
    {
      pre_flip = current;
      current = current->next;
      counter++;
    }
    while (counter <= n)
    {
      holder.push(current);
      if (counter != n)
        current = current->next;
      counter++;
    }
    if (m == 1)
      to_return = current;
    ListNode* post_flip;
    post_flip = current->next;
    if (pre_flip == NULL)
      pre_flip = to_return;
    while (holder.empty() == 0)
    {
      ListNode* temp = holder.top();
      pre_flip->next = temp;
      pre_flip = pre_flip->next;
      holder.pop();
    }
    pre_flip->next = post_flip;
    return to_return;
}
};
therainmaker
  • 4,253
  • 1
  • 22
  • 41
  • 1
    One [SSCCE](http://www.sscce.org) please. – Baum mit Augen Feb 18 '15 at 16:34
  • 1
    Performance is tricky. Trust experimental data over theory. Repeat your performance tests for different list lengths (especially huge ones). See if it makes a difference what kind of background processes you have running at the time. – Austin Mullins Feb 18 '15 at 16:36
  • compilers optimize everything nowadays. Might as well flatten your recursive reverse function. – lucasg Feb 18 '15 at 16:36
  • @AustinMullins : I had written this code for oj.leetcode.com They ran this code on 44 test cases and the execution took 8 ms. Other recursive codes have shown an execution of around 4 ms. – therainmaker Feb 18 '15 at 16:42
  • 1
    You'd have to measure. The call stack is probably faster than the free store (since each stack frame is created just by adjusting a couple of registers, and maybe writing a few values to it, with no need for thread safety or heap management), but typically has a finite size and explodes horribly when it overflows. But if it's a linked list, you should be able to reverse it by moving nodes from one list to another (popping from the front of one, then pushing to the front of the other) with no extra storage. – Mike Seymour Feb 18 '15 at 16:42
  • 1
    Have a look at the following answer http://stackoverflow.com/questions/161053/c-which-is-faster-stack-allocation-or-heap-allocation – sanjayk79 Feb 18 '15 at 16:43
  • @sanjayk79 , So that answer supports my observation since the STL would be using heap memory. Hence recursion should be faster. Any other views? – therainmaker Feb 18 '15 at 16:52
  • You have to consider branching (function calls) as well as data access. On many processors, a jump or branch instruction will cause the processor to flush the instruction cache and reload. This may be more of a performance hit than whether the data is in one part of memory (stack) versus another (heap). – Thomas Matthews Feb 18 '15 at 17:14
  • As far as data access performance goes, generally, there is no performance difference between accessing a variable on the stack, heap, or global memory. The processor still has to fetch the data from external memory into the data cache, then into registers. If the stack or heap lies in memory that is in on the same piece of silicon as the processor, this will speed up access; otherwise, it doesn't make a difference. – Thomas Matthews Feb 18 '15 at 17:16

0 Answers0