如何将数组长度划分为长度为3倍的数组

Question

因此，我有一个相当大的数组，其中包含xyz坐标，其中array = x0，array1 = y0，array2 = z0，array3 = x1，array4 =y1.诸若此类。

我正在这个数组上运行一个算法，所用的时间比我想要的要长，我想将工作分散到线程中。我已经设置了我的线程，但是我不知道如何正确地划分这个数组，这样我就可以在3个线程上分发这个工作。

即使我有一个可以被3整除的数组长度，但这是行不通的，因为分裂成3可以拆分一个xyz坐标(例如，如果我的数组大小为15，除以3将给出大小为5的数组，这意味着我正在分割一个XYZ坐标。

我如何分割这个数组(它不一定要大小相等)，这样我就可以分配工作了。(例如，在前面的示例中，我希望有两个大小为6的数组和一个大小为3的数组)。

注意:数组的大小是可变的，但总是可以被3整除。

编辑：对不起，应该提到我在工作。我的算法迭代一组坐标，并确定哪个坐标位于特定三维形状(如椭球体)内。它保存这些坐标，并使用这些坐标执行其他任务(我正在开发一个计算机图形应用程序)。

EDIT2:，我将更详细地阐述算法。

基本上，我是在Android OpenGL-ES-3.0中工作。我有一个复杂的三维物体，大约有230000个顶点，接近100万个三角形。

在该应用程序中，用户可以将一个椭球体或框(他们选择哪一个)移动到靠近对象或对象上的位置。移动它之后，他们点击一个按钮，运行我的算法。

该算法的目的是确定我的对象中的哪些点位于椭球体或框内。这些点随后被更改为不同的颜色。然而，更复杂的是，我将变换矩阵应用于对象的点和椭球/框的点。

我现在的算法从遍历对象的所有点开始。对于那些在我的迭代中不清楚的人来说，这是我的循环。

for(int i = 0; i < numberOfVertices*3;)
{ 
   pointX = vertices[i];
   i++;
   pointY = vertices[i];
   i++;
   pointZ = vertices[i];
   i++;
   //consider transformations, then run algorithm
 }

我执行必要的步骤来考虑所有的转换，在转换完成之后，我从我的对象和椭球/盒质心的位置得到了一个点。

然后，根据形状使用下列算法之一：

椭球:我使用椭圆的质心，并应用公式(x−c)T RT A R(x−c) (对不起，我不知道如何格式化，我将解释公式)。X是一个列向量，它描述了我在迭代过程中所使用的对象的xyz点。C是描述质心的xyz点的列向量。T的意思是转置。R是我的旋转矩阵。A是带有条目(1/a^2，1/b^2，1/ c ^2)的对角线矩阵，我有a b和c的值。如果这个公式> 1，则x位于我的椭球面之外，不是有效点。如果它是<=1，那么我保存x。

方框:我只是检查这个点是否在一个范围内。如果物体的点在离质心的X方向，Y方向和Z方向有一定的距离，我保存它。

这些算法是准确的，并按预期工作。问题是，显然是效率问题。我似乎没有很好的理解什么使我的应用程序紧张，什么不是。我认为多线程会起作用，我尝试了一些所描述的技术，但它们在性能上没有明显的改善。如果有人想过滤掉我的搜索，所以我不会重复所有这些点，这会有帮助的。

Answer 1

我可以建议一个稍微不同的方法来处理它吗？我知道这不是你问题的直接答案，但请考虑一下。

如果您将其实现为坐标对象(每个对象都具有x、y和z值)，这可能会更容易看到。你的“数组”现在是1/3长。你可能会认为这会降低效率--你可能是对的--但是你会惊讶于java能够很好地优化事情。通常，Java会针对人们使用最多的情况进行优化，而您所建议的手动操作这个数组的速度可能甚至比使用对象还要慢。在你证明最易读的设计太慢之前，你不应该优化它。

现在，您有了一组坐标对象。Java有多个线程可以有效地从其中提取的队列。将所有对象转储到一个队列中，并让每个线程通过处理它并将其放入“已完成”队列中来拉一个并处理它。请注意，这使您能够轻松地添加或删除线程，而不会影响您的代码，只有一个数字除外。如何将基于数组的解决方案用于4或6个线程？

祝好运

Answer 2

这是一个演示的工作解释如下。

观测

• 每个坐标是3个索引。
• 你有三根线。

假设你有17个坐标，那就是51个索引。您希望在3个线程中拆分17个坐标。

var arraySize = 51;
var numberOfThreads = 3;
var numberOfIndexesPerCoordinate = 3;
var numberOfCoordinates = arraySize / numberOfIndexesPerCoordinate; //17 coordinates

现在，在线程之间拆分这17个坐标。

var coordinatesPerThread = numberOfCoordinates / numberOfThreads; //5.6667

这不是偶数，所以你需要分配不均匀。我们可以使用Math.floor和模块化来分发。

var floored = Math.floor(coordinatesPerThread); //5 - every thread gets at least 5.
var modulod = numberOfCoordinates % floored; // 2 - there will be 2 left that need to be placed sequentially into your thread pool

这应该会给你所有你需要的信息。在不知道您使用的是什么语言的情况下，我不想给出任何真正的代码示例。

我看到您编辑了您的问题，将Java指定为您的语言。我不打算为你做线程工作，但我会给出一个粗略的想法。

float[] coordinates = new float[17 * 3]; //17 coordinates with 3 indexes each.
int numberOfThreads = 3;
int numberOfIndexesPerCoordinate = 3;
int numberOfCoordinates = coordinates.length / numberOfIndexesPerCoordinate ; //coordinates * 3 indexes each = 17

//Every thread has this many coordinates
int coordinatesPerThread = Math.floor(numberOfCoordinates / numberOfThreads);
//This is the number of coordinates remaining that couldn't evenly be split.
int remainingCoordinates = numberOfCoordinates % coordinatesPerThread

//To make things easier, I'm just going to track the offset in the original array. It could probably be computed instead, but its just an int.
int offset = 0;
for (int i = 0; i < numberOfThreads; i++) {
    int numberOfIndexes = coordinatesPerThread * numberOfIndexesPerCoordinate;

    //If this index is one of the remainders, then increase by 1 coordinate (3 indexes).
    if (i < remainingCoordinates)
        numberOfIndexes += numberOfIndexesPerCoordinate ;

    float[] dest = new float[numberOfIndexes];
    System.arraycopy(coordinates, offset, dest, 0, numberOfIndexes);
    offset += numberOfIndexes;

    //Put the dest array of indexes into your threads.
}

另一个可能更好的选择是使用一个具有所有坐标的并发Deque，并让每个线程从其中提取，因为它们需要一个新的坐标来处理。对于这个解决方案，您需要创建Coordinate对象。

声明一个坐标对象

public static class Coordinate {
    protected float x;
    protected float y;
    protected float z;

    public Coordinate(float x, float y, float z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }
}

声明一项任务来完成您的工作，并将其传递给您的并发设备。

public static class CoordinateTask implements Runnable {
    private final Deque<Coordinate> deque;

    public CoordinateTask(Deque<Coordinate> deque) {
        this.deque = deque;
    }

    public void run() {
        Coordinate coordinate;

        while ((coordinate = this.deque.poll()) != null) {
            //Do your processing here.
            System.out.println(String.format("Proccessing coordinate <%f, %f, %f>.",
                coordinate.x,
                coordinate.y,
                coordinate.z));
        }
    }
}

下面是演示示例的主要方法

public static void main(String []args){

    Coordinate[] coordinates = new Coordinate[17];

    for (int i = 0; i < coordinates.length; i++)
        coordinates[i] = new Coordinate(i, i + 1, i + 2);

    final Deque<Coordinate> deque = new ConcurrentLinkedDeque<Coordinate>(Arrays.asList(coordinates));

    Thread t1 = new Thread(new CoordinateTask(deque));
    Thread t2 = new Thread(new CoordinateTask(deque));
    Thread t3 = new Thread(new CoordinateTask(deque));

    t1.start();
    t2.start();
    t3.start();

}

请参阅此演示。

Answer 3

在尝试使用并发优化之前，通过使用可用的最有效的碰撞检测方法，尽量减少需要测试的点数，并尽量减少这些测试的成本。

一些一般性建议：

• 在运行计算之前，请考虑将所有内容标准化为一个通用的参考框架。例如，不要将转换应用于每个点，而是将选择框/椭球转换为形状的坐标系，这样您就可以在每次迭代中执行碰撞检测而无需转换。 您还可以将部分或全部转换(旋转、平移等)组合在一起。转换成一个矩阵计算，但是除非执行大量的转换，否则这不会给您带来什么好处，这是您应该尽量避免的。 一般来说，保持转换管道尽可能精简，并将所有坐标计算保持在同一个空间中是有益的，以尽可能避免转换。
• 尽量减少执行最慢计算所需的点数。最精确的碰撞测试应该只对那些你不能用更快的方法排除在形状内的点来说是必要的，使用形状的近似值，例如球体的集合，或者形状的凸壳。简化形状允许您将最慢的计算限制在那些非常接近您的形状实际边界的点上。 在我过去的2D工作中，我发现即使是对数百个复杂动画形状的凸壳进行实时计算，也比直接不使用凸壳进行碰撞检测要快，因为它们能够更快地进行碰撞计算。
• 考虑计算/存储有关形状的附加信息，例如可以用作快速初始筛选器的内外碰撞球(所有点中的一个球体和所有点之外的一个球)。在较小的球体内的任何东西都保证在你的形状内，外部球体之外的任何东西都知道在你的形状之外。您甚至可能希望存储一个简化版本的形状(或其凸包)，您可以预先计算，并使用它来帮助碰撞检测。
• 同样，考虑在初始计算中使用一个或多个球来近似椭球，以最小化需要测试碰撞的点。
• 而不是计算实际距离，而是计算平方距离，并使用这些比较。但是，如果可能的话，更喜欢使用更快的碰撞测试。例如，对于凸多边形，可以使用分离轴定理，它将顶点投影到公共轴/平面上，以允许非常快速的重叠计算。