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

Скажем, у меня есть произвольная последовательность 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. То есть каждая запись является одной из следующих: (1,1), где она имеет сумму и значение.

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

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

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

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

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

Спасибо!


java arraylist run-length-encoding
person user977036    schedule 16.10.2011    source источник
comment
Возможно, лучше использовать связанный список вместо ArrayList из соображений производительности.   -  person Mark Byers    schedule 16.10.2011
comment
Даже если мне придется удалить запись в индексе?   -  person user977036    schedule 16.10.2011
comment
@ user977036: +1, но ... Если вы не сохраните дополнительную информацию, вам потенциально придется много распаковывать. Например, если ваше изображение имеет 10000 пикселей, и вы хотите установить 5000 пикселей, то независимо от того, начинаете ли вы с самого начала или пытаетесь стать умнее, начиная снизу, вам придется распаковывать половину пикселей. Так что либо вы каким-то образом отслеживаете различные индексы, либо вам нужно довольно много распаковывать, чтобы делать то, что вы хотите (если я не ошибаюсь). Если вам нужно сделать несколько таких изменений, вы можете индексировать при распаковке один раз, а затем выполнять все свои вставки.   -  person TacticalCoder    schedule 16.10.2011
comment
@ user988052 Я немного не понимаю - цель состоит в том, чтобы вообще не распаковывать. Какую дополнительную информацию вы упомянули? Кроме того, мне нужно менять только одну запись за раз, а не массово.   -  person user977036    schedule 16.10.2011
comment
@ user977036: цель состоит в том, чтобы вообще не выполнять распаковку ‹ -- что именно вы имеете в виду? Вы можете избежать сохранения в памяти всех распакованных данных, но вы не можете избежать просмотра данных. Я имею в виду, что смысл RLE в том, чтобы сжимать и быть относительно небольшим. Если вы хотите получить доступ/изменить данные, вы должны распаковать... Если только вы не контролируете алгоритм и не приходите с чем-то, что содержит больше данных (но, следовательно, больше, чем типичный RLE).   -  person TacticalCoder    schedule 16.10.2011
comment
@user988052 user988052 Но я думаю, что есть способ избежать распаковки при установке одного значения, поэтому я задаю свой вопрос   -  person user977036    schedule 16.10.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

Действия те же, очевидно:

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

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

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

person alf    schedule 16.10.2011