Kyl*_*ich 5 java arrays algorithm android
这是一个奇怪的问题.我在Java中有一个整数数组,其中每个int代表一种颜色.它们将是0xFFFFFFFF或0x0.如果此数组包含任何等于0xFFFFFFFF的值,那么最快的方法是什么？
这是我目前的代码:
int length = w * h;
for (int i = 0; i < length; i++) {
if (pixels[i] == 0xFFFFFFFF) {
return true;
}
}
我不知道是否有更快的方法来做到这一点.我想你的兽医可能会有一两招.
编辑:看起来它只是来自Bitmap.getPixels()的一个愚蠢的像素数组,它无法被排序或转换为另一个存储结构.感谢大家的投入,看起来循环是这种情况下的最佳方式.
tem*_*def 11
没有切换到其他一些数据结构,没有,没有更好的方法来查找数组是否包含该值.您必须查看所有数组元素以查看它是否存在,因为如果您不检查某个特定位置,则可能会错过该像素颜色的一个副本.
也就是说,有其他方法可以解决这个问题.以下是关于如何提高速度的一些想法:
如果每个值都保证为白色或黑色,则可以在数组旁边存储两个额外的布尔值,表示是否有白色或黑色像素.这样,一旦你运行扫描一次,你就可以回读一下布尔.您还可以存储白色和黑色像素的数量以及数组,然后每当您写入像素时,通过递减原始颜色的像素数并增加新颜色的像素数来更新计数.这样就可以通过查看正确的计数器是否为非零来检查O(1)中是否存在给定颜色的像素.
或者,如果您碰巧知道某些图像(可能是白色和黑色像素应该在哪里),您可以考虑以不同的顺序进行迭代.例如,如果你正在寻找的像素倾向于聚集在图像的中心,重写循环以检查那里首先可能是一个好主意,因为如果有任何类型的像素你会更快地找到它们.这仍然具有相同的最坏情况行为,但对于"逼真"的图像可能会快得多.
如果你有多个线程可用并且数组非常庞大(数百万个元素),你可以考虑让多个线程分别搜索数组的一部分来获取值.只有当您有理由怀疑大部分图像不是白色时,这才是可行的.
因为在大多数逼真的图像中你可能认为图像是混合颜色而你只是在寻找一种颜色的东西,那么你可能想要考虑将图像存储为稀疏数组,在那里存储像素列表碰巧是一种颜色(比方说是白色),然后假设其他一切都是黑色的.如果您希望大多数图像是带有少量异常值的纯色,这可能是一个非常好的表示.此外,它可以让您不断查询是否存在任何黑色或白色像素 - 只需检查设置像素列表是否为空或者是否包含整个图像.
如果顺序无关紧要,您还可以将元素存储在某个容器中,如哈希表,这可以让您(O)查询元素是否存在.您还可以对数组进行排序,然后只检查端点.
作为微优化,你可以考虑总是在真实图像上附加两个值 - 一个白色像素和一个黑色像素 - 这样你就可以一直迭代直到找到值.这消除了循环中的一个比较(检查是否是入境),并且一些作者推荐使用非常大的数组.
如果你假设大多数图像是白色和黑色的很好的混合,并且可以在一小部分时间内得到错误的答案,你可以考虑探测一些随机位置并检查它们中的任何一个是否是正确的颜色.如果是这样,那么显然存在正确颜色的像素并且您已完成.否则,运行完整线性扫描.对于颜色很好混合的图像,这可以节省大量的时间,因为你可以探测一些少量的位置(比如它们的O(log n))并最终避免在许多地方进行大量线性扫描案例.这比以前快了几倍.
如果每个值都是白色或黑色,您还可以考虑将图像存储在位向量中.这会将数组的大小压缩机器字大小的因子(可能在32-128x压缩之间)然后您可以遍历压缩数组并查看是否有任何值不等于0以查看是否有任何像素是白色的.这也节省了大量的空间,我实际上建议这样做,因为它也使很多其他操作变得容易.
希望这可以帮助!