Вопрос производительности: Самый быстрый способ преобразовать шестнадцатеричный символ в его числовое значение в Java?

Question

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

'0'->0, '1' -> 1, 'A' -> 10, 'a' -> 10, 'f' -> 15 etc...

Я буду очень часто вызывать этот метод, поэтому производительность важна. Есть ли более быстрый способ, чем использовать предварительно инициализированный HashMap<Character,Byte> для получения значения?

Ответ

Кажется, что это сложная задача между использованием коммутатора и решения Jon Skeet для непосредственных вычислений - хотя решение для коммутатора, похоже, очень незначительно. Метод массива Грега побеждает. Вот результаты производительности (в мс) для 200 000 000 прогонов различных методов:

Character.getNumericValue:
8360

Character.digit:
8453

HashMap<Character,Byte>:
15109

Greg's Array Method:
6656

JonSkeet's Direct Method:
7344

Switch:
7281

Спасибо, ребята!

Код метода эталонного теста

Вот, пожалуйста, JonSkeet, старый конкурент. ; -)

public class ScratchPad {

    private static final int NUMBER_OF_RUNS = 200000000;

    static byte res;

    static HashMap<Character, Byte> map = new HashMap<Character, Byte>() {{
        put( Character.valueOf( '0' ), Byte.valueOf( (byte )0 ));
        put( Character.valueOf( '1' ), Byte.valueOf( (byte )1 ));
        put( Character.valueOf( '2' ), Byte.valueOf( (byte )2 ));
        put( Character.valueOf( '3' ), Byte.valueOf( (byte )3 ));
        put( Character.valueOf( '4' ), Byte.valueOf( (byte )4 ));
        put( Character.valueOf( '5' ), Byte.valueOf( (byte )5 ));
        put( Character.valueOf( '6' ), Byte.valueOf( (byte )6 ));
        put( Character.valueOf( '7' ), Byte.valueOf( (byte )7 ));
        put( Character.valueOf( '8' ), Byte.valueOf( (byte )8 ));
        put( Character.valueOf( '9' ), Byte.valueOf( (byte )9 ));
        put( Character.valueOf( 'a' ), Byte.valueOf( (byte )10 ));
        put( Character.valueOf( 'b' ), Byte.valueOf( (byte )11 ));
        put( Character.valueOf( 'c' ), Byte.valueOf( (byte )12 ));
        put( Character.valueOf( 'd' ), Byte.valueOf( (byte )13 ));
        put( Character.valueOf( 'e' ), Byte.valueOf( (byte )14 ));
        put( Character.valueOf( 'f' ), Byte.valueOf( (byte )15 ));
        put( Character.valueOf( 'A' ), Byte.valueOf( (byte )10 ));
        put( Character.valueOf( 'B' ), Byte.valueOf( (byte )11 ));
        put( Character.valueOf( 'C' ), Byte.valueOf( (byte )12 ));
        put( Character.valueOf( 'D' ), Byte.valueOf( (byte )13 ));
        put( Character.valueOf( 'E' ), Byte.valueOf( (byte )14 ));
        put( Character.valueOf( 'F' ), Byte.valueOf( (byte )15 ));
    }};
    static int[] charValues = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, -1, 10, 11, 12, 13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1,
                    -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10, 11, 12, 13,14,15};
    static char[] cs = new char[]{'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f','A','B','C','D','E','F'};

    public static void main(String args[]) throws Exception {
        long time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getNumericValue( i );
        }
        System.out.println( "Character.getNumericValue:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getDigit( i );
        }
        System.out.println( "Character.digit:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            try {
                res = getValueFromArray( i );
            } catch (IllegalArgumentException e) {
            }
        }
        System.out.println( "Array:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getValueFromHashMap( i );
        }
        System.out.println( "HashMap<Character,Byte>:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            char c = cs[i%cs.length];
            res = getValueFromComputeMethod( c );        
        }
        System.out.println( "JonSkeet's Direct Method:" );
        System.out.println( System.currentTimeMillis()-time );
        time = System.currentTimeMillis();
        for( int i = 0; i < NUMBER_OF_RUNS; i++ ) {
            res = getValueFromSwitch( i );

        }
        System.out.println( "Switch:" );
        System.out.println( System.currentTimeMillis()-time );
    }

    private static byte getValueFromSwitch( int i ) {
        byte res;
        char ch = cs[i%cs.length];
        switch( ch ) {
            case '0':
                res = 0;
                break;
            case '1':
                res = 1;
                break;
            case '2':
                res = 2;
                break;
            case '3':
                res = 3;
                break;
            case '4':
                res = 4;
                break;
            case '5':
                res = 5;
                break;
            case '6':
                res = 6;
                break;
            case '7':
                res = 7;
                break;
            case '8':
                res = 8;
                break;
            case '9':
                res = 9;
                break;
            case 'a':
            case 'A':
                res = 10;
                break;
            case 'b':
            case 'B':    
                res = 11;
                break;
            case 'c':
            case 'C':    
                res = 12;
                break;
            case 'd':
            case 'D':    
                res = 13;
                break;
            case 'e':
            case 'E':    
                res = 14;
                break;
            case 'f':
            case 'F':    
                res = 15;
                break;
            default:
                throw new RuntimeException("unknown hex character: " + ch );
        }
        return res;
    }

    private static byte getValueFromComputeMethod( char c ) {
        byte result = 0;
        if (c >= '0' && c <= '9')
        {
            result =  (byte)(c - '0');
        }
        if (c >= 'a' && c <= 'f')
        {
            result = (byte)(c - 'a' + 10);
        }
        if (c >= 'A' && c <= 'F')
        {
            result =  (byte)(c - 'A' + 10);
        }
        return result;
    }

    private static byte getValueFromHashMap( int i ) {
        return map.get( Character.valueOf( cs[i%cs.length] ) ).byteValue();
    }

    private static byte getValueFromArray( int i ) {
        char c = cs[i%cs.length];
        if (c < '0' || c > 'f') {
            throw new IllegalArgumentException();
        }
        byte result = (byte)charValues[c-'0'];
        if (res < 0) {
            throw new IllegalArgumentException();
        }
        return result;
    }

    private static byte getDigit( int i ) {
        return (byte)Character.digit( cs[i%cs.length], 16 );
    }

    private static byte getNumericValue( int i ) {
        return (byte)Character.getNumericValue( cs[i%cs.length] );
    }

}

Answer 1

Предварительно инициализированный массив будет быстрее, чем HashMap. Примерно так:

int CharValues['f'-'0'+1] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, ... -1, 10, 11, 12, ...};

if (c < '0' || c > 'f') {
    throw new IllegalArgumentException();
}
int n = CharValues[c-'0'];
if (n < 0) {
    throw new IllegalArgumentException();
}
// n contains the digit value

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

Answer 2

Хеш-таблица будет относительно медленной. Это довольно быстро:

if (c >= '0' && c <= '9')
{
    return c - '0';
}
if (c >= 'a' && c <= 'f')
{
    return c - 'a' + 10;
}
if (c >= 'A' && c <= 'F')
{
    return c - 'A' + 10;
}
throw new IllegalArgumentException();

Другим вариантом было бы попробовать оператор switch / case. Массив может быть в порядке, если он находится в кеше, но промах может быть дорогим.

Answer 3

Я не помню, чтобы видел этот метод раньше, но Микко Рантанен указал это уравнение в комментарии к вопросу, Код гольфа - двоичное (шестнадцатеричное) двоичное преобразование

(char | 32) % 39 - 9

Я не знаю, что это будет за эталонный тест (возможно, кто-то может добавить его к тесту выше и запустить его, но я предполагаю, что% убивает производительность) - но это аккуратный, простой однострочный для одиночного символ шестнадцатеричное в десятичное преобразование. Ручки 0-9, A-F, a-f.

Answer 4

int CharValues[256] = 
{
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,0,1,2,3,4,5,6,7,8,9,16,16,16,16,16,16,16,
16,10,11,12,13,14,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,10,11,12,13,14,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,
16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16
}

int n = CharValues[c];

if (n == 16)
 throw new IllegalArgumentException();

// n contains the digit value

Answer 5

Использование массива должно быть самым быстрым.

Массив может иметь размер 16, 16 ^ 2, 16 ^ 3, 16 ^ 4 и т. Д.

Преобразование числа в более крупные группы, чем одна, приведет к увеличению производительности.

Там будет приятное место, где оно будет наиболее полезным, возможно, 4 цифры (таблица 64 КБ).

Answer 6

Чувак, я программист микроконтроллеров, и в этом крошечном мире скорость действительно имеет значение. Самый быстрый способ преобразовать цифру ASCII в байт (от «A» до 0x0A) - использовать этот небольшой фрагмент кода

c|=0x20;
return c<='9'? c+0xD0 : c+0xA9;

Магия этой команды проста: если вы посмотрите таблицу ascii, вы найдете числа, начинающиеся с 0x3_, и буквы в столбцах 0x4_ и 0x6_ соответственно. 1) если вы "или" входящий символ (переменная "c") с 0x20, вы никогда не будете менять цифры ... но для букв вы будете конвертировать прописные в строчные. Поскольку мы ищем только значения A..F (a..f) ... мне все равно. 2) теперь магия. Чтобы избежать вычитаний, я использую аддитивные операторы. 0xD0 равен -0x30, а 0xA9 равен -'a '+ 10;

Инструкция ветвления, сгенерированная сравнением, довольно проста и не требует дополнительных затрат на поиск таблиц, а также на "mod" или другие операторы!

Наслаждайтесь ...

Answer 7

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

private static byte lookUpTest(int i) {
    return (byte) cs[i%cs.length];
}

Answer 8

Вот моя измененная версия кода Грега. На моей коробке это незначительно быстрее - но, вероятно, в пределах шума. Это позволяет избежать проверки нижней границы и не требует каких-либо вычитаний. Создание массива 64K и отказ от проверки на либо замедлили ход событий, но опять же, с такой синхронизацией, практически невозможно быть уверенным, что реально, а что шум.

public class HexParser
{
    private static final byte VALUES = new int['f'];

    // Easier to get right for bozos like me (Jon) than
    // a hard-coded array :)
    static
    {
        for (int i=0; i < VALUES.length; i++)
        {
            VALUES[i] = (byte) -1;
        }
        for (int i='0'; i <= '9'; i++)
        {
            VALUES[i] = (byte) i-'0';
        }
        for (int i='A'; i <= 'F'; i++)
        {
            VALUES[i] = (byte) (i-'A'+10);
        }
        for (int i='a'; i <= 'f'; i++)
        {
            VALUES[i] = (byte) (i-'a'+10);
        }
    }

    public static byte parseHexChar(char c)
    {
        if (c > 'f')
        {
            throw new IllegalArgumentException();
        }
        byte ret = VALUES[c];
        if (ret == -1)
        {
            throw new IllegalArgumentException();
        }
        return ret;
    }
}

Answer 9

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

static final int[] precalc = new int['f'+1];
static {
    for (char c='0'; c<='9'; c++) precalc[c] = c-'0';
    for (char c='A'; c<='F'; c++) precalc[c] = c-'A';
    for (char c='a'; c<='f'; c++) precalc[c] = c-'a';
}

System.out.println(precalc['f']);

Answer 10

просто, но медленно:

int i = Integer.parseInt(String.ValueOf(c), 16);

быстрее:

int i = Character.digit(c, 16);

Я не буду использовать какой-либо специальный код для "проблем производительности". Если вы действительно часто используете это, JIT создаст скомпилированный код, и выполнение станет быстрым. Держите ваш код в чистоте. У вас может быть попытка написать тест производительности, сравнивающий время выполнения из приведенного выше кода и любую специальную реализацию - держу пари, вы не получите существенных улучшений.