Преобразование значение по таблице

const int base = 1234;
int conversion_table[] = { 0, 1, 2, 3, ... };

inline int
convert_value(int i) { return base + conversion_table[i]; }

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

Я тоже думал об этом в первую очередь, но проблема в том, что между значениями большие промежутки.

Я бы switch оставил.

Решил тут упороться.

/*
 * 1 => 77
 * 7 => 2
 * 9 => 99
 * 11 => 8
 * 31 => 81
 * 77 => 5
 * 81 => 333
 * 9999 => 0
 */

/* Всего преобразований 2 ** QSIZE */
#define QSIZE 3

int tr[] = {
    31, 16, 81, 10, 9999, 8, 9999, 0,
    81, 333, 77, 14, 77, 5, 31, 81,
    9, 24, 11, 22, 11, 8, 9, 99,
    7, 28, 7, 2, 1, 77};

int translate(int input)
{
    int idx = 0;                                                    
    int i;                                                          
    for (i = 0; i < QSIZE; ++i) {                                   
        if (input < tr[idx]) {                                      
            idx = tr[idx + 1];                                      
        } else {                                                    
            idx += 2;                                               
        }
    }

    if (input == tr[idx]) {
        return tr[idx+1];
    }

    return -1;
}

Выглядит громоздко.

Поместите case и return на одной строке! Куда уж короче?

Можешь рассказать, как генерируется таблица?

Это лучше бы нарисовать. А вообще, в коде же видно :)
Коротко, в таблице содержатся пары:

int tr[] = {
/* 0 */    31, 16, // 1е число для сравнения, смещение следующей пары, если меньше
/* 2 */    81, 10, // 2е...
/* 4 */    9999, 8, // 3е...
/* 6 */    9999, 0, // 9999 => 0, это уже преобразование
/* 8 */    81, 333, //   81 => 333
/* 10 */    77, 14,
/* 12 */    77, 5,   //   77 => 5
/* 14 */    31, 81,  //   31 => 81
/* 16 */    9, 24, // 2е число для сравнения если в первом было меньше
/* 18 */    11, 22,
/* 20 */    11, 8,   //   11 => 8
/* 22 */    9, 99,   //    9 => 99
/* 24 */    7, 28,
/* 26 */    7, 2,    //    7 => 2
/* 28 */    1, 77,   //    1 => 77
};

А насколько большой разброс у этих 10-20 int'ов? Если небольшой, почему бы не сделать их индексом массива?
Правда, строить его нужно будет отдельно, но это тоже можно вынести на этап компиляции, раз уже там всё это известно.

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

1 | 7 | 9 | 11 | 31 | 77 | 81 | 9999
                 31 <- 1е сравнение
        9                  81 <- 2е сравнения
    7       11        77        9999 <- 3е сравнения

struct
{
  int from;
  int to;
} mapping[] = 
{
  { from1, to1 },
  { from2, to2 },
  .....
};

Лучше расположить значения упорядоченно, можно будет тогда искать делением пополам. Если значений действительно 10-20, то пофиг, хоть обычный for напиши.

Но будет ли это эффективнее по скорости, чем простой switch на небольшом объёме данных?

Целиком зависит от того, во что превратит этот switch твой компилятор. А вообще, ты уверен, что на небольшом объёме данных тебе так уж важна скорость? Это реально узкое место? Дергается в цикле?

Тебе надо X_MACRO.

Если набор данных известен - для него можно сгенерировать Perfect Hash Function. Её возвращаемое значение число от от нуля до количества элементов-1, который дальше можно использовать как индекс в массиве.

Для строк код такой функции генерируется GNU gperf, для чисел - не знаю.

Если разброс значиний не слишком большой (и не заморачиваться на размер data section), то можно сделать так:

#define nelem(x) (sizeof(x) / sizeof((x)[0]))
#define value(x) ((x) + 1)

int map[] = {
	[1]    = value(77),
	[7]    = value(2),
	[9]    = value(11),
	[11]   = value(8),
	[31]   = value(81),
	[77]   = value(5),
	[81]   = value(333),
	[9999] = value(0),
};

int
get(int a)
{
	if (a >= 0 && a < nelem(map))
		return map[a] - 1;
	return -1;
}

UPD: поправил, что бы возващал -1 для неуказанных элементов.

Конечно же написать на хаскеле программу, которая будет генерить нужный сишный код:

import Data.List

align :: String -> String
align code = unlines $ map ("   "++)  (lines code)

cIf c t e = "if(" ++ c++ "){\n" ++ align t ++ "} else {\n" ++ align e ++ "}\n"

tableSmall :: [(String, String)] -> String
tableSmall t = "case(x){\n" ++ (align $ unlines $ map l t ++ ["default: return -1;"]) ++ "}\n"
    where l (x, y) = "case " ++ x ++ ": return " ++ y ++ ";"

table :: [(String, String)] -> String
table t | length t <=4   = tableSmall t
        | otherwise = cIf ("x<="++pivot) (table ht1) (table ht2)
            where xs = map fst t
                  ys = map snd t
                  n = length xs
                  ht1 = take (n `div` 2) t
                  ht2 = drop (n `div` 2) t
                  pivot = fst $ last ht1
          
tableFunction name t = "int " ++ name ++ "(int x){\n" ++ align (table st) ++ "}"
    where st = map (\(a, b) -> (show a, show b)) (sort t)

Чтобы потом просто делать вот так:

Prelude> :l generate.hs 
[1 of 1] Compiling Main             ( generate.hs, interpreted )
Ok, modules loaded: Main.
*Main> putStrLn $ tableFunction "f" [(4, 14), (2, 12), (777, 5), (3, 13), (1, 11), (7, 17), (0, 10), (105, 3453), (999, 666)]
int f(int x){
   if(x<=3){
      case(x){
         case 0: return 10;
         case 1: return 11;
         case 2: return 12;
         case 3: return 13;
         default: return -1;
      }
   } else {
      if(x<=7){
         case(x){
            case 4: return 14;
            case 7: return 17;
            default: return -1;
         }
      } else {
         case(x){
            case 105: return 3453;
            case 777: return 5;
            case 999: return 666;
            default: return -1;
         }
      }
   }
}

У меня objdump на этом примере сломался или как увидеть инициализацию массива?

$ objdump -D -S -Mintel -j.data test.o

test.o:     file format elf32-i386


Disassembly of section .data:

00000000 <map>:
       0:       00 00                   add    BYTE PTR [eax],al
        [9999] = value(0),
};

int
get(int a)
{
       2:       00 00                   add    BYTE PTR [eax],al
        if (a >= 0 && a < nelem(map))
       4:       4e                      dec    esi
        ...
                return map[a] - 1;
      19:       00 00                   add    BYTE PTR [eax],al
      1b:       00 03                   add    BYTE PTR [ebx],al
      1d:       00 00                   add    BYTE PTR [eax],al
      1f:       00 00                   add    BYTE PTR [eax],al
      21:       00 00                   add    BYTE PTR [eax],al
        return -1;
      23:       00 0c 00                add    BYTE PTR [eax+eax*1],cl
      26:       00 00                   add    BYTE PTR [eax],al
}
      28:       00 00                   add    BYTE PTR [eax],al
      2a:       00 00                   add    BYTE PTR [eax],al
      2c:       09 00                   or     DWORD PTR [eax],eax
        ...
      7a:       00 00                   add    BYTE PTR [eax],al
      7c:       52                      push   edx
        ...
     131:       00 00                   add    BYTE PTR [eax],al
     133:       00 06                   add    BYTE PTR [esi],al
        ...
     141:       00 00                   add    BYTE PTR [eax],al
     143:       00 4e 01                add    BYTE PTR [esi+0x1],cl
        ...
    9c3a:       00 00                   add    BYTE PTR [eax],al
    9c3c:       01 00                   add    DWORD PTR [eax],eax
        ...

P.S.

Язык программирования можно указать в параметре, например [code=java]. Поддерживаются следующие языки:

А ассемблера нет - непорядок.

Не годный у тебя objdump. ж) Вот тебе мой:

map:     file format elf64-x86-64


Disassembly of section .data:

0000000000601240 <__data_start>:
        ...

0000000000601248 <__dso_handle>:
        ...

0000000000601280 <map>:
  601280:       00 00                   add    BYTE PTR [rax],al
  601282:       00 00                   add    BYTE PTR [rax],al
  601284:       4e 00 00                rex.WRX add BYTE PTR [rax],r8b
        ...
  60129b:       00 03                   add    BYTE PTR [rbx],al
  60129d:       00 00                   add    BYTE PTR [rax],al
  60129f:       00 00                   add    BYTE PTR [rax],al
  6012a1:       00 00                   add    BYTE PTR [rax],al
  6012a3:       00 0c 00                add    BYTE PTR [rax+rax*1],cl
  6012a6:       00 00                   add    BYTE PTR [rax],al
  6012a8:       00 00                   add    BYTE PTR [rax],al
  6012aa:       00 00                   add    BYTE PTR [rax],al
  6012ac:       09 00                   or     DWORD PTR [rax],eax
        ...
  6012fa:       00 00                   add    BYTE PTR [rax],al
  6012fc:       52                      push   rdx
        ...
  6013b1:       00 00                   add    BYTE PTR [rax],al
  6013b3:       00 06                   add    BYTE PTR [rsi],al
        ...
  6013c1:       00 00                   add    BYTE PTR [rax],al
  6013c3:       00 4e 01                add    BYTE PTR [rsi+0x1],cl
        ...
  60aeba:       00 00                   add    BYTE PTR [rax],al
  60aebc:       01 00                   add    DWORD PTR [rax],eax
        ...

Весь это блоб и есть int map[] — 1000 записей по sizeof(int).

Но, если честно этот вариант не намного лучше варианта со switch, а может даже и хуже.

В теории он должен быть быстрее (просто индекс в массив), но жрёт больше места. Но это скорей всего не так, т.к. компилятор сам соптимизирует switch и получится тоже самое, но с меньшим объёмом данных.

Блин, ошибся, там нужно везде case(x) заменить на switch(x).

Не годный у тебя objdump. ж)

А, тогда годный. Просто зная, что там int, т.е. значения по 4 байта, можно было бы группировать по 4, а не по 2. Да и дизассемблировать данные... эм, тоже лишнее. Так что теперь вижу:

00000000 <map>:
int map[] = {
       0:       00 00
       2:       00 00
[1]    = value(77),
       4:       4e       -->   04: 4e
        ...
      19:       00 00
[7]    = value(2),
      1b:       00 03    -->   1c: 03
      1d:       00 00
      1f:       00 00
      21:       00 00
[9]    = value(11),
      23:       00 0c    -->   24: 0c
      26:       00 00
      28:       00 00
      2a:       00 00
[11]   = value(8),
      2c:       09 00    -->   2c: 09
        ...
      7a:       00 00
[31]   = value(81),
      7c:       52       -->   7c: 52
        ...
     131:       00 00
[77]   = value(5),
     133:       00 06    -->  134: 06
        ...
     141:       00 00
[81]   = value(333),
     143:       00 4e 01 -->  144: 014e
        ...
    9c3a:       00 00
[9999] = value(0),
    9c3c:       01 00    --> 9c3c: 01
        ...

P.S. а что нужно, чтобы к движку ЛОРа прикрутить подсветку ассемблера?

поскольку значения на этапе компиляции известны, запихнуть их в массив в отсортированном порядке, а затем в рантайме искать двоичным поиско

Это может быть быстрее свитча.

А еще быстрее был бы хардкод с двоичным поискам на if:

if(x<10){
    if(x<5){
      ..
    }else{
      ..
    }
} else{
    if(x<20){
      ..
    }else{
      ..
    }
}

Хм, налабал простенький бенч, и вот результат:

1000000 times map: 3.229190s
1000000 times switch: 4.083110s

А сравни еще с хардкод-бинарным поиском от Waterlaz'а позязя

В вот ещё 2 других предложенных решения:

1000000 times map: 3.371125s
1000000 times switch: 4.098025s
1000000 times translate: 8.200937s
1000000 times f: 3.590784s

Обновил gist + см. чуть выше.

Предлагаю довести таблицу до 10-20 значений, как это указано в условии.

На всякий случай, исправленная версия генерилки: http://pastebin.com/J0ACyM0X

Т.ч. индекс в массив всё же быстрее. Т.ч. классический trade-off RAM vs. CPU.

Теперь бы ещё с хеш-функцией попробовать.

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

Но почему бы не переложить оптимизацию на оптимизирующий компилятор? Разумеется, без доп. инфы он это не осилит. Так может для switch есть какие-то pragma подсказки компилятору, в какую сторону оптимизировать: сортировка case'ов, хеш-функция, бинарный поиск, большой массив?

Ну что, устроем новый LOR-Contest 2.0? ;)

У тебя для Waterlaz'овского кода другая таблица используется, если что :)

А ещё, если использовать ту таблицу (9999 -> 0), то для свича на 4 там всего один if...

KivApple, таки скинь нам пример таблицы на 20 интов, м?

Оно пробегает по всем значениям от 0 и до 1000. Т.ч. размер там особой роли не играет.

Нужно только договориться о двух принципиальных вещах:

1) Какой диапазон чисел на входе?

2) Как часто числа на входе не попадают в таблицу. Это достаточно принципиальный вопрос, кмк. Если следовать духу условия ТС, то это должно быть относительно редко (уж точно реже, чем в существующем тесте).

Размер таблицы и разброс значений будут играть роль для бинарного поиска.

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

Значит определяйтесь с условиями, а я опять буду координировать. ;)

/me AFK на пару часиков. Позже загляну.

Действительно, пусть KivApple предложит нам одну таблицу.

Содержит 10-20 значений типа int

Выглядит громоздко. Как это можно реализовать лучше на plain C? Без привлечения сторонних библиотек

1. можно таблицу сортировать и юзать bsearch,

2. можно по таблице на этапе компиляции генерить ваши case с бантиками

Можно запилить какую-нибудь самодельную реализацию хеш-таблицы

3. лучше оставить как есть :-) 10-20 значений - это ничто..какие тут нахрен хеш-таблицы от пары десятков интов ??

3. лучше оставить как есть :-) 10-20 значений - это ничто..какие тут нахрен хеш-таблицы от пары десятков интов ??

Наверное, этот switch - hotspot. В свитче нужно провести до 20 сравнений (а gcc его как оптимизирует?), а в хеш-таблице, может, 1-2 операции.

В свитче нужно провести до 20 сравнений (а gcc его как оптимизирует?)

В тот же двоичный поиск и оптимизирует, так что ln(20)

В тот же двоичный поиск и оптимизирует, так что ln(20)

Не надо тут сказки рассказывать. Впрочем, пойду проверю.

Блин, ты прав...

Я уже пришёл к выводу, что действительно лучшим решением будет преобразовывать не два произвольных набора int в два произвольных наборов int, а сначала int в индексы в массиве, а уже в массиве хранить во что int преобразуется.

1073807360 -> 0
1073741824 -> 1
1073742848 -> 2
1073743872 -> 3
1073744896 -> 4
1073745920 -> 5
1073746944 -> 6
1073808384 -> 7
1073823744 -> 8
1073824768 -> 9
1073825792 -> 10
1073747968 -> 11
1073748992 -> 12
1073750016 -> 13

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

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

Посмотрел ассемблерный листинг своего кода - там явно не тупое сравнение со всеми вариантами. Возможно, case действительно является наиболее оптимальным вариантом.

Нульчую x-macro и свич:

Пишешь table.def:

    /*Упорядочиваем по возрастанию id*/
    MY_HT(13, 1,2,3)
    MY_HT(87, 3,1,2)
    MY_HT(96, 1,3,2)
    MY_HT(176,2,1,3)

Пишешь заголовок my_ht.h:

#ifndef _MY_HT_H_
#define _MY_HT_H_

typedef srtuct
{
    int a;
    int b;
    int c;
} my_ht_content;

#define MY_HT_CAT(a,b) a##b
#define MY_HT_CAT2(a,b) MY_HT_CAT(a,b)

#define MY_HT_ID(a) MY_HT_CAT(_,a)

typedef enum
{
#   define MY_HT(id,...) MY_HT_ID(id),
#   include "table.def"
#   undef MY_HT
    MY_HT_SZ
} my_ht_id;

extern my_ht_content my_ht[];

my_ht_id my_ht_lookup(int i);

#endif  //_MY_HT_H_

#include "my_ht.h"

my_ht_content my_ht[] = 
{
#   define MY_HT(id,a,b,c) {a,b,c},
#   include "table.def"
#   undef MY_HT
    {0,0,0}
}

my_ht_id my_ht_lookup(int i)
{
    switch(id)
    {
#   define MY_HT(i,...) case i: return MY_HT_ID(i);
#   include "table.def"
#   undef MY_HT
    default: return MY_HT_SZ;
    }
}

В принципе значения id можно добавить в саму структуру, и делать лукап не свичом, а бинарным поиском в цикле, но в случае свича ослабляется требование по упорядочиванию table.def.

my_ht_content my_ht[] = 
{
#   define MY_HT(id,a,b,c) {a,b,c},
#   include "table.def"
#   undef MY_HT
    {0,0,0}
};

Точку с запятой забыл.

А можно вообще писать

    foo(my_ht[MY_HT_ID(i)].a);

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

10-20 значений типа int

На маленьких массивах, кстати, линейный поиск может быть быстрее бинарного. Ну и непредсказанные переходы (которые могут дать эти switch/if) тоже не очень быстры

Вот я добавил такой код к «бенчмарку» beastie:

int linearmap[][2] = {
        {1, 77},
        {7, 2},
        {9, 11},
        {11, 8},
        {31, 81},
        {77, 5},
        {81, 333},
        {9999, 0}
};

int
linearsearch(int a)
{
        int i;

        for (i=0; i<sizeof(linearmap)/sizeof(linearmap[0]); i++) {
                if (linearmap[i][0] == a) {
                        return linearmap[i][1];
                }
        }

        return -1;
}

Результат:

1000000 times map: 1.680000s
1000000 times switch: 2.570000s
1000000 times translate: 3.190000s
1000000 times f: 2.520000s
1000000 times linearsearch: 2.220000s

Второе место. Очень достойно, щитаю. Правда, в массиве всего 8 значений, на 20 может будет не так быстро

Вот:
таблица,
заголовок,
диспетчер,
применение диспетчера,

По сути получается этот ваш map, сгенерированный во время компилляции.