Нахождение подмассива в большом массиве целых чисел

Question

Я бы хотел вычислить верхний водяной знак стека задач на моем встроенном процессоре, используя C ++. К сожалению, ОС не предлагает такой метод.

Сам стек задач представляет собой массив целых чисел. Неназванный стек содержит 0xCDCDCDCD в качестве значения. Так как 0xCDCDCDCD может быть допустимым значением, я бы хотел найти первый случай последовательности завершения, повторенной 4 раза.

Поэтому я ищу массив int (sub) в большом массиве int. Так как я должен приостановить задачу, этот метод должен быть очень эффективным.

Я попробовал очень наивный способ.

#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 с режимом релиза)