Es una pila falsa más rápida que una pila real

Question

Estoy haciendo un análisis recursivo.

Actualmente tengo una pila falsa, donde almaceno estados para mi máquina de estados finitos, así que cuando profundizo recursivamente, presiono el estado en el que estaba, y lo explico más tarde después de haber terminado de procesar el fragmento de texto recursivo .

¿Sería más rápido para tener una "Identificación del estado de pila como:

int* stack = 0 
int top = 0; 
// ... 
// drill down bit 
if (stack == 0) 
    stack = (int*)malloc(STACK_JUMP_SIZE); 
else if (top % STACK_JUMP_SIZE == 0) 
    stack = (int*)realloc(stack, (top+STACK_JUMP_SIZE) * sizeof(int)); 
stack[top++] = currentState; 
// ... 
// pop up later 
{currentState = stack[--top]; { 
if (top == 0) { 
    free(stack); 
    stack = 0; 
} else if ((top+1) % STACK_JUMP_SIZE == 0) { 
    stack = (int*)realloc(stack, (top+1)*sizeof(int)); 
} 

o sería más rápido para dividir la cosa arriba en funciones propias y dejar que C++ preocuparse por la pila.

(Sé que alguien me dirá 'eso es C, no es C++', por lo que respondo de manera preventiva, el C++ de mi programa pero tiene mucha c).

Answer 1

Depende de la implementación — no hay forma de decirlo de antemano. En una máquina donde las llamadas a funciones son baratas (por ejemplo, SPARC), la pila de la función probablemente sea más rápida, pero incluso allí, problemas como la localización intervienen. (La pila de la máquina requiere más espacio, ya que apila más información de , que la pila simulada). Lo dividiría en las funciones recursivas , y solo intentaré la gestión manual de la pila si este resulta ser un cuello de botella. A menos que ... La administración manual de la pila tenga una ventaja importante: manejo de errores. El desbordamiento de la pila de la máquina es comportamiento indefinido: si malloc o realloc devuelven un puntero nulo, usted puede al menos informar el error limpiamente.

Si lo hace simular la pila, se debe considerar el uso de std::vector, y no malloc/realloc/free. Le salvará si hay una excepción , y también es probable que sea un poco más rápida. Si puede establecer un límite superior para el tamaño de la pila, y no es irracionalmente grande, declarando la pila como una matriz de estilo C en la pila sería incluso más rápido.