目錄

1. 引言

1.1 實(shí)驗(yàn)?zāi)康?/p>

1.2 實(shí)驗(yàn)內(nèi)容

1.3 實(shí)驗(yàn)要求

2. 實(shí)驗(yàn)運(yùn)行環(huán)境

2.1 硬件環(huán)境

2.2 軟件環(huán)境

3. 程序設(shè)計(jì)說(shuō)明

3.1 功能概述

3.2 程序目錄結(jié)構(gòu)的介紹

4 界面操作說(shuō)明

4.1 鼠標(biāo)輸入點(diǎn)的界面操作

4.2 隨機(jī)生成點(diǎn)的界面操作

5 實(shí)驗(yàn)結(jié)果及相關(guān)結(jié)論

6 程序使用的一些技巧和優(yōu)點(diǎn)

6.1 使用的一些技巧

6.2 程序的優(yōu)點(diǎn)

1. 引言

1.1 實(shí)驗(yàn)?zāi)康?/p>

通過(guò)使用普通方法和分治法對(duì)求平面上最近兩點(diǎn)，比較在不同輸入規(guī)模情況下Θ(n^2)和Θ(nlgn)算法的實(shí)際運(yùn)行時(shí)間，加強(qiáng)對(duì)分治法的理解與掌握。

1.2 實(shí)驗(yàn)內(nèi)容

實(shí)現(xiàn)求平面上最近點(diǎn)對(duì)的復(fù)雜度為Θ(nlgn) 的算法

A. 有圖形界面，能夠通過(guò)鼠標(biāo)輸入點(diǎn)，并標(biāo)識(shí)出最近點(diǎn)對(duì);

B. 能夠隨機(jī)生成大量平面點(diǎn)(要求可達(dá)到一百萬(wàn)個(gè)點(diǎn))，并輸出最近點(diǎn)對(duì)。

1.3 實(shí)驗(yàn)要求

要求交源碼，可執(zhí)行程序，實(shí)驗(yàn)報(bào)告。

2. 實(shí)驗(yàn)運(yùn)行環(huán)境

2.1 硬件環(huán)境

CPU: 2.5 GHz Intel Core i7

內(nèi)存:16.0GB

2.2 軟件環(huán)境

操作系統(tǒng):mac OS10.12?

語(yǔ)言及編譯平臺(tái):Java【jdk1.8】，Eclipse

?

3. 程序設(shè)計(jì)說(shuō)明

3.1 功能概述

在主界面中，存在兩個(gè) Tab 控件，其中在“隨 機(jī)產(chǎn)生點(diǎn)”控件中，用戶可以輸入 2～1000000 之間的一個(gè)整數(shù)，來(lái)表示隨機(jī)產(chǎn)生的平面點(diǎn)數(shù)；在“鼠標(biāo)生成點(diǎn)”Tab控件中， 用戶能夠通過(guò)鼠標(biāo)點(diǎn)擊輸入點(diǎn)，通過(guò)計(jì)算后，使用紅色標(biāo)識(shí)出最近點(diǎn)對(duì)。

3.2 程序目錄結(jié)構(gòu)的介紹

在這次程序編寫過(guò)程中，在mac 系統(tǒng)下采用了 Eclipse IDE 環(huán)境，求平面上點(diǎn)程序的目錄截圖如下:

A、其中mainScreen.java 是程序的主界面類，該界面手工編寫，提高代碼的可讀性;該類生成了主界面，獲取用戶在前臺(tái)界面的輸入，后臺(tái)獲取到數(shù)據(jù)進(jìn)行計(jì)算，然后返回，在界面中響應(yīng)給用戶，該類起到前后臺(tái)交互的作用;

B、CalProcess.java是程序的后臺(tái)實(shí)現(xiàn)類，該類實(shí)現(xiàn)了接受前臺(tái)傳入的參數(shù)， 使用普通方法和分治法計(jì)算平面最近點(diǎn)對(duì)的算法，然后將結(jié)果作為參數(shù)返回給前臺(tái);

C、pointsPanel.java是鼠標(biāo)輸入面板的實(shí)現(xiàn)類，該類接收鼠標(biāo)在該面板上的點(diǎn)擊事件，獲取點(diǎn)擊的坐標(biāo)位置，畫出點(diǎn)，并將點(diǎn)存至點(diǎn)集合中，同時(shí)存儲(chǔ)坐標(biāo)位置以便后來(lái)的計(jì)算。

D、pointsProperty.java是隨機(jī)生成點(diǎn)的vo類，定義橫縱坐標(biāo)，并生成get和set方法。

E、RandomPoints.java是隨機(jī)生成點(diǎn)的方法，并調(diào)用后臺(tái)的兩種方法，同時(shí)計(jì)算對(duì)應(yīng)方法使用的時(shí)間。

3.3 程序?qū)崿F(xiàn)方案

3.3.1 一般方法Θ(n2)的實(shí)現(xiàn)方案

普通方法：通過(guò)對(duì)所有的n個(gè)點(diǎn)進(jìn)行兩兩匹配，算出兩點(diǎn)之間距離的平方，然后進(jìn)行比較來(lái)得到最短距離和最近點(diǎn)對(duì)。

3.3.2 分治法 Θ(nlgn)的實(shí)現(xiàn)方案:

分治法：

1.求出x的中位數(shù)，按照中位數(shù)，將點(diǎn)集合分成左右兩個(gè)點(diǎn)集合。在左右集合中遞歸調(diào)用divided()方法，求出左右集合最近點(diǎn)對(duì)的距離，并得到最小值d。

2. 左右兩側(cè)收集距離中線小于d的點(diǎn)，分別存放于兩個(gè)數(shù)組中。再將小于d的點(diǎn)的2個(gè)集合轉(zhuǎn)化為數(shù)組類型，按y升序排序。再在距離中線最近的左右兩個(gè)數(shù)組，求解更近的點(diǎn)。再利用分治法對(duì)點(diǎn)集合中的點(diǎn)x／y進(jìn)行升序排序。最后合并排序結(jié)果。

3.3.3 總體實(shí)現(xiàn)方案:

1、在鼠標(biāo)輸入 Tab 面板中，創(chuàng)建完面板后，接收用戶的鼠標(biāo)點(diǎn)擊事件，獲取到點(diǎn)擊的坐標(biāo)，存儲(chǔ)這些坐標(biāo)點(diǎn)，同時(shí)進(jìn)行界面的重繪來(lái)完成畫點(diǎn)操作，實(shí)現(xiàn)的部分代碼如下:

當(dāng)用戶點(diǎn)擊“計(jì)算”按鈕之后，將所有獲取到的點(diǎn)坐標(biāo)的序列作為參數(shù)傳送到后臺(tái)進(jìn)行計(jì)算，然后根據(jù)計(jì)算結(jié)果修改面板(將最近點(diǎn)對(duì)標(biāo)識(shí)為紅色)。下圖為點(diǎn)擊計(jì)算按鈕后，調(diào)用普通和分治法的操作：

下圖為點(diǎn)擊重置按鈕執(zhí)行的操作：

2、在隨機(jī)生成點(diǎn)面板中，創(chuàng)建完面板后，用戶輸入一個(gè) 2～1000000的一個(gè)整數(shù)(其他輸入為非法輸入，將提示用戶重新輸入)，點(diǎn)擊“開始計(jì)算”按鈕之后，將獲取到的用戶輸入數(shù)值作為參數(shù)傳送到后臺(tái)，之后進(jìn)行計(jì)算，根據(jù)計(jì)算結(jié)果修改面板(將最近點(diǎn)對(duì)標(biāo)識(shí)為紅色)。如果用戶輸入的整數(shù)大于100000，將只使用分治法進(jìn)行計(jì)算，因?yàn)槭褂闷胀ǚ椒ㄋǖ臅r(shí)間太長(zhǎng)了。 其實(shí)現(xiàn)的部分代碼如下:

4 界面操作說(shuō)明

4.1 鼠標(biāo)輸入點(diǎn)的界面操作:

A、運(yùn)行程序后得到如下界面:

B、通過(guò)鼠標(biāo)點(diǎn)擊藍(lán)色眶內(nèi)畫點(diǎn)，可以得到如下界面:

C、點(diǎn)擊“計(jì)算”按鈕之后，將用紅色標(biāo)識(shí)出最近點(diǎn)對(duì)，如下圖:?

4.2 隨機(jī)生成點(diǎn)的界面操作:

A、剛開始該 Tab 控件面板的界面如下:

B、輸入一個(gè)整數(shù)，出現(xiàn)如下界面:

點(diǎn)擊“計(jì)算”按鈕，將出現(xiàn)下面的界面:

C、如果輸入的整數(shù)大于 100000，比如說(shuō)500000，點(diǎn)擊“計(jì)算”按鈕之后，將出現(xiàn)如下界面:

D、如果輸入的整數(shù)大于 100000，比如說(shuō) 1000000，計(jì)算結(jié)果如下:

5 實(shí)驗(yàn)結(jié)果及相關(guān)結(jié)論

? 通過(guò)在運(yùn)行程序時(shí)，輸入結(jié)果所等待時(shí)間的長(zhǎng)短，可以很明顯看出:在求解最近平面點(diǎn)對(duì)時(shí)，分治算法的性能明顯優(yōu)于普通算法，特別是當(dāng)輸入的整數(shù)越大，性能差別會(huì)越明顯。針對(duì)不同的輸入規(guī)模，一般法和分治法所花的時(shí)間對(duì)比如下表格和折線圖展示:

生成的平面點(diǎn)數(shù)目一般法求解所花時(shí)間(單位為: 毫秒)分治法求解所花時(shí)間(單位為: 毫秒)

2 ? ? ? ? ? ? ? ? ? ? 0????????????????????????????????????????0

100 ? ? ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1

1000 ? ? ? ? ? ? ? 3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 14

10000 ? ? ? ? ? ? 141 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 11

100000 ? ? ? ? ?9334? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?144

500000 ? ? ? ? ?太慢????????????????????????????????984

1000000????????幾小時(shí)甚至算不出來(lái) ? ? 4683

從表格和折線圖中可以看出，輸入規(guī)模不斷增大，一般法求解的所花時(shí)間也不斷變長(zhǎng)，當(dāng)輸入為 100000 時(shí)，所花的時(shí)間已經(jīng)超過(guò)10秒了，當(dāng)輸入為 500000 時(shí)，所花的時(shí)間已經(jīng)算得很慢了，所以對(duì)于輸入為 1000000 時(shí)，該方法甚至?xí)ㄙM(fèi)幾個(gè)小時(shí)才能算出來(lái);而輸入為 20000000 時(shí)， 則幾乎不可能算出來(lái)了。對(duì)于分治法，基本上也是隨著輸入規(guī)模的增大，所花費(fèi)的時(shí)間也不斷增多。

綜上所述，Θ(n2)的普通算法和Θ(nlgn)的分治法隨著輸入規(guī)模 n 的增大， 兩者的運(yùn)行時(shí)間差別也越來(lái)越大。因此，在平時(shí)的編程時(shí)，特別是面對(duì)大數(shù)據(jù)輸入之類的編程時(shí)，我們應(yīng)該努力優(yōu)化自己的算法，這樣才能夠有效的提高自己的程序運(yùn)行效率。

6 程序使用的一些技巧和優(yōu)點(diǎn)

6.1 使用的一些技巧

(1)由于實(shí)驗(yàn)要求能夠處理 1000000 個(gè)點(diǎn)，所以隨機(jī)生成點(diǎn)的坐標(biāo)只設(shè)置 從-1000000～+1000000，這樣能夠減少計(jì)算兩個(gè)點(diǎn)距離的時(shí)間;

(2)在比較最近點(diǎn)對(duì)時(shí)，只計(jì)算了兩點(diǎn)之間距離的平方，而沒有進(jìn)行開方操作，這樣也可以減少很多操作;

(3)在使用分治法求解，遞歸回溯的過(guò)程中，計(jì)算d*2d的矩形中所有點(diǎn)的最近點(diǎn)對(duì)時(shí)，每個(gè)點(diǎn)需要進(jìn)行 7 次比較，本程序?qū)ξ挥谕粋?cè)的點(diǎn)對(duì)沒有進(jìn)行求解兩點(diǎn)間距離平方的操作而是直接跳過(guò)，這樣也可以節(jié)省不少時(shí)間。

6.2 程序的優(yōu)點(diǎn)

(1)界面代碼純手工進(jìn)行編寫，可讀性非常高;而且也具有一定的可交互性;

(2)排序時(shí)，沒有使用 java 中 ArrayList 本身的排序算法，而是自己寫了歸并排序的算法，這樣排序的速度會(huì)更快點(diǎn);

(4)雖然使用 Java 進(jìn)行編寫，但是程序的運(yùn)行速度還是比較快的，輸入為 1000000 個(gè)點(diǎn)時(shí)，只花費(fèi)了 4 秒多即可算出結(jié)果。