面試經(jīng)典數(shù)據(jù)結(jié)構(gòu)和算法匯總

如果說(shuō)數(shù)據(jù)結(jié)構(gòu)是骨架，那么算法就是靈魂。沒了骨架，靈魂沒有實(shí)體寄托；沒了靈魂，骨架也是個(gè)空殼。兩者相輔相成，缺一不可，在開發(fā)中起到了砥柱中流的作用。

10年積累的做網(wǎng)站、網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)后付款的網(wǎng)站建設(shè)流程，更有海東免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

現(xiàn)在我對(duì)各種數(shù)據(jù)結(jié)構(gòu)和算法做一總結(jié)，對(duì)比一下它們的效率

1.數(shù)據(jù)結(jié)構(gòu)篇

1. 如果讓你手寫個(gè)棧和隊(duì)列，你還會(huì)寫嗎？

2. 開發(fā)了那么多項(xiàng)目，你能自己手寫個(gè)健壯的鏈表出來(lái)嗎？

3. 下次面試若再被問(wèn)到二叉樹，希望你能對(duì)答如流！

4. 面試還在被紅-黑樹虐？看完這篇輕松搞定面試官 ！

2.排序算法篇

1. 幾個(gè)經(jīng)典的基礎(chǔ)排序算法，你還記得嗎？

2. 手把手教你學(xué)會(huì)希爾排序，很簡(jiǎn)單！

3. 快速排序算法到底有多快？

4. 五分鐘教你學(xué)會(huì)歸并排序

5. 簡(jiǎn)單說(shuō)下二叉樹排序

6. 學(xué)會(huì)堆排序只需要幾分鐘

7. 圖，這個(gè)玩意兒竟然還可以用來(lái)排序！

掌握了這些經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法，面試啥的基本上沒什么問(wèn)題了，特別是對(duì)于那些應(yīng)屆生來(lái)說(shuō)。接下來(lái)再總結(jié)一下不同數(shù)據(jù)結(jié)構(gòu)和算法的效率問(wèn)題，做一下對(duì)比，這也是面試官經(jīng)常問(wèn)的問(wèn)題。

數(shù)據(jù)結(jié)構(gòu)常用操作效率對(duì)比：

常用排序算法效率的對(duì)比：

關(guān)于經(jīng)典的數(shù)據(jù)結(jié)構(gòu)和算法，就總結(jié)到這，本文建議收藏，利用等公交、各種排隊(duì)之時(shí)提升自己。這世上天才很少，懶蛋卻很多，你若對(duì)得起時(shí)間，時(shí)間便對(duì)得起你。

PHP面試都會(huì)問(wèn)什么？

簡(jiǎn)單的列出10點(diǎn)供你參考吧

1、php基礎(chǔ)知識(shí)

2、常用函數(shù)使用

3、排序算法

4、引用變量的理解

5、session cookie 的理解

6、http請(qǐng)求 get post php://input 使用

7、mysql數(shù)據(jù)庫(kù)鏈表查詢，索引優(yōu)化方案等

8、linux基本命名的使用 crontab，grep ，tail等

9、緩存 redis，memcached等的使用

10、市場(chǎng)上常用的流行PHP框架掌握，熟悉情況

PHP中高級(jí)面試題 – 第三天

一、簡(jiǎn)述一下MongoDB的應(yīng)用場(chǎng)景

mongodb 支持副本集、索引、自動(dòng)分片，可以保證較高的性能和可用性。

更高的寫入負(fù)載

默認(rèn)情況下，MongoDB 更側(cè)重高數(shù)據(jù)寫入性能，而非事務(wù)安全，MongoDB 很適合業(yè)務(wù)系統(tǒng)中有大量 “低價(jià)值” 數(shù)據(jù)的場(chǎng)景。但是應(yīng)當(dāng)避免在高事務(wù)安全性的系統(tǒng)中使用 MongoDB，除非能從架構(gòu)設(shè)計(jì)上保證事務(wù)安全。

高可用性

MongoDB 的復(fù)副集 (Master-Slave) 配置非常簡(jiǎn)潔方便，此外，MongoDB 可以快速響應(yīng)的處理單節(jié)點(diǎn)故障，自動(dòng)、安全地完成故障轉(zhuǎn)移。這些特性使得 MongoDB 能在一個(gè)相對(duì)不穩(wěn)定（如云主機(jī)）的環(huán)境中，保持高可用性。

數(shù)據(jù)量很大或者未來(lái)會(huì)變得很大

依賴數(shù)據(jù)庫(kù) (MySQL) 自身的特性，完成數(shù)據(jù)的擴(kuò)展是較困難的事，在 MySQL 中，當(dāng)一個(gè)單達(dá)表到 5-10GB 時(shí)會(huì)出現(xiàn)明顯的性能降級(jí)，此時(shí)需要通過(guò)數(shù)據(jù)的水平和垂直拆分、庫(kù)的拆分完成擴(kuò)展，使用 MySQL 通常需要借助驅(qū)動(dòng)層或代理層完成這類需求。而 MongoDB 內(nèi)建了多種數(shù)據(jù)分片的特性，可以很好地適應(yīng)大數(shù)據(jù)量的需求。

基于位置的數(shù)據(jù)查詢

MongoDB 支持二維空間索引，因此可以快速及精確地從指定位置獲取數(shù)據(jù)。

表結(jié)構(gòu)不明確

在一些傳統(tǒng) RDBMS 中，增加一個(gè)字段會(huì)鎖住整個(gè)數(shù)據(jù)庫(kù) / 表，或者在執(zhí)行一個(gè)重負(fù)載的請(qǐng)求時(shí)會(huì)明顯造成其它請(qǐng)求的性能降級(jí)。通常發(fā)生在數(shù)據(jù)表大于 1G 的時(shí)候（當(dāng)大于 1TB 時(shí)更甚）。 因 MongoDB 是文檔型數(shù)據(jù)庫(kù)，為非結(jié)構(gòu)貨的文檔增加一個(gè)新字段是很快速的操作，并且不會(huì)影響到已有數(shù)據(jù)。另外一個(gè)好處當(dāng)業(yè)務(wù)數(shù)據(jù)發(fā)生變化時(shí)，是將不再需要由 DBA 修改表結(jié)構(gòu)。

二、數(shù)據(jù)庫(kù)設(shè)計(jì)經(jīng)驗(yàn)，為什么進(jìn)行分表？分庫(kù)？一般多少數(shù)據(jù)量開始分表？分庫(kù)？分庫(kù)分表的目的？

1、為什么要分表

當(dāng)一張表的數(shù)據(jù)達(dá)到幾百萬(wàn)時(shí)，你查詢一次所花的時(shí)間會(huì)變多，如果有聯(lián)合查詢的話，有可能會(huì)死在那兒了。分表的目的就在于此，減小數(shù)據(jù)庫(kù)的負(fù)擔(dān)，縮短查詢時(shí)間。日常開發(fā)中我們經(jīng)常會(huì)遇到大表的情況，所謂的大表是指存儲(chǔ)了百萬(wàn)級(jí)乃至千萬(wàn)級(jí)條記錄的表。這樣的表過(guò)于龐大，導(dǎo)致數(shù)據(jù)庫(kù)在查詢和插入的時(shí)候耗時(shí)太長(zhǎng)，性能低下，如果涉及聯(lián)合查詢的情況，性能會(huì)更加糟糕。

分表和表分區(qū)的目的就是減少數(shù)據(jù)庫(kù)的負(fù)擔(dān)，提高數(shù)據(jù)庫(kù)的效率，通常點(diǎn)來(lái)講就是提高表的增刪改查效率。數(shù)據(jù)庫(kù)中的數(shù)據(jù)量不一定是可控的，在未進(jìn)行分庫(kù)分表的情況下，隨著時(shí)間和業(yè)務(wù)的發(fā)展，庫(kù)中的表會(huì)越來(lái)越多，表中的數(shù)據(jù)量也會(huì)越來(lái)越大，相應(yīng)地，數(shù)據(jù)操作，增刪改查的開銷也會(huì)越來(lái)越大；另外，由于無(wú)法進(jìn)行分布式式部署，而一臺(tái)服務(wù)器的資源（CPU、磁盤、內(nèi)存、IO 等）是有限的，最終數(shù)據(jù)庫(kù)所能承載的數(shù)據(jù)量、數(shù)據(jù)處理能力都將遭遇瓶頸。

2、分表的方案

做 mysql 集群，有人會(huì)問(wèn) mysql 集群，根分表有什么關(guān)系嗎？雖然它不是實(shí)際意義上的分表，但是它啟到了分表的作用，做集群的意義是什么呢？為一個(gè)數(shù)據(jù)庫(kù)減輕負(fù)擔(dān)，說(shuō)白了就是減少 sql 排隊(duì)隊(duì)列中的 sql 的數(shù)量，舉個(gè)例子：有 10 個(gè) sql 請(qǐng)求，如果放在一個(gè)數(shù)據(jù)庫(kù)服務(wù)器的排隊(duì)隊(duì)列中，他要等很長(zhǎng)時(shí)間，如果把這 10 個(gè) sql 請(qǐng)求，分配到 5 個(gè)數(shù)據(jù)庫(kù)服務(wù)器的排隊(duì)隊(duì)列中，一個(gè)數(shù)據(jù)庫(kù)服務(wù)器的隊(duì)列中只有 2 個(gè)，這樣等待時(shí)間是不是大大的縮短了呢？

linux mysql proxy 的安裝，配置，以及讀寫分離

mysql replication 互為主從的安裝及配置，以及數(shù)據(jù)同步

優(yōu)點(diǎn)：擴(kuò)展性好，沒有多個(gè)分表后的復(fù)雜操作（php 代碼）

缺點(diǎn)：?jiǎn)蝹€(gè)表的數(shù)據(jù)量還是沒有變，一次操作所花的時(shí)間還是那么多，硬件開銷大。

三、簡(jiǎn)述一下數(shù)據(jù)庫(kù)主從復(fù)制，讀寫分離

* 什么是主從復(fù)制

主從復(fù)制，是用來(lái)建立一個(gè)和主數(shù)據(jù)庫(kù)完全一樣的數(shù)據(jù)庫(kù)環(huán)境，稱為從數(shù)據(jù)庫(kù)；

* 主從復(fù)制的原理：

1.數(shù)據(jù)庫(kù)有個(gè)bin-log二進(jìn)制文件，記錄了所有的sql語(yǔ)句。

2.只需要把主數(shù)據(jù)庫(kù)的bin-log文件中的sql語(yǔ)句復(fù)制。

3.讓其從數(shù)據(jù)的relay-log重做日志文件中再執(zhí)行一次這些sql語(yǔ)句即可。

* 主從復(fù)制的作用

1.做數(shù)據(jù)的熱備份，作為后備數(shù)據(jù)庫(kù)，主數(shù)據(jù)庫(kù)服務(wù)器故障后，可切換到從數(shù)據(jù)庫(kù)繼續(xù)工作，避免數(shù)據(jù)丟失。

2.架構(gòu)的擴(kuò)展。業(yè)務(wù)量越來(lái)越大，I/O訪問(wèn)頻率過(guò)高，單機(jī)無(wú)法滿足，此時(shí)做多庫(kù)的存儲(chǔ)，降低磁盤I/O訪問(wèn)頻率，提高單機(jī)的I/O性能

3.主從復(fù)制是讀寫分離的基礎(chǔ)，使數(shù)據(jù)庫(kù)能制成更大 的并發(fā)。例如子報(bào)表中，由于部署報(bào)表的sql語(yǔ)句十分慢，導(dǎo)致鎖表，影響前臺(tái)的服務(wù)。如果前臺(tái)服務(wù)使用master，報(bào)表使用slave，那么報(bào)表sql將不會(huì)造成前臺(tái)所，保證了前臺(tái)的訪問(wèn)速度。

* 主從復(fù)制的幾種方式：

1.同步復(fù)制：所謂的同步復(fù)制，意思是master的變化，必須等待slave-1,slave-2,…,slave-n完成后才能返回。

2.異步復(fù)制：如同AJAX請(qǐng)求一樣。master只需要完成自己的數(shù)據(jù)庫(kù)操作即可。至于slaves是否收到二進(jìn)制日志，是否完成操作，不用關(guān)心。MYSQL的默認(rèn)設(shè)置。

3.半同步復(fù)制：master只保證slaves中的一個(gè)操作成功，就返回，其他slave不管。

這個(gè)功能，是由google為MYSQL引入的。

* 關(guān)于讀寫分離

在完成主從復(fù)制時(shí)，由于slave是需要同步master的。所以對(duì)于insert/delete/update這些更新數(shù)據(jù)庫(kù)的操作，應(yīng)該在master中完成。而select的查詢操作，則落下到slave中。

經(jīng)典筆試面試知識(shí)整理，數(shù)據(jù)結(jié)構(gòu)與算法(代碼演示)

題目描述：

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

輸入描述: array： 待查找的二維數(shù)組 target：查找的數(shù)字

輸出描述:

查找到返回true，查找不到返回false

題目描述：

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過(guò)替換之后的字符串為We%20Are%20Happy。

題目描述： 輸入一個(gè)鏈表，從尾到頭打印鏈表每個(gè)節(jié)點(diǎn)的值。

輸入描述： 輸入為鏈表的表頭

輸出描述： 輸出為需要打印的“新鏈表”的表頭

題目描述：

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。

例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

題目描述：

把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。輸入一個(gè)遞增排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。

例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。 NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請(qǐng)返回0。

1、題目描述：

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。n=39

2、題目描述：

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

3、題目描述：

一只青蛙一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求該青蛙跳上一個(gè)n級(jí)的臺(tái)階總共有多少種跳法。

4、題目描述：

我們可以用2*1的小矩形橫著或者豎著去覆蓋更大的矩形。請(qǐng)問(wèn)用n個(gè)2*1的小矩形無(wú)重疊地覆蓋一個(gè)2*n的大矩形，總共有多少種方法？

1、題目描述：

輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。其中負(fù)數(shù)用補(bǔ)碼表示。

2、題目描述：

給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。

題目描述：

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來(lái)調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。

題目描述：

用兩個(gè)棧來(lái)實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作， 隊(duì)列中的元素為int類型。

題目描述：

輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

php面試題 memcache和redis的區(qū)別

Redis與Memcached的區(qū)別

傳統(tǒng)MySQL+ Memcached架構(gòu)遇到的問(wèn)題

實(shí)際MySQL是適合進(jìn)行海量數(shù)據(jù)存儲(chǔ)的，通過(guò)Memcached將熱點(diǎn)數(shù)據(jù)加載到cache，加速訪問(wèn)，很多公司都曾經(jīng)使用過(guò)這樣的架構(gòu)，但隨著業(yè)務(wù)數(shù)據(jù)量的不斷增加，和訪問(wèn)量的持續(xù)增長(zhǎng)，我們遇到了很多問(wèn)題：

1.MySQL需要不斷進(jìn)行拆庫(kù)拆表，Memcached也需不斷跟著擴(kuò)容，擴(kuò)容和維護(hù)工作占據(jù)大量開發(fā)時(shí)間。

2.Memcached與MySQL數(shù)據(jù)庫(kù)數(shù)據(jù)一致性問(wèn)題。

3.Memcached數(shù)據(jù)命中率低或down機(jī)，大量訪問(wèn)直接穿透到DB，MySQL無(wú)法支撐。

4.跨機(jī)房cache同步問(wèn)題。

眾多NoSQL百花齊放，如何選擇

最近幾年，業(yè)界不斷涌現(xiàn)出很多各種各樣的NoSQL產(chǎn)品，那么如何才能正確地使用好這些產(chǎn)品，最大化地發(fā)揮其長(zhǎng)處，是我們需要深入研究和思考的

問(wèn)題，實(shí)際歸根結(jié)底最重要的是了解這些產(chǎn)品的定位，并且了解到每款產(chǎn)品的tradeoffs，在實(shí)際應(yīng)用中做到揚(yáng)長(zhǎng)避短，總體上這些NoSQL主要用于解

決以下幾種問(wèn)題

1.少量數(shù)據(jù)存儲(chǔ)，高速讀寫訪問(wèn)。此類產(chǎn)品通過(guò)數(shù)據(jù)全部in-momery 的方式來(lái)保證高速訪問(wèn)，同時(shí)提供數(shù)據(jù)落地的功能，實(shí)際這正是Redis最主要的適用場(chǎng)景。

2.海量數(shù)據(jù)存儲(chǔ)，分布式系統(tǒng)支持，數(shù)據(jù)一致性保證，方便的集群節(jié)點(diǎn)添加/刪除。

3.這方面最具代表性的是dynamo和bigtable 2篇論文所闡述的思路。前者是一個(gè)完全無(wú)中心的設(shè)計(jì)，節(jié)點(diǎn)之間通過(guò)gossip方式傳遞集群信息，數(shù)據(jù)保證最終一致性，后者是一個(gè)中心化的方案設(shè)計(jì)，通過(guò)類似一個(gè)分布式鎖服務(wù)來(lái)保證強(qiáng)一致性,數(shù)據(jù)寫入先寫內(nèi)存和redo log，然后定期compat歸并到磁盤上，將隨機(jī)寫優(yōu)化為順序?qū)懀岣邔懭胄阅堋?/p>

4.Schema free，auto-sharding等。比如目前常見的一些文檔數(shù)據(jù)庫(kù)都是支持schema-free的，直接存儲(chǔ)json格式數(shù)據(jù)，并且支持auto-sharding等功能，比如mongodb。

面對(duì)這些不同類型的NoSQL產(chǎn)品,我們需要根據(jù)我們的業(yè)務(wù)場(chǎng)景選擇最合適的產(chǎn)品。

Redis適用場(chǎng)景，如何正確的使用

前面已經(jīng)分析過(guò)，Redis最適合所有數(shù)據(jù)in-momory的場(chǎng)景，雖然Redis也提供持久化功能，但實(shí)際更多的是一個(gè)disk-

backed的功能，跟傳統(tǒng)意義上的持久化有比較大的差別，那么可能大家就會(huì)有疑問(wèn)，似乎Redis更像一個(gè)加強(qiáng)版的Memcached，那么何時(shí)使用

Memcached,何時(shí)使用Redis呢?

如果簡(jiǎn)單地比較Redis與Memcached的區(qū)別，大多數(shù)都會(huì)得到以下觀點(diǎn)：

1 Redis不僅僅支持簡(jiǎn)單的k/v類型的數(shù)據(jù)，同時(shí)還提供list，set，zset，hash等數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)。

2 Redis支持?jǐn)?shù)據(jù)的備份，即master-slave模式的數(shù)據(jù)備份。

3 Redis支持?jǐn)?shù)據(jù)的持久化，可以將內(nèi)存中的數(shù)據(jù)保持在磁盤中，重啟的時(shí)候可以再次加載進(jìn)行使用。

拋開這些，可以深入到Redis內(nèi)部構(gòu)造去觀察更加本質(zhì)的區(qū)別，理解Redis的設(shè)計(jì)。

在

Redis中，并不是所有的數(shù)據(jù)都一直存儲(chǔ)在內(nèi)存中的。這是和Memcached相比一個(gè)最大的區(qū)別。Redis只會(huì)緩存所有的

key的信息，如果Redis發(fā)現(xiàn)內(nèi)存的使用量超過(guò)了某一個(gè)閥值，將觸發(fā)swap的操作，Redis根據(jù)“swappability =

age*log(size_in_memory)”計(jì)

算出哪些key對(duì)應(yīng)的value需要swap到磁盤。然后再將這些key對(duì)應(yīng)的value持久化到磁盤中，同時(shí)在內(nèi)存中清除。這種特性使得Redis可以

保持超過(guò)其機(jī)器本身內(nèi)存大小的數(shù)據(jù)。當(dāng)然，機(jī)器本身的內(nèi)存必須要能夠保持所有的key，畢竟這些數(shù)據(jù)是不會(huì)進(jìn)行swap操作的。同時(shí)由于Redis將內(nèi)存

中的數(shù)據(jù)swap到磁盤中的時(shí)候，提供服務(wù)的主線程和進(jìn)行swap操作的子線程會(huì)共享這部分內(nèi)存，所以如果更新需要swap的數(shù)據(jù)，Redis將阻塞這個(gè)

操作，直到子線程完成swap操作后才可以進(jìn)行修改。

使用Redis特有內(nèi)存模型前后的情況對(duì)比：

VM off: 300k keys, 4096 bytes values: 1.3G used

VM on: 300k keys, 4096 bytes values: 73M used

VM off: 1 million keys, 256 bytes values: 430.12M used

VM on: 1 million keys, 256 bytes values: 160.09M used

VM on: 1 million keys, values as large as you want, still: 160.09M used

當(dāng)

從Redis中讀取數(shù)據(jù)的時(shí)候，如果讀取的key對(duì)應(yīng)的value不在內(nèi)存中，那么Redis就需要從swap文件中加載相應(yīng)數(shù)據(jù)，然后再返回給請(qǐng)求方。

這里就存在一個(gè)I/O線程池的問(wèn)題。在默認(rèn)的情況下，Redis會(huì)出現(xiàn)阻塞，即完成所有的swap文件加載后才會(huì)相應(yīng)。這種策略在客戶端的數(shù)量較小，進(jìn)行

批量操作的時(shí)候比較合適。但是如果將Redis應(yīng)用在一個(gè)大型的網(wǎng)站應(yīng)用程序中，這顯然是無(wú)法滿足大并發(fā)的情況的。所以Redis運(yùn)行我們?cè)O(shè)置I/O線程

池的大小，對(duì)需要從swap文件中加載相應(yīng)數(shù)據(jù)的讀取請(qǐng)求進(jìn)行并發(fā)操作，減少阻塞的時(shí)間。

如果希望在海量數(shù)據(jù)的環(huán)境中使用好Redis，我相信理解Redis的內(nèi)存設(shè)計(jì)和阻塞的情況是不可缺少的。

補(bǔ)充的知識(shí)點(diǎn)：

memcached和redis的比較

1 網(wǎng)絡(luò)IO模型

Memcached是多線程，非阻塞IO復(fù)用的網(wǎng)絡(luò)模型，分為監(jiān)聽主線程和worker子線程，監(jiān)聽線程監(jiān)聽網(wǎng)絡(luò)連接，接受請(qǐng)求后，將連接描述

字pipe 傳遞給worker線程，進(jìn)行讀寫IO, 網(wǎng)絡(luò)層使用libevent封裝的事件庫(kù)，多線程模型可以發(fā)揮多核作用，但是引入了cache

coherency和鎖的問(wèn)題，比如，Memcached最常用的stats

命令，實(shí)際Memcached所有操作都要對(duì)這個(gè)全局變量加鎖，進(jìn)行計(jì)數(shù)等工作，帶來(lái)了性能損耗。

(Memcached網(wǎng)絡(luò)IO模型)

Redis使用單線程的IO復(fù)用模型，自己封裝了一個(gè)簡(jiǎn)單的AeEvent事件處理框架，主要實(shí)現(xiàn)了epoll、kqueue和select，

對(duì)于單純只有IO操作來(lái)說(shuō)，單線程可以將速度優(yōu)勢(shì)發(fā)揮到最大，但是Redis也提供了一些簡(jiǎn)單的計(jì)算功能，比如排序、聚合等，對(duì)于這些操作，單線程模型實(shí)

際會(huì)嚴(yán)重影響整體吞吐量，CPU計(jì)算過(guò)程中，整個(gè)IO調(diào)度都是被阻塞住的。

2.內(nèi)存管理方面

Memcached使用預(yù)分配的內(nèi)存池的方式，使用slab和大小不同的chunk來(lái)管理內(nèi)存，Item根據(jù)大小選擇合適的chunk存儲(chǔ)，內(nèi)

存池的方式可以省去申請(qǐng)/釋放內(nèi)存的開銷，并且能減小內(nèi)存碎片產(chǎn)生，但這種方式也會(huì)帶來(lái)一定程度上的空間浪費(fèi)，并且在內(nèi)存仍然有很大空間時(shí)，新的數(shù)據(jù)也可

能會(huì)被剔除，原因可以參考Timyang的文章：

Redis使用現(xiàn)場(chǎng)申請(qǐng)內(nèi)存的方式來(lái)存儲(chǔ)數(shù)據(jù)，并且很少使用free-list等方式來(lái)優(yōu)化內(nèi)存分配，會(huì)在一定程度上存在內(nèi)存碎片，Redis

跟據(jù)存儲(chǔ)命令參數(shù)，會(huì)把帶過(guò)期時(shí)間的數(shù)據(jù)單獨(dú)存放在一起，并把它們稱為臨時(shí)數(shù)據(jù)，非臨時(shí)數(shù)據(jù)是永遠(yuǎn)不會(huì)被剔除的，即便物理內(nèi)存不夠，導(dǎo)致swap也不會(huì)剔

除任何非臨時(shí)數(shù)據(jù)(但會(huì)嘗試剔除部分臨時(shí)數(shù)據(jù))，這點(diǎn)上Redis更適合作為存儲(chǔ)而不是cache。

3.數(shù)據(jù)一致性問(wèn)題

Memcached提供了cas命令，可以保證多個(gè)并發(fā)訪問(wèn)操作同一份數(shù)據(jù)的一致性問(wèn)題。 Redis沒有提供cas 命令，并不能保證這點(diǎn)，不過(guò)Redis提供了事務(wù)的功能，可以保證一串 命令的原子性，中間不會(huì)被任何操作打斷。

4.存儲(chǔ)方式及其它方面

Memcached基本只支持簡(jiǎn)單的key-value存儲(chǔ)，不支持枚舉，不支持持久化和復(fù)制等功能

Redis除key/value之外，還支持list,set,sorted set,hash等眾多數(shù)據(jù)結(jié)構(gòu)，提供了KEYS

進(jìn)行枚舉操作，但不能在線上使用，如果需要枚舉線上數(shù)據(jù)，Redis提供了工具可以直接掃描其dump文件，枚舉出所有數(shù)據(jù)，Redis還同時(shí)提供了持久化和復(fù)制等功能。

5.關(guān)于不同語(yǔ)言的客戶端支持

在不同語(yǔ)言的客戶端方面，Memcached和Redis都有豐富的第三方客戶端可供選擇，不過(guò)因?yàn)镸emcached發(fā)展的時(shí)間更久一些，目

前看在客戶端支持方面，Memcached的很多客戶端更加成熟穩(wěn)定，而Redis由于其協(xié)議本身就比Memcached復(fù)雜，加上作者不斷增加新的功能

等，對(duì)應(yīng)第三方客戶端跟進(jìn)速度可能會(huì)趕不上，有時(shí)可能需要自己在第三方客戶端基礎(chǔ)上做些修改才能更好的使用。

根據(jù)以上比較不難看出，當(dāng)我們不希望數(shù)據(jù)被踢出，或者需要除key/value之外的更多數(shù)據(jù)類型時(shí)，或者需要落地功能時(shí)，使用Redis比使用Memcached更合適。

關(guān)于Redis的一些周邊功能

Redis除了作為存儲(chǔ)之外還提供了一些其它方面的功能，比如聚合計(jì)算、pubsub、scripting等，對(duì)于此類功能需要了解其實(shí)現(xiàn)原

理，清楚地了解到它的局限性后，才能正確的使用，比如pubsub功能，這個(gè)實(shí)際是沒有任何持久化支持的，消費(fèi)方連接閃斷或重連之間過(guò)來(lái)的消息是會(huì)全部丟

失的，又比如聚合計(jì)算和scripting等功能受Redis單線程模型所限，是不可能達(dá)到很高的吞吐量的，需要謹(jǐn)慎使用。

總的來(lái)說(shuō)Redis作者是一位非常勤奮的開發(fā)者，可以經(jīng)常看到作者在嘗試著各種不同的新鮮想法和思路，針對(duì)這些方面的功能就要求我們需要深入了解后再使用。

總結(jié)：

1.Redis使用最佳方式是全部數(shù)據(jù)in-memory。

2.Redis更多場(chǎng)景是作為Memcached的替代者來(lái)使用。

3.當(dāng)需要除key/value之外的更多數(shù)據(jù)類型支持時(shí)，使用Redis更合適。

4.當(dāng)存儲(chǔ)的數(shù)據(jù)不能被剔除時(shí)，使用Redis更合適。

談?wù)凪emcached與Redis(一)

1. Memcached簡(jiǎn)介

Memcached是以LiveJurnal旗下Danga Interactive公司的Bard

Fitzpatric為首開發(fā)的高性能分布式內(nèi)存緩存服務(wù)器。其本質(zhì)上就是一個(gè)內(nèi)存key-value數(shù)據(jù)庫(kù)，但是不支持?jǐn)?shù)據(jù)的持久化，服務(wù)器關(guān)閉之后數(shù)

據(jù)全部丟失。Memcached使用C語(yǔ)言開發(fā)，在大多數(shù)像Linux、BSD和Solaris等POSIX系統(tǒng)上，只要安裝了libevent即可使

用。在Windows下，它也有一個(gè)可用的非官方版本()。Memcached

的客戶端軟件實(shí)現(xiàn)非常多，包括C/C++, PHP, Java, Python, Ruby, Perl, Erlang,

Lua等。當(dāng)前Memcached使用廣泛，除了LiveJournal以外還有Wikipedia、Flickr、Twitter、Youtube和

WordPress等。

在Window系統(tǒng)下，Memcached的安裝非常方便，只需從以上給出的地址下載可執(zhí)行軟件然后運(yùn)行memcached.exe –d

install即可完成安裝。在Linux等系統(tǒng)下，我們首先需要安裝libevent，然后從獲取源碼，make make

install即可。默認(rèn)情況下，Memcached的服務(wù)器啟動(dòng)程序會(huì)安裝到/usr/local/bin目錄下。在啟動(dòng)Memcached時(shí)，我們可

以為其配置不同的啟動(dòng)參數(shù)。

1.1 Memcache配置

Memcached服務(wù)器在啟動(dòng)時(shí)需要對(duì)關(guān)鍵的參數(shù)進(jìn)行配置，下面我們就看一看Memcached在啟動(dòng)時(shí)需要設(shè)定哪些關(guān)鍵參數(shù)以及這些參數(shù)的作用。

1）-p num Memcached的TCP監(jiān)聽端口，缺省配置為11211；

2）-U num Memcached的UDP監(jiān)聽端口，缺省配置為11211，為0時(shí)表示關(guān)閉UDP監(jiān)聽；

3）-s file Memcached監(jiān)聽的UNIX套接字路徑；

4）-a mask 訪問(wèn)UNIX套接字的八進(jìn)制掩碼，缺省配置為0700；

5）-l addr 監(jiān)聽的服務(wù)器IP地址，默認(rèn)為所有網(wǎng)卡；

6）-d 為Memcached服務(wù)器啟動(dòng)守護(hù)進(jìn)程；

7）-r 最大core文件大小；

8）-u username 運(yùn)行Memcached的用戶，如果當(dāng)前為root的話需要使用此參數(shù)指定用戶；

9）-m num 分配給Memcached使用的內(nèi)存數(shù)量，單位是MB；

10）-M 指示Memcached在內(nèi)存用光的時(shí)候返回錯(cuò)誤而不是使用LRU算法移除數(shù)據(jù)記錄；

11）-c num 最大并發(fā)連數(shù)，缺省配置為1024；

12）-v –vv –vvv 設(shè)定服務(wù)器端打印的消息的詳細(xì)程度，其中-v僅打印錯(cuò)誤和警告信息，-vv在-v的基礎(chǔ)上還會(huì)打印客戶端的命令和相應(yīng)，-vvv在-vv的基礎(chǔ)上還會(huì)打印內(nèi)存狀態(tài)轉(zhuǎn)換信息；

13）-f factor 用于設(shè)置chunk大小的遞增因子；

14）-n bytes 最小的chunk大小，缺省配置為48個(gè)字節(jié)；

15）-t num Memcached服務(wù)器使用的線程數(shù)，缺省配置為4個(gè)；

16）-L 嘗試使用大內(nèi)存頁(yè)；

17）-R 每個(gè)事件的最大請(qǐng)求數(shù)，缺省配置為20個(gè)；

18）-C 禁用CAS，CAS模式會(huì)帶來(lái)8個(gè)字節(jié)的冗余；

2. Redis簡(jiǎn)介

Redis是一個(gè)開源的key-value存儲(chǔ)系統(tǒng)。與Memcached類似，Redis將大部分?jǐn)?shù)據(jù)存儲(chǔ)在內(nèi)存中，支持的數(shù)據(jù)類型包括：字

符串、哈希表、鏈表、集合、有序集合以及基于這些數(shù)據(jù)類型的相關(guān)操作。Redis使用C語(yǔ)言開發(fā)，在大多數(shù)像Linux、BSD和Solaris等

POSIX系統(tǒng)上無(wú)需任何外部依賴就可以使用。Redis支持的客戶端語(yǔ)言也非常豐富，常用的計(jì)算機(jī)語(yǔ)言如C、C#、C++、Object-C、PHP、

Python、Java、Perl、Lua、Erlang等均有可用的客戶端來(lái)訪問(wèn)Redis服務(wù)器。當(dāng)前Redis的應(yīng)用已經(jīng)非常廣泛，國(guó)內(nèi)像新浪、淘

寶，國(guó)外像Flickr、Github等均在使用Redis的緩存服務(wù)。

Redis的安裝非常方便，只需從獲取源碼，然后make make

install即可。默認(rèn)情況下，Redis的服務(wù)器啟動(dòng)程序和客戶端程序會(huì)安裝到/usr/local/bin目錄下。在啟動(dòng)Redis服務(wù)器時(shí)，我們

需要為其指定一個(gè)配置文件，缺省情況下配置文件在Redis的源碼目錄下，文件名為redis.conf。

PHP程序員上機(jī)面試題（并附答案，回答好的加分）

某大公司的PHP面試題

管理提醒: 本帖被 haowubai 執(zhí)行取消置頂操作(2009-07-30)

1. 如何用php的環(huán)境變量得到一個(gè)網(wǎng)頁(yè)地址的內(nèi)容？ip地址又要怎樣得到？

[php]

echo $_SERVER ['PHP_SELF'];

echo $_SERVER ['SERVER_ADDR'];

[/php]

2. 求兩個(gè)日期的差數(shù)，例如2007-2-5 ~ 2007-3-6 的日期差數(shù)

[php]

$begin=strtotime('2007-2-5');

$end=strtotime('2007-3-6');

echo ($end-$begin)/(24*3600);

[/php]

3. 請(qǐng)寫一個(gè)函數(shù)，實(shí)現(xiàn)以下功能：

字符串“open_door” 轉(zhuǎn)換成 “OpenDoor”、”make_by_id” 轉(zhuǎn)換成 ”MakeById”。

[php]

function changeStyle( $str) {

/*$str = str_replace ( "_", " ", $str );

$str = ucwords ( $str );

$str = str_replace ( " ", "", $str );

return $str;*/

$arrStr=explode('_',$str);

foreach($arrStr as $key=$value){

$arrStr[$key]=strtoupper(substr($value,0,1)).substr($value,1);

}

return implode('',$arrStr);

}

$s = "open_door";

echo changeStyle ( $s );

[/php]

4. 要求寫一段程序，實(shí)現(xiàn)以下數(shù)組$arr1轉(zhuǎn)換成數(shù)組$arr2：

[php]$arr1 = array (

'0' = array ('fid' = 1, 'tid' = 1, 'name' ='Name1' ),

'1' = array ('fid' = 1, 'tid' = 2 , 'name' ='Name2' ),

'2' = array ('fid' = 1, 'tid' = 5 , 'name' ='Name3' ),

'3' = array ('fid' = 1, 'tid' = 7 , 'name' ='Name4' ),

'4' = array ('fid' = 3, 'tid' = 9, 'name' ='Name5' )

);

$arr2 = array (

'0' = array (

'0' = array ( 'tid' = 1, 'name' = 'Name1'),

'1' = array ( 'tid' = 2, 'name' = 'Name2'),

'2' = array ( 'tid' = 5, 'name' = 'Name3'),

'3' = array ( 'tid' = 7, 'name' = 'Name4')

),

'1' = array (

'0' = array ( 'tid' = 9, 'name' = 'Name5' )

)

);

?php

$arr1 = array (

'0' = array ('fid' = 1, 'tid' = 1, 'name' ='Name1' ),

'1' = array ('fid' = 1, 'tid' = 2 , 'name' ='Name2' ),

'2' = array ('fid' = 1, 'tid' = 5 , 'name' ='Name3' ),

'3' = array ('fid' = 1, 'tid' = 7 , 'name' ='Name4' ),

'4' = array ('fid' = 3, 'tid' = 9, 'name' ='Name5' )

);

function changeArrayStyle($arr){

foreach($arr as $key=$value){

$result[$value['fid']][]=$value;

}

return array_values($result);

}

$arr2=changeArrayStyle($arr1);

echo "pre";

var_dump($arr2);

[/php]

5. 請(qǐng)簡(jiǎn)述數(shù)據(jù)庫(kù)設(shè)計(jì)的范式及應(yīng)用。

一般第3范式就足以，用于表結(jié)構(gòu)的優(yōu)化，這樣做既可以避免應(yīng)用程序過(guò)于復(fù)雜同時(shí)也避免了SQL語(yǔ)句過(guò)于龐大所造成系統(tǒng)效率低下。

ANSWER：

第一范式：若關(guān)系模式R的每一個(gè)屬性是不可再分解的，再屬于第一范式。

第二范式：若R屬于第一范式，且所有的非碼屬性都完全函數(shù)依賴于碼屬性，則為第二范式。

第三范式：若R屬于第二范式，且所有的非碼屬性沒有一個(gè)是傳遞函數(shù)依賴于候選碼，則屬于第三范式。

6.一個(gè)表中的Id有多個(gè)記錄，把所有這個(gè)id的記錄查出來(lái)，并顯示共有多少條記錄數(shù)，用SQL語(yǔ)句及視圖、存儲(chǔ)過(guò)程分別實(shí)現(xiàn)。

存儲(chǔ)過(guò)程：

[php]

DELIMITER //

create procedure proc_countNum(in columnId int,out rowsNo int)

begin

select count(*) into rowsNo from member where member_id=columnId;

end

call proc_countNum(1,@no);

select @no;

[/php]

視圖：

create view v_countNum as select member_id,count(*) as countNum from member group by member_id

select countNum from v_countNum where member_id=1

7 表中有A B C三列,用SQL語(yǔ)句實(shí)現(xiàn)：當(dāng)A列大于B列時(shí)選擇A列否則選擇B列，當(dāng)B列大于C列時(shí)選擇B列否則選擇C列。

[php]select

case

when first_namemiddle_name then

case when first_namelast_name then first_name

else last_name end

else

case when middle_namelast_name then middle_name else last_name

end

end as name

from member

[/php]

8請(qǐng)簡(jiǎn)述項(xiàng)目中優(yōu)化sql語(yǔ)句執(zhí)行效率的方法,從哪些方面,sql語(yǔ)句性能如何分析?

ANSWER: sql優(yōu)化有鳥用，不如直接加索引。

9 如果模板是用smarty模板。怎樣用section語(yǔ)句來(lái)顯示一個(gè)名為$data的數(shù)組。比如：

[php]$data = array(

[0] = array( [id]=8 [name]=’name1′)

[1] = array( [id]=10 [name]=’name2′)

[2] = array( [id]=15 [name]=’name3′)

……

)[/php]

寫出在模板頁(yè)的代碼？ 若用foreach語(yǔ)句又要怎樣顯示呢？

占無(wú)答案.

10 寫一個(gè)函數(shù)，能夠遍歷一個(gè)文件夾下的所有文件和子文件夾。（目錄操作）

[php] ?php

$d = dir(dirname(__file__));

//echo "Handle: " . $d-handle . "\n";

//echo "Path: " . $d-path . "\n";

while ( false !== ($entry = $d-read ()) ) {

echo $entry . "br /";

}

$d-close ();

[/php]

11 兩張表 city表和province表。分別為城市與省份的關(guān)系表。

city:

id City Provinceid

1 廣州 1

2 深圳 1

3 惠州 1

4 長(zhǎng)沙 2

5 武漢 3

………. 廣州

province:

id Province

1 廣東

2 湖南

3 湖北

……….

（1） 寫一條sql語(yǔ)句關(guān)系兩個(gè)表，實(shí)現(xiàn)：顯示城市的基本信息。？

（2） 顯示字段：城市id ，城市名， 所屬省份 。

如：

Id（城市id） Cityname(城市名) Privence(所屬省份)

。。。。。。。。。

。。。。。。。。。

（2）如果要統(tǒng)計(jì)每個(gè)省份有多少個(gè)城市，請(qǐng)用group by 查詢出來(lái)。？

顯示字段：省份id ，省份名，包含多少個(gè)城市。

ANSWER:

1.select A.id,A.Cityname,B.Province from city A,province B where A.provinceid=B.id

2.select B.id,B.Province,count(*) as num from city A,province B where A.provinceid=B.id group by B.id

12. 按照你的經(jīng)驗(yàn)請(qǐng)簡(jiǎn)述軟件工程進(jìn)行軟件開發(fā)的步驟。以下工具Rational Rose、PowerDesigner、Project、VSS或CVS、TestDirector使用過(guò)那種,有缺點(diǎn)是什么？

公司用dbdesigner及cvs,測(cè)試管理工具用的是Mantis

13. 請(qǐng)簡(jiǎn)述操作系統(tǒng)的線程與進(jìn)程的區(qū)別。列舉LINUX下面你使用過(guò)的軟件？

14. 請(qǐng)使用偽語(yǔ)言結(jié)合數(shù)據(jù)結(jié)構(gòu)冒泡排序法對(duì)以下一組數(shù)據(jù)進(jìn)行排序 10 2 36 14 10 25 23 85 99 45。

[php]function bubble_sort( $arr){

$number=count($arr);

for($i=0;$i$number-1;$i++){

for($j=0;$j$number-1-$i;$j++){

if($arr[$j]$arr[$j+1]){

$tmp=$arr[$j];

$arr[$j]=$arr[$j+1];

$arr[$j+1]=$tmp;

}

}

}

}

$str="10 2 36 14 10 25 23 85 99 45";

$arr=explode(" ",$str);

bubble_sort($arr);

echo "pre";

var_dump($arr);

[/php]

網(wǎng)站標(biāo)題：php數(shù)據(jù)結(jié)構(gòu)算法面試題,高級(jí)php面試題及部分答案
本文URL：http://chinadenli.net/article20/dsggcco.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、標(biāo)簽優(yōu)化、App開發(fā)、云服務(wù)器、自適應(yīng)網(wǎng)站、網(wǎng)站營(yíng)銷

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)