目錄
- 組員職責分工
- github 的送出日志截圖
- 程式運作截圖
- 程式運作環境
- GUI界面
- 基礎功能實作
- 運作視訊
- LCG算法
- 過濾(降級)算法
- 算法思路
- 紅黑樹
- 附加功能一
- 背景
- 實作
- 附加功能二(疊代中)
- 附加功能三
- 引言
- 解決方法
- 實作效果
- 效果截圖
- 遇到的困難及解決方法
- 組員:胡緒佩
- 組員:莊卉
- 組員:周政演
- 組員:劉一好
- 組員:翟丹丹
- 組員:劉恺琳
- 組員:青元
- 組員:葛家燦
- 組員:何家偉
- 組員:黃鴻傑
- 組員:何宇恒
- 馬後炮
- 貢獻分評估
- PSP表格
- 個人學習進度條
組員 | 職責 |
---|---|
緒佩 | 組織分工、改進前端、後端、雲化 |
莊卉 | 改進前端、後端 |
家偉 | 算法關鍵詞識别、附加題實作 |
家燦 | 資料庫 |
一好 | 算法随機數、算法審查 |
鴻傑 | |
政演 | 提供算法思路、附加題idea思路、部落格撰寫 |
凱琳 | 前端審查 |
丹丹 | |
青元 | 前端改進 |
宇恒 |
github位址
運作結果
抽獎結果名單
環境 | 名稱 |
---|---|
作業系統 | Windows10 |
編譯器 | Eclipse javaee |
本地伺服器 | Tomcat |
MySQL | |
可視化資料庫工具 | Navicat |
進入界面
抽獎規則設定1
抽獎規則設定2
錯誤提示
釋出成功顯示
本算法具有以下模式:
- 不過濾模式:剔除機器,所有參與抽獎的人,都納入開獎範圍。
- 普通模式:篩除隻參與抽獎而無發表任何原創言論的使用者(抽獎機器人),鼓勵大家積極參與有意義的發言。
- 深度模式:為了使發言更有意義,減少灌水,對以下使用者的中獎機率進行降級處理:
- 隻參與抽獎而無發表任何原創言論(抽獎機器人)
- 隻參與抽獎且隻發送表情(水軍)
視訊連結:https://v.youku.com/v_show/id_XMzkyODA4NDY0OA==.html?spm=a2h0k.11417342.soresults.dtitle
随機算法:
我們的抽獎算法基于LCG算法,LCG(linear congruential generator)線性同餘算法,是一個古老的産生随機數的算法。
本算法有以下優點:
- 計算速度快:抽獎時的算法時間複雜度是一個較大的問題,在微網誌開獎的時候,由于抽獎人數衆多,(例如王思聰的抽獎微網誌,轉發量、評論數、點贊數均達到了兩千萬,總數達到了六千萬,輸入量十分巨大)是以常常需要花費幾十分鐘的時間開獎,如此的算法性能是難以忍受的。對此,我們的算法基于LCG算法,利用其速度優勢,減少開獎時間。
- 易于實作:算法易于了解,可以通過改變取餘數來控制算法的空間複雜度與随機分布效果。且算法是線性的算法,和非線性的模型相比,具有較低的複雜度。
- 易于推廣:本算法改變取餘參數,對空間資源和随機準确率權衡,根據不同的裝置資源和計算能力調優,具有很強的靈活性,易于使用推廣。
本算法基于的LCG算法由以下參數組成:
參數 | m | a | c | X |
---|---|---|---|---|
性質 | 模數 | 乘數 | 加數 | 随機數 |
作用 | 取模 | 移位 | 偏移 | 作為結果 |
LCG算法是如下的一個遞推公式,每下一個随機數是目前随機數向左移動 log2 a 位,加上一個 c,最後對 m 取餘,使随機數限制在 0 ~ m-1 内
從該式可以看出,該算法由于構成簡單,具有以下優點:
- 計算速度快
- 易于實作
- 易于寫入硬體
以下是針對不同參數 lcg 産生随機數的效果圖
可以看出,針對不同的參數,lcg産生的效果差别很大
以下是針對不同環境下的參數選擇
根據我們機器的情況,我們選擇使用參數:
抽獎算法對兩種情況進行了處理:
無發言剔除:當使用者隻轉發抽獎關鍵字,而沒有相關發言時,直接剔出抽獎名單。
惡意刷屏:抽獎者可以自行定義一個抽獎門檻值φ1,當發言數超過φ1時,對該使用者進行中獎機率降級處理。
灌水剔除:抽獎者可以自行定義一個抽獎門檻值φ2,發送的表情數超過門檻值的時候,判定為灌水,剔出抽獎名單
for (Map.Entry<String, Integer> en : map.entrySet()) {
//System.out.println(en.getKey() + "=" + en.getValue());
x[i] = ( a * x[i-1] + b ) % m;
if (en.getValue() < 0) { //發言為空,剔出抽獎名單
i++;
continue;
} else if (en.getValue() > 0) { //惡意刷屏,降低權重
weight = en.getValue();
if (weight > 30) {
weight = 30;
}
x[i] = (int) (x[i] * ((double)(30 - weight) / 30.0));
}
map.put(en.getKey(), x[i]);
//System.out.println(en.getKey() + "=" + en.getValue());
i++;
}
紅黑樹是一種自平衡的二叉查找樹,是一種高效的查找樹。
- 提供良好的效率:可在O(logN)時間内完成查找、增加、删除等操作,能保證在最壞情況下,基本的動态幾何操作的時間均為O(lgn)。隻要求部分地達到平衡要求,降低了對旋轉的要求,任何不平衡都會在三次旋轉之内解決,進而提高了效率。抽獎伏安法涉及大量增删改查操作,紅黑樹算法提供了良好的效率支撐。
- 提供性能下限保證:相比于BST,紅黑樹可以能確定樹的最長路徑不大于兩倍的最短路徑的長度,可見其查找效果的最低保證。最壞的情況下也可以保證O(logN)的複雜度,好于二叉查找樹O(N)複雜度。在大資料量情況下,紅黑樹算法為抽獎算法提供良好的性能保證。
- 提供詞頻統計的高性能:紅黑樹的算法時間複雜度和AVL樹相同,但統計性能更高。插入 AVL樹和紅黑樹的速度取決于所插入的資料。在資料比較雜亂的情況,則紅黑樹的統計性能優于AVL樹。在抽獎時時,資料分布較為雜亂,在此應用場景下,紅黑樹算法與抽獎器契合。
- 提供較小的資源開銷:與基于哈希的算法相比,基于紅黑樹方法帶來更小的資源開銷,程式消耗記憶體較少。哈希的算法占用大量資源,需要維護大量的計數器,并且在哈希過程中消耗了大量的計算資源。抽獎系統器消耗的資源較少。
現抽獎的人數也越來越多。例如:王思聰抽獎微網誌總數達到了六千萬對每個抽獎賬号還需要維護巨大的資料量。惡意灌水、轉發的賬号,或是機器人賬号,将大大影響抽獎的性能。抽獎機器人大量的抽獎參與,也将給系統帶來很大的影響。對此,我們設定了一個針對抽獎的惡意檢測功能。可以針對灌水言論,設定一個門檻值,可以對門檻值進行調整。當發言數超過門檻值時,報出該為惡意使用者,可以列入黑名單。在之後的抽獎活動中,可以屏蔽黑名單中的使用者,減少系統的資源消耗,同時保證公平性。該功能基于下文中基于sketch的資料處理功能,在較小的空間開銷下,完成資料挖掘。
并且,該功能可以鼓勵有意義的發言,減少惡意灌水等不良行為。
如果除去關鍵字後發送内容為空判定為符合普通過濾規則,将除抽獎關鍵字外僅發送表情定義為惡意灌水,标記為num = 1,如果該id未出現過,存入map
private void handleMap(String talkContent) {
boolean flag = true;
int num = 0;
if (filterType != 1) {
talkContent = talkContent.replaceAll("#(.*)#", " ");
//talkContent.replaceAll("、", " ");
if (Pattern.matches("\\s*", talkContent)) { // 如果除去關鍵字後發送内容為空-->符合普通過濾規則
flag = false;
/*将除抽獎關鍵字外僅發送表情定義為惡意灌水,标記為num = 1*/
} else if (Pattern.matches("\\s*[\\[表情\\]]+\\s*", talkContent) && filterType == 3) {
//System.out.println(talkContent);
num = 1;
}
}
if (!map.containsKey(userID) && flag) { // 如果該id未出現過
map.put(userID, num); // 存入map
} else if (num > 0) {
num = (int) map.get(userID) + 1;
map.put(userID, num);
}
}
發言為空,剔出抽獎名單,惡意刷屏,降低權重,加入惡意灌水名單,因為文本中聊天樣本資料過少,一次灌水即踢出名單,以下是文本資料大時考慮修改,少量刷屏僅降低權重
if (en.getValue() < 0) { //發言為空,剔出抽獎名單
i++;
continue;
} else if (en.getValue() > 0) { //惡意刷屏,降低權重
weight = en.getValue();
if (weight > 0) {
/*加入惡意灌水名單*/
//因為文本中聊天樣本資料過少,一次灌水即踢出名單
if (!uselessName.contains(en.getKey())) {
uselessName.add(en.getKey());
x[i] = -1;
continue;
}
//以下是文本資料大時考慮修改,少量刷屏僅降低權重
if (weight > 30) {
weight = 30;
}
}
x[i] = (int) (x[i] * ((double)(30 - weight) / 30.0));
}
此處僅僅對該功能進行測試,由于樣本資料不足,設定的門檻值也較小,将黑名單的内容輸出到檔案中可以顯示如下内容:
我們将該系統實作在雲端虛拟化裝置上。使用者可以在不同裝置上調用該功能,便于産品的推廣使用和推廣。而且,人們常常忽略的是本地伺服器的安全問題。本地伺服器通常資源較少,安全機制不完善,一旦受到DDos攻擊,功能将癱瘓。而在雲端,有營運商提供良好的安全服務體系,大大提高安全性,保證系統能夠正常運作。
我們做了以下部署工作:
- 将雲端環境鏡像與本地環境比對正确
- 雲端資料庫進行同步
- 将項目檔案壓縮成wra形式傳至雲端
以上工作均正常操作完成
仍存在以下不足
浏覽器無法正常編譯jsp中嵌入的java代碼,導緻和資料庫互動無法實作,頁面之間跳轉出現bug。
雲端連結(仍在優化中):http://119.29.249.194/index.jsp
目前情況:
本功能利用了Sketch對抽獎資料進行挖掘,可以保持在高速條件下對海量資料的快速處理,節省空間資源。
現抽獎的活動越多,參與抽獎的人數也越來越多。例如:王思聰抽獎微網誌的轉發量、評論數、點贊數均達到了兩千萬,總數達到了六千萬,對每個抽獎賬号還需要維護巨大的資料量。當需要對該資料進行處理挖掘的時候,巨大的資料量将消耗巨大的空間和計算資源。然而,我們有時候隻需要部分的資料資訊,例如:想了解每個地區使用者的發言數,我們并不需要記下每一個用的發言數量,并将它們累加起來,在允許的誤差範圍内,隻需要了解這個數量的近似值即可。對此,我們的算法基于Sketch的算法,将巨大的資料散列到Skecth内,在有限的空間内完成巨大的資料計算,減少資源開銷。
sketch 是一種基于散列的資料結構,可以對海量資料,實時地存儲資料特征資訊,隻占用較小的空間資源,并且具備在理論上可證明的估計精度與記憶體的平衡特性。
Sketch的原理
sketch是基于散列的資料結構,通過設定散列函數,将具有相同散列值的鍵值資料存入相同的桶内,以減少空間開銷。桶内的資料值作為測量結果,是真實值的近似。利用開辟二維位址空間,多重散列等技術減少散列沖突,提高測量結果的準确度。Count-Min 是一種典型的 sketch ,在 2004 年被提出。
實際上 Count-Min sketch 用到的是分類的思想:将具有相同哈希值的key歸為一類,并使用同一個計數器計數。
當資料到來時,逐個記錄所有資料的資訊,會帶來巨大的計算和空間資源開銷。而我們的功能往往也無需記錄所有的資訊。
基于CM-Sketch實作
Count-Min sketch由多個哈希函數(f1……fn)和一張二維表組成。二維表的每個存儲空間維護了一個計數器,其中每個哈希函數分别對應表中的每一行。當資料到來時,需要經過每個哈希函數 f1……fn 的處理,根據處理得到的哈希值分别存入每一行對應哈希值的計數器。有幾個哈希函數,就要計算幾次。算完後,取這m個計數器中的最小值,作為計算的最終值。
設計考量
測量值偏大:使用哈希的方法會産生沖突,多個資料哈希到同一個桶内,那麼這個桶的計數值就會偏大。
- 為什麼允許有誤差:在大量資料條件下,若把所有資訊都準确地記錄下來,要消耗大量計算和空間開銷,無法滿足實時性;而且在很多情況下,并不需要非常精确的資料,在一定程度上可靠的估計值,便足以滿足需求。
- 為什麼要設定多個哈希函數:如果隻設定一個哈希函數,多個流資料存入同一個桶,誤差就會很大。通過設計多個哈希函數,減少哈希值的沖突,以減少誤差。每個流都要經過所有哈希函數的處理,存入不同的計數器中。計數器的最小值雖然還是大于等于真實值,但最接近真實值。這也是 “ Count-Min ”的由來。
- 哈希函數個數:哈希函數越多,沖突越少,測量值越精确,但計算開銷大。需要權衡測量精度和準确度,來設定合适的哈希函數個數。
- 使用Sketch的方法,對資料進行處理,對文本資料進行處理後,設定好參數,使用多個散列函數對資料進行處理,将資料的出現次數存入桶内。以此我們的算法基于Sketch的算法,将巨大的資料散列到Skecth内,在有限的空間内完成巨大的資料計算,減少資源開銷。
- 将CM-Sketch實作在抽獎系統當中,可以通過調整輸入的兩個參數值對空間資源和計算準确度進行近似:
- eps (for error), 0.01 < eps < 1
- gamma (probability for accuracy), 0 < gamma < 1
通過輸入eps和gamma值,可以根據自己的系統環境調整資源開銷。由于估計該測試環境的資源開銷大小,需要具備良好的數學知識,并且對個方面資料進行評估計算。我們将空間開銷抽象封裝成錯誤估計值和精确度。隻需要對自己的需求估計,确定該參數值,就可以滿足對空間開銷的确定。
- 完成了某個處理場景,對抽獎文本進行處理,得出每個使用者的發言次數。
以下是處理抽獎資料的類的定義:
public class CountMinSketch {
private static final long LONG_PRIME = 4294967311l;
private int width;
private int depth;
/**
* eps(for error), 0.01 < eps < 1 the smaller the berrer
*/
private double eps;
/**
* gammga(probability for accuracy), 0 < gamma < 1 the bigger the better
*/
private double gamma;
/**
* used in generation of hash funtion
*/
private int aj;
private int bj;
private int total;
/**
* array of arrays of counters
*/
//private HashMap<String, Integer> C = new HashMap<>();
private int[][] C;
private int[][] C2;
/**
* array of hash values for particular item contians two element arrays {aj,
* bj}
*/
private int[][] hashes;
public CountMinSketch(double eps, double gamma) {
this.eps = eps;
this.gamma = gamma;
width = (int) Math.ceil(Math.exp(1.00) / eps);
depth = (int) Math.ceil(Math.log(1.00 / gamma));
total = 0;
C = new int[depth][width];
C2 = new int[depth][width];
initHashes();
}
其中,以下部分完成了調整兩個參數值對空間資源和計算準确度的權衡:
/**
* eps(for error), 0.01 < eps < 1 the smaller the berrer
*/
private double eps;
/**
* gammga(probability for accuracy), 0 < gamma < 1 the bigger the better
*/
private double gamma;
width = (int) Math.ceil(Math.exp(1.00) / eps);
depth = (int) Math.ceil(Math.log(1.00 / gamma));
以上是算法得出的效果截圖,兩張圖的結果幾乎相同,少數資料略有不同,完成的功能的實作,達到預期效果,驗證了該近似算法。
困難:
- 分工沒有分很合理;
- 分好工的準備的不夠充分;
- 和隊友交流不夠密切及時,導緻他們誤入歧途寫了很久效率卻還很低;
- JavaWeb不熟悉,差不多全忘了...重頭再寫很艱難;
- web界面細節布局還是處理的不夠好,是以界面還挺醜;
- 其他作業、考試實在太多,忙不過來;
- 軟工這麼多項目,已經占用了太多太多其他學科的時間了;
解決辦法
- 下次盡力在開始的時候明确合理分工;
- 争取高效率、及時的和隊友交流(這次是因為下午有實驗,隊友直接就默默地開始打);
- 重頭寫也不難,不就是通個宵嗎?
- 盡量把軟工規定在每天什麼時間做吧,不能再占用過多其他的時間了。大學不僅僅隻有軟工實踐;
- 考試優先,考後熬夜;
困難:alpha還在單機階段課堂實戰已經進入web,時間配置設定不均,分工出現混亂,作為後端負責人沒有檢查環境軟體版本甚至不少人沒有某某軟體,導緻不熟悉。
解決辦法:冷靜冷靜冷靜,盡量不焦慮,事情一件一件來(嗯,體會到了瀕臨死亡的感覺)
困難:時間太短,對代碼要求很高,不允許疊代修改bug。算法全新,需要構思。附加題構思。
解決辦法:考慮到前一段學習的djb2散列函數,修改使用LCG線性同餘法,解決随機數的問題。考慮在實際場景下,微網誌轉發數量太大,要進行資料挖掘等工作,需要耗費很大計算和空間資源,故使用LCG和Sketch解決。
困難:随機數生成算法需要從網上查閱很多相關資料,需要同後端使用相同的類和傳參方式
1.編碼方面,在其他人面前,真的是有點過于弱。
2.前端方面,淺顯的還能寫出來,深度一點的就會一直出bug。
3.擅長的東西過于單一,了解的知識也是過于膚淺,個人能力有待提升。
解決辦法:
1.看教程,一步步來。
2.看隊友操作,積累經驗。
解決辦法:在網上查找代碼,并同其他同學交流,制定相同的傳參規則
困難:前端界面太不友好,不了解代碼,修改起來有難度。與後端交接時,傳回值有待商榷。
解決辦法:檢視網上代碼,下載下傳模闆進行修改。
- 不會寫java,要現學
- 不會寫html和css,要現學
- 隻能盡量學。
- 對于javaweb的0知識量,導緻的無從下手
- 動态html頁面的實作
- 頁面之間跳轉之後,怎麼做到向新頁面傳遞資訊
- 用servlrt實作一個動态頁面的out,頁面的資料資料從伺服器的資料庫中導出
- 用到中的action觸發servlet,在form中使用type=hidden,作為一個隐藏域,傳遞它的value給servlet
- 有函數可以直接實作,伺服器内部的頁面跳轉
困難:對于抽獎應該如何實作沒有頭緒
解決辦法:求助了組内的周政演和黃鴻傑同學
- 關于線性同餘法的了解很粗淺
- 關于JAVA的String和DATE之間的轉換
- 網絡上基本上都是僞代碼,在轉化成JAVA代碼過程中各種參數不知道怎麼設定
- 稍微熟悉了JAVA代碼的書寫
- 修改網絡部落格上的轉換執行個體符合項目的需求
- 找部落格看原理,茫茫大海裡面找到了有JAVA示例的代碼修改
困難:對于web很麼有經驗,對于排版,真的難為我這個男生
解決辦法:找了一個婚慶的模闆套了一下,改了些字和圖
由于本次現場程式設計開發進度低于預期,給每位同學一個一句話吐槽機會,格式為:如果……,那麼……
如果能睡一個好覺,那麼我會補一個月的覺
如果我有好好學搜尋引擎或者好好看前端,那麼這次作業大家做起來都會快很多
如果時間長一點,那麼我還有很多idea可以實作呢
如果我能力強一些,那麼我的團隊就可以更快更完美的完成這項項目。
如果給定時間長一點或者不在考試之前釋出這麼複雜的問題,那麼大家能更輕松愉快地完成這項任務。
如果能拿到相關教程,學習一段時間,那麼我們就不會感覺很慌張
如果能重來,那麼我一定要在課前學習,課上裝逼。
如果能重來一次,那麼我可能會選擇做自閉軟體或者直接自閉吧
如果我再強一些,那麼我的團隊就可以更開心的完成
如果能重來一次,,那麼大家能更輕松愉快地完成這項任務。
如果我再強一些,那麼我們就不會感覺很慌張
隊員名 | 貢獻度 |
---|---|
胡緒佩 | 15% |
周政演 | 11.5% |
黃鴻傑 | 8% |
葛家燦 | 9% |
何宇恒 | 4% |
胡青元 | |
劉一好 | |
劉恺琳 | |
翟丹丹 | 6% |
何家偉 | 12% |
PSP2.1 | header 2 | 預估耗時(分鐘) | 實際耗時(分鐘) |
---|---|---|---|
Planning | 計劃 | 40 | 30 |
· Estimate | ·估計這個任務需要多少時間 | 20 | |
Development | 開發 | 150 | 240 |
· Analysis | 需求分析(包括學習新技術) | 10 | 120 |
· Design Spec | · 生成設計文檔 | ||
· Design Review | · 設計複審 | ||
· Coding Standard | · 代碼規範 (為目前的開發制定合适的規範) | ||
· Design | · 具體設計 | 180 | |
· Coding | · 具體編碼 | 600 | |
· Code Review | · 代碼複審 | ||
· Test | ·測試(自我測試,修改代碼,送出修改) | 100 | |
Reporting | 報告 | ||
· Test Repor | · 測試報告 | ||
· Size Measurement | · 計算工作量 | ||
· Postmortem & Process Improvement Plan | · 事後總結, 并提出過程改進計劃 | ||
合計 | 680 | 1410 |
第N周 | 新增代碼(行) | 累計代碼(行) | 本周學習耗時(小時) | 累計學習耗時(小時) | 重要成長 |
---|---|---|---|---|---|
1 | 391 | 25 | 複習c++,學習單元測試和代碼覆寫率,更熟悉Visual Studio的使用 | ||
2 | 491 | 5 | 在優化代碼和改bug | ||
3 | 15 | 45 | 閱讀《建構之法》第三章和第八章,學習使用Axure RP8,對UI設計有進一步了解和認識,對項目開發架構進一步的了解 | ||
4 | 441 | 932 | 70 | 對爬蟲初步認識,還有待學習(隊友負責子產品),Debug能力++; | |
85 | 詳細了解需求規格說明書以及接口文檔書寫 | ||||
6 | 232 | 1164 | 105 | 學習基礎前端界面布局及學習思維導圖制作 | |
7 | 597 | 1761 | 125 | 學習前端互動,查資料能力++,對前端認識越來越深,恐懼越來越大,懂得做一個項目的艱難! |