二分實(shí)現(xiàn)及工程使用—Kafka

典型的二分思想：“猜數(shù)字”的游戲。大家規(guī)定一個(gè)范圍，一個(gè)人在心里想一個(gè)這個(gè)范圍內(nèi)的具體數(shù)字，比如一個(gè) 1-100 的自然數(shù)，然后另幾個(gè)人來猜數(shù)字；每次猜錯(cuò)，這個(gè)人都會(huì)提示他們的猜測(cè)是大了還是小了，看誰最快猜到數(shù)字。

大家的第一反應(yīng)也都會(huì)是從比較中間的位置，比如 50，開始猜起。畢竟如果 50 猜錯(cuò)了，因?yàn)橐崾臼谴罅诉€是小了，范圍就要么縮小到 1-49，要么縮小到 51-100，這樣猜測(cè)范圍就可以成倍的縮小。

如果每一次我們都猜測(cè)可能范圍內(nèi)的中間值，那么即使猜錯(cuò)了也能成倍的縮小范圍，這樣的策略其實(shí)就是二分查找算法。

有了二分查找算法，即使更大的范圍內(nèi)進(jìn)行游戲，比如在 1-1,000,000 的范圍內(nèi)，我們按照二分的策略，最多也只需要 20 次即可完成任意數(shù)字的猜測(cè)，極大的減少的猜數(shù)字所需的時(shí)間

二分查找

比如在剛剛說的猜數(shù)字游戲里，我們之所以每次能排除一半的搜索空間，就是因?yàn)閿?shù)字整體是有序排列的，如果某次猜測(cè)的數(shù) x，比目標(biāo)值 target 大，那么當(dāng)然比 x 更大的數(shù)就沒有必要猜測(cè)了。

百度：

二分查找是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜索過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結(jié)束；如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

當(dāng)搜索空間里只剩一個(gè)可能元素時(shí)，也就是最后一次猜測(cè)，我們要么猜到了答案，要么就是答案不存在。這樣最壞的搜索次數(shù)就是最大搜索空間折半多少次可以變成 1。所以二分搜索的時(shí)間復(fù)雜度就是 O(logn) 了。

下面我們用代碼來實(shí)現(xiàn)一下：

int guess(int num); // num比答案高返回-1； 否則返回1

class Solution {

public:

int guessNumber(int n) {

int l = 1;

int r = n;

while(l < r) { int mid = l + (r-l)/2; // 每次用左右邊界的中點(diǎn)作為猜測(cè)值 if (guess(mid) == 0) return mid; //猜中直接返回 if (guess(mid) < 0) { // 猜的數(shù)大了 r = mid - 1; } else { // 猜的數(shù)小了 l = mid+1; } } return l; }

};

Kafka中二分的使用

Kafka 的海量消息就是按照寫入的時(shí)間順序，依次追加在許多日志文件中。那在某個(gè)日志文件中，每條消息自然會(huì)距離第一條消息有一個(gè)對(duì)應(yīng)的 offset，不過這里的 offset 更像是一個(gè)消息的自增 ID，而不是一個(gè)消息在文件中的偏移量。

怎么找到日志

Kafka 雖然不允許從尾部以外的地方插入或者修改數(shù)據(jù)，但我們?cè)?Kafka 中還是很可能需要從某個(gè)時(shí)間點(diǎn)開始讀數(shù)據(jù)的，這就意味著我們要通過一個(gè) offset，快速查找到某條消息在日志文件的什么位置。這里再?gòu)?qiáng)調(diào)一下，kafka 中的 offset 實(shí)際上是類似于消息自增 ID 的存在，并不是真的在磁盤上的偏移量。

00000000000000000000.log

00000000000000000000.index

00000000000000000000.timeindex

00000000000000000035.log

00000000000000000035.index

00000000000000000035.timeindex

.log 文件就是存儲(chǔ)了消息體本身的日志文件；

.index 文件就是用于幫我們快速檢索消息在文件中位置的索引文件；

這里還有個(gè).timeindex 后綴的文件，它和 index 其實(shí)差不多都是索引文件，只不過在這個(gè)文件中關(guān)聯(lián) position 的變成了時(shí)間戳。

在整個(gè) Kafka 中，二分搜索的核心作用就是用于加速索引指定 offset 的消息，所以相應(yīng)的代碼都在 core/src/main/scala/kafka/log/AbstractIndex.scala 中。 indexSlogRangeFor 就是用于檢索目標(biāo)值的函數(shù)，其返回值就代表可能范圍的上下界，我們會(huì)不斷的遞歸搜索，如果最終返回的下界和上界相等，就說明我們找到了目標(biāo)值。

private def indexSlotRangeFor(idx: ByteBuffer, target: Long, searchEntity: IndexSearchEntity): (Int, Int) = { // 檢查index是否為空 if(_entries == 0) return (-1, -1) // 二分搜索 def binarySearch(begin: Int, end: Int) : (Int, Int) = { var lo = begin var hi = end while(lo < hi) { val mid = ceil(hi/2.0 + lo/2.0).toInt val found = parseEntry(idx, mid) val compareResult = compareIndexEntry(found, target, searchEntity) if(compareResult > 0) hi = mid - 1 else if(compareResult < 0) lo = mid else return (mid, mid) } (lo, if (lo == _entries - 1) -1 else lo + 1) } val firstHotEntry = Math.max(0, _entries - 1 - _warmEntries) // 查詢的目標(biāo)offset是否在熱區(qū) if(compareIndexEntry(parseEntry(idx, firstHotEntry), target, searchEntity) < 0) { return binarySearch(firstHotEntry, _entries - 1) } // 查詢的目標(biāo)offset是否小于最小的offset if(compareIndexEntry(parseEntry(idx, 0), target, searchEntity) > 0) return (-1, 0) return binarySearch(0, firstHotEntry) }

Kafka

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請(qǐng)聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。