Java的Map與Set在找尋Distinct與反向Map的分享

處理大量資料時,尤其採用Lucene作為資料索引架構,沒有SQL這類高階查詢查詢語言的DISTINCT(找出獨一無二的值),要找出Unique就需透過程式階層的實作。

通常找獨一無二值在Text Mining會被用來找尋語詞的集合,而在Data Mining,更可用來找尋屬性的有限集合(Finite State),對於離散型的資料,若能找出有限集合,可降低問題的複雜性,也可節省需多不必要的運算。

在我處理的問題上,遇到了兩種不同的資料類型,並且需要找出他們的有限集合,這兩種屬性為網路位置與斷詞後的文字,我想要找出在這幾千萬筆的資料當中,到底有多少個Unique IP以及多少個詞(Term)。

這其實很簡單,用一個HashSet,用一個回圈,透過Lucene飛快地掃過幾千萬筆資料,把每個IP或是Term丟到這個HashSet裡面,即可。

但因為需要後續進行資料分析的需求,我必須對於這些Unique Term進行索引與反向索引,例如:現在有以下幾個Unique Terms:你、我、他,所以可以對這些uniuqe詞進行編號,並且希望能夠過這些詞能反查到這些編號,因此HashMap就非常符合這樣的需求。

HashMap<String,Integer> termSet = new HashMap<String,Integer>();

for(…….){

if(termSet.get(“xxx")==null){

termSet.put(“xxx",count);

count++;

}

}

其實上述這樣的寫法是先比對要放進去的資料是否已經存在,若不存在再把這筆資料放入Map。以前我都這樣做,其實感覺程式碼也很精簡,跑起來也不感覺慢,今天跑上千萬筆資料,頓時發現越跑越慢,最後慢到一種極致,仔細想想,當HashMap長得越大的時候,要比對的次數就越多,時間複雜度較高,HashMap在這種寫法下,就失去Hash比對的效率性了(瓶頸會在if)。

所以這篇的重點是:我們先用HashSet找出Finite Set,然後在依序放入HashMap中,短短一個非常簡單的想法,節省了許多時間。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s