整數(shù)坐標(biāo)排序.doc

整數(shù)坐標(biāo)排序1、線性排序算法原理32位整數(shù)排序算法的原型是基于不等式K+1KK-1的，該式子對(duì)于任何K值都成立。那么如果有一個(gè)坐標(biāo)，長(zhǎng)度為Kn，每個(gè)Kx都可以映射到這個(gè)坐標(biāo)軸的相應(yīng)點(diǎn)上。這樣一來(lái)，就可以得到一系列自然次序排列的點(diǎn)?，F(xiàn)在針對(duì)具體的例子來(lái)看看這個(gè)算法的具體內(nèi)容，假設(shè)有一個(gè)數(shù)例：9, 6, 3 與 7。取第一個(gè)數(shù)（9），將它從坐標(biāo)軸原點(diǎn)開(kāi)始向右移動(dòng)9個(gè)普通單元并標(biāo)記這個(gè)點(diǎn)。然后，取下一個(gè)數(shù)（6）并重復(fù)操作等。這些操作的結(jié)果如圖1所示?，F(xiàn)在，從左向右沿坐標(biāo)線移動(dòng)， 并將沒(méi)有標(biāo)記的所有點(diǎn)都丟棄掉（或者突出顯示經(jīng)過(guò)標(biāo)記的點(diǎn)）。于是，得到一系列按升序排列的數(shù)。如果從右往左沿坐標(biāo)線移動(dòng)，那么將得到一系列按降序排列的數(shù)。這里有一點(diǎn)最令人感興趣：不管數(shù)是如何給定的，對(duì)它們進(jìn)行排序所需要的操作次數(shù)將總是等于N+VAL_N，其中N是待排序的數(shù)據(jù)個(gè)數(shù)，而VAL_N是數(shù)據(jù)可能取值的最大個(gè)數(shù)。由于VAL_N是個(gè)常數(shù)，因此可以將它從估算算法復(fù)雜性公式中去掉。之后，這個(gè)公式就變成為O(N)了?？赡茏x者已經(jīng)注意到這種排序算法的弱點(diǎn)了。性能增益是以犧牲內(nèi)存為代價(jià)的。線性排序算法在內(nèi)存消耗方面的開(kāi)銷很大。下面是關(guān)的一些估算值。如表1所示：雖然存在這樣的弱點(diǎn)，但是卻仍然蓋不住它的優(yōu)點(diǎn)，在算法分析和設(shè)計(jì)中，人們通?？偸菍⒆羁斓乃惴ㄅc最有效的算法等同起來(lái)，這是因?yàn)闀r(shí)間需求常常是決定算法在實(shí)際中是否真正有效的決定性因素。用它跟快速排序算法比較，線性排序算法時(shí)間復(fù)雜度為O(n)，而快速排序算法平均需要O(nlgn)次操作，并且在最壞的情況下需要O(m2)次操作。針對(duì)上面線性排序算法的弱點(diǎn)，如果要排序的數(shù)數(shù)值范圍在0 到 2147483647，那么至少需要8GB的內(nèi)存，需要的內(nèi)存在現(xiàn)實(shí)中將是不可能提供的；并且也不能排序正數(shù)跟負(fù)數(shù)相混合的情況，我們必須對(duì)這個(gè)算法加以改進(jìn)，以滿足現(xiàn)實(shí)應(yīng)用中的需求。2、改進(jìn)后的線性排序算法2.1 改進(jìn)思想：在日常應(yīng)用程序中，整數(shù)最常用的數(shù)值一般都處在百萬(wàn)以內(nèi)，而構(gòu)造一百萬(wàn)個(gè)坐標(biāo)點(diǎn)的坐標(biāo)，需要大約4M的內(nèi)存，這在現(xiàn)在的計(jì)算機(jī)內(nèi)存配置上完全是可行的。于是我們專門針對(duì)這種特點(diǎn)對(duì)原型改造，將4字節(jié)的32位整數(shù)按位分類排序（4字節(jié)的整數(shù)有32位），把32位分成兩段，前12位為一段，后20位為第二段，用十六進(jìn)制來(lái)表示，既0XFFF00000（高12位）和0X000FFFFF（低20位）。分段以后我們?cè)谟吧涮幵?到1048576的整數(shù)時(shí)，就可以按原型的方法直接影射在1048576個(gè)坐標(biāo)點(diǎn)的坐標(biāo)上，對(duì)大于1048576的值，我們會(huì)繼續(xù)對(duì)它的低20位分段排序，這種處理方式極好地保證了最常用的整數(shù)值的排序效率。2.2影射坐標(biāo)定義：一個(gè)32位的整數(shù)，它能表示值的區(qū)間為 -2147483648 到 2147483647，按照改進(jìn)思相，我們把這個(gè)區(qū)間分為三段：1)0XFFF00000 到 0XFFFFFFFF 區(qū)間，代表的值為期 -1048576 到 -1，它們的高十二位值都是相同的，為 0XFFF，在排序的時(shí)候我們把它們歸為一類，可以影射到代表負(fù)數(shù)的 1048576 個(gè)坐標(biāo)點(diǎn)的坐標(biāo)上，我們把這個(gè)坐標(biāo)設(shè)為 a 坐標(biāo)2)0X00000000 到 0X000FFFFF 區(qū)間，代表的值為 0 到 1048576，它們的高十二位值也是相同的，為 0X000,也把它們歸為一類，可以影射到代表正數(shù)的 1048576 個(gè)坐標(biāo)點(diǎn)的坐標(biāo)上，我們把這個(gè)坐標(biāo)設(shè)為 b 坐標(biāo)3)剩余的兩個(gè)區(qū)間為 0X80000000 到 0XFFEFFFFF 區(qū)間和 0X001FFFFF 到 0x7FFFFFFF 區(qū)間，它們分別表示的范圍是 -2147483648到 -1048577 和1048577 到2147483647, 處在這個(gè)區(qū)間的值，我們先它們按各自的前 12 位的值影射到 4096 個(gè)坐標(biāo)點(diǎn)的坐標(biāo)上（0XFFF 轉(zhuǎn)為十進(jìn)制為 4096），我們把這個(gè)坐標(biāo)設(shè)為 c 坐標(biāo)4)對(duì)于處在0X80000000 到 0XFFEFFFFF 區(qū)間和 0X001FFFFF 到 0x7FFFFFFF 區(qū)間的情況，我們將把它們按高 12 位分類以后，不能立即分析出其大小的（一個(gè)坐標(biāo)點(diǎn)上影射有兩個(gè)以上的整數(shù)），再對(duì)其低 20 位分段，進(jìn)行第二次影射。第一段為低20位的前12位，坐標(biāo)點(diǎn)數(shù)為4096個(gè)，我們把這個(gè)坐標(biāo)設(shè)為 d 坐標(biāo)5)對(duì)處在0X80000000 到 0XFFEFFFFF 區(qū)間和 0X001FFFFF 到 0x7FFFFFFF 區(qū)間的情況，經(jīng)過(guò)第二次影射以后還不能立即區(qū)分大小的，再對(duì)它們的低20位的低8位進(jìn)行影射到256個(gè)坐標(biāo)點(diǎn)的坐標(biāo)上，我們把這個(gè)坐標(biāo)設(shè)為 e 坐標(biāo)由上面可以看出，我們總共定義了5個(gè)坐標(biāo)，a，b，c三個(gè)用來(lái)影射不同區(qū)間的整數(shù)，分別是0XFFF00000 到 0XFFFFFFFF(a坐標(biāo))、0X00000000 到 0X000FFFFF(b坐標(biāo))、0X80000000 到 0XFFEFFFFF 和 0X001FFFFF 到 0x7FFFFFFF(c坐標(biāo))；d，e這兩個(gè)是用來(lái)幫助分類c坐標(biāo)上的整數(shù)2.3影射算法流程：a)掃描整個(gè)要排序的整數(shù)，依次取出一個(gè)整數(shù) xb)執(zhí)行與操作 y = x & 0XFFF00000，再執(zhí)行移位操作，把 y 向右移 20 位, y = y20，便獲得這個(gè)整數(shù)的高 12 值c)判斷得到的 y 是否為 0， 如果是，則影射 x 到 b 坐標(biāo)上，如果不是，則再判斷 y 值是否為 0xFFF，如果是，則影射 x 到 a 坐標(biāo)上，否則影再判斷 y 值是否大于2048， 如果是則表示 x 為0X80000000 到 0XFFEFFFFF 區(qū)間的負(fù)數(shù)，把 y 減去 2048 后影射到 c 坐標(biāo)上，否則表示 x 為0X001FFFFF 到 0x7FFFFFFF 區(qū)間正數(shù)，把 y 加上 2048后影射到 c 坐標(biāo)上。影射以后把該坐標(biāo)點(diǎn)上的統(tǒng)計(jì)該坐標(biāo)點(diǎn)擁有整數(shù)個(gè)數(shù)的變量加一d)所有待排序整數(shù)影射完成，所有區(qū)間的整數(shù)就會(huì)分類存放在坐標(biāo)a，b，c上，然后我們似次遍歷這三個(gè)坐標(biāo)來(lái)輸出它們，在正序排序時(shí)，我們先輸出c坐標(biāo)上0到2047的坐標(biāo)點(diǎn)上的值，因這這段區(qū)間存放的是，2147483648到 -1048577之間的負(fù)整數(shù)e)依次判斷c坐標(biāo)從0到2046坐標(biāo)點(diǎn)上各坐標(biāo)點(diǎn)上整數(shù)的個(gè)數(shù)，如果整數(shù)個(gè)數(shù)小于n(實(shí)驗(yàn)對(duì)比下來(lái)，n取值小于等于200的時(shí)候，用快速排序算法對(duì)該坐標(biāo)上的整數(shù)比再次影射坐標(biāo)排序來(lái)得快)，我們可以使用快速排序法來(lái)排序這個(gè)坐標(biāo)點(diǎn)上的幾個(gè)整數(shù)，否則，我們就再次對(duì)這些整數(shù)進(jìn)行第二次掃描，把它們按整數(shù)的低20位的高12值影射到輔坐標(biāo)d上。執(zhí)行操作：1)依次讀取c坐標(biāo)的i（0i2046）坐標(biāo)點(diǎn)上的整數(shù) x，然后取得其低20位的高12值y（y = x & 0X000FFFFF 8）2)把x按y值射到坐標(biāo)d上，并把統(tǒng)計(jì)該坐標(biāo)點(diǎn)擁有整數(shù)個(gè)數(shù)的變量加一3)當(dāng)i坐標(biāo)點(diǎn)上所有整數(shù)被第二次影射完必以后，我們按從頭到尾的順序掃描坐標(biāo)d，依次判斷各個(gè)坐標(biāo)點(diǎn)上整數(shù)的個(gè)數(shù)，如果整數(shù)各數(shù)小于n(同上)，我們可以使用快速排序法來(lái)排序這個(gè)坐標(biāo)點(diǎn)上的幾個(gè)整數(shù)，否則，我們就再次對(duì)這些整數(shù)進(jìn)行第三次掃描，把它們按整數(shù)的低20位的低8位值影射到輔坐標(biāo)e上。執(zhí)行操作：1.依次讀取d坐標(biāo)的i（0i4095）坐標(biāo)點(diǎn)上的整數(shù) x，然后取得其低20位的低8值y（y = x & 0X000000FF）2.把x按y值射到坐標(biāo)e上（不需要統(tǒng)計(jì)變量，原因見(jiàn)下面第3點(diǎn)）3.當(dāng)i坐標(biāo)點(diǎn)上所有整數(shù)被第三次影射完必以后，我們按從頭到尾的順序掃描坐標(biāo)e，依次輸出各個(gè)坐標(biāo)點(diǎn)上的整數(shù)索引到存放索引的緩沖區(qū)中（如果坐標(biāo)e上某個(gè)坐標(biāo)上存在多個(gè)整數(shù)，那這些整數(shù)的值一定是相等的，不用再排序，因?yàn)樗鼈兊母?2位相同，低20位的高12相同，低20位的低8位相同）f)當(dāng)?shù)竭_(dá)c坐標(biāo)的2047坐標(biāo)點(diǎn)時(shí)，這上面應(yīng)該存放的是-1048576 到 -1這個(gè)區(qū)間的整數(shù)，而這個(gè)區(qū)間的整數(shù)我們用了專門一個(gè)坐標(biāo)a來(lái)存放，于是我們按從頭到尾的順序掃描坐標(biāo)a，依次輸出各個(gè)坐標(biāo)點(diǎn)上的整數(shù)索引到存放索引的緩沖區(qū)中（如果坐標(biāo)a上某個(gè)坐標(biāo)上存在多個(gè)整數(shù)，那這些整數(shù)的值一定是相等的，不用再排序，因?yàn)樗鼈兊母?2位相同，低20位也相同）g)當(dāng)?shù)竭_(dá)c坐標(biāo)的2048坐標(biāo)點(diǎn)時(shí)，這上面應(yīng)該存放的是0到1048576這個(gè)區(qū)間的整數(shù)，而這個(gè)區(qū)間的整數(shù)我們用了專門一個(gè)坐標(biāo)b來(lái)存放，于是我們按從頭到尾的順序掃描坐標(biāo)b，依次輸出各個(gè)坐標(biāo)點(diǎn)上的整數(shù)索引到存放索引的緩沖區(qū)中（如果坐標(biāo)b上某個(gè)坐標(biāo)上存在多個(gè)整數(shù)，那這些整數(shù)的值一定是相等的，不用再排序，因?yàn)樗鼈兊母?2位相同，低20位也相同）h)最后一步我們要掃描坐標(biāo)c的2049到4095這個(gè)區(qū)間，這段區(qū)間存放的是大于1048576的正整數(shù)，掃描輸出的方法跟掃描輸出小于-1048576的負(fù)整數(shù)一樣，這里不再重述i)當(dāng)c坐標(biāo)被整個(gè)遍歷完以后，我們就會(huì)在輸出索引緩沖區(qū)中得到一條整數(shù)從小到大排序好的索引序列2.4影射坐標(biāo)圖例：為了方便理解上面的影射思想，我們?cè)谙旅鎴D解了一下影射六個(gè)整數(shù)高12位到坐標(biāo)c上的情景，整數(shù)是用16進(jìn)制表示圖2 整數(shù)高12位到坐標(biāo)c上的情景注：上圖 c 坐標(biāo)為了影射表示方便，沒(méi)有把整數(shù)高12位的值加2048后再影射到 c 坐標(biāo)上3、多CPU的支持3.1 性能提升空間經(jīng)過(guò)實(shí)際的試驗(yàn)和分析，在改進(jìn)后的算法實(shí)現(xiàn)中，花費(fèi)的時(shí)間主要集中在輸出第一次掃坐后的坐標(biāo) a，b，c 上！因?yàn)槲覀冏鴺?biāo)點(diǎn)上的整數(shù)用的是單向鏈表的形式組織的，分類時(shí)不斷的把整數(shù)的索引描述結(jié)點(diǎn)不斷插入到對(duì)應(yīng)的坐標(biāo)點(diǎn)的鏈表上；因此，在遍歷各個(gè)坐標(biāo)點(diǎn)的鏈表時(shí)將會(huì)對(duì)內(nèi)存進(jìn)行隨機(jī)訪問(wèn)，這就會(huì)造成CPU高速緩存的缺頁(yè)，CPU將會(huì)遭受延時(shí)處罰，嚴(yán)重影響了整數(shù)排序算法的性能，于是就想到了用多個(gè)CPU按坐標(biāo)點(diǎn)順序分段輸出 a，b，c 三個(gè)坐標(biāo)的想法，以便減少單個(gè)CPU被延時(shí)處罰的次數(shù)，達(dá)到算法性能提升的目的。3.2 影射坐標(biāo)定義1)共用坐標(biāo)：共用坐標(biāo)是用來(lái)存放第一次掃描后的整數(shù)分類情況，從第二節(jié)我們可以了解到 a，b，c 這三個(gè)坐標(biāo)就是共用坐標(biāo)2)每個(gè)CPU輔助坐標(biāo)的定義：在第二節(jié)中我們可以了解到，要輸出c坐標(biāo)上的整數(shù)，我們需要用到 d 和 e 坐標(biāo)來(lái)繼續(xù)分類整數(shù)，于是我們需要為每個(gè)CPU定義兩個(gè)輔助坐標(biāo) d 和 e3.2 分段規(guī)則假如要用4個(gè)CPU排序200萬(wàn)個(gè)整數(shù)，那么在理想的情況下，分段后每個(gè)CPU處理的整數(shù)個(gè)數(shù)應(yīng)該為50萬(wàn)個(gè)（200萬(wàn)/4 = 50萬(wàn)），實(shí)際情況中并不能完全保證按這一比一的比例來(lái)分配任務(wù)，因?yàn)槿蝿?wù)分配是按坐標(biāo)點(diǎn)而不是整數(shù)個(gè)數(shù)，我們不可能會(huì)把一個(gè)坐標(biāo)點(diǎn)上的鏈表分段后交給多個(gè)CPU處理。也就是說(shuō)，如果排序的200萬(wàn)個(gè)整數(shù)值都是相等的，那這200萬(wàn)個(gè)整數(shù)將會(huì)存在同一個(gè)坐標(biāo)的同一個(gè)坐標(biāo)點(diǎn)上，那么我們?cè)诜侄螘r(shí)，就把這個(gè)坐標(biāo)點(diǎn)只分給一個(gè)CPU來(lái)輸出（大家不用擔(dān)心這種情況會(huì)影響算法性能，因這鏈表上的各個(gè)節(jié)點(diǎn)處在的內(nèi)存空間是連續(xù)的，而CPU訪問(wèn)連續(xù)的內(nèi)存空間將會(huì)非?？欤７侄畏椒ǎ?)按包含整數(shù)大小的順序把 a，b，c 三個(gè)坐標(biāo)分四類：1. c坐標(biāo)的0-2046區(qū)間（x-1048576）2. a坐標(biāo)（-1048576x0）3. b坐標(biāo)（0x1048576）4. c坐標(biāo)的2049-4095區(qū)間（1048576x）2)定義4個(gè)變量用來(lái)存放分段的信息：unsigned int start_pos, start_type, start_output_pos, end_pos, end_type, end_output_pos；它們分別代表開(kāi)始坐標(biāo)的起始位置，開(kāi)始掃描坐標(biāo)的類型（四類坐標(biāo)區(qū)間的那一類），輸出索引緩沖區(qū)的開(kāi)始位置偏移量，結(jié)束坐標(biāo)的位置，結(jié)束坐標(biāo)的類型，輸出索引緩沖區(qū)的結(jié)束位置偏移量3)計(jì)算每個(gè)CPU理想情況下的終止輸出索引時(shí)在索引輸出緩沖區(qū)中的偏移量(end_output_pos = num/cpu_n + num/cpu_n * i，其中num為整數(shù)的總個(gè)數(shù)，cpu_n為CPU的個(gè)數(shù)，i代表當(dāng)前CPU是第幾個(gè)CPU)，沿用那個(gè)200萬(wàn)個(gè)整數(shù)的例子，按此方法計(jì)算后，第一個(gè)CPU輸出索引終止偏移量為50萬(wàn)，第二個(gè)CPU為 100 萬(wàn)，第三個(gè)為150萬(wàn)，第四個(gè)為200萬(wàn)4)按坐標(biāo)分類的順序，設(shè)置第一個(gè)CPU的起始位置為第1類坐標(biāo)的第0個(gè)坐標(biāo)點(diǎn)，然后依次掃描坐標(biāo)累加每個(gè)坐標(biāo)點(diǎn)上整數(shù)的個(gè)數(shù)，如果累加的個(gè)數(shù)已經(jīng)大于第一個(gè)CPU理想情況下輸出索引的編移量時(shí)，那么，把這一坐標(biāo)設(shè)置為它的終止位置，保存該坐標(biāo)的類型和當(dāng)前坐標(biāo)的位置，并重置它人輸出索引偏移量為累加到的整數(shù)個(gè)數(shù)值5)當(dāng)要設(shè)置第二個(gè)CPU的起始和終止掃描位置時(shí)，它就會(huì)從把第一個(gè)CPU的終止坐標(biāo)的下一個(gè)坐標(biāo)點(diǎn)當(dāng)作自己的起始坐標(biāo)點(diǎn)，坐標(biāo)類型拷貝第一個(gè)CPU終止的坐標(biāo)類型，累加的整數(shù)個(gè)數(shù)初始化為第一個(gè)CPU的輸出索個(gè)編移量；然后按照第一個(gè)CPU的方尋找屬于自己的終止位置6)設(shè)置接下去幾個(gè)CPU的起始和終止掃描位置方法類似第二個(gè)CPU的設(shè)置方法3.2 分段掃描流程a)掃描整個(gè)待排數(shù)的整數(shù)數(shù)組，把它們分類到坐標(biāo) a，c，d 上b)取得當(dāng)前系統(tǒng)CPU的個(gè)數(shù) cpu_n c)創(chuàng)建 cpu_n 1 個(gè)新線程(因?yàn)楫?dāng)前線程也會(huì)參于后面的分段排序，所以只需要?jiǎng)?chuàng)建 cpu_n 1個(gè)新線程)d)當(dāng)前線程在創(chuàng)建完其它線程后，直接從第一個(gè)坐標(biāo)的第0個(gè)坐標(biāo)點(diǎn)開(kāi)始按第二節(jié)的影射算法排序，只是在排序過(guò)程中，當(dāng)要讀取下一個(gè)坐標(biāo)點(diǎn)時(shí)，先要判斷累加處理的整數(shù)各數(shù)是否大于等于它的索引終止偏移量，如果不是，則繼續(xù)處理，否則，在處理完當(dāng)前點(diǎn)以后，就立即停止處理，等待其它線程完成各自己的任務(wù)后再返回e)如果被創(chuàng)建的線程屬于第二個(gè)CPU，那么它首先要按上一小節(jié)分段規(guī)則的思想查找第一個(gè)CPU處理時(shí)的終止位置，通過(guò)它再確定自己的起始位置，接著按分段規(guī)則查找自己的終止位置，最后按影射算排序算法排序和輸出自己任務(wù)段的整數(shù)f)如果被創(chuàng)建的線程屬于第二個(gè)后面的幾個(gè)CPU，那么，它們首先停阻塞在當(dāng)前位置，直到自己上一個(gè)CPU確定了終止位置后，它才能設(shè)置自己的開(kāi)始位置和查找自己的終止位置，最后按影射算排序算法排序和輸出自己任務(wù)段的整數(shù)4、TOP N 的實(shí)現(xiàn)現(xiàn)實(shí)應(yīng)用中還存在一種情況，那就是雖然要排序成百上千萬(wàn)個(gè)整數(shù)，但應(yīng)用只需要用到成百上千萬(wàn)個(gè)整數(shù)的前N個(gè)整數(shù)（比如數(shù)據(jù)庫(kù)中的SELECT TOP N語(yǔ)句）。這種情況下那么就沒(méi)有必要把所有整數(shù)排序完才返回，只要在索引輸出時(shí)增加監(jiān)視，輸入索引個(gè)數(shù)達(dá)到N時(shí)就可以返回了，這種情況也可以提升性能很多倍。在上面多CPU的線性排序中，我們只需要輕松更改每個(gè)CPU輸出索引緩沖區(qū)終止的偏移量就能達(dá)到這個(gè)目的。5、算法的復(fù)雜度分析5.1 時(shí)間復(fù)雜度在排序從-1048576x1048576區(qū)間的整數(shù)時(shí)，每個(gè)整數(shù)只會(huì)被影射一次，所以它的時(shí)間復(fù)雜度為O(N)在排序x-1048576和1048576x區(qū)間的整數(shù)時(shí)，在最壞的情況下，每個(gè)整數(shù)會(huì)被影射三次，所以它的時(shí)間復(fù)雜度為O(3N)。在實(shí)際應(yīng)用當(dāng)中，x-1048576和1048576x區(qū)間會(huì)存在很多整數(shù)在第一次或是第二次影射后（在坐標(biāo)上只存在一個(gè)或是兩個(gè)整數(shù)的情況），就可以立即輸出它的索引了，不需要再次影射。 從時(shí)間復(fù)雜度上看，該算法理論上是非常迅速的，但實(shí)際的性能受到了鏈表訪問(wèn)操作的影響，CPU在整個(gè)算法里花了大量的時(shí)間來(lái)加載隨機(jī)訪問(wèn)的內(nèi)存，導(dǎo)致該算法達(dá)不到理論上的速度5.2 空間復(fù)雜度 該算法中，總