Can I multithread a function for all entries in a list and return the list entry that gives the max value in O(n)?

Question

I have a list of 3D X/Y/Z points, foundPoints and single 3D X/Y/Z point, rayOrigin. I'm looking to return the point from the list that is farthest from rayOrigin. It is likely that the list could contain several thousand points so I had wanted to multithread it.

I have an existing single thread function that works fine and is O(n). The first attempt I've made at multithreading is O(2n) because I'm going through the lists twice, I fully admit it isn't pretty but I'm struggling to find a way to do this with multiple threads but in O(n). I suspect the answer will be something with PLINQ but I'm very much open to suggestions.

Here's my single thread code

static List<double> getFarthestPoint(List<List<double>> foundPoints, double[] rayOrigin)
{
    //No need to iterate if we have one point
    if (foundPoints.Count == 1)
    {
        return foundPoints[0];
    }

    //Run through a bunch of output points and compare to eyePoin
    List<double> farthestPoint = foundPoints[0];
    double maxDistance = getPointDistance(rayOrigin, farthestPoint);
    
    double pointDistance;

    foreach (List<double> foundPoint in foundPoints)
    {
        pointDistance = getPointDistance(rayOrigin, foundPoint);

        if (pointDistance > maxDistance)
        {
            maxDistance = pointDistance;
            farthestPoint = foundPoint;
        }
    }

    //Return max distance point
    return farthestPoint;
}

And here's my mediocre multithreaded code

static List<double> getFarthestPointMultiThread(List<List<double>> foundPoints, double[] rayOrigin)
{
    //No need to iterate if we have one point
    if (foundPoints.Count == 1)
    {
        return foundPoints[0];
    }

    //This is multi-threaded but still O(2n) is there a way to multi-thread an O(n)?
    Dictionary<Double, List<Double>> calculatedDistances = new Dictionary<double, List<double>>();

    //Multi thread to create dictionary of all distances
    Parallel.For(0, foundPoints.Count, i =>
        calculatedDistances.Add(getPointDistance(rayOrigin, foundPoints[i]), foundPoints[i]));

    //return point of max distance
    return calculatedDistances[calculatedDistances.Keys.AsParallel().Max()];
}

Answer 1

I'm not all that familiar with PLINQ, but this call chain should allow you to distribute the workload:

return foundPoints
        .AsParallel()
        .Select(point => (point: point, distance: getPointDistance(rayOrigin, point)))
        .Aggregate((p1, p2) => p1.distance > p2.distance ? p1 : p2)
        .point;

Thanks to @PeterDuniho for pointing out a major flaw in my previous benchmark setup.
Here are the results (20 million points, 100 iterations, running on an i7-3820 @ 3.6 GHz):

      1 core                2 cores               4 cores               8 cores
-------------------   -------------------   -------------------   -------------------
 Average:  1673 ms     Average:  932 ms      Average:   581 ms     Average:   454 ms
-------------------   -------------------   -------------------   -------------------
 Batch 0:  1698 ms     Batch 0:  1004 ms     Batch 0:   595 ms     Batch 0:   401 ms
 Batch 1:  1670 ms     Batch 1:   966 ms     Batch 1:   652 ms     Batch 1:   381 ms
 Batch 2:  1624 ms     Batch 2:   872 ms     Batch 2:   624 ms     Batch 2:   424 ms
 Batch 3:  1639 ms     Batch 3:   887 ms     Batch 3:   688 ms     Batch 3:   446 ms
 Batch 4:  1662 ms     Batch 4:   870 ms     Batch 4:   596 ms     Batch 4:   372 ms
 Batch 5:  1650 ms     Batch 5:   891 ms     Batch 5:   638 ms     Batch 5:   460 ms
 Batch 6:  1679 ms     Batch 6:   861 ms     Batch 6:   594 ms     Batch 6:   450 ms
 Batch 7:  1699 ms     Batch 7:   922 ms     Batch 7:   619 ms     Batch 7:   440 ms
 Batch 8:  1663 ms     Batch 8:   906 ms     Batch 8:   576 ms     Batch 8:   361 ms
 Batch 9:  1662 ms     Batch 9:   848 ms     Batch 9:   599 ms     Batch 9:   460 ms
 Batch 10: 1622 ms     Batch 10:  905 ms     Batch 10:  605 ms     Batch 10:  362 ms
 Batch 11: 1646 ms     Batch 11:  969 ms     Batch 11:  586 ms     Batch 11:  459 ms
 Batch 12: 1675 ms     Batch 12:  940 ms     Batch 12:  573 ms     Batch 12:  405 ms
 Batch 13: 1598 ms     Batch 13:  887 ms     Batch 13:  620 ms     Batch 13:  462 ms
 Batch 14: 1618 ms     Batch 14:  869 ms     Batch 14:  572 ms     Batch 14:  418 ms
 Batch 15: 1597 ms     Batch 15:  851 ms     Batch 15:  567 ms     Batch 15:  515 ms
 Batch 16: 1611 ms     Batch 16:  858 ms     Batch 16:  587 ms     Batch 16:  529 ms
 Batch 17: 1602 ms     Batch 17:  877 ms     Batch 17:  590 ms     Batch 17:  445 ms
 Batch 18: 1644 ms     Batch 18:  869 ms     Batch 18:  607 ms     Batch 18:  359 ms
 Batch 19: 1615 ms     Batch 19: 1021 ms     Batch 19:  648 ms     Batch 19:  490 ms
 Batch 20: 1700 ms     Batch 20:  957 ms     Batch 20:  530 ms     Batch 20:  454 ms
 Batch 21: 1642 ms     Batch 21:  902 ms     Batch 21:  583 ms     Batch 21:  433 ms
 Batch 22: 1680 ms     Batch 22:  857 ms     Batch 22:  567 ms     Batch 22:  513 ms
 Batch 23: 1615 ms     Batch 23:  894 ms     Batch 23:  562 ms     Batch 23:  436 ms
 Batch 24: 1680 ms     Batch 24:  907 ms     Batch 24:  584 ms     Batch 24:  371 ms
 Batch 25: 1611 ms     Batch 25:  851 ms     Batch 25:  569 ms     Batch 25:  519 ms
 Batch 26: 1590 ms     Batch 26:  865 ms     Batch 26:  514 ms     Batch 26:  385 ms
 Batch 27: 1686 ms     Batch 27:  934 ms     Batch 27:  634 ms     Batch 27:  521 ms
 Batch 28: 1729 ms     Batch 28:  931 ms     Batch 28:  582 ms     Batch 28:  415 ms
 Batch 29: 1655 ms     Batch 29:  863 ms     Batch 29:  560 ms     Batch 29:  442 ms
 Batch 30: 1700 ms     Batch 30:  939 ms     Batch 30:  553 ms     Batch 30:  420 ms
 Batch 31: 1651 ms     Batch 31:  892 ms     Batch 31:  565 ms     Batch 31:  401 ms
 Batch 32: 1613 ms     Batch 32:  861 ms     Batch 32:  562 ms     Batch 32:  511 ms
 Batch 33: 1629 ms     Batch 33:  841 ms     Batch 33:  543 ms     Batch 33:  549 ms
 Batch 34: 1652 ms     Batch 34:  918 ms     Batch 34:  545 ms     Batch 34:  551 ms
 Batch 35: 1714 ms     Batch 35:  954 ms     Batch 35:  554 ms     Batch 35:  375 ms
 Batch 36: 1709 ms     Batch 36:  906 ms     Batch 36:  566 ms     Batch 36:  415 ms
 Batch 37: 1665 ms     Batch 37:  898 ms     Batch 37:  588 ms     Batch 37:  366 ms
 Batch 38: 1659 ms     Batch 38:  886 ms     Batch 38:  585 ms     Batch 38:  500 ms
 Batch 39: 1620 ms     Batch 39:  903 ms     Batch 39:  536 ms     Batch 39:  421 ms
 Batch 40: 1627 ms     Batch 40:  851 ms     Batch 40:  572 ms     Batch 40:  542 ms
 Batch 41: 1607 ms     Batch 41:  864 ms     Batch 41:  560 ms     Batch 41:  605 ms
 Batch 42: 1678 ms     Batch 42:  926 ms     Batch 42:  575 ms     Batch 42:  561 ms
 Batch 43: 1679 ms     Batch 43:  890 ms     Batch 43:  560 ms     Batch 43:  612 ms
 Batch 44: 1707 ms     Batch 44:  941 ms     Batch 44:  556 ms     Batch 44:  531 ms
 Batch 45: 1863 ms     Batch 45: 1001 ms     Batch 45:  567 ms     Batch 45:  483 ms
 Batch 46: 1667 ms     Batch 46:  968 ms     Batch 46:  634 ms     Batch 46:  576 ms
 Batch 47: 1640 ms     Batch 47:  968 ms     Batch 47:  567 ms     Batch 47:  398 ms
 Batch 48: 1666 ms     Batch 48:  952 ms     Batch 48:  551 ms     Batch 48:  556 ms
 Batch 49: 1636 ms     Batch 49:  969 ms     Batch 49:  566 ms     Batch 49:  442 ms
 Batch 50: 1675 ms     Batch 50:  984 ms     Batch 50:  558 ms     Batch 50:  421 ms
 Batch 51: 1806 ms     Batch 51:  951 ms     Batch 51:  571 ms     Batch 51:  365 ms
 Batch 52: 1768 ms     Batch 52:  881 ms     Batch 52:  575 ms     Batch 52:  478 ms
 Batch 53: 1828 ms     Batch 53:  859 ms     Batch 53:  550 ms     Batch 53:  460 ms
 Batch 54: 1743 ms     Batch 54:  915 ms     Batch 54:  540 ms     Batch 54:  508 ms
 Batch 55: 1637 ms     Batch 55: 1066 ms     Batch 55:  563 ms     Batch 55:  488 ms
 Batch 56: 1668 ms     Batch 56: 1059 ms     Batch 56:  570 ms     Batch 56:  478 ms
 Batch 57: 1760 ms     Batch 57: 1110 ms     Batch 57:  505 ms     Batch 57:  437 ms
 Batch 58: 1814 ms     Batch 58:  874 ms     Batch 58:  626 ms     Batch 58:  426 ms
 Batch 59: 1855 ms     Batch 59:  893 ms     Batch 59:  555 ms     Batch 59:  440 ms
 Batch 60: 1818 ms     Batch 60:  927 ms     Batch 60:  570 ms     Batch 60:  432 ms
 Batch 61: 1701 ms     Batch 61:  932 ms     Batch 61:  551 ms     Batch 61:  452 ms
 Batch 62: 1691 ms     Batch 62:  875 ms     Batch 62:  537 ms     Batch 62:  389 ms
 Batch 63: 1743 ms     Batch 63:  966 ms     Batch 63:  592 ms     Batch 63:  521 ms
 Batch 64: 1698 ms     Batch 64: 1010 ms     Batch 64:  611 ms     Batch 64:  430 ms
 Batch 65: 1744 ms     Batch 65:  964 ms     Batch 65:  563 ms     Batch 65:  505 ms
 Batch 66: 1687 ms     Batch 66:  918 ms     Batch 66:  553 ms     Batch 66:  382 ms
 Batch 67: 1656 ms     Batch 67: 1021 ms     Batch 67:  567 ms     Batch 67:  457 ms
 Batch 68: 1684 ms     Batch 68:  965 ms     Batch 68:  548 ms     Batch 68:  480 ms
 Batch 69: 1675 ms     Batch 69:  891 ms     Batch 69:  548 ms     Batch 69:  516 ms
 Batch 70: 1700 ms     Batch 70:  893 ms     Batch 70:  560 ms     Batch 70:  429 ms
 Batch 71: 1687 ms     Batch 71:  971 ms     Batch 71:  531 ms     Batch 71:  486 ms
 Batch 72: 1654 ms     Batch 72: 1145 ms     Batch 72:  555 ms     Batch 72:  394 ms
 Batch 73: 1669 ms     Batch 73:  924 ms     Batch 73:  554 ms     Batch 73:  477 ms
 Batch 74: 1637 ms     Batch 74: 1023 ms     Batch 74:  591 ms     Batch 74:  481 ms
 Batch 75: 1653 ms     Batch 75: 1108 ms     Batch 75:  639 ms     Batch 75:  404 ms
 Batch 76: 1618 ms     Batch 76:  978 ms     Batch 76:  627 ms     Batch 76:  464 ms
 Batch 77: 1711 ms     Batch 77:  969 ms     Batch 77:  620 ms     Batch 77:  392 ms
 Batch 78: 1647 ms     Batch 78:  953 ms     Batch 78:  593 ms     Batch 78:  501 ms
 Batch 79: 1724 ms     Batch 79:  898 ms     Batch 79:  574 ms     Batch 79:  385 ms
 Batch 80: 1680 ms     Batch 80:  945 ms     Batch 80:  622 ms     Batch 80:  381 ms
 Batch 81: 1630 ms     Batch 81:  973 ms     Batch 81:  555 ms     Batch 81:  448 ms
 Batch 82: 1618 ms     Batch 82:  906 ms     Batch 82:  828 ms     Batch 82:  441 ms
 Batch 83: 1703 ms     Batch 83:  958 ms     Batch 83:  580 ms     Batch 83:  436 ms
 Batch 84: 1683 ms     Batch 84:  920 ms     Batch 84:  636 ms     Batch 84:  467 ms
 Batch 85: 1618 ms     Batch 85: 1032 ms     Batch 85:  588 ms     Batch 85:  427 ms
 Batch 86: 1695 ms     Batch 86:  947 ms     Batch 86:  547 ms     Batch 86:  410 ms
 Batch 87: 1691 ms     Batch 87: 1008 ms     Batch 87:  561 ms     Batch 87:  393 ms
 Batch 88: 1764 ms     Batch 88:  953 ms     Batch 88:  587 ms     Batch 88:  510 ms
 Batch 89: 1704 ms     Batch 89:  935 ms     Batch 89:  568 ms     Batch 89:  464 ms
 Batch 90: 1631 ms     Batch 90:  962 ms     Batch 90:  570 ms     Batch 90:  435 ms
 Batch 91: 1613 ms     Batch 91:  983 ms     Batch 91:  569 ms     Batch 91:  439 ms
 Batch 92: 1604 ms     Batch 92:  930 ms     Batch 92:  582 ms     Batch 92:  428 ms
 Batch 93: 1592 ms     Batch 93:  926 ms     Batch 93:  507 ms     Batch 93:  518 ms
 Batch 94: 1596 ms     Batch 94:  946 ms     Batch 94:  613 ms     Batch 94:  444 ms
 Batch 95: 1688 ms     Batch 95:  894 ms     Batch 95:  572 ms     Batch 95:  492 ms
 Batch 96: 1613 ms     Batch 96:  939 ms     Batch 96:  586 ms     Batch 96:  490 ms
 Batch 97: 1651 ms     Batch 97:  915 ms     Batch 97:  606 ms     Batch 97:  489 ms
 Batch 98: 1689 ms     Batch 98:  946 ms     Batch 98:  639 ms     Batch 98:  482 ms
 Batch 99: 1680 ms     Batch 99:  953 ms     Batch 99:  614 ms     Batch 99:  400 ms
-------------------   -------------------   -------------------   -------------------

Test code:

double CalculateDistance(List<double> p1, List<double> p2) {
    double dx = p2[0] - p1[0];
    double dy = p2[1] - p1[1];
    double dz = p2[2] - p1[2];
    return Math.Sqrt(dx * dx + dy * dy + dz * dz);
}

var initTime = Stopwatch.StartNew();
var origin = new List<double> { 20, 40, 60 };
var points = Enumerable
    .Range(0, 20000000)
    .Select(i => new List<double> { i, i, i })
    .ToList();
WriteLine($"Initialization: {initTime.ElapsedMilliseconds} ms");

var times = new List<long>();

for(int i = 0; i < 100; i++) {
    var sw = Stopwatch.StartNew();
    points
        .AsParallel()
        .WithDegreeOfParallelism(8)
        .Select(point => (point: point, distance: CalculateDistance(point, origin)))
        .Aggregate((p1, p2) => p1.distance > p2.distance ? p1 : p2);
    
    long time = sw.ElapsedMilliseconds;
    WriteLine($"Batch {i}: {time} ms");
    times.Add(time);
}

WriteLine($"Average: {times.Average()} ms");