clojure - assoc in clojure: 内部の説明

Question

のコードは次のassocとおりです。

(def assoc
 (fn assoc
   ([map key val] (. clojure.lang.RT (assoc map key val)))))

1. とはどういう意味clojure.lang.RTですか?

2. assocベクター/マップでの呼び出しの複雑さは?

3. によって作成された構造にアクセスすることの複雑さはassoc?

Answer 1

1. clojure.lang.RTメインの Clojure RunTime クラスです。言語のコアを構成するほとんどのメソッドが含まれています。

2. assocベクトルとマップを含むすべての連想データ構造に対して O(1) です。array-map最初のいくつかのアイテムに対して線形で開始し、それ自体を a に昇格させて、hash-mapO(1) にもします。もちろん、必要に応じて、O(1) 以外のものを使用して連想インターフェイスを実装することもできます。

3. 技術的には、別のマップを呼び出して作成されたマップまたはベクター内のアイテムのアクセス時間assocは O(log32 N) です。これらのデータ構造には最大 2^32 アイテムのサイズの上限があるため、実質的に一定の時間である最大ツリー深度は 6 になります。

Clojure の連想データ構造は、空間ではすべて O(nLog n) です (ツリーであるため)。