如何基于Mesh对象列表实现多线程高效Shear作业排序？

Alright, let's break down how to implement efficient parallel Shear Sort for your Mesh list in a multi-threaded environment. First, let's align on basics: Shear Sort is a grid-based parallel algorithm that alternates between sorting rows (odd rows ascending, even rows descending) and columns (all ascending)—this structure makes it perfect for leveraging multiple CPU cores.

1. First, Define Your Sorting Key #

Before diving into parallelization, you need a clear way to compare Mesh objects. Based on your class structure, common criteria could be total grid area (GridWidth * GridHeight), number of associated Files, or even a property from the File objects (like file size, if you add that to the File class).

Create a reusable comparer to keep your code clean and consistent:

private static readonly IComparer<Mesh> MeshAreaComparer = Comparer<Mesh>.Create((m1, m2) =>
{
    int area1 = m1.GridWidth * m1.GridHeight;
    int area2 = m2.GridWidth * m2.GridHeight;
    return area1.CompareTo(area2);
});

2. Understand Shear Sort's Parallelization Sweet Spots #

Shear Sort’s two core phases are inherently parallelizable with no shared state conflicts:

• Row Sort Phase: Each row can be sorted independently (odd rows ascending, even rows descending). No overlap between rows, so we can process them in parallel.
• Column Sort Phase: Each column can be sorted independently (all ascending). Columns don’t interfere with each other, making this another perfect candidate for parallel processing.

3. Implement Parallel Shear Sort with .NET Tasks #

We’ll use System.Threading.Tasks.Parallel to handle thread management automatically—it optimizes core utilization better than manual thread creation, and handles edge cases like load balancing across cores.

Key Implementation Details: #

• Grid Conversion: Convert your linear List<Mesh> into a 2D grid (Shear Sort operates on grids). Fill empty slots with null as placeholders for non-square grids.
• Parallel Row/Column Processing: Use Parallel.For to process multiple rows/columns at once.
• Termination Check: Loop until the entire grid is sorted (we’ll check this in parallel to save time).

Here’s a complete, production-ready implementation:

public static void ParallelShearSort(List<Mesh> meshes, IComparer<Mesh> comparer)
{
    if (meshes == null || meshes.Count <= 1) return;

    int itemCount = meshes.Count;
    int rows = (int)Math.Ceiling(Math.Sqrt(itemCount));
    int cols = (int)Math.Ceiling((double)itemCount / rows);

    // Convert list to 2D grid (arrays for fast random access)
    Mesh[][] grid = new Mesh[rows][];
    for (int i = 0; i < rows; i++)
    {
        grid[i] = new Mesh[cols];
        for (int j = 0; j < cols; j++)
        {
            int listIndex = i * cols + j;
            grid[i][j] = listIndex < itemCount ? meshes[listIndex] : null;
        }
    }

    bool isGridSorted = false;
    while (!isGridSorted)
    {
        // Phase 1: Parallel row sort (odd ascending, even descending)
        Parallel.For(0, rows, rowIndex =>
        {
            // Extract non-null items from the row
            List<Mesh> rowItems = grid[rowIndex].Where(m => m != null).ToList();
            
            // Sort row based on its parity
            if (rowIndex % 2 == 0)
                rowItems.Sort(comparer);
            else
                rowItems.Sort(comparer.Reverse());
            
            // Put sorted items back into the grid
            int itemIdx = 0;
            for (int colIdx = 0; colIdx < cols; colIdx++)
            {
                grid[rowIndex][colIdx] = itemIdx < rowItems.Count ? rowItems[itemIdx++] : null;
            }
        });

        // Phase 2: Parallel column sort (all ascending)
        Parallel.For(0, cols, colIndex =>
        {
            // Extract non-null items from the column
            List<Mesh> colItems = new List<Mesh>();
            for (int rowIdx = 0; rowIdx < rows; rowIdx++)
            {
                if (grid[rowIdx][colIndex] != null)
                    colItems.Add(grid[rowIdx][colIndex]);
            }
            
            // Sort column and put back
            colItems.Sort(comparer);
            int itemIdx = 0;
            for (int rowIdx = 0; rowIdx < rows; rowIdx++)
            {
                grid[rowIdx][colIndex] = itemIdx < colItems.Count ? colItems[itemIdx++] : null;
            }
        });

        // Check if grid is fully sorted (parallel check for efficiency)
        isGridSorted = true;

        // Check rows first
        Parallel.For(0, rows, rowIndex =>
        {
            if (!isGridSorted) return; // Early exit if already marked unsorted
            
            for (int colIdx = 0; colIdx < cols - 1; colIdx++)
            {
                Mesh current = grid[rowIndex][colIdx];
                Mesh next = grid[rowIndex][colIdx + 1];
                
                if (current == null || next == null) continue;
                
                // Validate row order based on parity
                if ((rowIndex % 2 == 0 && comparer.Compare(current, next) > 0) ||
                    (rowIndex % 2 == 1 && comparer.Compare(current, next) < 0))
                {
                    isGridSorted = false;
                    break;
                }
            }
        });

        // If rows are sorted, check columns
        if (isGridSorted)
        {
            Parallel.For(0, cols, colIndex =>
            {
                if (!isGridSorted) return;
                
                for (int rowIdx = 0; rowIdx < rows - 1; rowIdx++)
                {
                    Mesh current = grid[rowIdx][colIndex];
                    Mesh next = grid[rowIdx + 1][colIndex];
                    
                    if (current == null || next == null) continue;
                    
                    if (comparer.Compare(current, next) > 0)
                    {
                        isGridSorted = false;
                        break;
                    }
                }
            });
        }
    }

    // Convert grid back to linear list
    meshes.Clear();
    foreach (var row in grid)
    {
        meshes.AddRange(row.Where(m => m != null));
    }
}

4. Critical Thread Safety Notes #

• Read-Only Objects: Since your Mesh and File classes have mostly read-only properties (GridWidth, GridHeight, Path), comparison operations are thread-safe as long as no other thread modifies these properties during sorting.
• Avoid Shared Writes: If you need to modify Mesh or File properties during sorting (e.g., updating a File's parsed data), wrap those modifications in a lock or use thread-safe data structures to prevent race conditions.
• Small Lists: For very small lists (<1000 items), parallelization overhead might outweigh benefits. Add a check to fall back to single-threaded sorting in these cases.

5. Optimization Tips #

• Preallocate Lists: When extracting rows/columns, preallocate list capacities (e.g., new List<Mesh>(cols) for rows) to reduce memory allocation overhead.
• Reuse Comparers: Use a static, pre-defined comparer (like MeshAreaComparer) instead of creating new comparers each time—this avoids unnecessary delegate allocations.
• Early Termination: Shear Sort typically requires log2(n) iterations of row+column sorting. For large lists, you can replace the full sorted check with a fixed number of iterations (but keep the full check for correctness if you’re unsure).

内容的提问来源于stack exchange，提问作者rweisse