以数学方式查找数字子串，无需进行字符串比较
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
这最初是我在工作中遇到的一个问题，但现在我正试图解决自己的好奇心。
我想知道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
编辑：对于每个人都说这个废话是不可读的和不必要的：你错过了这一点。关键是要找出一个有趣的问题，不要在生产代码中找到答案。
解决方案
这是沿着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清楚地表明，这不是一个生产问题，更多的是一种空闲的好奇心，所以我的回答解决了这种好奇心。我的猜测是速度是一个问题，当他试图在生产中解决它时，但作为一种空闲的好奇心，<！>“这种方法将被称为数百万次<！>”;不再适用。由于他不得不向一张海报解释，它不再被视为生产代码，因此复杂性不再重要。
另外，它提供了页面上唯一能够找到<！>“123 <！>”的实现。在<！>“551241238 <！>”中，所以除非正确性是一个无关紧要的问题，否则它提供了这一点。 <！>“解决方案空间也是一种算法，它使用Java原语以数学方式解决问题但击败优化的本机代码<！>可能是 EMPTY 。
另外，从您的评论中不清楚您是否将苹果与苹果进行比较。功能规范是f（int，int） - <！> gt; boolean，not f（String，String） - <！> gt; 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）编码+ log 10 （b）编码+实际找到匹配，这也是O（ n ）其中< em> n 是最大的对数。
其他提示
它应该更快的字符串方式，因为你的问题是文本的，而不是数学的。请注意，您的<！>“包含<！>”;关系中没有关于数字的说法，它只是说明了他们的十进制表示。
另请注意，您要编写的函数将无法读取 - 另一位开发人员永远不会理解您在做什么。 （看看你在这里遇到了什么麻烦。）另一方面，字符串版本非常清楚。
我能想到的唯一优化就是在转换时自行转换为字符串并比较数字（从右到左）。首先转换b的所有数字，然后从a右边转换，直到找到b的第一个数字（从右边）开始匹配。比较直到所有b匹配或您遇到不匹配。如果您遇到不匹配，请回溯到您开始匹配b的第一个数字的位置，然后前进并重新开始。
除了左边，IndexOf必须做基本相同的反向跟踪算法。根据实际数字，这可能会更快。我认为如果数字是随机的，那应该是因为它不应该多次转换所有的数据。
看起来你的功能实际上做得很好，但是有一点改进：
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，就不值得继续寻找，不是吗？ 如果找到解决方案，祝你好运并发帖！
这是一个有趣的问题。许多String.class的函数实际上都是本地制作，因为字符串是一个困难的命题。但是这里有一些帮手：
提示1：不同的简单整数操作具有不同的速度。
通过示例程序中的快速计算显示：
% ~ T
* ~ 4T
/ ~ 7T
所以你想尽可能少地使用除法来支持乘法或模数。未示出的是减法，加法和比较运算符，因为它们将所有这些都从水中吹出。另外，使用<！> quot; final <！> quot;尽可能允许JVM进行某些优化。加速你<！>“getLength <！>”;功能：
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
这使功能提高了7倍。如果b <！> gt;你得到一个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 <！> lt; = b <！>”;我没有对此进行测试，也不确定每次迭代惩罚是否超过了您不浪费任何迭代的事实。我确信有一种方法可以使用聪明的数学来摆脱分裂，但我现在想不到它。
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
除非您想知道某个特定的数字序列是否在另一个数字序列中。
在这种情况下，将其转换为字符串将比计算数学更快。
这绝不会回答你的问题，但无论如何都是建议： - ）
方法名称findMatch不是很具描述性。在这种情况下，我有一个静态方法ContainerBuilder.number(int)，它返回一个ContainerBuilder，其上有方法contains。这样你的代码就变成了：
boolean b = number(12345).contains(234);
从长远来看，我会提出一些建议！
哦，是的，我的意思是，你应该定义你的意思<！> quot; contains <！> quot;
有没有办法用二进制计算？显然，包含另一个字符的二进制整数的整数的二进制值并不意味着decical的作用相同。但是，是否有某种二进制技巧可以使用？可能将像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.因此，现在您可以将字符串转换为其压缩的二进制值，如本文第一部分所述。将这些值存储在整数数组中。现在，您对数组中的整数值进行按位AND，如果结果为A，则A包含B.现在将B的整数数组移位到左边的4位，然后再次进行比较。这样做直到你开始从B的左边弹出位。
*前一段中的*表示您可以跳过此步骤。可能有一种方法可以在不使用字符串的情况下完成此操作。你可以做一些奇特的二进制技巧来获得我在第一段中讨论的压缩二进制表示。应该有一些二进制技巧可以使用，或者一些快速数学运算将整数转换为我之前讨论过的十进制值。
我可以问你在代码中使用此功能的位置吗？也许有另一种方法可以解决目前正在解决的问题，这会更快。这可能就像我的朋友要求我完全重新调整他的吉他一样，并且在我意识到我可以将整个底部琴弦降低一步并获得相同的结果之前我就这样做了。
