Нужно оптимизировать последовательную передачу данных

Question

Моя текущая функция:

void Path(Point j){
   if(j.y > 0 && j.y <= a){
      char moveMsg[1] = {'j'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > a && j.y <= b){
      char moveMsg[1] = {'i'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > b && j.y <= c){
      char moveMsg[1] = {'h'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > c && j.y <= d){
      char moveMsg[1] = {'g'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > d && j.y <= e){
      char moveMsg[1] = {'f'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > e && j.y <= f){
      char moveMsg[1] = {'e'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > f && j.y <= g){
      char moveMsg[1] = {'d'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > g && j.y <= h){
      char moveMsg[1] = {'c'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > h && j.y <= i){
      char moveMsg[1] = {'b'};
      write(fd1, moveMsg, 1);
   }
   else if(j.y > i && j.y <= r){
      char moveMsg[1] = {'a'};
      write(fd1, moveMsg, 1);
   }
}

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

Спасибо!

Answer 1

• Если целочисленные значения переменных a, b, c... i, а также r монотонно возрастающие, тогда условия можно оптимизировать.
• Повторный доступ к элементу структуры и элементу массива может быть оптимизирован для локальных переменных масштабирования.
• Повторное выделение и освобождение локальной переменной может быть исключено для оптимизации времени.

• Повторение системного вызова write() может быть исключено для оптимизации пространства и удобства сопровождения кода.

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

Следующее (проверено и) может быть оптимальным для пространства и времени.

void Path(Point j)
{
   int val = j.y;
   char moveMsg = 0;

   /* ASSERT(0 < a < b < c < d < e < f < g < h < i < r) */

   if (val <= e) {
      if (val <= b) {
         if (val <= a) {
            if (val > 0)   /* && val <= a */
               moveMsg = 'j';
         } else    /* val <= b && val > a */
            moveMsg = 'i';
      } else {  
         if (val <= c)      /* && val > b */
            moveMsg = 'h';
         else if (val <= d) /* && val > c */
            moveMsg = 'g';
         else      /* val <= e && val > d */
            moveMsg = 'f';
      }
   } else {
      if (val <= h) {
         if (val <= f)      /* && val > e */
            moveMsg = 'e';
         else if (val <= g) /* && val > f */
            moveMsg = 'd';
         else      /* val <= h && val > g */
            moveMsg = 'c';    
      } else {
         if (val <= i)      /* && val > h */
            moveMsg = 'b';
         else if (val <= r) /* && val > i */
            moveMsg = 'a';
      }
   }

   if (moveMsg)
      write(fd1, &moveMsg, 1);
}

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

---

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

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

---

добавление

Не могли бы вы объяснить, почему вы сделали такие заявления if? Зачем делать больше, если заявления помогают сделать это быстрее?

В оптимизированном коде 11 операторов if для поиска диапазона; это только одно "больше", чем оригинальный код.
Более того, каждый оператор if представляет собой всего лишь одно простое целочисленное сравнение, а не оригинальное составное логическое выражение двух сравнений.
С точки зрения количества фактических операций ALU (а не сложности исходного кода), исходный код явно дороже, чем оптимизированный код.

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

Наихудший сценарий с исходным кодом происходит, когда входное значение равно максимальному значению r,
Именно тогда исходный код должен выполнить все 10 операторов if и выполнить 20 целочисленных сравнений.
Оптимизированный код использует двоичный поиск, который выполняет 4 оператора if и выполняет только 4 сравнения целых чисел для того же ввода.
В худшем случае с оптимизированным кодом выполняется 4 оператора if и 4 сравнения целых чисел.

В лучшем случае сценарий с исходным кодом происходит, когда входное значение равно минимальному значению a,
Исходный код должен выполнять только 1 оператор if, но для этого требуется 2 целочисленных сравнения.
Оптимизированный код будет выполнять 4 оператора if и выполнять 4 сравнения целых чисел для того же ввода.
Это только 2 сравнения, и это количество сравнений, влияющих на время выполнения, а не количество операторов if в исходном коде.
Наказание еще двух сравнений для этого лучшего случая компенсируется значительным преимуществом в 16 меньших сравнений для худшего случая.

В среднем случае предпочтение отдается оптимизированному коду с использованием бинарного поиска.
Исходные операторы 5 if, выполняющие 10 целочисленных сравнений, медленнее, чем оптимизированные 4, если операторы, выполняющие только 4 целочисленных сравнения.
Это преимущество 6 целочисленных сравнений.

На самом деле, если только входное значение не превышает a (т. е. первый интервал), тогда оптимизированный код выполнит то же число или меньшее число целочисленных сравнений, чем исходный код, несмотря на появление большего количества операторов if.

Это кажется мне нелогичным.

При использовании алгоритмов поиска (и сортировки) простой или прямой обычно означает медленный.