Задача оптимизации адаптивного ввода-вывода

Question

Вот интересная проблема оптимизации, о которой я думаю уже несколько дней:

В системе я читаю данные с устройства медленного ввода-вывода. Я не знаю заранее, сколько данных мне нужно. Точная длина известна только после того, как я прочитал весь пакет (представьте, что у него есть какой-то символ конца). Чтение большего количества данных, чем требуется, не является проблемой, за исключением того, что оно тратит время на ввод-вывод.

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

Пакеты, которые я читаю, обычно имеют размер от 9 до 64 байтов, но в редких случаях встречаются пакеты большего или меньшего размера. Весь диапазон будет от 1 до 120 байтов.

Конечно, я знаю немного о моих данных: пакеты поставляются в последовательностях одинакового размера. Я могу классифицировать три модели здесь:

Последовательности чтения с одинаковыми размерами:

   A A A A A ...

Чередующиеся последовательности:

  A B A B A B A B ...

И последовательности троек:

 A B C A B C A B C ...

Также существует особый случай вырожденных троек:

 A A B A A B A A B ...

(здесь A, B и C обозначают некоторый размер упаковки от 1 до 120).

Вопрос:

Как рассчитать размер следующего запроса на чтение в зависимости от размера предыдущих пакетов? Мне нужно что-то, что быстро адаптируется, использует мало памяти (скажем, меньше 500 байт) и быстро с вычислительной точки зрения.

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

Есть идеи?

Answer 1

Вам необходимо прочитать не менее 3 пакетов и не более 4 пакетов, чтобы определить шаблон.

1. Прочитайте 3 пакета. Если они все одинакового размера, то шаблон AAAAAA ...
2. Если они все не одинакового размера, прочитайте 4-й пакет. Если 1 = 3 и 2 = 4, шаблон ABAB. В противном случае, шаблон ABCABC ...

С этой схемой, вероятно, хорошей идеей будет умозрительное чтение 3-х размеров пакетов (что-то вроде 3 * 64 байта за один раз).

Answer 2

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

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

Затем, когда вы узнаете фактический размер сообщения, используйте правило Байеса, чтобы обновить вероятности модели, и сделайте это снова.

Может быть, этоЗвучит сложно, но если вероятности хранятся в виде дробей с фиксированной запятой, вам не придется иметь дело с плавающей запятой, поэтому кода может быть немного.Я бы использовал что-то вроде алгоритма Metropolis-Hastings в качестве базового симулятора и байесовской инфраструктуры обновления.(Это всего лишь начальная попытка обдумать это.)

Answer 3

Я не вижу здесь проблемы .. Но сначала несколько вопросов:

1) Можно ли асинхронно читать входные данные (например, отдельный поток, подпрограмма прерывания и т. Д.)?

2) Есть ли у вас свободная память для буфера?

3) Если вы задали более длинное чтение, можете ли вы получить первый байт (ы) до считывания всего пакета?

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

РЕДАКТИРОВАТЬ: я вижу .. это из-за CRC или шифрования? Ну, тогда вы могли бы использовать некоторые идеи из сжатия данных:

Рассмотрим простой адаптивный алгоритм порядка N для M возможных символов:

int freqs[M][M][M]; // [a][b][c] : occurences of outcome "c" when prev vals were "a" and "b"
int prev[2];    // some history

int predict(){
    int prediction = 0;
    for (i = 1; i < M; i++)
        if (freqs[prev[0]][prev[1]][i] > freqs[prev[0]][prev[1]][prediction])
        prediction = i;
    return prediction;
};

void add_outcome(int val){
    if (freqs[prev[0]][prev[1]][val]++ > DECAY_LIMIT){
        for (i = 0; i < M; i++)
            freqs[prev[0]][prev[1]][i] >>= 1;
    };
    pred[0] = pred[1];
    pred[1] = val;
};

freqs должен быть массивом порядка N+1, и вы должны запомнить N прежних значений. N и DECAY_LIMIT должны быть скорректированы в соответствии со статистикой ввода. Однако даже их можно сделать адаптивными (например, если произойдет слишком много промахов, тогда предел затухания может быть сокращен).

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