c++ - 在大整数数组中查找子数组

Question

我想使用 C++ 在我的嵌入式 CPU 上计算任务堆栈的高水位线。 不幸的是，操作系统不提供这样的方法。

任务堆栈本身是一个整数数组。 unsed 堆栈包含 0xCDCDCDCD 作为值。由于 0xCDCDCDCD 可能是一个有效值，我想找到重复 4 次的终止序列的第一次出现。

所以我在一个大的 int 数组中搜索一个 int (sub) 数组。 由于我必须暂停任务，因此这种方法应该非常有效。

我尝试了非常幼稚的方式。

#define STACK_DEFAULT_VALUE 0xCDCDCDCD          ///< marking for an empty stack element
#define N_EMPTY_SUCCESSORS  4                   ///< Min number of succeedeing stack elements before we assume we found the high watermark

int Get_Task_Stack_High_Watermark(const int* const pStack, const int stack_size)
{
    int res = 0;
    for(int i = 0;i<stack_size;i++)
    {
        if(*(pStack[i] != STACK_DEFAULT_VALUE))
        {
            //this part of the stack was allready in use
            continue;
        }

        bool res = true;

        //we found a stack mark => check if the next stack elements are unused as well
        for(int j = i; j<i+N_EMPTY_SUCCESSORS; j++)
        {
            if(j>= stack_size)
            {
                //we reached the end of the stsck!
                return 0;
            }

            if(*(pStack[j] != STACK_DEFAULT_VALUE))
            {
                //this is not the end of the stack
                res = false;
            }

        }

        if(res)
        {
            //this is the end of the (used) stack
            //calculate remaining stack size
            res = stack_size - i;
            break;
        }
    }

    return res;

}

但是我想知道是否有更快的方法来做到这一点？

你对我有什么建议吗？

Answer 1

您可以使用计数器来跟踪一行中特殊值的数量:

#define STACK_DEFAULT_VALUE 0xCDCDCDCD          ///< marking for an empty stack element
#define N_EMPTY_SUCCESSORS  4                   ///< Min number of succeedeing stack elements before we assume we found the high watermark

int Get_Task_Stack_High_Watermark(const int* const pStack, const int stack_size)
{
    int consecutiveEmpties = 0;

    for(int i = 0;i < stack_size; i++)
    {
        if(pStack[i] == STACK_DEFAULT_VALUE)
        {
            consecutiveEmpties++;

            if(consecutiveEmpties == N_EMPTY_SUCCESSORS)
            {
                return i - 4;
            }
        }
        else 
        {
            consecutiveEmpties = 0;
        }
    }

    return stack_size;
}

或者如果您真的不关心可读性:

int Get_Task_Stack_High_Watermark_2(const int* const pStack, const int stack_size)
{
    int consecutiveEmpties = 0;

    for (int i = 0; i < stack_size; i++)
    {
        if ((consecutiveEmpties = (consecutiveEmpties + 1) * (pStack[i] == STACK_DEFAULT_VALUE)) == N_EMPTY_SUCCESSORS)
        {
            return i - 4;
        }
    }

    return stack_size;
}

第二个版本快一点(visual studio with release mode)