璺宠〃 skip list

寮ヨˉ閾捐〃鐨勭己闄 鍗囩淮 绌洪棿鎹㈡椂闂
– 濡備綍缁欓摼琛ㄥ姞閫
-娣诲姞绗竴绾х储寮曪紝绗簩绾х储寮 (log2n涓骇绱㈠紩)
– 鏃堕棿澶嶆潅搴﹀垎鏋
– n/2,n/4,n/8绗琸绾х储寮曡妭鐐圭殑涓暟灏辨槸n/(2^k),鍋囪绱㈠紩鏈塰绾э紝鏈楂樼骇鐨勭储寮曟湁2涓俷/(2^h)=2,浠庤屾眰寰梙=log2(n)-1
– 澧炲姞鍜屽垹闄ょ殑鏃跺欙紝瑕佹洿鏂扮储寮曪紝鎵浠ュ鍔犲拰鍒犻櫎鐨勬椂闂村鏉傚害灏变細缂栫▼logn浜
– 璺宠〃鐨勭┖闂村鏉傚害鍒嗘瀽
– 姣2涓妭鐐规娊1涓紝姣忓眰绱㈠紩鑺傜偣 n/2,n/4n/8…8,4,2 绌洪棿澶嶆潅搴︽槸O(n)

璺宠〃鐨勫簲鐢

redis鐨勮烦琛

鍙傝冧簬 https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html(redis璁捐涓庡疄鐜)
– redis涓轰簡婊¤冻鑷韩鐨勫姛鑳介渶瑕侊紝淇敼浜
– 鍏佽閲嶅鐨剆core鍊硷紝澶氫釜涓嶅悓鐨刴ember鐨剆core鍊煎彲浠ョ浉鍚屻
– 杩涜瀵规瘮鎿嶄綔鏃讹紝涓嶄粎瑕佹鏌core鍊硷紝杩樿妫鏌ember;褰搒core鍊煎彲浠ラ噸澶嶆椂锛屽崟闈爏core鍊兼棤娉曞垽鏂竴涓厓绱犵殑韬唤锛屾墍浠ラ渶瑕佽繛member鍩熼兘涓骞舵鏌ユ墠琛屻
– 姣忎釜鑺傜偣閮藉甫鏈変竴涓珮搴︿负1灞傜殑鍚庨鎸囬拡锛岀敤浜庝粠琛ㄥ熬鏂瑰悜琛ㄥご鏂瑰悜杩唬锛涘綋鎵цzrevrange鎴杬revrangebyscore绫讳互閫嗗簭澶勭悊鏈夊簭闆嗙殑鍛戒护鏃讹紝灏变細鐢ㄥ埌杩欎釜灞炴с
杩欎釜淇敼鐗堢殑璺宠穬琛ㄧ敱 redis.h/zskiplist 缁撴瀯瀹氫箟锛

typedef struct zskiplist {

    // 澶磋妭鐐癸紝灏捐妭鐐
    struct zskiplistNode *header, *tail;

    // 鑺傜偣鏁伴噺
    unsigned long length;

    // 鐩墠琛ㄥ唴鑺傜偣鐨勬渶澶у眰鏁
    int level;

} zskiplist;

璺宠穬琛ㄧ殑鑺傜偣鐢 redis.h/zskiplistNode 瀹氫箟锛

typedef struct zskiplistNode {

    // member 瀵硅薄
    robj *obj;

    // 鍒嗗
    double score;

    // 鍚庨鎸囬拡
    struct zskiplistNode *backward;

    // 灞
    struct zskiplistLevel {

        // 鍓嶈繘鎸囬拡
        struct zskiplistNode *forward;

        // 杩欎釜灞傝法瓒婄殑鑺傜偣鏁伴噺
        unsigned int span;

    } level[];

} zskiplistNode;
redis> ZADD s 6 x 10 y 15 z
(integer) 3

redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

鍦ㄥ簳灞傚疄鐜颁腑锛 Redis 涓 x 銆 y 鍜 z 涓変釜 member 鍒嗗埆鍒涘缓浜嗕笁涓瓧绗︿覆锛 鍊煎垎鍒负 double 绫诲瀷鐨 6 銆 10 鍜 15 锛 鐒跺悗鐢ㄨ烦璺冭〃灏嗚繖浜涙寚閽堟湁搴忓湴淇濆瓨璧锋潵锛 褰㈡垚杩欐牱涓涓烦璺冭〃

LRU缂撳瓨鏈哄埗

http://leetcode-cn.com/problems/lru-cache (LRU缂撳瓨鏈哄埗)杩愮敤浣犳墍鎺屾彙鐨勬暟鎹粨鏋勶紝璁捐鍜屽疄鐜颁竴涓 LRU (鏈杩戞渶灏戜娇鐢) 缂撳瓨鏈哄埗銆傚畠搴旇鏀寔浠ヤ笅鎿嶄綔锛 鑾峰彇鏁版嵁 get 鍜 鍐欏叆鏁版嵁 put 銆傝幏鍙栨暟鎹 get(key) 濡傛灉瀵嗛挜 (key) 瀛樺湪浜庣紦瀛樹腑锛屽垯鑾峰彇瀵嗛挜鐨勫硷紙鎬绘槸姝f暟锛夛紝鍚﹀垯杩斿洖 -1銆傚啓鍏ユ暟鎹 put(key, value) – 濡傛灉瀵嗛挜宸茬粡瀛樺湪锛屽垯鍙樻洿鍏舵暟鎹硷紱濡傛灉瀵嗛挜涓嶅瓨鍦紝鍒欐彃鍏ヨ缁勩屽瘑閽/鏁版嵁鍊笺嶃傚綋缂撳瓨瀹归噺杈惧埌涓婇檺鏃讹紝瀹冨簲璇ュ湪鍐欏叆鏂版暟鎹箣鍓嶅垹闄ゆ渶涔呮湭浣跨敤鐨勬暟鎹硷紝浠庤屼负鏂扮殑鏁版嵁鍊肩暀鍑虹┖闂淬傝繘闃:
浣犳槸鍚﹀彲浠ュ湪聽O(1) 鏃堕棿澶嶆潅搴﹀唴瀹屾垚杩欎袱绉嶆搷浣滐紵
绀轰緥:
LRUCache cache = new LRUCache( 2 /* 缂撳瓨瀹归噺 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 杩斿洖 1
cache.put(3, 3); // 璇ユ搷浣滀細浣垮緱瀵嗛挜 2 浣滃簾
cache.get(2); // 杩斿洖 -1 (鏈壘鍒)
cache.put(4, 4); // 璇ユ搷浣滀細浣垮緱瀵嗛挜 1 浣滃簾
cache.get(1); // 杩斿洖 -1 (鏈壘鍒)
cache.get(3); // 杩斿洖 3
cache.get(4); // 杩斿洖 4

All posts

Other pages

鍙戣〃璇勮

閭鍦板潃涓嶄細琚叕寮銆 蹇呭~椤瑰凡鐢*鏍囨敞