Stack versus Integer

Question

I've created a program to solve Cryptarithmetics for a class on Data Structures. The professor recommended that we utilize a stack consisting of linked nodes to keep track of which letters we replaced with which numbers, but I realized an integer could do the same trick. Instead of a stack {A, 1, B, 2, C, 3, D, 4} I could hold the same info in 1234.

My program, though, seems to run much more slowly than the estimation he gave us. Could someone explain why a stack would behave much more efficiently? I had assumed that, since I wouldn't be calling methods over and over again (push, pop, top, etc) and instead just add one to the 'solution' that mine would be faster.

This is not an open ended question, so do not close it. Although you can implement things different ways, I want to know why, at the heart of C++, accessing data via a Stack has performance benefits over storing in ints and extracting by moding.

Although this is homework, I don't actually need help, just very intrigued and curious.

Thanks and can't wait to learn something new!

EDIT (Adding some code)

letterAssignments is an int array of size 26. for a problem like SEND + MORE = MONEY, A isn't used so letterAssignments[0] is set to 11. All chars that are used are initialized to 10. answerNum is a number with as many digits as there are unique characters (in this case, 8 digits).

int Cryptarithmetic::solve(){
while(!solved()){       
    for(size_t z = 0; z < 26; z++){
        if(letterAssignments[z] != 11) letterAssignments[z] = 10;
    }
    if(answerNum < 1) return NULL;
    size_t curAns = answerNum;

    for(int i = 0; i < numDigits; i++){ 
        if(nextUnassigned() != '$') {
            size_t nextAssign = curAns % 10;
            if(isAssigned(nextAssign)){
                    answerNum--;
                    continue;
                }
            assign(nextUnassigned(), nextAssign);
            curAns /= 10;
        }
    }
    answerNum--;
}
return answerNum;
}

Two helper methods in case you'd like to see them:

char Cryptarithmetic::nextUnassigned(){ 
char nextUnassigned = '$';
for(int i = 0; i < 26; i++) {
    if(letterAssignments[i] == 10) return ('A' + i);
}
}

void Cryptarithmetic::assign(char letter, size_t val){
assert('A' <= letter && letter <= 'Z');  // valid letter
assert(letterAssignments[letter-'A'] != 11); // has this letter
assert(!isAssigned(val)); // not already assigned.
letterAssignments[letter-'A'] = val;
}

Answer 1

From the looks of things the way you are doing things here is quite inefficiant.

As a general rule try to have the least amount of for loops possible since each one will slow down your implementation greatly.

for instance if we strip all other code away, your program looks like

while(thing) {
  for(z < 26) {

  }
  for(i < numDigits) {
    for(i < 26) {

    }
    for(i < 26) {

    }
  }
}

this means that for each while loop you are doing ((26+26)*numDigits)+26 loop operations. Thats assuming isAssigned() does not use a loop.

Idealy you want:

while(thing) {
  for(i < numDigits) {
  }
}

which i'm sure is possible with changes to your code. This is why your implementation with the integer array is much slower than an implementation using the stack which does not use the for(i < 26) loops (I assume).

In Answer to your original question however, storing an array of integers will always be faster than any struct you can come up with simply because there are more overheads involved in assigning the memory, calling functions, etc.

But as with everything, implementation is the key difference between a slow program and a fast program.

Answer 2

The problem is that by counting you are considering also repetitions, when may be the problem asks to assign a different number to each different letter so that the numeric equation holds.

For example for four letters you are testing 10*10*10*10=10000 letter->number mappings instead of 10*9*8*7=5040 of them (the bigger is the number of letters and bigger becomes the ratio between the two numbers...).

Answer 3

The div instruction used by the mod function is quite expensive. Using it for your purpose can easily be less efficient than a good stack implementation. Here is an instruction timings table: http://gmplib.org/~tege/x86-timing.pdf

You should also write unit tests for your int-based stack to make sure that it works as intended.

Answer 4

Programming is actually trading memory for time and vice versa. Here you are packing data into integer. You spare memory but loose time.

Speed of course depends on the implementation of stack. C++ is C with classes. If you are not using classes it's basically C(as fast as C).

const int stack_size = 26;

struct Stack
{
  int _data[stack_size];
  int _stack_p;
  Stack()
  :_stack_size(0)
  {}
  inline void push(int val)
  {
     assert(_stack_p < stack_size); // this won't be overhead 
                                    // unless you compile debug version(-DNDEBUG) 
     _data[_stack_p] = val;
  }

  inline int pop()
  {
    assert(_stack_p > 0);       // same thing. assert is very useful for tracing bugs
    return _data[--_stack_p];  // good hint for RVO
  }

  inline int size()
  {
    return _stack_p;
  }

  inline int val(int i)
  {
    assert(i > 0 && i < _stack_p);      
    return _data[i];
  }
}

There is no overhead like vtbp. Also pop() and push() are very simple so they will be inlined, so no overhead of function call. Using int as stack element also good for speed because int is guaranteed to be of best suitable size for processor(no need for alignment etc).