以数学方式查找数字子串,无需进行字符串比较

Question

这本来是我在工作中遇到的一个问题,但现在我正试图解决我自己的好奇心.

我想知道int'a'是否以最有效的方式包含int'b'.我编写了一些代码,但似乎无论我编写什么,将其解析为字符串然后使用indexOf的速度是数学上的两倍.

记忆不是问题(在合理范围内),只是纯粹的处理速度.

这是我用数学方式编写的代码:

private static int[] exponents = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

private static boolean findMatch(int a, int b) {
    if (b > a) return false;

    if (a == b) return true;

    int needleLength = getLength(b);

    int exponent = exponents[needleLength];
    int subNum;
    while (a >= 1) {
        subNum = a % exponent;

        if (subNum == b)
            return true;

        a /= 10;
    }
    return false;
}

private static int getLength(int b) {

    int len = 0;

    while (b >= 1) {
        len++;
        b /= 10;
    }

    return len;
}

这是我正在使用的字符串方法,它似乎胜过上面的数学方法:

private static boolean findStringMatch(int a, int b) {      
    return String.valueOf(a).indexOf(String.valueOf(b)) != -1;      
}

因此,尽管我并不是真的需要完成我的工作,但我只是想知道是否有人能想出任何方式来进一步优化我的数学方法,或者完全是一种全新的方法.再一次记忆没问题,我只是为了速度而拍摄.

我真的很想看到或听到任何人提供的任何东西.

编辑: 当我说包含我的意思是可以在任何地方,所以例如,findMatch(1234,23)== true

编辑:对于每个人说这个废话是不可读和不必要的:你错过了这一点.关键是要找出一个有趣的问题,不要想出在生产代码中使用的答案.

Answer 1

它应该是更快的字符串方式,因为你的问题是文本的,而不是数学的.请注意,您的"包含"关系没有说明数字,它只是说明了它们的十进制表示.

另请注意,您要编写的函数将无法读取 - 另一位开发人员永远不会理解您正在执行的操作.(看看你在这里遇到了什么麻烦.)另一方面,字符串版本非常清楚.

Answer 2

这是按照 Kibbee 的路线，但在他发布并解决这个问题之前我对此有点感兴趣：

long mask ( long n ) { 
    long m   = n % 10;
    long n_d = n;
    long div = 10;
    int  shl = 0;
    while ( n_d >= 10 ) { 
        n_d /= 10;
        long t = n_d % 10;
        m |= ( t << ( shl += 4 ));
    }
    return m;
}

boolean findMatch( int a, int b ) { 
    if ( b < a  ) return false;
    if ( a == b ) return true;

    long m_a = mask( a );    // set up mask O(n)
    long m_b = mask( b );    // set up mask O(m)

    while ( m_a < m_b ) {
        if (( m_a & m_b ) == m_a ) return true;
        m_a <<= 4;  // shift - fast!
        if ( m_a == m_b ) return true;
    }  // O(p)
    return false;
}       

void testContains( int a, int b ) { 
    print( "findMatch( " + a + ", " + b + " )=" + findMatch( a, b ));
}

testContains( 12, 120 );
testContains( 12, 125 );
testContains( 123, 551241238 );
testContains( 131, 1214124 );
testContains( 131, 1314124 );

由于 300 个字符太少，无法进行争论，因此我正在编辑这篇主要帖子来回应 Pyrolistical。

与 OP 不同的是，本机编译的 indexOf 比带有原语的 Java 代码更快，我对此并不感到惊讶。所以我的目标不是找到比 Java 代码中调用无数次的本机方法更快的东西。

OP 明确表示这不是生产问题，更多的是出于闲置的好奇心，所以我的回答解决了这种好奇心。我的猜测是，当他试图在生产中解决这个问题时，速度是一个问题，但出于一种闲置的好奇心，“这种方法将被调用数百万次”不再适用。正如他必须向一位发帖人解释的那样，它不再被视为生产代码，因此复杂性不再重要。

另外，它提供了页面上唯一能够在“551241238”中找到“123”的实现，因此除非正确性是一个无关紧要的问题，否则它会提供这一点。此外，“使用 Java 原语以数学方式解决问题但击败优化的本机代码的算法”的解决方案空间可能是EMPTY。

另外，从您的评论中不清楚您是否将苹果与苹果进行比较。函数规范是 f( int, int )-> boolean，而不是 f( String, String )-> boolean （这是 ) 的域indexOf。因此，除非你测试了类似的东西（它仍然可以击败我的，我不会感到非常惊讶。）额外的开销可能会消耗掉多余的 40% 的一部分。

boolean findMatch( int a, int b ) { 
    String s_a = "" + a;
    String s_b = "" + b;
    return s_a.indexOf( s_b ) > -1;
}

它执行相同的基本步骤。log ₁₀ ( a ) 编码 + log ₁₀ ( b ) 编码 + 实际找到匹配项，这也是 O( n )，其中n是最大对数。