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

《算法神探:一部谷歌首席工程师写的CS小说》3 罪犯农场里的数组和索引

关灯直达底部

Frank看到一匹警队的马正拴在Crannock先生的房子外,不禁大声爆了一句粗口。既然警长已经亲自上门来雇他了,怎么还会碰到其他的警官?如果警长不信任自己的警官们,或者是他们遭到了怀疑,警长就会把他们委派到城市边远地带去调查一些小案子。如果他们只是单纯的能力低下,也会落得同样的下场。但是,从现在的情况看,有人已经在调查这个案子,而且Frank已经落后了。

Frank从虚掩着的前门溜了进去,到门厅去听那位来调查的女警官和Crannock先生的谈话。Crannock先生厌恶地瞥了Frank一眼,不过Frank的出现似乎早在他预料之中。但是,那位女警官看起来倒有些措手不及。

“你是谁?”她拿着羊皮纸和羽毛笔转向Frank问道。

Frank懒得理她。“Crannock先生,”他说,“再次见到你很高兴。”

“你又来烦我们了,是吗?”Crannock说,“这里可不欢迎你。”

“我才没指望你们欢迎我,”Frank答,“我是来找你妻子的,想问她几个小问题。”

那位女警官打量着他。“Frank?”她问,“Frank Runtime先生?前警探改行做私家侦探了?你在这做什么?谁的宠物龙走丢了吗?”她嘲笑道。

Frank还是没搭理她,说道:“Crannock先生,您的妻子究竟在哪?”

那个老男人举起了双手:“她啥都没干!她已经金盆洗手了,这次是真的。”这一幕演得算得上是业余演员了。

Frank笑了,他知道这话问得很令人不安,Crannock一定畏缩了。

“我知道,Crannock先生,我是来向她请教专业知识的。要不我请这位警官接着和你聊……”

“我是Notation警官。”那位年轻的女警官插嘴道,“我正在查案。”

她在撒谎,因为警官们永远都是和搭档一起调查案子的。更重要的是,Frank突然注意到她警徽上的名字是警长给他的执勤人员名单之中的一个,也就是说案发当晚,她也在警局值班。

“Notation警官,”Frank说,“谁说我是来查案的了?说不定我只是来找一条走丢的龙呢!”

她皱了皱眉头。

屋后传来了一阵骚动,有人在叫Crannock,不过被一声响亮的马叫声打断了。“我的妻子正和那些马待在一块,”Crannock先生不耐烦地说,“行了,她在2号谷仓,快去吧,别再赖在我的房子里了!”Crannock把他们往前门赶,然后从后门急匆匆地跑了。

“谢谢你!”Frank转身离开的时候喊道,“Crannock先生,见到您总是很愉快!”

Notation警官跟着Frank穿过了小花园,她很生气,每一步都重重地跺着地面,问道:“你知道你在往哪走吗?”

“2号谷仓啊。”Frank回答。

“我当然知道,”她咆哮道,“但2号谷仓在哪啊?”

Frank停下来转向她问道:“你是刚从警校毕业吗?Notation警官?”

“什么?”

“这样的搜索问题,只有菜鸟才会问。你没有上过警务程序课和数据结构课吗?或者是他们已经把这些课换成了小海龟画图这样不严谨规范的课程了?”

Notation愣了愣,说道:“我当然上过那些课啊,”她听起来有些底气不足,“但我的意思是……”

Frank打断了她:“那你就应该知道数组和索引。”

“是的,不过……”Notation说。

“在一个农场上找一个谷仓是一个再简单不过的搜索任务了,”Frank又打断了她,“我们可以用穷举的方法去搜索每一个建筑物。对农场上的每一个建筑都要检查一下是否为2号谷仓。在我上警校的那个年代,这是我们警用算法课第一节的内容。

“但是我们现在可以做得更好。Crannock一家把六个谷仓排在了一条整齐的线上,就像是一个巨型数组。Crannock先生非常好心地为我们写好了谷仓的编号,也就是数组的索引,我们现在只需要走到对应的谷仓就行了。”

“我不是想问这个!”Notation挥动着手臂大声吼道,“我知道怎么用数组里的索引,我也知道我们只用走到2号谷仓就好了,我毕业时在数据结构课和警用算法课上都拿到了第一,所以我不需要你在这给我说教如何正确使用数组。”

“刚刚是你自己问的啊。”Frank回答道。

“我问的是:你知不知道这个美丽可爱的谷仓数组在哪里?”

“哦,原来你问的是这个啊,”他开始继续向前走,说道,“虽然你说你是第一名,但看起来仍像一个菜鸟。”

“谷仓到底在哪?”Notation又一次吼着,仍然踩着重重的步伐赶上Frank。

Frank回头对她一笑:“这座小山上。”

他几年前得知,Crannock一家在生活中总是热爱运用数组的思想,近乎疯狂。他们会把所有的事物整理成井井有条的线性结构,然后将每个数组中的元素都标上清晰的索引。当Frank走过0号谷仓时,他看到了15个猪槽,每个猪槽可以放一份食物,农场里的喂猪人沿着猪槽摆放的直线,用勺子将猪食一份一份地送到这个数组的对应位置上。

Frank和Notation走到了2号谷仓,谷仓门口有个牌子标记着一个大大的“2”。相比之前遇到的人的态度,Crannock太太有些高冷的问候已经很令人欣慰了,至少她没有向他们砸任何东西……至少现在还没有。

“你们想干什么?”Crannock太太问。

“Crannock太太,”Notation担心Frank抢走了她的目击证人,抢先问道,“我能不能问你几个问题?”

Frank决定让Notation先问。Billy提供的线索只能指引他找到这个农场,但是Notation看起来收集了更多的信息。

Crannock太太冷笑一声,朝地上吐了口唾沫说道:“我啥都没干,我已经金盆洗手了。”

“我不是来逮捕你的,”Notation说,“我想问你一些关于驴车——Array Cart(数组车)的问题。”

Frank心里闪过一丝疑惑。Notation难道是为了调查另一个案子才来这里的吗?他有些怀疑。直觉告诉他这个女人是为了那些丢失的文件而来的,而且他很相信自己的直觉。

“Array Cart啊,”Crannock太太说道,虽然她表面上是毫不遮掩的傲慢,但是语气里还是夹杂着疑虑,“这是我的发明,基于数组的原理而创造的。它有很多分开的棚,用来存放我的动物们。每一个棚只能存放一只动物。我可以直接把某一只动物放出来或者关进去,因为每个棚都有一扇门。这样可以直接地访问每一个存储位置,既方便又节约时间。”

“这方法确实很巧妙,”Notation承认道,“你把数组和索引的概念运用在了牲畜的转移上。”

“这只是一个开始,”Crannock太太补充说,“我和一个巫师在研究一种新型Array Cart,新型的Array Cart上带有魔法指针!我敢打赌它们作为警队的装备是再好不过的了。跟你的警长说我可以给他一点折扣。”

Frank不得不赞扬Notation的机智,一旦说到数组,Crannock家的人就开始喋喋不休了。

“你现在是不是租出去了几辆Array Cart?”Notation试探道。

Crannock太太突然变得极其冷漠地说:“我们做的事没有违法,我们交了税。”

Frank差点笑出声,但还是忍住了。

“两天前的晚上你是不是恰好把某些Array Cart租给了别人?”Notation步步紧逼地问道,“一种小一点的只有六个棚的Array Cart?”

“有可能吧。”Crannock太太说。她冷漠的举止渐渐转变为敌意。

Notation问:“你有记录是租给谁了吗?”

“没,”Crannock太太说,“一旦借的人把Array Cart还回来,我就会把记录撕掉,我现在也想不起来谁借的那一辆了。”

Billy的暗示似乎已经得到了验证。一个想逃跑的罪犯能租到Array Cart的地方不多,租完Array Cart就被忘记更是不太可能,Crannock太太虽说自己已经金盆洗手,但她很明显地在向从前的同伙提供非常有价值的帮助。

“你确定你一点都不记得之前的客户了吗?”Notation不罢休地问道,但是Frank知道这个问题是没有意义的。他曾经为了一头被偷的牦牛而问过她三个小时,尽管她是被偷的一方,但她还是没有告诉他任何信息。Crannock太太不愿意开口。

Notation在尝试几种不同的问法,希望套出一点话,这时Frank悄悄地从谷仓溜了出去,找到了Array Cart的停车场。

不出他所料,停车场的十个车位被整理成了标过号码的数组,只有2号、4号和8号车位停着Array Cart。不过2号和4号的车位上停的都是有10个棚的Array Cart,都不是Notation说的那种。8号车位上停的才是有6个棚的Array Cart,它的轮子上还留着没完全干的泥土。

Frank扫视了周围,跳进这个有六个棚的Array Cart上。Array Cart的地板上零散地铺着稻草,但没有牲畜。Frank逐一打开每一个棚的门,在空无一物的空间里寻找线索。他趴在地上,一层层拨开稻草,直到找到了一些羊皮纸的碎片。

Frank一共找到了六片,可能是在把文件搬下Array Cart时被钉子割下来的边边角角。其中只有两片有文字,看起来像是账目的一部分。虽然这不是什么可靠的线索,但这能表示这辆Array Cart和案子脱不了干系。

Frank开始检查Array Cart的前面,小心地在驾驶座找线索。他在椅子那里找到了第一条真正的线索——在木椅子残破的地方,卡着几根黑色和橙色的细线,是披风上的线。Frank断定这件披风一定是新的,因为细线还没褪色。他心满意足地把细线装在口袋里,从Array Cart上跳下来。

当呼吸到一口新鲜空气时他才意识到,原来自己一直是屏住呼吸的。Array Cart的周围弥漫着鱼腐烂后的腥臭味。他嗅了嗅,循着臭气找到了根源——被泥土盖住的轮子。他深吸了一口气,但是立马就后悔了,那些泥土散发出的鳗鱼腐臭的气味是如此恶心。

Frank一边微笑一边作呕地远离了这辆Array Cart,因为虽然他不知道是谁租了这辆Array Cart,但他毫无疑问地知道了这辆Array Cart曾经去过哪里。

警用算法导论:数组

节选自Drecker教授讲义

数组是可以让你存储多个值的简单数据结构。一个数组就像一排箱子一样,每个箱子可以存储一条信息,例如一个数或一个字符。

数组结构的意义在于,可以通过指定一个位置或索引的方法来存储或读取数组中的任何值(或元素)。很多编程语言数组的索引都是从0开始的。这也就意味着第1个值存放在第0位,第2个值存放在第1位,以此类推。通常数组A中索引为i的值存储在A[i]中。例如,上面的数组A的第3个元素的索引为2,我们用A[2]表示,存储的值为19。

昨天警校组织大家参观监狱时你可能已经发现了这个结构的运用。国王亲自建议使用索引来对牢房进行编号,这样可以简化对犯人的检索。现在每个警局都根据当地犯人的人数配备了4~8个编过号的数组牢房来关押犯人。