8

这最初是我在工作中遇到的一个问题，但现在我只是为了自己的好奇心而尝试解决的问题。

我想找出 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

编辑：对于每个人都说这个废话是不可读和不必要的：你错过了重点。关键是要解决一个有趣的问题，而不是想出一个用于生产代码的答案。

4

10 回答 10

10

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

另请注意，您要编写的函数将是不可读的——另一个开发人员永远不会理解您在做什么。（看看你在这里遇到了什么麻烦。）另一方面，字符串版本非常清楚。

于 2008-10-23T23:50:42.957 回答
4

这是 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 10 ( a ) encoding + log 10 ( b ) encoding + 实际找到匹配，这也是 O( n ) 其中n是最大对数。

于 2008-10-24T05:28:00.093 回答
3

我能想到的唯一优化是自己转换为字符串并在转换时比较数字（从右到左）。首先转换 b 的所有数字，然后从 a 的右边开始转换，直到找到 b 的第一个数字（从右边开始）的匹配。比较直到所有 b 匹配或您遇到不匹配。如果您遇到不匹配的问题，请回溯到您开始匹配 b 的第一个数字的点，然后进入 a 并重新开始。

IndexOf 将必须执行基本相同的回溯算法，除了从左侧开始。根据实际数字，这可能会更快。我认为如果数字是随机的，应该是因为应该有很多次不必转换所有 a.

于 2008-10-23T23:36:37.180 回答
2

看起来你的功能实际上做得很好，但有一个小改进：

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 > b) {
                subNum = a % exponent;

                if (subNum == b)
                        return true;

                a /= 10;
        }
        return false;
}

仅仅因为一旦a小于b，就不值得一直寻找，不是吗？如果您找到解决方案，祝您好运并发布！

于 2008-10-23T23:59:16.667 回答
2

这是一个有趣的问题。String.class 的许多函数实际上是原生的，这使得击败 String 成为一个困难的命题。但这里有一些帮手：

提示 1：不同的简单整数运算具有不同的速度。

通过示例程序中的快速计算表明：

% ~ T
* ~ 4T
/ ~ 7T

因此，您希望使用尽可能少的除法来支持乘法或取模。未显示减法、加法和比较运算符，因为它们会将所有这些都从水中吹走。此外，尽可能使用“final”允许 JVM 进行某些优化。加快你的“getLength”功能：

private static int getLength(final int b) {        
   int len = 0;
   while (b > exponents[len]) {
       len++;
   }
   return len + 1
}

这使功能提高了约 7 倍。如果 b > 指数中的最大值，则会出现 indexOutOfBounds 异常。为了解决这个问题，您可以拥有：

private static int getLength(final int b) {        
   int len = 0;
   final int maxLen = exponents.length;
   while (len < maxLen && b > exponents[len]) {
       len++;
   }
   return len + 1;
}

如果 b 太大，这会稍微慢一些并且给你一个不正确的长度，但它不会抛出异常。

提示 2：不必要的对象/基元创建和方法调用会增加运行时间。

我猜“getLength”不会在其他任何地方被调用，所以虽然拥有一个单独的函数可能会很好，但从优化的角度来看，它是一个不必要的方法调用和对象“len”的创建。我们可以把代码放在我们使用它的地方。

private static boolean findMatch(int a, final int b) {
        if (b > a) return false;
        if (a == b) return true;
        int needleLength = 0;
        while (b > exponents[len]) {
            needleLength ++;
        }
        needleLength++;

        final int exponent = exponents[needleLength];
        int subNum;
        while (a >= 1 && a <= b) {
                subNum = a % exponent;
                if (subNum == b)
                        return true;
                a /= 10;
        }
        return false;
}

另外，请注意我将底部的 while 循环更改为还包括“a <= b”。我还没有测试过，并且不确定每次迭代的惩罚是否超过了你不浪费任何迭代的事实。我确信有一种方法可以使用聪明的数学来摆脱除法，但我现在想不出。

于 2008-10-24T03:23:16.040 回答
0

嗯，我可能完全误解了这个问题，但是......

// Check if A is inside B lol
bool Contains (int a, int b)
{
    return (a <= b);
}

除非你想知道一个特定的数字序列是否在另一个数字序列中。

在这种情况下，将其转换为字符串将比进行数学计算更快。

于 2008-10-23T23:24:18.983 回答
0

无论如何，这绝不会回答您的问题，但无论如何都是建议:-)

方法名称findMatch不是很有描述性。在这种情况下，我有一个静态方法ContainerBuilder.number(int)，它返回一个ContainerBuilder，它上面有方法contains。这样你的代码就变成了：

boolean b = number(12345).contains(234);

从长远来看，只是一些建议！

哦，是的，我还想说，你应该定义你所说的“包含”是什么意思

于 2008-10-23T23:28:54.560 回答
0

有没有办法用二进制计算这个？显然，包含另一个字符的二进制整数的整数的二进制值并不意味着十进制的作用相同。但是，是否可以使用某种二进制技巧？也许将像 12345 这样的数字转换为 0001 0010 0011 0100 0101，然后进行一些位移来确定其中是否包含 23 (0010 0011)。因为您的字符集只有 10 个字符，您可以通过在单个字节中存储 2 个字符值来缩短计算时间。

编辑

稍微扩展一下这个想法。如果您有 2 个整数 A 和 B，并且想知道 A 是否包含 B，则首先检查 2 件事。如果 A 小于 B，则 A 不能包含 B。如果 A = B，则 A 包含 B。此时您可以将它们转换为字符串*。如果 A 包含与 B 相同数量的字符数，则 A 不包含 B，除非它们相等，但是如果它们相等，我们就不会在这里，所以如果两个字符串的长度相同，则 a 不包含 b . 此时，A 的长度将比 B 长。因此，现在您可以将字符串转换为其打包的二进制值，正如我在本文第一部分中所指出的那样。将这些值存储在整数数组中。现在对数组中的整数值进行按位与运算，如果结果为 A，则 A 包含 B。现在将 B 的整数数组向左移动 4 位，并再次进行比较。这样做直到你开始从 B 的左边弹出位。

*上一段中的 * 表示您可以跳过此步骤。可能有一种方法可以完全不使用字符串。你可以做一些花哨的二进制技巧来获得我在第一段中讨论的打包二进制表示。应该有一些可以使用的二进制技巧，或者一些快速的数学运算，可以将整数转换为我之前讨论过的十进制值。

于 2008-10-23T23:55:56.893 回答
0

我能问一下你在代码中哪里使用这个函数吗？也许还有另一种方法可以解决它目前正在解决的问题，这种方法会更快。这可能就像我的朋友要求我完全重新调音他的吉他，而我在意识到我可以将底弦降低一整步并获得相同的结果之前就这样做了。

于 2008-10-24T08:30:52.313 回答
-1

供参考

http://refactormycode.com/

可以为你工作。

于 2008-10-24T00:00:59.957 回答