代码之家 › 专栏 › 技术社区 › Epaga Alex Reynolds

性能问题:在Java中将十六进制字符转换为其数值的最快方法?

algorithm performance java

Epaga Alex Reynolds · 技术社区 · 17 年前

我想将代表十六进制值(大写或小写)的char转换为字节,如下所示

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

我会非常频繁地调用这种方法,所以性能很重要。有没有比使用预初始化更快的方法 HashMap<Character,Byte> 从中获取价值?

回答

似乎 ~~这是使用开关情况和Jon Skeet的直接计算解决方案之间的一个跳跃——不过,开关情况解决方案似乎稍微有点边缘化。~~ Greg的数组方法胜出。以下是各种方法200000000次运行的性能结果(单位:ms):

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] );
    }

}

14 回复 | 直到 17 年前

Community Mohan Dere 8 年前

预初始化数组比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

您应该将此方法与其他方法进行基准测试(例如 Jon Skeet's 直接法),以确定哪种方法最适合您的应用程序。

Jon Skeet 17 年前

哈希表的速度相对较慢。这很快:

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语句。如果数组在缓存中,它可能是可以的,但错过可能会代价高昂。

Community Mohan Dere 8 年前

我不记得以前见过这种方法,但Mikko Rantanen在评论这个问题时指出了这个方程式, Code golf - hex to (raw) binary conversion

(char | 32) % 39 - 9

我不知道它会作为什么基准测试(也许有人可以将其添加到上面的基准测试中并运行它,但我猜%会降低性能),但它是一个整洁、简单的单行代码,用于单字符十六进制到十进制的转换。手柄0-9、A-F、A-F。

Jason Plank Maksim Kondratyuk 14 年前

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

pro 17 年前

使用数组应该是最快的。

数组的大小可以是16、16^2、16^3、16^4等。。

将数字转换为比一个更大的组会提高性能。

将有一个最值得的最佳点,可能是4位数(64k表)。

Keeg 17 年前

老兄,我是微控制器程序员,在这个小小的世界里,速度真的很重要。将“ASCII”数字转换为字节(从“A”到0x0A)的最快方法是使用这小段代码

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

这个命令的神奇之处很简单,如果你查看ascii表,你会发现以0x3_开头的数字,以及分别位于0x4_和0x6_列的字母。 1) 如果你“或”传入的char(变量“c”)为0x20,你永远不会改变数字。..但对于字母,您将把大写转换为小写。因为我们只寻找A..F(A..F)值。…我不在乎别人。 2) 现在魔术。为了避免减法,我使用了加法运算符。0xD0与-0x30相同,0xA9与-a’+10相同;

比较生成的分支指令非常简单,没有表查找的开销,也没有“mod”或其他运算符!

享受。..

Arne Burmeister 17 年前

Character.getNumericValue(char)是另一种方式:

char c = 'a';
System.out.println(c + "->" + Character.getNumericValue(c));

打印'a->例如,10’就像你想要的那样。其他人必须对静态metod调用与HashMap查找的效率发表评论,或者你可以自己检查一下。不过,对我来说,它似乎更干净/更易读。

Staale 17 年前

简单但缓慢:

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

更快:

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

我不会为“性能问题”使用任何特殊代码。如果你真的经常使用它,JIT会创建编译后的代码,执行速度会变快。保持代码干净。您可以尝试编写一个性能测试,比较上述代码和任何特殊实现的执行时间——我打赌您不会得到显著的改进。

Jon Skeet 17 年前

我认为你无法击败直接数组查找。

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']);

Peter Lawrey 16 年前

这是我对Greg代码的修改版本。在我的盒子上 轻微地 速度更快,但可能在噪音范围内。它避免了下限检查,不需要做任何减法。创建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;
    }
}

mauricio_martins 12 年前

值得注意的是,在大多数测试中,您都在对%操作进行计时。此操作所需的时间与其他一些选项大致相同。

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

user207421 12 年前

一个16位值的表,一次可以查找两位数字,应该比其他答案中建议的8位值数组更快。您将以两倍的速度迭代数据,以一半的频率访问数组,并访问shorts而不是bytes,所有这些都让CPU做得更少,做得更多。

8位值将预先计算为 x[Integer.toHexString(i).charAt[0]] = i 给 0 <= i < 256 。然后你只需查找 x[c] 对于每个字符 c 在十六进制字符串中。您可能希望复制每个十六进制值的大写和小写变体的条目。

32位值的表应该更快,这取决于你能负担得起多少空间。