Длинное ЕСЛИ дерево со строками - PullRequest
1 голос
/ 27 марта 2010

У меня есть программа на C, которая использует Lua для написания скриптов. Чтобы сохранить читабельность и избежать импорта нескольких констант в отдельных состояниях Lua, я сжимаю большое количество функций в рамках простого вызова (например, «ObjectSet (id,« ANGLE », 45)»), используя «действие» строка.

Для этого у меня есть большое дерево if, сравнивающее строку действия со списком (например, "if (stringcompare (action," ANGLE ") ... else if (stringcompare (action," X ") ... и т.д. ")

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

А с Lua в интенсивном использовании, может быть, есть способ использовать его для этой цели? (встроенные «куски» составляют словарь?) Хотя эта часть в основном из любопытства.

Редактировать: я должен отметить, что я не использую C ++

Ответы [ 8 ]

4 голосов
/ 27 марта 2010

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

typedef enum objectsetAction {
  objectset_angle = 0,
  objectset_other,
  ...
} objectsetAction;

Затем определите функцию ObjectSet, которая будет принимать аргумент objectsetAction вместо строки.

Таким образом, вы можете просто написать

switch(action) {
  case objectset_angle:
    //dostuff
    break;
  case objectset_other:
    //dostuff
    break;
  ...
}
1 голос
/ 27 марта 2010

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

Вот эскиз дизайна:

typedef struct action {
    const char *name;
    int (*doit)(lua_State *L, int idx);
} *Action;

static Action my_actions[] = {
  { "angle", set_angle },
  { "color", set_color },
  ...
  { NULL, NULL }
};

int i_replace_nest_of_ifs(lua_State *L) {
  const char *action = luaL_checkstring(L, 1);
  for (int i = 0; my_actions[i].name && strcmp(my_actions[i].name, action); i++)
    ;
  if (my_actions[i].name) 
    return my_actions[i].doit(L, 2);
  else
    return luaL_error("Asked for unknown action '%s'", action);
}

Если линейный поиск по действиям становится слишком дорогим, вы можете отсортировать по имени при открытии библиотеки, а затем позвонить bsearch.

1 голос
/ 27 марта 2010

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

Вы можете легко превратить звонок, например, ObjectSet(id, "ANGLE", 45), в звонок, подобный actions.ANGLE(id,45).

. Для этого необходимо организовать actions таблица, содержащая функции для реализации каждого действия.Самый простой способ - задействовать блок кода Lua, который инициализирует таблицу, но это, безусловно, также можно сделать со стороны C.

actions = {
  ANGLE = function(id,theta)
              -- do something with id and theta 
          end,
  X = function (id, x)
      -- do something with id and x
      end,
}

или, возможно, более ясно, как

module("actions")
function ANGLE(id,theta)
  -- ...
end

function X(id,theta)
  -- ...
end

Из C вы можете реализовать ObjectSet() что-то вроде этого (не проверено):

void ObjectSet(int id, const char *action, int arg) {
    lua_getglobal(L,"actions");
    lua_getfield(L,-1,action);
    lua_remove(L,-2);
    lua_pushinteger(L,arg);
    if (lua_pcall(L,1,0,0)) {
        fprintf(stderr, "Lua error: %s\n", lua_tostring(L,-1));
    }
    return;
}

Реальная обработка ошибок оставлена ​​в качестве упражнения.Обратите внимание, что lua_pcall() используется здесь, чтобы ошибки Lua не распространялись из ObjectSet().Если вы используете C ++, вы должны быть осторожны, потому что Lua использует setjmp() и longjmp() для ошибок, которые, как правило, должны переводиться в исключения C ++ путем перехвата ошибки Lua и создания подходящего исключения.

I 'Мы также естественным образом оставили ассоциирование идентификатора объекта с реальным объектом на стороне Lua в качестве упражнения.Однако вы можете реализовать все функции из таблицы actions в C и в значительной степени избежать этой проблемы.

1 голос
/ 27 марта 2010

Вы можете создать себе автомат , который проверяет символ за символом, например

if (curChar == 'a')
{
  curChar = next;
  if (curChar == 'b')
  {
     // all strings that begin with "ab"
  }
}

Это оптимизирует сравнения, имеющие O (n) вместо O (n * m) для всей цепочки if. Конечно, вам не придется делать это вручную: вы можете искать автоматизированный инструмент, который может построить ваш соответствующий автомат из нужных вам строк ... на самом деле это похоже на то, что делает регулярное выражение.

В противном случае, если вы хотите O (1) O (nlogn) (извините, думал, что вместо хеш-карты используется двоичное дерево), вы можете использовать std::map и хранить строки в качестве ключей и указателей. к функциям как значениям, они представляют поведение каждого другого выполнения строки. Таким образом, с помощью O (1) вы получаете правильный указатель и затем вызываете эту функцию.

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

Используя первый подход, вы эффективно получите O (1) (если хеш-карта не слишком мала по сравнению с количеством строк), а с другим вы в конечном итоге получите смиллярный подход к автомату.

Для хэш-карты вам просто нужно:

  • способ вычисления хеш-кода строки: вы можете просто сделать int hash = string[0]^31 + string[1]^30 + ..., чтобы получить хорошее уникальное число, представляющее вашу строку.
  • затем с хорошей хеш-функцией отметьте здесь вы можете преобразовать хеш-код в индекс массива указателей на функции и получить нужный элемент.
  • вам понадобится способ обработки коллизий (две строки, заканчивающиеся на один и тот же индекс хеш-таблицы)

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

Извините, если я предложил C ++, но не учел, что вы спрашиваете о простом C, std::map является компонентом стандартной библиотеки шаблонов, которая используется для хранения пар значений <key, value>. В вашем случае у вас будет <string, funcPointer>, но, как указано в комментариях, сложность будет O (nlogn) для их поиска.

0 голосов
/ 27 марта 2010

Поскольку вы указываете C, а не C ++, отсортированные параллельные массивы:

#define VERB_COUNT 10
void *context_data;
char *verbs[VERB_COUNT] = { "ABC", "DEF", "GHI", ... }; // sorted list
int (*actions[VERB_COUNT])(void *) = { abc_func, def_func, ghi_func, ... };
int idx, ret = -1;

int idx = bsearch(action, verbs, VERB_COUNT, sizeof char*, strcmp); // I think I got these in the right order
if (idx >= 0)
   ret = (*actions[idx])(context_data);
return ret;
0 голосов
/ 27 марта 2010

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

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

0 голосов
/ 27 марта 2010

Простой способ:
Тривиальной заменой было бы заменить ваши «строки действия» на enum, который вы определяете; это будет работать точно так же, за исключением того, что оператор switch для enum (по сути, целое число) намного быстрее, чем сравнение строк. switch также будет выглядеть намного красивее ( imo:) ), чем дерево if, как вы описываете.

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

0 голосов
/ 27 марта 2010

вы всегда можете поиграть с троичными операторами. Например, вместо того, чтобы делать что-то вроде

   if(condition){
        a=b+c;
   }else{
        a=b+d;
   }

Вы можете заменить его на

   a=b+(condition?c:d);

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...