怎麼把同一列重複的資料標出來

阿巴可懂的實時排行榜系統設計和實現思路。

大家好，我是魚皮，暑假快到了，我的老弟小阿巴聽說我家有很多好康的，就跑來找我玩。

結果我擺出了幾個以前開發過的小系統，準備在這段時間帶著小阿巴多做些作品，學習程式設計專案的設計思路。這樣等他開學了，就可以更輕鬆地跟著老師做做專案了。

今天，就先帶他做一個很常見的小功能：使用者實時積分排行榜。

實時積分排行榜

需求

先描述下需求，在我的程式設計導航專案（https：//www。code-nav。cn）中，為了鼓勵大家共同維護網站，使用者可以透過推薦資源、積極評論、舉報違規資源等方式獲取積分。

為了進一步激勵大家，網站需要提供一個使用者積分排行榜，分為

實時總積分榜

、

周榜

和

月榜

，均

只取前 10 名

。所有使用者都能夠檢視當前排行榜，以及檢視自己的

實時

總積分排名，後續管理員就可以給上榜使用者頒發獎品了。

效果如下圖：

點選

我的排名

按鈕，可以檢視自己的實時排名：

本文篇幅有限，先僅討論

實時總積分榜

的設計實現。

聽了需求後，小阿巴爽朗一笑：這有啥難的？且讓我設計一波，再給你娓娓道來。

設計實現

先看下資料庫的結構，總共有 2 個表：

使用者表

和

使用者積分表

。

使用者表儲存了使用者資訊，以及使用者的總積分（實時更新），也就是說總積分榜需要的資料可以直接從這裡取到，不需要再去計算。

使用者表內容：

使用者 id

使用者名稱

積分（score）

1 小阿巴 10

2 李魚皮 1000

3 小李 100

……

100 李老熱 66

如果要取前 10 名，只需要把所有使用者的資訊先取出來，再排個序就好啦，寫 SQL 語句查詢的話就是：

select * from `user` order by score；

然後如果要取自己的總排名，就對查到的有序資料進行一次遍歷，找到自己所在的位置下標就行，虛擬碼如下：

// 從資料庫查詢全部使用者列表list = getAllDataList（）for（i = 0； i < total； i++） { // 找到自己的位置 if（list［i］。id == ‘我的id’） { return i + 1； }}

小阿巴得意到：這不就實現總積分榜了麼？你這需求太簡單，嘖嘖。

我笑到：還不錯，總積分榜的思路是正確的，起碼知道要對所有的資料進行排序。但如果使用者數特別多呢？比如幾十萬個，你只需要查自己的總排名，還需要把全部的資料都做一個排序麼？

小阿巴陷入沉思，想了半天，沒想出來。

於是我提示到：假如在一次考試中你想知道自己的排名，是不是隻需要知道有多少人的分數比自己高就行了，不用去管其他人排第幾對吧？

小阿巴一拍腦袋：對啊，我只需要先查出自己的分數，然後統計分數大於我的使用者數量，不就知道自己的排名了？

先用 SQL 語句查出使用者的分數：

/* 只取需要的列 */select score as myScorefrom `user`where id = “使用者 id”；

然後再用 SQL 語句統計分數大於該使用者分數的數量：

select count（*） from `user`where score > myScore；

最後只需要將該查詢結果加 1，就是自己的排名啦~

小阿巴感嘆到：原來轉換一點點思路，就能省去多餘的排序帶來的效能開銷，起飛~

更多思考

魚皮：先別起飛，其實對於一般使用者量的系統，上面的方案就已經足夠了。下面讓我們加大難度，假如使用者數再多一點點呢，比如說一億個，怎麼實時獲取前 10 名呢？

小阿巴：還真是 “億點點”，就您那破程式設計導航還想著有一億個使用者？

魚皮：少廢話，夢想還是要有的，萬一有億個使用者呢？快想想系統怎麼做！

小阿巴：且不說對一億個資料排序有多慢，能不能存的下都是個問題啊。。。啊，等等，這難道就是面試常見的 Top N 問題！

魚皮：不錯，我面試的時候被問過好幾次 Top N 問題，如何從海量資料中找出前 N 個數呢？

小阿巴：這我完全不懂啊，演算法不會，真要命。

魚皮：其實 Top N 問題的核心在於保證空間和時間複雜度，先要考慮資料能存入記憶體運算，在怎樣算得更快。

通常 Top N 問題有下列幾種解決方案。

Top N 解決方案

全部排序

直接對所有資料進行排序（快排等），缺點是需要將資料一次性載入到記憶體中。

區域性淘汰

記憶體中維護一個大小為 N 的容器，再讓剩餘的數一個個進入容器，並淘汰容器內的最小值。最終容器內剩下的數就是前 N 名。優點是能節省記憶體，缺點是太慢了。

分治

把資料分為多個小組，小組內先分別選出前 N 名小組長，最後再讓這些小組長同臺競技，選出最終的前 N 名。

雜湊預處理

假如資料重複度很高，可以透過 hash 的方式，去掉很多重複資料。比如 1 億個資料裡，一半是 0，一半是 1，那麼取前 10 名時，可以直接淘汰掉另一半為 0 的資料。

但是預處理本身也需要時間和空間，這就需要我們對資料的重複度有一個清晰的判斷，否則自作聰明、適得其反。

小根堆

面試演算法中的高頻考點 —— 堆排序，可以先取前 N 個數組成小根堆，堆頂始終是最小值。 然後遍歷後續數字，大於堆頂就替換掉堆頂並調整最小堆結構。該演算法時間複雜度和空間複雜度（為 N，常數）都不錯，所以必須要掌握。

小根堆

但是具體選擇哪種方案呢？還是要結合我們實際的專案和業務場景來分析。

實際解決

由於我們的資料庫來記錄積分，所以當用戶量級很大時，首先要

分庫分表

，通常是水平分表，根據一定規則（比如 id）把使用者資料行分批儲存在多個數據表中。

分表

然後就和大資料 Map / Reduce 處理機制一樣了，可以採用

分治

的方式

平行計算

每個表的前 10 名（map），都計算好後，再彙總到一起計算最終的前 10 名（reduce）。

一次大資料並行處理過程

用這種方式，別說 1 億了，2 億、3 億的計算模式都是一樣的，加機器水平擴容就好了~

所以遇到 Top N 問題的時候，大家可以先答一下上面的幾種方案，再結合具體的場景分析，分治和最小堆是我覺得相對

核心

的點。

Redis

最後，對於實時排行榜的設計，肯定很多背過八股文面試題的朋友在第一時間會想到使用 Redis 的有序集合 zset，的確也是一種方案，但也要結合場景去分析利弊，不要秒答。

使用基於記憶體的 Redis zset 的確運算更快，且天然支援排序、使用方便。但資料量大時同樣面臨資料更新、維護、同步、持久化儲存等問題，而且對於我們這種實時性要求不高的需求來說，有些大材小用了哈哈。

zset 資料結構

我是魚皮，肝文不易，

點贊

還是要求一下的，祝大家都能心想事成、發大財、行大運。

最後再送大家一些

幫助我拿到大廠 offer 的學習資源

，影片教程 + 習題 + 答案 + 原始碼、程式設計書籍、大廠面經、實戰專案等。

指路：跑了，留下 6T 的資源！

（https：//t。1yb。co/qOJG）

我是如何從零開始透過自學，拿到騰訊、位元組等大廠 offer 的，可以看這篇文章，不再迷茫！

指路：我學計算機的四年，共勉！

（https：//t。1yb。co/q0mS）