diff options
author | Kuan-Wei Chiu <visitorckw@gmail.com> | 2023-11-11 00:53:14 +0800 |
---|---|---|
committer | Tzung-Bi Shih <tzungbi@kernel.org> | 2023-11-13 12:46:42 +0800 |
commit | d131f1f3b459980d38a59adc3598c96cc3a6ad5e (patch) | |
tree | 2ab9c10ad6f5d29d8191bb721cab24035560ecf1 /drivers/platform/chrome | |
parent | platform/chrome: sensorhub: Fix typos (diff) | |
download | wireguard-linux-d131f1f3b459980d38a59adc3598c96cc3a6ad5e.tar.xz wireguard-linux-d131f1f3b459980d38a59adc3598c96cc3a6ad5e.zip |
platform/chrome: sensorhub: Implement quickselect for median calculation
The cros_ec_sensor_ring_median function currently uses an inefficient
sorting algorithm (> O(n)) to find the median of an array. This patch
replaces the sorting approach with the quickselect algorithm, which
achieves an average time complexity of O(n).
The algorithm employs the median-of-three rule to select the pivot,
mitigating worst-case scenarios and reducing the expected number of
necessary comparisons. This strategy enhances the algorithm's
efficiency and ensures a more balanced partitioning.
In the worst case, the runtime of quickselect could regress to O(n^2).
To address this, alternative algorithms like median-of-medians that
can guarantee O(n) even in the worst case. However, due to higher
overhead and increased complexity of implementation, quickselect
remains a pragmatic choice for our use case.
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
Link: https://lore.kernel.org/r/20231110165314.1559285-1-visitorckw@gmail.com
Signed-off-by: Tzung-Bi Shih <tzungbi@kernel.org>
Diffstat (limited to 'drivers/platform/chrome')
-rw-r--r-- | drivers/platform/chrome/cros_ec_sensorhub_ring.c | 62 |
1 files changed, 45 insertions, 17 deletions
diff --git a/drivers/platform/chrome/cros_ec_sensorhub_ring.c b/drivers/platform/chrome/cros_ec_sensorhub_ring.c index 9e17f7483ca0..1205219515d6 100644 --- a/drivers/platform/chrome/cros_ec_sensorhub_ring.c +++ b/drivers/platform/chrome/cros_ec_sensorhub_ring.c @@ -133,33 +133,61 @@ int cros_ec_sensorhub_ring_fifo_enable(struct cros_ec_sensorhub *sensorhub, return ret; } -static int cros_ec_sensor_ring_median_cmp(const void *pv1, const void *pv2) +static void cros_ec_sensor_ring_median_swap(s64 *a, s64 *b) { - s64 v1 = *(s64 *)pv1; - s64 v2 = *(s64 *)pv2; - - if (v1 > v2) - return 1; - else if (v1 < v2) - return -1; - else - return 0; + s64 tmp = *a; + *a = *b; + *b = tmp; } /* * cros_ec_sensor_ring_median: Gets median of an array of numbers * - * For now it's implemented using an inefficient > O(n) sort then return - * the middle element. A more optimal method would be something like - * quickselect, but given that n = 64 we can probably live with it in the - * name of clarity. + * It's implemented using the quickselect algorithm, which achieves an + * average time complexity of O(n) the middle element. In the worst case, + * the runtime of quickselect could regress to O(n^2). To mitigate this, + * algorithms like median-of-medians exist, which can guarantee O(n) even + * in the worst case. However, these algorithms come with a higher + * overhead and are more complex to implement, making quickselect a + * pragmatic choice for our use case. * - * Warning: the input array gets modified (sorted)! + * Warning: the input array gets modified! */ static s64 cros_ec_sensor_ring_median(s64 *array, size_t length) { - sort(array, length, sizeof(s64), cros_ec_sensor_ring_median_cmp, NULL); - return array[length / 2]; + int lo = 0; + int hi = length - 1; + + while (lo <= hi) { + int mid = lo + (hi - lo) / 2; + int pivot, i; + + if (array[lo] > array[mid]) + cros_ec_sensor_ring_median_swap(&array[lo], &array[mid]); + if (array[lo] > array[hi]) + cros_ec_sensor_ring_median_swap(&array[lo], &array[hi]); + if (array[mid] < array[hi]) + cros_ec_sensor_ring_median_swap(&array[mid], &array[hi]); + + pivot = array[hi]; + i = lo - 1; + + for (int j = lo; j < hi; j++) + if (array[j] < pivot) + cros_ec_sensor_ring_median_swap(&array[++i], &array[j]); + + /* The pivot's index corresponds to i+1. */ + cros_ec_sensor_ring_median_swap(&array[i + 1], &array[hi]); + if (i + 1 == length / 2) + return array[i + 1]; + if (i + 1 > length / 2) + hi = i; + else + lo = i + 2; + } + + /* Should never reach here. */ + return -1; } /* |