Последовательность RLE, установка значения - PullRequest
Новая
       6

Последовательность RLE, установка значения

4 голосов
/ 16 октября 2011

Скажите, у меня есть произвольная последовательность RLE.(Для тех, кто не знает, RLE сжимает массив типа [4 4 4 4 4 6 6 1 1] в [(5,4) (2,6) (2,1)]. Сначала идет числоконкретное целое число в серии, а затем само число.)

Как определить алгоритм для установки значения по заданному индексу без распаковки всего этого?Например, если вы установите (0,1), RLE станет [(1,1) (4,4) (2,6) (2,1)].(В наборе первое значение - это индекс, второе - это значение)

Кроме того, я разделил эту сжатую последовательность на ArrayList of Entries.То есть каждая запись является одной из них: (1,1) где она имеет сумму и значение.

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

Любая помощь будет принята с благодарностью.Сейчас я работаю над алгоритмом, вот некоторые из них: 

while(i<rleAL.size() && count != index)
    {
        indexToStop=0;
        while(count<index || indexToStop == rleAL.get(i).getAmount())
        {
            count++;
            indexToStop++;
        }

        if(count != index)
        {
            i++;
        }
    }

Как вы можете видеть, это становится все более небрежным ...

Спасибо!

1 Ответ

1 голос
/ 17 октября 2011

RLE, как правило, плохо при обновлении, именно по указанной причине. Изменение ArrayList на LinkedList не очень поможет, так как LinkedList ужасно медленен во всем, кроме вставок (и даже со вставками вы уже должны содержать ссылку на определенное местоположение, например, ListIterator).

Если говорить о первоначальном вопросе, то нет необходимости распаковывать все. Все, что вам нужно, это найти правильное место (суммируя счет), которое является линейным временем (рассмотрите список пропусков, чтобы сделать это быстрее), после которого у вас будет только четыре варианта:

  1. Вы находитесь в блоке, и этот блок совпадает с числом, которое вы пытаетесь сохранить.
  2. Вы внутри блока, и номер другой.
  3. Вы находитесь в начале или в конце блока, номер отличается от номера блока, но совпадает с соседним.
  4. Вы находитесь в начале или конце блока, номер не совпадает ни с номером блока, ни с номером соседа.

Действия одинаковы, очевидно:

  1. Ничего не делать
  2. Изменить счетчик в блоке, добавить два блока
  3. Смена счетчиков в двух блоках
  4. Изменить счетчик в одном блоке, вставить новый

(Обратите внимание, что если у вас есть пропускаемые списки, вы также должны обновить их.)

Обновление: становится интереснее, если блок для обновления имеет длину 1, правда. Тем не менее, все это остается тривиальным: в любом случае изменения ограничиваются максимум тремя блоками.

...