Как улучшить набор условий else-if, которые оценивают переменную внутри диапазона среди известных значений?

Question

Есть ли способ преобразовать этот код ниже во что-то более масштабируемое? Я упростил это, но мой реальный должен проверить несколько различных значений, и он требует рефакторинга.

     if (x < 0) foo1();
else if (x < 3) foo2();
else if (x < 8) foo3();
else            foo4();

Я пробовал следующее:

struct Ptr2foo {
    void (*foo_x)();
}

Ptr2foo ptr2foo_x[4] {
    foo1,
    foo2,
    foo3,
    foo4
}

ptr2foo_x[someMagicWithMy_X_AndMyKnownValues].foo_x();

Те значения известны до компиляции, и такое количество условий внутри al oop снижает производительность.

Является ли это наилучшим способом решения этой проблемы? Любое альтернативное решение с его объяснением высоко ценится

Answer 1

В общем случае, когда у вас есть интервалы [a1, a2), [a2, a3), ..., [an, infty) и вы хотите найти интервал, в котором лежит x, вы можете сделать это с помощью сравнения log n в худшем случае (по сравнению с вашей цепочкой if-else, * в худшем случае n сравнения). Вы делаете это, выполняя бинарный поиск по интервалам. Таким образом, вы сначала проверите, меньше ли x, чем a(n/2), а затем еще раз проверьте меньшие интервалы в if и большие в else. Для вашего примера, приведенного выше, преобразуйте

     if (x < 0) foo1();
else if (x < 3) foo2();
else if (x < 8) foo3();
else            foo4();

, который имеет 4 сравнения на самом длинном пути и 1 на его самом коротком пути до

if( x < 3 ) {
  if( x < 0 ) foo1();
  else        foo2();
} else {
  if( x < 8 ) foo3();
  else        foo4();
}

Это имеет 2 сравнения на всех его путях.

Обратите внимание, что меньшее количество сравнений в худшем случае не обязательно быстрее. Это быстрее, если x примерно одинаково распределен. Если x отрицателен в 90% случаев, ваша первая версия будет быстрее, так как в основном она будет использовать только одно сравнение, в то время как моя версия всегда использует 2.

Вот почему вы должны также подумать о том, что является горячим путем (то есть наиболее частым путем) через этот код. Если, возможно, x в большинстве случаев равно как минимум 8, вам обязательно нужно сначала проверить его и так далее.

Answer 2

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

m_map.insert(std::make_pair(0, foo1));
m_map.insert(std::make_pair(3, foo2));
m_map.insert(std::make_pair(8, foo3));

, тогда вы можете просто получить нужную функцию с помощью m_map[1]. это вернет первую функцию на карте.

Примечание: я даю ссылку в качестве примера. Реализация может быть проблематичной c. Вам лучше проверить это перед использованием.