3

我有一个类似于下面代码的函数。它的目的是从一组点中一次取一个三角形面，其中每三个点都是一个面，并将它们细分，用边长不超过 nodeSize 的较小面的列表替换面。

当然，对于任何真实的刻面网格来说，这个函数都是很耗时的。我想重构它以使用一些粗略的并行化。但是，Parallel.For 似乎没有办法在保留索引号的同时每隔一段时间遍历数组中的索引。

记住SplitTriangle循环内的函数在计算上不利于并行化，我该如何重构这个函数？

Protected Shared Function SplitTriangles(Points As IEnumerable(Of Point3D), nodeSize As Single) As List(Of Point3D)
    Dim resultList As New List(Of Point3D)

        For i As Integer = 0 To Points.Count - 1 Step 3
            resultList.AddRange(SplitTriangle(Points(i), Points(i + 1), Points(i + 2), nodeSize * 4))
        Next

    Return resultList
End Function
4

3 回答 3

2

我认为这里最简单的解决方案是首先检查这些点并将它们分成一组 3 点组。然后你可以Parallel.For在那个数组上使用。

编辑：既然你有数百万分并且一直这样做，你应该做点别的。

首先，确保您的Points容器允许轻松随机访问（使用数组或 a List）。然后这样做：

  • 分配resultList适当的大小。
  • 分成Points几个部分（“几个”可能很难估计，你应该稍微玩一下）。假设您的列表有 12,000,000 个点，那么resultList4,000,000 个元素的长度也是如此。并假设您决定 4 个部分是最佳拆分。
    • 每个部分必须是连续的（0-3M、3M-6M、6M-9M、9M-12M）。
    • 找到最佳分割并不容易，但微不足道的分割可能证明足够好，所以现在不要担心。
  • 有 4 个线程，每个线程处理一个部分（您可以使用Task API，在我看来，它会使代码比Parallel.For在这种情况下更清晰。

关于线程安全的注意事项：

List<Point>当您将 a 用作固定大小的数组时，我不是 100% 相信它是线程安全的。应该是，但如果你想 100% 确定使用数组。

于 2012-11-27T21:26:51.810 回答
1

如果不是传递按惯例视为三角形的 IEnumerable 点，而是直接传递三角形，那么您的代码将简单得多。

如果将点转换为三角形，则可以使用 PLINQ 编写以下内容：

    Function SplitTriangles(triangles As IEnumerable(Of Triangle3D), nodeSize As Single) As List(Of Triangle3D)
    Dim resultList As New List(Of Point3D)

    Dim results = (From triangle In triangles.AsParallel()
                   From newTriangle In SplitTriangle(triangle.A, triangle.B, triangle.C)
                   Select newTriangle).ToList()

    Return results
End Function

AsParallel 不保留排序，但您可以通过在 AsParallel 之后添加 .AsOrdered 来强制执行此操作

使用 Parallel.For 需要使用接受本地初始化器和终结器的重载来收集每个计算的结果。最终的代码要复杂得多，在这种情况下没有任何好处。

IEnumerable(Of Point3) 的问题在于每个三元组的点之间存在非常强的关系。Parallel.For/Foreach 适用于每个项目独立于其他项目的列表。

您可以使用此处改编的 Marc Gravell 的 Partition 方法将初始点列表转换为三角形列表，以将点分组为三元组并返回三角形而不是 IEnumerable。

一个更简单但不太通用的解决方案是创建一个从点返回三角形的迭代器：

 Iterator Function Triangulize(points As IEnumerable(Of Point3D)) As IEnumerable(Of Triangle3D)

    Dim count As Integer = 0

    Dim buffer(3) As Point3D

    For Each point As Point3D In points
        buffer(count) = point
        count += 1
        If count = 3 Then
            Yield New Triangle3D(buffer(0), buffer(1), buffer(2))
            count = 0
        End If
    Next

End Function
于 2012-11-28T12:03:04.537 回答
0

您可以使用该Enumerable.Range()函数为您生成索引。我对 VB.NET 不太熟悉，所以我打算用 C# 来编写它。

Enumerable.Range(0, Points.Count / 3).AsParallel().ForAll( loopVar => {
    var i = loopVar * 3;
    resultList.AddRange(SplitTriangle(Points(i), Points(i + 1), Points(i + 2), nodeSize * 4))
});

更新 我认为这个版本是线程安全的，但您应该检查以确保它是线程安全的并且结果的顺序正确。

resultList = Enumerable.Range(0, Points.Count / 3).AsParallel().SelectMany( loopVar => {
    var i = loopVar * 3;
    return SplitTriangle(Points(i), Points(i + 1), Points(i + 2), nodeSize * 4);
});
于 2012-11-27T21:31:40.163 回答