c++ - 堆栈与整数

Question

我创建了一个程序来解决数据结构类的密码学问题。教授建议我们利用一个由链接节点组成的堆栈来跟踪我们用哪些数字替换了哪些字母，但我意识到一个整数也可以做同样的事情。我可以在 1234 中保存相同的信息，而不是堆栈 {A, 1, B, 2, C, 3, D, 4}。

不过，我的程序似乎比他给我们的估计运行得慢得多。有人可以解释为什么堆栈的行为会更有效率吗？我曾假设，因为我不会一遍又一遍地调用方法(push、pop、top 等)，而只是将一个方法添加到“解决方案”中，这样​​我的方法会更快。

这不是一个开放式问题，所以不要关闭它。尽管您可以用不同的方式实现事物，但我想知道为什么在 C++ 的核心，通过堆栈访问数据比存储在 int 中和通过调制提取数据具有性能优势。

虽然这是作业，但我其实不需要帮助，只是非常好奇和好奇。

谢谢，迫不及待想学习新东西!

编辑(添加一些代码)

letterAssignments 是一个大小为 26 的 int 数组。对于像 SEND + MORE = MONEY 这样的问题，不使用 A，因此 letterAssignments[0] 设置为 11。所有使用的字符都初始化为 10。answerNum 是一个数字，其位数与唯一字符数一样多(在本例中为 8 位数字)。

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;
}

两个辅助方法，以防您希望看到它们:

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

从表面上看，您在这里做事的方式非常低效。

作为一般规则，尽量使用尽可能少的 for 循环，因为每个循环都会大大减慢您的实现速度。

例如，如果我们去掉所有其他代码，您的程序看起来像

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

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

    }
    for(i < 26) {

    }
  }
}

这意味着对于每个 while 循环，您都在执行 ((26+26)*numDigits)+26 循环操作。那是假设 isAssigned()不使用循环。

理想情况下你想要:

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

我确信可以通过更改您的代码来实现。这就是为什么使用整数数组的实现比使用不使用 for(i < 26) 的堆栈的实现慢得多的原因。循环(我假设)。

然而，在回答您最初的问题时，存储整数数组总是比您可以想出的任何结构都快，因为在分配内存、调用函数等方面涉及更多的开销。

但与所有事情一样，实现是慢程序和快程序之间的关键区别。