快速選擇算法:優化大數據中的 Top-K 問題

在處理海量數據時,經常會遇到這樣的需求:找出數據中最大的前 K 個數,而不必對整個數據集進行排序。這種場景下,快速選擇算法(Quickselect)就成了一個非常高效的解決方案。本文將通過一個 C++ 實現的快速選擇算法來詳細講解其原理和應用。

快速選擇算法原理

快速選擇算法是由 Tony Hoare 在 1961 年提出的,它基于快速排序(Quicksort)的思想。與快速排序不同的是,快速選擇只需要處理包含目標元素的那一部分子數組,因此其平均時間復雜度為 O (n),優于排序算法的 O (n log n)。

快速選擇的核心思想是利用快速排序中的分區(partition)過程:選擇一個基準元素(pivot),將數組分為兩部分,使得左邊部分的所有元素都大于等于基準元素,右邊部分的所有元素都小于基準元素。然后根據基準元素的位置與 K 的關系,決定是繼續在左半部分還是右半部分查找。

代碼實現與解析

下面是一個使用快速選擇算法查找前 K 大元素的 C++ 實現:

#include<iostream>
#include<algorithm>
#include<vector>
#include<time.h>
using namespace std;// 快速選擇函數:查找數組中前top大的元素
template<class T>
void find(vector<T>& q, int top, int l, int r) {if (l >= r) return;// 選擇中間元素作為基準int mid = (l + r) / 2;T val = q[mid];// 初始化左右指針int i = l;int j = r;// 分區過程while (i < j) {// 從左向右找到第一個小于等于基準的元素while (q[i] > val && i < j) i++;// 從右向左找到第一個大于等于基準的元素while (q[j] < val && i < j) j--;// 交換這兩個元素if (i < j) swap(q[i], q[j]);else break;}// 根據分區結果遞歸處理if (j - l + 1 > top) {// 左半部分元素數量大于top,在前半部分繼續查找find(q, top, l, i);} else {// 否則在后半部分查找剩余的元素find(q, top - (j - l + 1), i + 1, r);}
}int main() {vector<double> q;vector<double> q1;  // 存儲快速選擇結果vector<double> q3;  // 存儲排序結果用于對比// 生成測試數據srand(time(NULL));for (int i = 0; i < 1000; i++) {q.push_back(rand() % 10000 + i * 1.0 / 100);}q3 = q;// 使用快速選擇算法查找前10大的元素find(q, 10, 0, 999);// 將結果存入q1for (int i = 0; i < 10; i++) q1.push_back(q[i]);// 對原數組進行降序排序sort(q3.rbegin(), q3.rend());// 對快速選擇的結果進行降序排序sort(q1.rbegin(), q1.rend());// 輸出結果cout << "快速選擇結果:";for (auto i : q1) cout << i << ' ';cout << endl;cout << "完整排序結果:";for (auto i : q3) cout << i << ' ';
}
代碼工作流程分析
  1. 分區過程

    • 選擇中間元素作為基準(pivot)
    • 使用雙指針法將數組分為兩部分:左邊部分大于等于基準,右邊部分小于基準
    • 通過交換元素實現分區
  2. 遞歸策略

    • 計算左半部分的元素數量
    • 如果左半部分元素數量大于 K,則在前半部分繼續查找
    • 否則在后半部分查找剩余的 K-(左半部分數量) 個元素
  3. 主函數測試

    • 生成 1000 個隨機數作為測試數據
    • 分別使用快速選擇和完整排序兩種方法
    • 比較兩種方法得到的前 10 大元素
快速選擇的性能優勢

快速選擇算法之所以高效,是因為它每次只處理目標元素所在的那一部分子數組。在平均情況下,其時間復雜度為 O (n),而空間復雜度為 O (1)(不考慮遞歸棧空間)。

相比之下,完整排序算法(如快速排序、歸并排序)的時間復雜度為 O (n log n),這意味著在處理大規模數據時,快速選擇算法的性能優勢會更加明顯。

應用場景

快速選擇算法在實際應用中非常廣泛,特別是在需要從大量數據中找出 Top-K 元素的場景:

  • 搜索引擎中的熱門搜索詞統計
  • 推薦系統中的 Top-N 推薦項
  • 游戲中的排行榜系統
  • 數據挖掘中的異常檢測

通過快速選擇算法,我們可以在不排序整個數據集的情況下,高效地找到所需的 Top-K 元素,大大提高了處理大規模數據的效率。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/80113.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/80113.shtml
英文地址,請注明出處:http://en.pswp.cn/web/80113.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

AQS 基本思想與源碼分析

充分了解 AbstractQueuedSynchronizer 對于深入理解并發編程是有益處的&#xff0c;它是用來構建鎖或者其他同步組件的基礎框架&#xff0c;我們常用的同步工具類如 CountDownLatch、Semaphore、ThreadPoolExecutor、ReentrantLock 和 ReentrantReadWriteLock 內部都用到了它。…

理解位圖算法:使用 C++ 實現高效數據查重

在處理海量數據時&#xff0c;我們常常需要檢查某個元素是否已經存在于集合中。傳統的方法如哈希表或集合容器雖然有效&#xff0c;但在數據量極大的情況下會占用大量內存。這時&#xff0c;位圖算法 (Bitmap) 就成為了一種非常高效的解決方案。本文將通過分析一段使用位圖算法…

數學復習筆記 12

前言 現在做一下例題和練習題。矩陣的秩和線性相關。另外還要復盤前面高數的部分的內容。奧&#xff0c;之前矩陣的例題和練習題&#xff0c;也沒有做完&#xff0c;行列式的例題和練習題也沒有做完。累加起來了。以后還是得學一個知識點就做一個部分的內容&#xff0c;日拱一…

1-10 目錄樹

在ZIP歸檔文件中&#xff0c;保留著所有壓縮文件和目錄的相對路徑和名稱。當使用WinZIP等GUI軟件打開ZIP歸檔文件時&#xff0c;可以從這些信息中重建目錄的樹狀結構。請編寫程序實現目錄的樹狀結構的重建工作。 輸入格式: 輸入首先給出正整數N&#xff08;≤104&#xff09;…

Python爬蟲實戰:研究 RPC 遠程調用機制,實現逆向解密

1. 引言 在網絡爬蟲技術的實際應用中,目標網站通常采用各種加密手段保護其數據傳輸和業務邏輯。這些加密機制給爬蟲開發帶來了巨大挑戰,傳統的爬蟲技術往往難以應對復雜的加密算法。逆向解密作為一種應對策略,旨在通過分析和破解目標網站的加密機制,獲取原始數據。 然而,…

debugfs:Linux 內核調試的利器

目錄 一、什么是 debugfs&#xff1f;二、debugfs 的配置和啟用方式2.1 內核配置選項2.2 掛載 debugfs2.3 Android 系統中的 debugfs 三、debugfs 的典型應用場景3.1 調試驅動開發3.2 內核子系統調試3.3 性能分析 四、常見 debugfs 子目錄與功能示例4.1 /sys/kernel/debug/trac…

lua 作為嵌入式設備的配置語言

從lua的腳本中獲取數據 lua中棧的索引 3 | -1 2 | -2 1 | -3 可以在lua的解釋器中加入自己自定的一些功能,其實沒啥必要,就是為了可以練習下lua

棋牌室臺球室快速接入美團團購接口

北極星平臺從2024年12月份開始慢慢關閉&#xff0c;現在很多開發者反饋北極星token已經不能刷新了&#xff0c;全部遷移到美團團購綜合平臺。 申請這個平臺要求很高 1、保證金費用要15萬起步 2、平臺必須是二級等保和安全產品 &#xff0c;一個二級等保費用10萬起步 所以很多…

開源輕量級地圖解決方案leaflet

Leaflet 地圖&#xff1a;開源輕量級地圖解決方案 Leaflet 是一個開源的 JavaScript 庫&#xff0c;用于在網頁中嵌入交互式地圖。它以輕量級、靈活性和易用性著稱&#xff0c;適用于需要快速集成地圖功能的項目。以下是關于 Leaflet 的詳細介紹和使用指南。 1. Leaflet 的核心…

一個批量文件Dos2Unix程序(Microsoft Store,開源)1.1.0 編碼檢測和預覽

之前的版本是個意思意思&#xff0c;驗證商店發布的&#xff08;其實是我以前自己用的工具&#xff09;&#xff0c;這次把格式檢查和轉換都做上了&#xff0c;功能應該差不多了&#xff0c;還有一些需要小改進的地方。 因為還沒什么用戶嘛&#xff0c;還是保持全功能免費試用。…

特征提取:如何從不同模態中獲取有效信息?

在多模態學習中&#xff0c;不同模態&#xff08;文本、圖像、語音、視頻、傳感器數據等&#xff09;所攜帶的信息豐富且互補。但不同模態的數據結構、表示空間、時空分布截然不同&#xff0c;因此&#xff0c;如何對各模態進行高效、有效的特征提取&#xff0c;是整個多模態學…

Go語言爬蟲系列教程 實戰項目JS逆向實現CSDN文章導出教程

爬蟲實戰&#xff1a;JS逆向實現CSDN文章導出教程 在這篇教程中&#xff0c;我將帶領大家實現一個實用的爬蟲項目&#xff1a;導出你在CSDN上發布的所有文章。通過分析CSDN的API請求簽名機制&#xff0c;我們將繞過平臺限制&#xff0c;獲取自己的所有文章內容&#xff0c;并以…

交叉熵損失函數,KL散度, Focal loss

交叉熵損失函數&#xff08;Cross-Entropy Loss&#xff09; 交叉熵損失函數&#xff0c;涉及兩個概念&#xff0c;一個是損失函數&#xff0c;一個是交叉熵。 首先&#xff0c;對于損失函數。在機器學習中&#xff0c;損失函數就是用來衡量我們模型的預測結果與真實結果之間…

149.WEB滲透測試-MySQL基礎(四)

免責聲明&#xff1a;內容僅供學習參考&#xff0c;請合法利用知識&#xff0c;禁止進行違法犯罪活動&#xff01; 內容參考于&#xff1a; 易錦網校會員專享課 上一個內容&#xff1a;148.WEB滲透測試-MySQL基礎&#xff08;三&#xff09; 非關系型數據庫&#xff1a; &a…

c/c++中程序內存區域的劃分

c/c程序內存分配的幾個區域&#xff1a; 1.棧區&#xff1a;在執行函數時&#xff0c;函數內局部變量的存儲單元都可以在棧上創建&#xff0c;函數執行結束時這些存儲單元自動被釋放&#xff0c;棧內存分配運算內置于處理器的指令集中&#xff0c;效率很高但是分配的內存容量有…

構建穩定的金字塔模式生態:從自然法則到系統工程

在自然界中&#xff0c;金字塔結構廣泛存在于生態系統之中&#xff0c;表現為營養級能量金字塔、生物量金字塔和數量金字塔等形式。這種結構不僅形象地描述了生態能量流轉的規律&#xff0c;也體現出生態系統中“穩定性”與“層級性”的天然法則。在現代軟件架構、企業組織、平…

Vue 3.0雙向數據綁定實現原理

Vue3 的數據雙向綁定是通過響應式系統來實現的。相比于 Vue2&#xff0c;Vue3 在響應式系統上做了很多改進&#xff0c;主要使用了 Proxy 對象來替代原來的 Object.defineProperty。本文將介紹 Vue3 數據雙向綁定的主要特點和實現方式。 1. 響應式系統 1.1. Proxy對象 Vue3 …

TIP-2021《SRGAT: Single Image Super-Resolution With Graph Attention Network》

推薦深藍學院的《深度神經網絡加速&#xff1a;cuDNN 與 TensorRT》&#xff0c;課程面向就業&#xff0c;細致講解CUDA運算的理論支撐與實踐&#xff0c;學完可以系統化掌握CUDA基礎編程知識以及TensorRT實戰&#xff0c;并且能夠利用GPU開發高性能、高并發的軟件系統&#xf…

大語言模型與多模態模型比較

一、核心差異&#xff1a;輸入數據類型與模態融合 輸入數據類型 LLM&#xff1a;僅處理文本數據&#xff0c;例如文本分類、機器翻譯、問答等任務&#xff0c;通過大規模語料庫學習語言規律。 LMM&#xff1a;支持文本、圖像、音頻、視頻等多種模態輸入&#xff0c;例如根據圖…

Apache HttpClient 5 用法-Java調用http服務

Apache HttpClient 5 核心用法詳解 Apache HttpClient 5 是 Apache 基金會推出的新一代 HTTP 客戶端庫&#xff0c;相比 4.x 版本在性能、模塊化和易用性上有顯著提升。以下是其核心用法及最佳實踐&#xff1a; 一、添加依賴 Maven 項目&#xff1a; <dependency><…