Стек против целого числа

Question

Я создал программу для решения Cryptarithmetics для класса по структурам данных. Профессор рекомендовал использовать стек, состоящий из связанных узлов, чтобы отслеживать, какие буквы мы заменили на какие числа, но я понял, что целое число может сделать то же самое. Вместо стека {A, 1, B, 2, C, 3, D, 4} я мог бы хранить ту же информацию в 1234.

Моя программа, похоже, работает намного медленнее, чем оценка, которую он дал нам. Может ли кто-нибудь объяснить, почему стек будет вести себя намного эффективнее? Я предположил, что, поскольку я не буду вызывать методы снова и снова (push, pop, top и т. Д.), А просто добавлю один к «решению», мое будет быстрее.

Это не открытый вопрос, поэтому не закрывайте его. Хотя вы можете реализовывать вещи по-разному, я хочу знать, почему в основе C ++ доступ к данным через стек имеет преимущества в производительности по сравнению с хранением в целых и извлечением с помощью модов.

Хотя это домашнее задание, мне на самом деле помощь не нужна, просто очень заинтригована и любопытна.

Спасибо и не могу дождаться, чтобы узнать что-то новое!

РЕДАКТИРОВАТЬ (добавить код)

letterAssignments - это массив int размера 26. для такой проблемы, как 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) (я полагаю).

Однако, в ответ на ваш первоначальный вопрос, сохранение массива целых чисел всегда будет быстрее, чем любая структура, которую вы можете придумать, просто потому, что при назначении памяти, вызове функций и т. Д. Требуется больше накладных расходов

Но, как и во всем, реализация - ключевое отличие медленной программы от быстрой.

Answer 2

Программирование фактически торгует памятью на время и наоборот. Здесь вы упаковываете данные в целое число. Вы экономите память, но теряете время.

Скорость конечно зависит от реализации стека. 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 будет иметь наилучший подходящий размер для процессора (нет необходимости в выравнивании и т. Д.).

Answer 3

Проблема в том, что при подсчете вы учитываете также повторы, когда, возможно, проблема заключается в том, чтобы назначить различное число для каждой другой буквы, чтобы числовое уравнение выполнялось.

Например, для четырех букв вы проверяете 10*10*10*10=10000 сопоставление букв-> цифр вместо 10*9*8*7=5040 (чем больше количество букв, тем больше соотношение между двумя числами ...).

Answer 4

Инструкция div , используемая функцией мода, довольно дорогая.Использование его для ваших целей может быть менее эффективным, чем хорошая реализация стека.Вот таблица времени выполнения команд: http://gmplib.org/~tege/x86-timing.pdf

Вы также должны написать модульные тесты для своего стека на основе int, чтобы убедиться, что он работает как задумано.