Оптимизация с использованием справочной таблицы - PullRequest
Новая
       19

Оптимизация с использованием справочной таблицы

0 голосов
/ 04 апреля 2011

Я сделал некоторый код c для программы, которая выполняет некоторую психоакустику для звуковых данных.

Есть фрагмент кода, который работает очень медленно.

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

Буду признателен за любые указания или помощь!:)

Ответы [ 4 ]

6 голосов
/ 04 апреля 2011

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

byteout = lut [разность / 50 + 12];

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

Между прочим, есть ошибка, все ваши отрицательные случаи отслеживаются вашим первым <=0 (мой пример предполагает, что вы хотите опустить первый случай).

2 голосов
/ 04 апреля 2011

Во-первых, посмотрите, где вы хотите первую проверку против 0, так как она делает все ваши отрицательные проверки бессмысленными.

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

Так это будет выглядеть примерно так: 

table[0] = 0b0110; // -500 through -599
table[1] = 0b0110;
...
table[100] = 0b0101; // -400 through -499
table[101] = 0b0101;
...

Поиск будет: 

if (value <= -600) {
    return 0b0111;
}
else {
    return table[value + 600];
}

Достаточно небольшое количество значений, чтобы размер массива не был запредельным. Инициализируйте цикл в начале вашей программы.

1 голос
/ 04 апреля 2011

Двоичный поиск выигрыша.

Сохраните все возможные значения в массиве и обязательно их отсортируйте.

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

Ваш массив может состоять из структур с минимальным значением и соответствующим значением byteout.

РЕДАКТИРОВАТЬ: Чтобы устранить возможные недоразумения, я имею в виду не каждое число от -1400 до 1400, а просто значения, которые вы проверяете в своем исходном коде.

0 голосов
/ 04 апреля 2011

Давайте посмотрим на первый бит: 

if (difference <= 0)
  byteout = 0b0000;
else if (difference <= -600)
  byteout = 0b0111;

Допустим, у вас есть значение -601.

Это <= 0? Да, так что <code>byteout = 0b0000;

ты никогда не доберешься до -600. Таким образом, ВСЕ отрицательные значения 0b0000. Это может быть, а может и не быть задумано, но если это так, вы можете избавиться от всех других отрицательных значений.

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

...