Nano Hash - криптовалюты, майнинг, программирование

Оптимизация цикла с манипуляциями с QString

В моем проекте я написал функцию для распаковки QString, которая сжата с использованием очень простого формата сжатия, который я написал в отдельной функции. Но после некоторого тестирования я обнаружил, что эта функция вызывает массовые замедления, поскольку она запускается на огромных QString и вызывается более 2900 раз.

Я пытался изменить эту функцию, чтобы она работала быстрее. Я баловался с QStringRef без хороших результатов (возможно, я сделал это неправильно). С QByteArrays и QByteRefs сложно работать и проверять значения (imo).

Мне действительно нужна помощь в оптимизации этой функции, чтобы она работала БЫСТРО! Как можно быстрее! Я считаю, что постоянный вызов .mid замедляет работу, но я просто не знаю другого способа читать/записывать байты.

РЕДАКТИРОВАТЬ: Лучший вопрос, есть ли обычная практика, которую я пропускаю, когда дело доходит до функций декомпрессии? Я использую zlib позже в этой же программе, и она сжимает быстрее, чем эта простая функция, которую я написал ниже. Почему это? Что zlib делает по-другому?

Спасибо за ваше время заранее. :)


Вот как будет выглядеть очень маленькая сжатая строка QString:

//Compressed
//This QString is just a hexadecimal representation of a QByteArray
//
QString com("010203ff0504ff0a05ff00ff01ff02ff0306);

А вот каким будет тот же QString после распаковки:

//Decompressed
QString decom("0102030404040404040505050505050505050505ffffffffffff06060606);

Извините, если вы не сразу поняли формат... это не имеет большого значения. Возможно, это поможет:

-a byte with "ff" tells us we're about to decompress
-the byte after "ff" is the number of times to repeat the NEXT byte + 1
-UNLESS that number is 0, 1, or 2, then "ff" is the value to be repeated

Examples:
-"010203" decompressed is "010203"

-"ff0401" decompressed is "0101010101"

-"ff02" decompressed is "ffffff"

Это функция декомпрессии, которую я написал:

int HexToIntS(QString num_hex)  //converts the byte to a number
{
    uint num_uint;
    bool ok;
    num_uint = num_hex.toUInt(&ok,16);
    return (int)num_uint;
}
void Decompress(QString com, QString &decom)
{
    QString c;                 //current byte
    QString n;                 //new/next byte
    int bytePos(0);            //current position in QString
    int byteRepeat;            //number of times to repeat byte n

    c = com.mid(bytePos, 2);   //get first byte (01)
    decom.clear();             //clear decom just in case it had values prior

    do
    {
        bytePos = bytePos + 2;      //move the current position to the next byte
        if(c == "ff")               //is decompression happening?
        {
            c = com.mid(bytePos, 2);   //current byte is now the "next" byte
            byteRepeat = HexToIntS(c); //c tells us how many times the NEXT byte needs to be repeated

            if(byteRepeat <= 2)        //if c's value is <= 2... then ff is the value
            {
                n = "ff";              //new byte is just ff
                bytePos = bytePos + 2; //update the current position
            }
            else                       //if not, then c is the number of times the NEXT byte should be appended
            {
                n = com.mid(bytePos + 2, 2); //new byte is the NEXT byte
                bytePos = bytePos + 4;       //update the current position
            }

            for(int j = 0; j<=byteRepeat; j++)//append n the correct number of times
                decom.append(n);
        }
        else                   //guess we're not decompressing, so just append c
            decom.append(c);
        c = com.mid(bytePos, 2);   //get the new current byte
    }while(bytePos < com.length());  //stop when all bytes were read
}

Текущая оптимизированная функция на основе ваших комментариев: (на 5%-10% быстрее только в режиме отладки)

void Decompress2(const QString com, QString &decom)
{
    QStringRef c;
    QString n;
    int bytePos(0);
    int byteRepeat;

    c = com.midRef(bytePos, 2);
    decom.clear();

    do
    {
        bytePos = bytePos + 2;
        if(c == "ff")
        {
            c = com.midRef(bytePos, 2);
            byteRepeat = c.toString().toInt(0,16);

            if(byteRepeat <= 2)
            {
                n = "ff";
                bytePos = bytePos + 2;
            }
            else
            {
                n = com.mid(bytePos + 2, 2);
                bytePos = bytePos + 4;
            }

            for(int j = 0; j<=byteRepeat; j++)
                decom.append(n);
        }
        else
            decom.append(c);
        c = com.midRef(bytePos, 2);
    }while(bytePos < com.length());
}
04.06.2015

  • Вы можете использовать профилировщик, чтобы увидеть, какая часть вашей функции занимает много времени, и попытаться оптимизировать/изменить/заменить эту часть эквивалентным кодом, который работает быстрее. 04.06.2015
  • Да, я изучал это. Вскоре я сделаю это для всего рабочего потока. Я всю ночь комментировал части своей программы, эта функция, без сомнения, вызывает огромные замедления. Что-то сразу кажется вам неправильным? 04.06.2015
  • Так вы пробовали вместо этого использовать midRef? 04.06.2015
  • Я сделал c QStringRef и изменил com.mid на com.midRef. Производительность увеличилась примерно на 10%, но мне нужно больше. 04.06.2015
  • Другие вещи, которые нужно сделать: 1) используйте const& для параметра com. 2) Однозначно переходить на QByteArray: почему для вас это сложнее, чем QString? 04.06.2015
  • Кроме того, я бы предпочел, чтобы HexToIntS был встроенным. Кроме того, преобразование строки в int происходит медленно. 04.06.2015
  • Хорошо, я переключусь на QByteArray. Мне нравится манипулировать/проверять данные в операторах if, и я не нашел хорошего способа просто сравнить шестнадцатеричное представление одного байта (или байтов) с чем-то вроде ff. По сути, мне гораздо труднее визуализировать QByteArrays и проверять, что они содержат. 04.06.2015
  • HexToIntS используется во всей моей программе. Однако я скопирую его в строку. Есть ли более быстрый способ получить значение int, скажем, 0b 04.06.2015
  • Это релизная сборка? 04.06.2015
  • Релизная сборка имеет очень незначительный прирост производительности. 04.06.2015
  • Возможно, вы захотите рассмотреть возможность выполнения всего этого в QByteArrays вместо QString. 04.06.2015
  • Сейчас работаю над созданием функции с bytearrays. Если com станет QByteArray, а c станет QByteRef... как мне проверить, если c == ff? 04.06.2015
  • byteRepeat = c.toString().toInt(0,16); почему бы не просто byteRepeat = c.toInt(0,16); ? 04.06.2015
  • Я голосую за то, чтобы закрыть этот вопрос как не относящийся к теме, поскольку он касается оптимизации рабочего кода и относится к Code Review. 04.06.2015
  • Кстати, НИКОГДА не проверяйте производительность в режиме отладки. Всегда в релизе с оптимизацией. 04.06.2015
  • toInt не является членом QStringRef. И Томас, я также спросил, что zlib и другие декомпрессоры делают по-другому. Какие распространенные практики я упускаю? * Обратите внимание на режим отладки. Спасибо. 04.06.2015
  • @mc360pro В документе я прочитал это... какая версия Qt вы используете? 04.06.2015
  • Давайте продолжим обсуждение в чате. 04.06.2015
  • Вы читали документацию? В частности, немного о более эффективном построении строк? (Это не изменилось в Qt 5) 04.06.2015
  • @Thomas Я смог переделать функцию, используя QByteArrays. Это плюс новый метод, о котором я говорил, устранил проблемы замедления на 90%. Спасибо :) 05.06.2015
  • @ mc360pro Я рад это читать! 05.06.2015
  • @Thomas Я пытаюсь работать с QByteArrays, но постоянно натыкаюсь на стены. Я очень стараюсь и много читаю документацию. Это новая территория для меня. Обратите внимание на stackoverflow. com/questions/30660127/ ? 05.06.2015

Ответы:


1

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

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

#include <vector>
#include <cstdint>
#include <iomanip>
#include <iostream>

std::vector<std::uint8_t> decompress(const std::vector<std::uint8_t>& com)
{
  std::vector<std::uint8_t> decom;
  decom.reserve(com.size()); // a conservative estimate of the required size

  for(auto it = begin(com); it != end(com); ++it)
  {
    if(*it == 0xff)
    {
      ++it;
      if(it != end(com))
      {
        std::uint8_t number_of_repeats = *it;
        if(number_of_repeats <= 2)
        {
          std::fill_n(std::back_inserter(decom), number_of_repeats, 0xff);
          continue;
        }
        else
        {
          ++it;
          if(it != end(com))
            std::fill_n(std::back_inserter(decom), number_of_repeats, *it);
          else
            throw 42; // handle error in some way
        }
      }
      else 
        throw 42; // handle error in some way
    }
    else
      decom.push_back(*it);
  }
  return decom;
}
int main()
{
  std::vector<std::uint8_t> com{0x01, 0x02, 0x03, 0xff, 0x05, 0x04, 0xff, 0x0a, 0x05, 0xff, 0x00, 0xff, 0x01, 0xff, 0x02, 0xff, 0x03, 0x06};


  for(const auto& value : com)
    std::cout << std::hex << std::setfill('0') << std::setw(2) << static_cast<unsigned short>(value) << ' ';
  std::cout << '\n';
  auto result = decompress(com);

  for(const auto& value : result)
    std::cout << std::hex << std::setfill('0') << std::setw(2) << static_cast<unsigned short>(value) << ' ';
}

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

Обратите внимание, что я считаю, что ваша распакованная строка в вашем длинном примере неверна. По вашим правилам должно быть

01 02 03 04 04 04 04 04 05 05 05 05 05 05 05 05 05 05 ff ff ff 06 06 06

Начиная со спины, повторяется 06 3 раза, затем 2 раза ff, затем 1 раз ff, затем 0 раз ff, затем остальные.

04.06.2015
  • Большое спасибо за то, что сделали все возможное в своем ответе. Я объединим это с новым алгоритмом, который я построил, и дам вам знать, как это работает. И нет, декомпрессия была правильной. Повторяемое число — это следующий байт + 1. Таким образом, ff0306 будет 06060606 (03 + 1). 04.06.2015
  • Ах, кажется, я пропустил плюс 1 тогда :). И вам очень рады! Не забудьте проголосовать/принять, если считаете, что мой ответ того заслуживает;). 04.06.2015
  • Новые материалы

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

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

    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..

    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..

    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..

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

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