linux-kernel - Re: [PATCH v2] platform/chrome: sensorhub: Implement quickselect for median calculation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <169994162395.30294.11655195968151519457.git-patchwork-notify@kernel.org>
Date:   Tue, 14 Nov 2023 06:00:23 +0000
From:   patchwork-bot+chrome-platform@...nel.org
To:     Kuan-Wei Chiu <visitorckw@...il.com>
Cc:     bleung@...omium.org, tzungbi@...nel.org, groeck@...omium.org,
        chrome-platform@...ts.linux.dev, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2] platform/chrome: sensorhub: Implement quickselect for
 median calculation

Hello:

This patch was applied to chrome-platform/linux.git (for-next)
by Tzung-Bi Shih <tzungbi@...nel.org>:

On Sat, 11 Nov 2023 00:53:14 +0800 you wrote:
> 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.
> 
> [...]

Here is the summary with links:
  - [v2] platform/chrome: sensorhub: Implement quickselect for median calculation
    https://git.kernel.org/chrome-platform/c/d131f1f3b459

You are awesome, thank you!
-- 
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html