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

So I have a fairly large array that contains xyz coordinates, where array[0] = x0, array[1] = y0, array[2] = z0, array[3] = x1, array[4] = y1... and so on.

我有一个相当大的数组，它包含xyz坐标，其中数组[0]= x0，数组[1]= y0，数组[2]= z0，数组[3]= x1，数组[4]= y1…等等。

I'm running an algorithm on this array that is taking longer than I would like it to, and I want to split the work amongst threads. I have my threads set up, but I am not sure how to divide this array properly so I can distribute this work across 3 threads.

我在这个数组上运行的算法比我想要的时间要长，我想在线程之间分配工作。我已经设置好了线程，但是我不确定如何正确地划分这个数组，这样我就可以在3个线程之间分配这些工作。

Even though I have an array length that is divisible by 3, this won't work, because splitting into 3 can split an xyz coordinate (for instance, if my array was size 15, dividing it by 3 will give me arrays of size 5, which means I'm splitting an XYZ coordinate.

即使数组长度可以被3整除，这也不行，因为分割成3可以分割一个xyz坐标(例如，如果数组的大小是15，除以3将得到一个5大小的数组，这意味着我分割一个xyz坐标。

How can I split this array (it doesn't have to necessarily be equal in size) so that I can distribute the work? (for instance, in the previous example, I would like to have two arrays of size 6 and one of size 3).

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

Note: The size of the array is variable, but is always divisible by 3.

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

EDIT: Sorry, should have mentioned that I'm working in Java. My algorithm iterates through a collection of coordinates and determines which coordinates lie inside of a particular 3d shape (such as an ellipsoid). It saves these coordinates and I perform other tasks with these coordinates (I'm working on a computer graphics app).

编辑:对不起，我应该提到我在Java工作。我的算法遍历一个坐标集合，并确定在一个特定的3d形状(比如一个椭圆体)内部的哪个坐标。它保存了这些坐标，我用这些坐标来执行其他任务(我正在处理一个计算机图形应用程序)。

EDIT2: I'm going to elaborate on the algorithm a bit more.

EDIT2:我将进一步阐述算法。

Basically, I am working in Android OpenGL-ES-3.0. I have complex 3D-object with somewhere around 230000 vertices and close to a million triangles.

基本上，我在Android操作系统OpenGL-ES-3.0中工作。我有一个复杂的3d对象大约有230000个顶点和接近百万三角形。

In the app, the user moves either a ellipsoid or box (they choose which one) to a location close to or on the object. After moving it, they click a button, which runs my algorithm.

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

The purpose of the algorithm is to determine which points from my object lie inside of the ellipsoid or box. These points are subsequently changed to a different color. To add to the complexity, however, is the fact that I have transformation matrices applied to both the points of the object and the points of the ellipsoid/box.

该算法的目的是确定对象中哪些点位于椭球体或方框内。这些点随后被改变成不同的颜色。然而，为了增加复杂性，我有一个事实，我有一个变换矩阵，它适用于物体的点和椭球/盒的点。

My current algorithm begins by iterating through all the points of the object. For those of you unclear on my iteration, this is my loop.

我当前的算法首先遍历对象的所有点。对于那些不清楚我的迭代，这是我的循环。

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

I perform the necessary steps to consider all my transformations, and after that is finished, I have a point from my object and the location of my ellipsoid/box centroid.

我执行必要的步骤来考虑所有的转换，在转换完成之后，我从对象中获得一个点，以及椭圆体/箱体质心的位置。

Then, depending on the shape, one of the following algorithms is used:

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

Ellipsoid: I use the centroid of the ellipse and apply the formula (x−c)T RT A R(x−c) (sorry I don't know how to format that, I'll explain the formula). x is a column vector describing the xyz point from my object that I am on in my iteration. c is a column vector describing the xyz point of my centroid. T is supposed to mean transpose. R is my rotation matrix. A is a diagonal matrix with entries with entries (1/a^2, 1/b^2, 1/c^2), and I have values for a b and c. If this formula is > 1, then x lies outside of my ellipsoid and is not a valid point. If it is <=1, then I save x.

椭球:我用椭圆的重心和应用公式(x−c)T RT R(x−c)(对不起,我不知道如何格式,我将解释公式)。x是一个列向量，描述我在迭代中的对象的xyz点。c是描述质心的xyz点的列向量。T是指转置。R是旋转矩阵。是一个对角矩阵的条目,条目(1 / ^ 2,1 / b ^ 2,1 / c ^ 2),我值b和c。如果这个公式> 1,那么x谎言之外的椭球体,不是一个有效的点。如果它<=1，那么我保存x。

Box: I simply check if the point falls within a range. If the point of the object lies a certain distance in the X-direction, Y-direction, and Z-direction from the centroid, I save it.

框:我只是检查点是否落在一个范围内。如果物体的点与质心在x方向，y方向和z方向上有一定的距离，我保存它。

These algorithms are accurate, and work as intended. The issue, is obviously efficiency. I don't seem to have a good understanding of what makes my app strain and what doesn't. I thought multi-threading would work, and I tried some of the techniques described but they didn't have a significant improvement on performance. If anyone has ideas on filtering out my search so I'm not iterating through all these points, it would help.

这些算法是准确的，并且可以按照预期工作。问题显然是效率。我似乎不太了解是什么让我的应用程序变得紧张，而不是什么。我认为多线程是可行的，我尝试了一些描述的技术，但是它们在性能上没有显著的改进。如果有人想要过滤掉我的搜索，所以我没有遍历所有这些点，这将会有所帮助。

3 个解决方案

#1

May I suggest a slightly different way to handle it. I know this isn't a direct answer to your question, but please consider it.

我可以提出一个稍微不同的处理方法吗?我知道这不是对你问题的直接回答，但请考虑一下。

This could be easier to see if you implemented it as coordinate Objects, each with x, y and z values. Your "array" would now be 1/3 as long. You might think this would be less efficient--and you might be right--but you'd be surprised at how well java can optimize things. Often Java optimizes for the cases people use the most and your manually manipulating this array as you suggest is possibly even slower than using objects. Until you've proven the most readable design too slow you shouldn't optimize it.

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

Now you have a collection of coordinate objects. Java has queues that multiple threads can pull from efficiently. Dump all your objects into a queue and have each of your threads pull one and work on it by processing it and putting it in a "Completed" queue. Note that this gives you the ability to add or remove threads easily, without effecting your code except for 1 number. How would you take the array based solution to 4 or 6 threads?

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

Good luck

祝你好运

#2

Here is a demo of the work explained below.

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

Observations

观察

• Each coordinate is 3 indexes.
• 每个坐标是3个指标。
• You have 3 threads.
• 你有3个线程。

Let's say you have 17 coordinates, that's 51 indexes. You want to split the 17 coordinates among your 3 threads.

假设有17个坐标，即51个索引。您希望将17个坐标分割到3个线程中。

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

Now split that 17 coordinates among your threads.

现在将这17个坐标分割到线程中。

var coordinatesPerThread = numberOfCoordinates / numberOfThreads; //5.6667

This isn't an even number, so you need to distribute unevenly. We can use Math.floor and modulo to distribute.

这不是一个偶数，所以需要不均匀分布。我们可以用数学。地板和模块分配。

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

This should give you all the information you need. Without knowing what language you are using, I don't want to give any real code samples.

这应该能给你所需的所有信息。在不知道您正在使用何种语言的情况下，我不想给出任何实际的代码示例。

---

I see you edited your question to specify Java as your language. I'm not going to do the threading work for you, but I'll give a rough idea.

我看到您编辑了您的问题，将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.
}

---

Another, potentially better option would be to use a Concurrent Deque that has all of your coordinates, and have each thread pull from it as they need a new coordinate to work with. For this solution, you'd need to create Coordinate objects.

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

Declare a Coordinate object

声明一个协调的对象

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;
    }
}

Declare a task to do your work, and pass it your concurrent deque.

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

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));
        }
    }
}

Here's the main method showing the example in action

下面是显示实际示例的主要方法

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();

}

See this demo.

看到这个演示。

#3

Before trying to optimize with concurrency, try to minimize the amount of points you need to test, and minimize the cost of those tests, by using the most efficient collision detection methods at your disposal.

在尝试使用并发性进行优化之前，通过使用最有效的冲突检测方法，尽量减少需要测试的点数量，并最小化这些测试的成本。

Some general suggestions:

一些一般性的建议:

• Consider normalizing everything to a common frame of reference before running through your calculations. For example, instead of applying transformations to each point, transform the selection box/ellipsoid into the shape's coordinate system so you can perform your collision detection without the transformations within each iteration.

  在进行计算之前，请考虑将所有内容规范化为通用的参考框架。例如，与其将转换应用到每个点上，不如将选择框/椭圆体转换为形状的坐标系统，这样您就可以执行碰撞检测，而无需在每次迭代中进行转换。

  You may also be able to combine some or all of your transformations (rotation, translation, etc.) into a single matrix calculation, but that won't gain you much unless you're performing a lot of transformations, which you should try to avoid.

  您也可以将一些或所有的转换(旋转、平移等)组合到一个单独的矩阵计算中，但是这不会给您带来多大的好处，除非您正在执行大量的转换，这是您应该尽量避免的。

  Generally speaking it's beneficial to keep the transformation pipeline as streamlined as possible, and keep all coordinate calculations in the same space to avoid transformations as much as possible.

  一般来说，保持转换管道尽可能流线型是有益的，并保持所有的坐标计算在相同的空间，尽可能避免转换。

• Try to minimize the number of points you need to perform your slowest calculations on. The most accurate collision test should only be necessary for points that you can't rule out as being inside the shape by faster means, using an approximation of the shape, such as a collection of spheres, or the shape's convex hull. Simplifying the shape allows you to limit the slowest calculations to only those points that lie very close to your shape's actual bounds.

  尽量减少你执行最慢计算所需的点数。最精确的碰撞测试应该只对那些不能通过更快的方法排除在形状内部的点进行，使用形状的近似值，比如球体的集合，或者形状的凸壳。简化形状允许您将最慢的计算限制在那些非常接近形状实际边界的点上。

  In my own 2D work in the past I found that even calculating the convex hulls for hundreds of complex animated shapes in real time was faster than doing collision detection directly without using their convex hulls, because they enable much faster collision calculations.

  在我过去的二维工作中，我发现，即使实时计算数百个复杂的动画图形的凸壳，也比不使用它们的凸壳直接进行碰撞检测要快得多，因为它们能更快地计算碰撞。

• Consider calculating/storing additional information about the shape, such as an inner and outer collision sphere (one sphere inside all points, and one outside all points) which you can use as a fast initial filter. Anything inside the smaller sphere is guaranteed to be inside your shape, anything outside the outer sphere is known to be outside your shape. You might even want to store a simplified version of your shape, (or its convex hull), which you could calculate in advance and use to aid collision detection.

  考虑计算/存储关于形状的附加信息，例如一个内部和外部碰撞球(一个球在所有点内，一个球在所有点外)，您可以使用它作为快速的初始过滤器。小一点的球体里面的任何东西都被保证是在你的形状里面，任何在外面的球体外面的东西都被知道是在你的形状外面。您甚至可能想要存储简化版的形状(或它的凸包)，您可以提前计算并使用它来帮助碰撞检测。

• Similarly, consider using one or more spheres to approximate your ellipsoid in initial calculations, to minimize which points you need to test for collision.

  类似地，考虑在初始计算中使用一个或多个球体来近似椭圆体，以最小化需要测试的碰撞点。

• Instead of calculating actual distances, calculate the squared distances and use those for comparison. However, prefer using faster tests for collision if possible. For example, for convex polygons you can use the Separating Axis Theorem, which projects vertices onto a common axis/plane to permit very quick overlap calculations.

  与其计算实际距离，不如计算平方距离，然后用它们进行比较。但是，如果可能的话，最好使用更快的碰撞测试。例如，对于凸多边形，可以使用分离轴定理，它将顶点投影到公共轴/平面上，以允许非常快速的重叠计算。