Перекодирование большого гистограммы


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

Например, маркера C (ниже) определяет любое число больше 255 (или 8 бит) до 16 бит) или 63535) из 0 высота ячейки в строке.

На данный момент, моя точка является перекодирование элементов данных, я определил из гистограммы.

Во-первых, большая гистограмма включена в список encodingData объекты, которые описывают 'работает' интервалов на гистограмме.

Код для EncodingData класс:

/** Holds data for the run-length encoding
*
*/
public class EncodingData {


/**
 *  The number of bins in the run
 */
private int length;

/**
 *  the frequency of the bins in the run
 */
private int frequency;

public EncodingData(int length, int frequency) {
    this.length = length;
    this.frequency = frequency;
}

public int getLength() {
    return length;
}

public void incrementLength() {
    this.length++;
}

public int getFrequency() {
    return frequency;
}

public void setFrequency(int frequency) {
    this.frequency = frequency;
}
}

В Transcoder занятие проходит в большой список кодирования данных объектов и превращает его в одну строку, которая является на основе маркеров. Первый метод определяет, как обрабатывать трасс encodingData объекты. Я опустил некоторые подробности данного класса, так что не беспокойтесь о входах.

private StringBuilder specBuilder;

 public String transcode(Resolution resolution, List<EncodingData> encodingData, String rname, int startPOS, ParsedAPUCommand command, int lastPOS) {

     specBuilder = new StringBuilder();

    //loop through -> bin > 1 or a single bin of 1 -> use regular characters
    //runs of all 1's -> if all the H's are less than 255, use R
    //runs of all 1's -> if all the H's are less than 65535, use S.

    int posTracker = startPOS;
    int byteCount = 0;

    List<EncodingData> run = new ArrayList<>();
    for (EncodingData data : encodingData) {
        byteCount += data.getLength();

        if (byteCount >= 1000) {
            //append a new W element and reset the byteCount;
            posTracker += byteCount;
            byteCount = 0;
            specBuilder.append(String.format("W000000000000000000%010d", posTracker));
        }

        if (data.getLength() == 1) {
            //can continue the run.
            run.add(data);
        } else {
            //must stop the run
            if (run.size() == 1) { //encode the single run = 1 element
                transcodeUsingRegularElements(run.get(0));
                run.clear();
            }else{
                transcodeSpecialOrMultipleRegularElements(run);
                run.clear();
            }

        //transcode the single greater than 1 bin run.
        transcodeUsingRegularElements(data);
        }


    }

    //encode last if run is not empty
    if (run.size() > 1) {
        //must encode the current run list and then encode the single greater than 1 list
        //count the heights, if less than 255, special R, if less than 65535 but more than 255 use S.
        //if greater than 65535 -> split the list until it fits and encode in multiple Special characters
        transcodeSpecialOrMultipleRegularElements(run);
        run.clear();
    } else if (run.size() == 1){ //encode the single run = 1 element
        transcodeUsingRegularElements(run.get(0));
        run.clear();
    }

    //append the escape sequence
    specBuilder.append("000000000000000000");


    return specBuilder.toString();
}


  /** Takes in a run of multiple encoding data points and finds the most efficient way of writing it
 * @param run list of encoding data points
 * @return String to append to the chunk
 */
private void transcodeSpecialOrMultipleRegularElements(List<EncodingData> run) {

    int SPECIAL_SIZE = 0;
    int SPECIAL_SWITCH = 0;

    //calculate the space required to encode the run using just special elements R and S
    //loop through an and see if all of the heights are less than 255, or less than 65535
    boolean lessThanOrEqual255 = true;
    boolean lessThanOrEqual65535 = true;

    for(EncodingData data : run){
        if(data.getFrequency() > 255) lessThanOrEqual255 = false;
        if(data.getFrequency() > 65535) lessThanOrEqual65535 = false;
    }

    //set the switch
    if(lessThanOrEqual255){
        SPECIAL_SIZE = 2 + run.size();
        SPECIAL_SWITCH = 1;
    }else if(lessThanOrEqual65535){
        SPECIAL_SIZE = 2 + 2*(run.size());
        SPECIAL_SWITCH = 2;
    }

    //Calculate the space required using just elements A, E,I, M and Z -> sizes (0,1,1,2,3) * (8 bits) respectively

    int REGULAR_SIZE = 0;

    if(SPECIAL_SWITCH != 0){ //if 0, frequencies greater than 65535, special not possible

        for(EncodingData data: run){
            int frequency = data.getFrequency();
            if(frequency <= 1) REGULAR_SIZE ++;
            else if(frequency <= 255) REGULAR_SIZE +=2;
            else if(frequency <= 65535) REGULAR_SIZE +=3;
            else REGULAR_SIZE += 7;
        }
    }

    //Determine and do the encoding
    if(SPECIAL_SWITCH == 0){
        //encode all in regular.
        for(EncodingData data : run){
            transcodeUsingRegularElements(data);
        }
    }else {
        if(SPECIAL_SIZE < REGULAR_SIZE){
            //encode in special
            if(SPECIAL_SWITCH == 1){
                //encode using a single R
                transcodeUsingSpecialElements(run, 'R');
            }else{
                //encode using a single S
                transcodeUsingSpecialElements(run, 'S');
            }
        }else{
            //encode all in regular
            for(EncodingData data : run){
                transcodeUsingRegularElements(data);
            }
        }
    }
}

/** Transcodes the run of encoding data using char element
 * @param run List of encoding data
 * @param element special element to use
 * @return String the transcoded string
 */
private void transcodeUsingSpecialElements(List<EncodingData> run, char element) {

    if(element != 'R' && element != 'S' ) return;

    int runCounter = 0;
    int sizeCounter = run.size();
    if(element == 'R'){
        for(EncodingData data : run){

            if(runCounter == 0){
                if(sizeCounter < 255){
                    specBuilder.append('R');
                    specBuilder.append(String.format("%03d", sizeCounter));
                }else{
                    specBuilder.append('R');
                    specBuilder.append("255");
                }
            }

            specBuilder.append(String.format("%03d", data.getFrequency()));
            runCounter++;

            if(runCounter == 255){
                runCounter = 0;
                sizeCounter -=255;
            }
        }
    }else { //S
        for (EncodingData data : run) {
            if (runCounter == 0) {
                if (sizeCounter < 255) {
                    specBuilder.append("S");
                    specBuilder.append(String.format("%03d", sizeCounter));
                } else {
                    specBuilder.append("S");
                    specBuilder.append("255");
                }
            }

            specBuilder.append(String.format("%05d", data.getFrequency()));
            runCounter++;

            if (runCounter == 255) {
                runCounter = 0;
                sizeCounter -= 255;
            }
        }
    }
}

/** Transcodes the encoding data point, spanning one or many bins
 * @param data encoding data object
 * @return String to append
 */
private void transcodeUsingRegularElements(EncodingData data) {

    int length = data.getLength();
    int height = data.getFrequency();

    //work out bits needed for both in
    int lengthBits = 0;
    int heightBits = 0;

    if(length == 0) lengthBits = 0;
    else if(length == 1) lengthBits = 1;
    else if(length <= 255) lengthBits = 8;
    else if(length <= 65535) lengthBits = 16;
    else if(length > 65536) lengthBits = 32;

    if(height == 0)  heightBits = 0;
    else if(height == 1)  heightBits = 1;
    else if(height <= 255) heightBits = 8;
    else if(height <= 65535) heightBits = 16;
    else if(height > 65536)  heightBits = 32;

    try {
        char token = determineToken(heightBits, lengthBits);
        specBuilder.append(token);
    }catch(InvalidTokenException ite){
        System.out.println(ite.getMessage());
        System.exit(0);
    }

    //get the maximum numbers for amount of bits - i.e for 16, 65335 (2^ bits - 1)

    specBuilder.append((length == 0 || length == 1) ? "" : String.format("%0"  + String.valueOf((int)(Math.pow(2, lengthBits))).length() + "d", length));
    specBuilder.append((height == 0 || height == 1) ? "" : String.format("%0" + String.valueOf((int)(Math.pow(2, heightBits))).length() + "d",  height));

}

/** Determines the token to use from the token enum
 * @param heightBits bits from the value
 * @param lengthBits bits from the length
 * @return char - the token
 * @throws InvalidTokenException token not found
 */
private char determineToken(int heightBits, int lengthBits) throws InvalidTokenException{

    //if height is 1 or 0, rewrite the bit size since we won't write that in the transcoding
    //find the correct token
    for(Token token : Token.values()){
        if(token.getHeight() == heightBits && token.getLength() == lengthBits) return token.name().charAt(0); //only one char per name.
    }

    throw new InvalidTokenException("Token does not exist");
}

маркер перечисления определяется ниже:

/** All lengths and heights in bits.
* All 1's are to be ignored in writing
* i.e 1 - 0 is transcoded as A.
* 1 -1 is transcoded as E
* 1 - 209 is transcoded as I209
* 1 - 2 is transcoded as I002
* 1 - 40000 is transcoded as M40000
* 1 - 290 is transcoded as M00290
*/
public enum Token {

A (1, 0),
B (8, 0),
C (16,0),
D (32,0),
E (1, 1),
F (8, 1),
G (16,1),
H (32,1),
I (1 ,8),
J (8, 8),
K (16,8),
L (32,8),
M (1,16),
N (8,16),
O (16,16),
P (32,16),
Q (16,32),
Z (1,32);


private final int length;
private final int height;


Token(int length, int height) {
    this.length = length;
    this.height = height;
}

public int getLength() {
    return length;
}

public int getHeight() {
    return height;
}

}

Моя проблема заключается в том, что значительное количество времени на процесс уходит петлять по списку кодирования данных элементов в transcode метод. Есть ли здесь явные ошибки, которые могут замедлить весь этот процесс? Я был сорван в прошлом дорогих строковые операции, поэтому старался избегать этих путем проведения глобальной StringBuilder и добавляя к этому, чтобы избежать строки творения.

Код работает, просто очень медленно для больших файлов. Пример размеров, является гистограмма 140,000,000 закромах. Это соответствует ~ список 6,000,000 EncodingData объекты.

Если я могу помочь что-нибудь разъяснить, пожалуйста, дайте мне знать.



157
2
задан 12 апреля 2018 в 12:04 Источник Поделиться
Комментарии
2 ответа

Во-первых, я не думаю, что используя глобальную StringBuilder переменная собирается сделать существенную разницу в производительности (если вообще), потому что она не препятствует созданию String объекты как таковые, его просто не заставить их быть передан от одного метода к другому. Но вы все еще создаете String объекты со всеми своими вызовами String.format(String, Object...)и можете ли вы передать их одному из собственных методов или напрямую StringBuilder.append(String) это, в конце концов, только вопрос читабельности. Ваш javadoc-комментарии показывают, что вы когда-то имели перекодирования методы возвращают String вместо void. Я хотел бы вернуться к этому подходу, потому что тогда методы будут только к государству, которое напрямую передать их в качестве аргументов, который я думаю, будет понятнее код дизайна, чем если глобальное государство участвует (Кстати, Ваш способ transcode еще есть местные specBuilder переменная скрывает поле с тем же именем).

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

Первое, что я бы переписать ваш выполнением различных маркеров и способ его получения соответствующим маркером для EncodingDataпотому что это не зависит ни от чего-то в коде. Существует система назначение букв в различных диапазонах, по крайней мере до тех пор, пока букву Р, поэтому вместо жесткого кодирования каждый знак, который попадает в эту систему, можно написать алгоритм, который вычисляет письмо на основе системы. Последние два маркера исключения (по любой причине), так что вам придется обрабатывать их по отдельности.

public class Token {

private static final int[] upperBoundaries;

static {
upperBoundaries = new int[4];
upperBoundaries[0] = (1 << 0) - 1; //0
upperBoundaries[1] = (1 << 1) - 1; //1
upperBoundaries[2] = (1 << 8) - 1; //255
upperBoundaries[3] = (1 << 16) - 1; //65535
}

/*
* Gets the index of the upper boundary of the range
* that the passed value falls into, i.e. 0 for 0 (and
* all negative values), 1 for 1, 2 for 2-255, 3 for
* 256-65535, and 4 for all values greater than 65535
*/
private static int getIndexOfUpperBoundary(int value) {
int index = Arrays.binarySearch(upperBoundaries, value);
if (index < 0) {
index = -(index + 1);
}
return index;
}

public static char determineToken(int height, int length) {
if (height < 0) {
throw new IllegalArgumentException("Invalid height: " + height);
} else if (length < 1) {
throw new IllegalArgumentException("Invalid length: " + length);
} else if (height <= upperBoundaries[3]) {
int heightIndex = getIndexOfUpperBoundary(height);
int lengthIndex = getIndexOfUpperBoundary(length) - 1; //length cannot be 0, hence -1
return (char) ('A' + heightIndex * 4 + lengthIndex);
} else if (length > upperBoundaries[2] && length <= upperBoundaries[3]) {
return 'Q';
} else if (length == 1) {
return 'Z';
} else {
throw new InvalidTokenException("Token does not exist");
}
}
}

Это конечно уменьшает Token в служебный класс, но это также делает Способ transcodeUsingRegularElements(EncodingData data) намного более компактным, поскольку обязанность определения диапазона, в котором высота и длина упасть, что определяет маркер будет потом лежать в Token класс, это означает, что метод перекодирования можете просто передать высоту и длину в качестве параметра, не беспокоясь о том, в каком диапазоне этих значений. Также это может быть быстрее, чем ваш код, потому что не придется перебрать несколько значений enum для того, чтобы найти правильный один, но рассчитывает персонажа напрямую от высоты и длины.

Следующее, что я хотел сделать, это пересмотреть методы transcodeSpecialOrMultipleRegularElements(List<EncodingData>) и transcodeUsingSpecialElements(List<EncodingData>, char). Если я правильно понял ваш код правильно, эти методы предназначены только для работы на EncodingData объекты, которые представляют одну-длина-бин-бегов. Это означает, что длина EncodingData объекты никогда не должны быть переданы к этим методам, в первую очередь, потому что методы не только не зависит от длины, но они бы даже привести к неверным результатам в случае EncodingData С длиной других, чем 1 передаваться эти методы. Так вместо этого, я хотел бы сделать эти два метода принимают List<Integer> а не List<EncodingData>, где List<Integer> представляет частоты один закромах. Это только для чтения, он не влияет на производительность, но как я уже сказал, ваш код будет настолько сложным, что все возможности для упрощения это может помочь предотвратить головные боли.

Теперь, давайте посмотрим на Способ transcodeSpecialOrMultipleRegularElements(List<EncodingData>) в деталь. Я хотел опустить два булевых флагов lessThanOrEqual255 и lessThanOrEqual65535 потому что они являются взаимозависимыми, то вполне возможно, что они противоречат друг другу (а именно если lessThanOrEqual255 == true и lessThanOrEqual65535 == false). Используя одно целое, как переключатель, как вы сделали, вполне достаточно. Однако, ради удобства чтения, я изменил этот параметр, чтобы сохранить максимальную верхнюю границу, которая может быть 255 или 65535, потому что сейчас нельзя сказать, что все меняется SPECIAL_SWITCH для не прочитав весь метод.

private static final NavigableSet<Integer> upperBoundaries;

static {
upperBoundaries = new TreeSet<>();
upperBoundaries.add((1 << 8) - 1); //255
upperBoundaries.add((1 << 16) - 1); //65535
}

/*
* Calculates the binary logarithm rounded up to an integer
*/
private static int log2ceil(int value) {
if (value <= 0) {
throw new IllegalArgumentException("value must be positive");
} else {
return 32 - Integer.numberOfLeadingZeros(value - 1);
}
}

/*
* Let's assume the method accepts a List<Integer>
* instead of a List<EncodingData>
*/
private String transcodeSpecialOrMultipleRegularElements(List<Integer> frequencies) {

Integer maximumUpperBoundary = Integer.MIN_VALUE; //can be null, hence Integer and not int
for (int frequency : frequencies) {
if (frequency > maximumUpperBoundary) {
maximumUpperBoundary = upperBoundaries.ceiling(frequency);
if (maximumUpperBoundary == null) {
break;
}
}
}

OptionalInt specialSize;
if (maximumUpperBoundary == null) {
specialSize = OptionalInt.empty();
} else {
int bytesNeededPerElement = (int) Math.ceil(log2ceil(maximumUpperBoundary + 1) / 8.0);
specialSize = OptionalInt.of(2 + frequencies.size() * bytesNeededPerElement);
}

//...
}

Отметим, что цикл определения максимальной верхней границей является расторгнутым после того, как частота больше, чем 65535 встречаются, потому что любая последующая частота не может повлиять на максимальную верхнюю границу, тогда как код проходит через весь список EncodingData объекты, даже если там уже был элемент с частотой больше, чем 65535, так что вы можете также сохранить игру. Я также сделал specialSize в OptionalIntтак что это только содержит значение, если оно имеет отношение (кроме того, прописные буквы имена переменных обычно используется только для констант, т. е. неизменяемым static final полей, так что я изменил имя переменной в specialSize).

Далее о методе transcodeUsingSpecialElements(List<EncodingData> run, char element). Помимо варварского дублирование кода (в if(element == 'R') и else блок отличается только в маркере характер и ширина формата строки), Я бы изменить способ так, что ширина тоже передается как параметр, как характер. Вот кстати, подтверждение законности сочетание символа и строки формата ширина является обязанностью абонента, в то время как сейчас эта ответственность дублируется в обоих transcodeUsingSpecialElements и transcodeSpecialOrMultipleRegularElements, что делает код запутанным и хрупкая (хрупкая в том смысле, что, если вы когда-нибудь хотели бы поменять R и Sвам придется переписать оба метода, если вы проходите ширина в качестве параметра, вы должны только переписать transcodeSpecialOrMultipleRegularElements).

Кроме того, есть некоторые случаи, когда небольшие изменения в код может сделать его более лаконичным и, таким образом, легче читать. Например, этот код:

runCounter++;

if(runCounter == 255){
runCounter = 0;
sizeCounter -=255;
}

Можно заменить это:

runCounter = (runCounter + 1) % 255;
sizeCounter--;

Или этот код:

if(runCounter == 0){
if(sizeCounter < 255){
specBuilder.append('R');
specBuilder.append(String.format("%03d", sizeCounter));
}else{
specBuilder.append('R');
specBuilder.append("255");
}
}

Может быть упрощен до:

if (runCounter == 0) {
specBuilder.append('R');
specBuilder.append(String.format("%03d", Math.min(sizeCounter, 255)));
}

Кроме того, я бы предложил переименовать переменную sizeCounter что-то вроде elementsRemaining, что бы описать свои цели более четко.

Наконец, я думаю, что есть еще ошибка в transcode метод. Поставив строку

transcodeUsingRegularElements(data);

в конце петли через элементы, один-бин-элементы будут преобразованы в два раза, потому что они добавляются run и транскодируется в вышеупомянутой линии.

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

1
ответ дан 13 апреля 2018 в 01:04 Источник Поделиться

В соответствии с этим, String.format() это дорогостоящая операция, которая имеет смысл, так как формат должен быть проанализирован (каждый раз это называется). Я хотел обратиться за помощью некоторые библиотеки, такие как Apache StringUtils или гуава делать необходимые отступы, а затем заменить формат с concatanation.

Кроме того, я не анализировал код, но если список Большой, можно разделить и параллельной обработке (возможно, с помощью Fork-присоединяйтесь к ДП), то это будет способствовать значительному росту объемов

0
ответ дан 12 апреля 2018 в 02:04 Источник Поделиться