Запрос имени алгоритма / структуры данных: массив фиксированного размера с увеличением шага при перезаписи - PullRequest
Новая
       9

Запрос имени алгоритма / структуры данных: массив фиксированного размера с увеличением шага при перезаписи

0 голосов
/ 01 октября 2018

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

Требования:

  1. Поддержка массива фиксированного размера

  2. При записи используются монотонно увеличивающиеся шаги в следующем смысле:

    Массив заполненот начала до конца с одним индексом увеличивается, пока массив не заполнится.Например, если задано целое число i = 0 и неизменное целое число n фиксированного размера, массив заполняется i ++ до тех пор, пока i = n.

    Затем индекс сбрасывается на второй элемент (индекс 1), поэтому i = 1Таким образом, шаг увеличивается на величину 1;в общем, шаг будет увеличиваться на 1 каждый раз, когда граница массива встречается или пересекается.Впервые шаг увеличивается, вместо i ++ мы имеем i = i + 2, пока i> = n. 

    int sRes=0;
template<T>
void addElement(T* element)
{
    if(i >= n)
    {
        if (stride > 2*n)
        { 
            sRes++;
            // keep stride from overflowing the integer type
            stride = (stride mod n);
        }
        stride += 1; 
        i = stride mod n; 
    }
    // array of AR type, AR defined in #3 below
    array[i] = new AR(element, stride);
    i += stride;
}

  3. Элементы массива включают «значение шага», когдазапись была написана / перезаписана.Таким образом, я могу определить, под каким шагом был написан текущий элемент.Таким образом, мы можем определить элемент массива следующим образом: 

    template<T> struct AR
{
    T* value;
    int stride;
}

  4. Чтения массива соответствуют модели произвольного доступа (например, любой индекс может быть прочитан в любое время из-за нижележащего массива).

Для меня это имеет несколько проблем;если я хочу узнать текущий шаг, я могу посмотреть его в массиве.Но в какой-то момент у меня будут успехи, которые варьируются от n до 2 * n.Хотя это кажется подходящим для вышеупомянутой задачи, я задаюсь вопросом о последствиях.Я работаю на встроенном устройстве, с небольшим объемом памяти.Я хочу знать, как долго я обновляю массив.Я мог бы сэкономить количество модификаций, используя дополнительную логику, чтобы уменьшить необходимую мета-информацию о значении шага, например, сделать текущий мод счетчиком статических значений;количество модов - это количество раз, которое я увеличил шаг.

Таким образом, интерес, который я проявляю к имени, может включать в себя наблюдения, такие как проблема с модом в представленном виде.Я могу сохранить текущее количество увеличений шага в int32.Под моими ограничениями это приемлемо;хотя мне нравится использовать собственное имя идеи, если она существует, и мне нравится читать о наблюдениях, которые я, возможно, пропустил.

Я надеюсь, что эта презентация проблемы понятна!Если нет, дайте мне знать, и я обновлю вас соответствующим образом.

Спасибо!

...