1

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

不过，我的程序似乎比他给我们的估计运行得慢得多。有人可以解释为什么堆栈的行为会更有效吗？我曾假设过，因为我不会一遍又一遍地调用方法（推送、弹出、顶部等），而只是将一个添加到我会更快的“解决方案”中。

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

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

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

编辑（添加一些代码）

letterAssignments 是一个大小为 26 的 int 数组。对于 SEND + MORE = MONEY 之类的问题，不使用 A，因此 letterAssignments[0] 设置为 11。所有使用的字符都初始化为 10。 answerNum 是一个带有 as 的数字许多数字，因为有唯一的字符（在本例中为 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;
}
4

4 回答 4

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)循环的堆栈的实现慢得多（我假设）。

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

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

于 2011-09-29T05:38:45.527 回答
0

mod 函数使用的div指令非常昂贵。将它用于您的目的很容易比良好的堆栈实现效率低。这是一个指令时序表： http: //gmplib.org/~tege/x86-timing.pdf

您还应该为基于 int 的堆栈编写单元测试，以确保它按预期工作。

于 2011-09-29T05:49:07.043 回答
0

问题是，通过计数你也在考虑重复，什么时候问题可能要求为每个不同的字母分配一个不同的数字，以便数字方程成立。

例如，对于四个字母，您正在测试字母10*10*10*10=10000->数字映射而不是10*9*8*7=5040它们（字母的数量越大，两个数字之间的比率越大......）。

于 2011-09-29T06:04:33.750 回答
0

编程实际上是用内存换取时间，反之亦然。在这里，您将数据打包成整数。您节省了内存，但浪费了时间。

速度当然取决于堆栈的实现。C++ 是带有类的 C。如果你不使用类，它基本上是 C（和 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];
  }
}

没有像 vtbp 这样的开销。pop() 和 push() 也非常简单，因此它们将被内联，因此没有函数调用的开销。使用 int 作为堆栈元素也有利于速度，因为 int 保证具有最适合处理器的大小（不需要对齐等）。

于 2011-09-29T06:37:33.653 回答