<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 集合 [TOC=2,3] `REDIS_SET` (集合)是 [SADD](http://redis.readthedocs.org/en/latest/set/sadd.html#sadd "(in Redis 命令參考 v2.8)") 、 [SRANDMEMBER](http://redis.readthedocs.org/en/latest/set/srandmember.html#srandmember "(in Redis 命令參考 v2.8)") 等命令的操作對象,它使用 `REDIS_ENCODING_INTSET` 和 `REDIS_ENCODING_HT` 兩種方式編碼: ![digraph redis_set { node [shape=plaintext, style = filled]; edge [style = bold]; // type REDIS_SET [label="集合\nREDIS_SET", fillcolor = "#95BBE3"]; // encoding REDIS_ENCODING_INTSET [label="intset\nREDIS_ENCODING_INTSET", fillcolor = "#FADCAD"]; REDIS_ENCODING_HT [label="字典\nREDIS_ENCODING_HT", fillcolor = "#FADCAD"]; // edge REDIS_SET -> REDIS_ENCODING_INTSET; REDIS_SET -> REDIS_ENCODING_HT; // datastruct 1 intset [label="intset.h/intset"]; REDIS_ENCODING_INTSET -> intset; // datastruct 2 dict [label="dict.h/dict"]; REDIS_ENCODING_HT -> dict;}](https://box.kancloud.cn/2015-09-13_55f4effcd9127.svg) ### 編碼的選擇 第一個添加到集合的元素,決定了創建集合時所使用的編碼: - 如果第一個元素可以表示為 `long long` 類型值(也即是,它是一個整數), 那么集合的初始編碼為 `REDIS_ENCODING_INTSET` 。 - 否則,集合的初始編碼為 `REDIS_ENCODING_HT` 。 ### 編碼的切換 如果一個集合使用 `REDIS_ENCODING_INTSET` 編碼,那么當以下任何一個條件被滿足時,這個集合會被轉換成 `REDIS_ENCODING_HT` 編碼: - `intset` 保存的整數值個數超過 `server.set_max_intset_entries` (默認值為 `512` )。 - 試圖往集合里添加一個新元素,并且這個元素不能被表示為 `long long` 類型(也即是,它不是一個整數)。 ### 字典編碼的集合 當使用 `REDIS_ENCODING_HT` 編碼時,集合將元素保存到字典的鍵里面,而字典的值則統一設為 `NULL` 。 作為例子,以下圖片展示了一個以 `REDIS_ENCODING_HT` 編碼表示的集合,集合的成員為 `elem1` 、 `elem2` 和 `elem3` : ![digraph hash_table_example { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes ht1 [label="<dictht>dictht |<table> table | size:4 | sizemask:3 | used:3", fillcolor = "#A8E270"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#95BBE3"]; pair_1 [label="<head>dictEntry |{<key>key\nelem1 |<value>value\nNULL |<next>next\nNULL}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{<key>key\nelem2 |<value>value\nNULL |<next>next\nNULL}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{<key>key\nelem3 |<value>value\nNULL |<next>next\nNULL}", fillcolor = "#FADCAD"]; null1 [label="NULL", shape=plaintext]; // lines ht1:table -> bucket:head; bucket:table0 -> pair_1:head; bucket:table1 -> null1; bucket:table2 -> pair_2:head; bucket:table3 -> pair_3:head;}](https://box.kancloud.cn/2015-09-13_55f4effce3008.svg) ### 集合命令的實現 Redis 集合類型命令的實現,主要是對 `intset` 和 `dict` 兩個數據結構的操作函數的包裝,以及一些在兩種編碼之間進行轉換的函數,大部分都沒有什么需要解釋的地方,唯一比較有趣的是 [SINTER](http://redis.readthedocs.org/en/latest/set/sinter.html#sinter "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/set/sinter.html#sinter] 、 [SUNION](http://redis.readthedocs.org/en/latest/set/sunion.html#sunion "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/set/sunion.html#sunion] 等命令之下的算法實現,以下三個小節就分別討論它們所使用的算法。 ### 求交集算法 [SINTER](http://redis.readthedocs.org/en/latest/set/sinter.html#sinter "(in Redis 命令參考 v2.8)") 和 [SINTERSTORE](http://redis.readthedocs.org/en/latest/set/sinterstore.html#sinterstore "(in Redis 命令參考 v2.8)") 兩個命令所使用的求并交集算法可以用 Python 表示如下: ~~~ # coding: utf-8 def sinter(*multi_set): # 根據集合的基數進行排序 sorted_multi_set = sorted(multi_set, lambda x, y: len(x) - len(y)) # 使用基數最小的集合作為基礎結果集,有助于降低常數項 result = sorted_multi_set[0].copy() # 剔除所有在 sorted_multi_set[0] 中存在 # 但在其他某個集合中不存在的元素 for elem in sorted_multi_set[0]: for s in sorted_multi_set[1:]: if (not elem in s): result.remove(elem) break return result ~~~ 算法的復雜度為 \(O(N^2)\) ,執行步數為 \(S * T\) ,其中 \(S\) 為輸入集合中基數最小的集合,而 \(T\) 則為輸入集合的數量。 ### 求并集算法 [SUNION](http://redis.readthedocs.org/en/latest/set/sunion.html#sunion "(in Redis 命令參考 v2.8)") 和 [SUNIONSTORE](http://redis.readthedocs.org/en/latest/set/sunionstore.html#sunionstore "(in Redis 命令參考 v2.8)") 兩個命令所使用的求并集算法可以用 Python 表示如下: ~~~ # coding: utf-8 def sunion(*multi_set): result = set() for s in multi_set: for elem in s: # 重復的元素會被自動忽略 result.add(elem) return result ~~~ 算法的復雜度為 \(O(N)\) 。 ### 求差集算法 Redis 為 [SDIFF](http://redis.readthedocs.org/en/latest/set/sdiff.html#sdiff "(in Redis 命令參考 v2.8)") 和 [SDIFFSTORE](http://redis.readthedocs.org/en/latest/set/sdiffstore.html#sdiffstore "(in Redis 命令參考 v2.8)") 兩個命令準備了兩種求集合差的算法。 以 Python 代碼表示的算法一定義如下: ~~~ # coding: utf-8 def sdiff_1(*multi_set): result = multi_set[0].copy() sorted_multi_set = sorted(multi_set[1:], lambda x, y: len(x) - len(y)) # 當 elem 存在于除 multi_set[0] 之外的集合時 # 將 elem 從 result 中刪除 for elem in multi_set[0]: for s in sorted_multi_set: if elem in s: result.remove(elem) break return result ~~~ 這個算法的復雜度為 \(O(N^2)\) ,執行步數為 \(S*T\) ,其中 \(S\) 為輸入集合中基數最小的集合,而 \(T\) 則為除第一個集合之外,其他集合的數量。 以 Python 代碼表示的算法二定于如下: ~~~ # coding: utf-8 def sdiff_2(*multi_set): # 用第一個集合作為結果集的起始值 result = multi_set[0].copy() for s in multi_set[1:]: for elem in s: # 從結果集中刪去其他集合中包含的元素 if elem in result: result.remove(elem) return result ~~~ 這個算法的復雜度同樣為 \(O(N^2)\) ,執行步數為 \(S\) ,其中 \(S\) 為所有集合的基數總和。 Redis 使用一個程序決定該使用那個求差集算法,程序用 Python 表示如下: ~~~ # coding: utf-8 from sdiff_1 import sdiff_1 from sdiff_2 import sdiff_2 def sdiff(*multi_set): # 算法一的常數項較低,給它一點額外的優先級 algo_one_advantage = 2 algo_one_weight = len(multi_set[0]) * len(multi_set[1:]) / algo_one_advantage algo_two_weight = sum(map(len, multi_set)) if algo_one_weight <= algo_two_weight: return sdiff_1(*multi_set) else: return sdiff_2(*multi_set) ~~~
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看