首页 » 算法神探:一部谷歌首席工程师写的CS小说 » 算法神探:一部谷歌首席工程师写的CS小说全文在线阅读

《算法神探:一部谷歌首席工程师写的CS小说》7 调整算法,大胆逃离

关灯直达底部

头顶的甲板传来了沉重的脚步声,Frank环顾四周思考着如何应对这一突发状况,但貌似并没有选择的余地,唯一的一道舱门通向的正是头顶的甲板和从那走来的不速之客们。而他们所在的储藏室现在几乎空无一物——早在抵达Usb港口的时候,船员已经将货物全都卸下了船。试图藏在这里简直就如同站在角落里说“你看不见我”一样荒谬。

Frank一个接一个地排除掉了他们可能选择的应对方案,包括那通常都不怎么奏效的躺下装死的伎俩。这时,他看见Notation拿出她的徽章,立正站定在原地。

“你在想什么啊?”Frank嘘声道。

“我是一个正在执行侦查任务的警官。”Notation解释道。

Frank难以置信地摇了摇头。“这套‘我是警察,停下别动’的伎俩在这种时候根本没用。事实上,绝大多数时候它都没用。我们正在一艘走私者的船上调查一起偷窃警局财产的案件。警局里根本没人知道你在这,不是吗?我敢打赌,待会儿走过那扇门的人也知道这一点。”

Notation张开嘴,试图去争辩,但她最终闭上了嘴,将她的徽章放回了外套口袋中。这时,一群身形巨大、穿着出奇讲究的恶棍从门外涌了进来。他们在储藏室内散开,将Frank和Notation围了起来。

“女士们先生们,”Frank说道,“我们已经完成了对这艘船的检查。看起来你们并没有携带任何腐坏的鳗鱼。我们的工作是试图保证这个王国食品供应的安全。谢谢你们的耐心和配合,我们这就离开。”

似乎是对Frank这番话的回应,两个身形巨大的恶棍抓住了Frank的手臂。他们将Frank拎了起来,准备将他带回甲板上面。多年来的经验让Frank对此已有准备:他发明了一种姿势,可以让自己在这种时刻尽可能舒适。但即便如此,他还是能感觉到自己的手臂在慢慢地青肿起来。

“喂!”Notation叫道。看来她也同样被带出了储藏室。

走上甲板,看到阳光的一刹那Frank不由地眨了一下眼睛。那群恶棍将他带到了甲板的中间,随即把他丢到了木地板上。砰的一声,Notation也被丢到了Frank的身边。紧接着,那群恶棍再一次把他们围了起来。

Frank一边打量着抓他们的这群人,一边慢慢将自己调整到了一个坐着的姿势。恶棍们一动不动,随着船身来回摇摆,他们似乎在等人,看来他们真正的领头人还没到。Frank抓住这个机会,转向离他最近的一个恶棍。

“接下来你们想把我们怎么样?”Frank问道,“关起来?丢到船下面?交给雇你们老大的人?”

那个恶棍耸了耸肩说:“别看我,我只在这里工作了15天。”

“新手啊!”Frank说道。

Vinettee集团对保密有着狂热般的信仰,他们只会把行事计划告诉队里资格最老的人。新来的人则需要一步步证明他们的忠诚,慢慢得到提拔。所以要想知道任何有用的信息,Frank首先得找出船上资格最老的人。

Frank慢慢开始有了主意。Vinettee集团的这群恶棍从来都是按照资历高低的顺序来站位的。这是因为在Vinettee集团的体制内,每个人都有一位资历刚好在自己之上的人作为自己的导师——比如刚刚加入的新人的导师便会是原本队内资历最浅的人。而在这种集体行动的时候,大家都会站在自己的导师旁边。

所以这一圈恶棍说到底只是一个被首尾相连的按资历排列的有序数组。二分搜索法似乎可以派上用场,不过得做一点调整去适应这个新的数据结构:这群恶棍们站成了一个圆,而不是一条直线。不幸的是,Frank并不知道这个数组的起点和终点。然而很快他就想到了一个能快速找到资历最深的恶棍的算法。有了这个算法,Frank便能减少所需要询问的恶棍的数量,从而能尽可能地在自己被再次带走之前得到想要的答案。

他转向那位新人恶棍右边的那位,问道:“你呢?你是这里的老手了吗?”

“19天。”她答道。

有了这个信息,Frank几乎可以确定这群人是按资历由浅到深沿着逆时针方向排列的了。但他并不能完全确定,因为或许“15天”和“19天”便是这群人中资历最浅和最深的人了,虽然这种情况的可能性很小。Frank曾经有过草草率率便开始搜索的经历,结果可想而知,并不理想。因此在他真正开始搜索之前,他需要再找一个数据点。他选了剩下的恶棍中正中间的那位。

“你呢?”他问了刚来15天的恶棍对面的那位女人。

“37天,”她回答道,“你关心这个干什么?”

有了这个信息,Frank得以证实了他之前的猜想——这群恶棍的确是按资历由浅至深按逆时针顺序排列的。因此,Frank可以不再考虑“15天”和“37天”之间的任何人了。资历最深的恶棍如果不是“37天”的话,就一定在“37天”的逆时针方向,且在“15天”之前。

Frank努力抑制住内心的一股恼怒的冲动,他从来没有和资历这么浅的一群恶棍打过交道,他甚至觉得自己被侮辱了。“这简直是太尴尬了,”Frank对抓住他们的那群恶棍说道,“我们被一群新手抓住了。你们是什么人,替补队吗?”

“你在干什么啊?”Notation悄悄对Frank说道。

“一个改良版的二分搜索。”Frank低声回复道。

Notation叹了口气说:“这个我知道。看起来你在试图找出资历最老的一位,你做的简直再明显不过了。但为什么?你又怎么知道他们是按资历深浅顺序站的?”

Frank无视了她,深吸了一口气,紧接着重新开始专心搜索。他不知道在大老板到来之前他还有多少时间。他选择了还没被排除的那群恶棍里正中间的一位,问道:“你呢?”

“这是我在这干的第三天。”那个恶棍犹豫地说道。

“我的天!”Frank大声嚷嚷道,“真的吗?”

“第三天?你不用先经过训练什么的吗?”Notation问道,听起来她是发自内心地感到好奇。

看来资历最老的人不可能是“15天”和“3天”之间的三个人中的任何一个。由此Frank再次缩小了他的搜索范围。

Frank再一次将剩下可能是老手的那群恶棍分成了两半。“你一定是相对来说的老手了吧?”Frank问中间的恶棍道。

“额……先生,这是我第一天在这干。”那个恶棍结结巴巴地说道。随着大家的目光集中在那个恶棍身上,他开始紧张得大汗淋漓。

Frank低声咒骂了一句。

“不要叫他‘先生’,”“19天”吼道,“他是我们的犯人。”

现在Frank已经把搜索缩小到了一个很小的范围。“我猜你也是第一天吧?”Frank对其中除了“37号”外的最后一个恶棍问道,毫不掩饰自己的鄙夷。

那个女恶棍笑道,“我已经在Vinettee集团干了一个多月了,”她说,“42天,天天都在防止你们这群警察来多管闲事。”

找到了!“真的吗?”Frank说道,“那你在这干什么呢?”

女恶棍皱了皱眉头,“你什么意思?”

“Vinettee集团一般都会把更重要的任务交给资格最老的亲信。来护送一批走私的卷心菜?这难道不是浪费你的时间吗?”他一边对女恶棍说道,一边努力地回忆着自己是否在任务日志中看到过任何对于卷心菜的提及。无论如何,这样说也不是毫无道理,因为所有的走私者在他们的走私生涯中或多或少都与卷心菜打过交道。最近由于卷心菜税的提升,Usb港的黑市内卷心菜的交易量几乎增长了一倍。

“卷心菜?”女恶棍不屑地笑道,“我来的第一天就干过卷心菜的活了。我们现在的活比卷心菜重要多了。”

“哦?”Frank说道,“已经升级到走私胡萝卜了?”

女恶棍脸红了。即便走私蔬菜能占到一个走私者总利润的八成以上,但它依旧是走私行业中不那么光鲜的勾当。

“不,”她说道,“比走私胡萝卜要好上百倍。我们在做一份私人的合约。”

“哦?”Frank说道,“我听说贩卖胡萝卜是个挺好的勾当啊,听说利润挺丰厚的。”

“你就别操心了,”女恶棍沾沾自喜地说道,“联盟给我们的回报挺丰厚的。它要我们……”

“Runtime先生,”一个熟悉的声音传了过来,“别再试图从我的手下口中套信息了。从他们那里套信息并不难,但你能知道的这个信息也没什么用。有价值的信息我当然不会告诉他们。”

Frank抬起头,看到Rebecca Vinettee也站到了那群恶棍的圈中,他不禁感到一阵胃痛。

“话说回来,你是?”Rebecca Vinettee朝向Notation警官问道。

“这是食品安全局腌鳗鱼部的Susan Pointer,”Frank说道,“我们在追查一批不合格的Usb港的银尾鱼。”

Rebecca Vinettee轻轻地嘘了一声。“哦,Runtime先生,我并不这么认为。”她停顿了一下,仔细看着Notation,“如果我没弄错的话,这是刚刚加入警察局Elizabeth Notation警官。”

“我在执行一起官方的……”Notation开始说道。

“不,”Rebecca Vinettee打断了她,“你没有在执行任何公务,Notation警官。我知道目前所有正在被安排执行公务的警官,上到水生侠盗的案子,下至非法鼻涕虫比赛的琐事。得益于我的线人,我对这些东西清楚得很。而你并没有被分配去执行任何公务,但你现在却在私闯我的货船,所以现在问题是,我该怎么处置你呢?”

“难道你不想先问问我为什么会在这吗?”Frank说道。

“Runtime先生,”Rebecca Vinettee异常耐心地说道,“请你不要低估我。我知道你为什么在这,你来之前我就知道了。我对整件事情的来龙去脉了如指掌。

“但话说回来,我该怎么处置两个多管闲事的警官呢——哦,不好意思,你已经不再是一个警官了,对吧,Frank?我应该这么说:我该怎么处置一个多管闲事的警官,和一个多管闲事又已经被解职的警官呢?”

Frank Vinettee握紧了拳头。他回想起自己在警察队伍里工作的最后一个月,还有Rebecca被从监狱中放出来时对他的嘲笑,当时Frank按部就班的调查并没能证明她有罪,所以警察局的长官不得已只能放了她。

“干脆你就接着这样自说自话,让我们无聊死算了。”Frank说道,“不如你来跟我们说说那个联盟吧?”

Rebecca Vinettee笑了,“别担心,Runtime先生。我没有准备久留你们来听我在这无聊地自说自话。我之前早就想好如果你们再一次妨碍我的话该如何处置你们了。你们还真以为你们对怎样结束自己的性命还有任何左右的余地吗?”

“结束?”Notation尖叫道。

Rebecca Vinettee对她的一圈亲信点了点头,他们随即上前一步,像一群表演无中生有的魔术师一般从他们考究的西服口袋中拿出了各式各样的武器。一个高个男人从他的领带下面拿出了一根长近一米的狼牙棒,另一个则从袖口中掏出了一把大砍刀。

然而出乎所有人意料的是,一个大桶随着一声巨响落在了甲板上。大桶裂开,一堆腌鳗鱼散落在了甲板上的木板上。

警用算法导论:改编你的二分搜索法

节选自Drecker教授讲义

在你的职业生涯中,并不是遇到的所有问题都会有现成的答案。的确,学者们积年累月,研究了大量的各式各样的问题,也想出了很多不同的解决办法。但在办案的时候你依然会遇到新的不同的问题。如果你上这门课仅仅是记住了一堆算法的话,你很快就会遇到很大的麻烦。

为了解决这些新问题,你必须理解每个算法背后的原理,从而知道如何去调整它,让它能适用于一个新的问题。二分搜索法背后的基本思想——利用数据中的规律去不断地将搜索的范围减半——远比二分搜索法具体的应用更重要。有了这个基本思想,你可以调整二分搜索法,让它适用于环形的有序数组。你甚至可以用它去找出咖啡的最佳饮用温度——只要不断地根据每次咖啡的冷热情况去尝试不同的温度,直到找到那个刚刚好的温度就好了。