1

我现在正在开发一个安卓应用程序。我在我的应用程序中遇到了一个重要方法的问题，因为我无法做出最佳算法来将许多输入等同于许多数据。

场景如下：方法的输入是来自 override 方法的坐标onTouchEvent()，所以当触摸屏幕并在其上移动手指时输入会很多。我必须将这么多坐标等同于数组中的 24 个值。数组中的值也是一个坐标。因此，当输入与数组中的值具有相同的值时，它会得分。

这是我使用的代码：

public void checkCoordinate(float x, float y){
    int sensitivity = 30; 
    for(int z = 0; z < 24; z++){
        if(x > (cxy[z][0]-sensivity) && x < (cxy[z][0]+sensivity) && y > (cxy[z][1]-sensivity) && y < (cxy[z][1]+sensivity)){
            points += 1; 
            Log.i("CheckCoordinate", "Total Points = "+points); 
    }
}

我有两种方法来等同。一，使用上面的算法，或者使用 24 if 检查每个输入。但我认为在这种情况下两种方法都不好。因此，如果您遇到与我相同的情况并且您已经解决了该问题，或者您有更好或最好的解决方案，我需要您的帮助，请告诉我。

先感谢您。对不起，如果我的英语不好。

4

2 回答 2

1

话虽如此，您的一般想法是正确的。问题是现在可以以某种方式对其进行优化吗？

我们可以在这里使用许多方法。诀窍在于您安排数据的方式。在您当前的情况下，您正在做一个中心点，您的灵敏度变量是您的跨度。可以想象第一个优化不是使用从中心点左右上下移动的灵敏度，而是可以实现一个左上点，其跨度只从左上点向右和向下移动。您的 if 语句将变为：

if(x > cxy[z][0] && x < (cxy[z][0]+sensivity) && y > cxy[z][1] && y < (cxy[z][1]+sensivity))

那么这对您有什么作用：上述优化允许您保存相同的总数据量，但每次检查无需进行 2 次数学运算。考虑到您的输入参数都是浮点数，这可以节省相当多的时间。

如果您正在执行所有基于像素的操作，那么这将带我进行下一个优化。使用整数而不是浮点数进行所有计算，这也将大大加快您的整体算法时间。

现在可以进行进一步的优化，如果您愿意花费更多 RAM 以获得更好的性能，您可以代替每个区域 1 个点，而是可以为每个区域设置一个左上角和一个右下角。这将使您的 if 语句如下所示：

if(x > tlxy[z][0] && x < brxy[z][0] && y > tlxy[z][1] && y < brxy[z][1])

where tlxy is the array of top-left points, brxy is the array of bottom-right points
and z is still the "region" you are checking against

这有什么帮助：正如您在上面的 if 语句中看到的，这现在绝对没有明确的数学运算。为了支持这个算法，你需要愿意花费 2 倍于数组 cxy 的内存。

现在在您的循环中，您将通过所有 24 个区域点。如果您确定您的区域没有重叠，那么一个点一次只能落在一个区域中。您可以通过在您还增加点的点处跳出 for 循环来节省大多数 xy 输入点的时间。如下所示：

public void checkCoordinate(float x, float y){
    for(int z = 0; z < 24; z++){
        if(x > tlxy[z][0] && x < brxy[z][0] && y > tlxy[z][1] && y < brxy[z][1]){
            points += 1; 
            break;
        }
    }
}

只有在您确定没有重叠区域（甚至没有边缘）的情况下，上述内容才有效。

在最终优化中，我可以看到可能有潜力。根据您所在区域的外观，您可以将所有区域预先分成象限。这样，您可以测试 x 点位于屏幕的左侧或右侧，然后测试 y 点位于顶部或底部。如果您的区域分布相当均匀，这可能会将您的测试时间缩短 4 倍，因为您不仅需要测试象限内的区域（如果给定的统计分布是我所说的）。在最坏的情况下，所有区域都位于一个象限中，并且您测试的所有点都在该象限中，在这种情况下，从复杂性的角度来看，问题并不比以前更糟。它只是在您的输入 x 和 y 上添加设置测试。

我希望这能给你足够的信息，至少让你开始上路！！！

于 2012-06-19T02:32:41.177 回答
0

对于 24 个值，这可能是多余的，但您可能还需要考虑使用普通数组哈希表（具有开放寻址冲突解决方案）：

  1. 为简单起见，假设您使用该y值来获取跳转位置（如果区域垂直分离得很好，这应该会减少检查次数）。假设您的屏幕分辨率为 600x800，您可以除以 y60 得到约 13 个插槽。如果您使用的是 8 位表，则相当于每个插槽约 18 个项目 ( round(800/60)=13, round(255/13)=18)。

  2. 为了加快计算速度，您应该使所有内容保持完整和简单，以便您可以使用以下方法获取插槽号：

    int yi = (int)y;

// this is your "hash function". depending on your actual data,
// you might want to modify it to get a lesser chance of collisions
byte slot = (byte)((yi / 60) * 18);

  3. 现在您有了插槽索引，只需跳转到哈希表并检查，直到没有更多要检查的项目：

    rectangle r;
int yi = (int)y;
for (byte slot=(byte)(yi / 26); slot < 256; slot++)
{
    r = hashtable[slot];

    // is this an empty slot?
    if (r.brxy == 0)
       break;

    // perform exact check
    if (r.left < x && x < r.right && 
        r.top < y && y < r.bottom)
       break;
}

  4. 哈希表需要在初始化期间以类似的方式创建：对于 24 个区域中的每一个，计算其哈希（插槽）索引。如果哈希表中的位置被占用，只需增加 1，直到找到一个空点。注意：您是否必须将每个区域添加到所有重叠的插槽中。最简单的方法是将其添加到slots和.s-1s+1

您的循环目前平均执行12 次查找，而基于哈希的方法执行单个哈希计算，并且平均应该只需要两次或三个查找（据说哈希表O(1)平均具有复杂性，假设一个好的哈希函数）。

例子

理想情况下，您hashtable应该看起来像：

hashtable[0]: rectangle(0, 0, 60, 60);
hashtable[1]: rectangle(20, 20, 80, 80);
hashtable[2]: (empty)
hashtable[3]: (empty)
...
// next slot starts at [18]
hashtable[18]: rectangle(20, 20, 80, 80); // this region is in slots 0 and 1
hashtable[19]: rectangle(30, 70, 90, 130);
hashtable[20]: rectangle(400, 70, 460, 130);
hashtable[21]: (empty)
...

因此，如果您的接触点是(430, 100)，则计算将继续如下：

a) slot = (byte)((100/60) * 18) = 18;
b) check hashtable[18], overlapping? no
c) check hashtable[19], overlapping? no
c) check hashtable[20], overlapping? yes, found after 3 checks

性能仅取决于选择的哈希函数：

如果您有许多具有相似x坐标的项目，您可能会在某些插槽中遇到很多冲突：这就是为什么选择一个好的散列函数很重要。如果区域是固定的，你甚至可以创建一个完美的散列。

于 2012-06-19T10:35:08.980 回答