11

私はRが初めてです。

ツリー ノードに似たクラスを定義しようとしています。つまり、左ノードと右ノードがあり、親ノードと同じクラスである必要があります。したがって、クラスを次のように定義します。

setClass('Node', representation=(left='Node',right='Node', ...))

プロトタイプを設定して Node のデフォルト値を NULL にしたいのですが、R は次のように言っています。

  invalid class "Node" object: invalid object for slot "left" in class "bicluster": got class "NULL", should be or extend class "Node"

しかし、デフォルト値を NULL に指定しないと、デフォルト値は深さ 4 の再帰ノードになり、リソースの無駄遣いになると思います。

私の考慮は不要ですか、それともより良い方法はありますか？

4

2 に答える 2

9

setClassUnion("listOrNULL",members=c("list", "NULL"))かつては、リストとして定義されたスロットに NULL を取得するために使用する必要がありました。それが現在利用可能なクラスだと思います。セットアップが不完全な間はテストできませんが、スーパークラス "NodeOrNull" を定義すると、最初の障壁を乗り越えることができます。

于 2011-09-19T05:53:12.833 に答える
7

これは修正された回答です。

クラス ユニオンはファンキーです。クラスを既存の階層の中間に効果的に挿入するため、拡張するものが突然list拡張しlistOrNULLます。

代わりに、「空」または「内部」のいずれかになる「ツリー」を表す小さなクラス階層を作成します。"Internal" クラスには、データ ("ANY" 型) を格納するためのスロットと、"Tree" 要素となる左右のリンクがあります。

setClass("Tree")

setClass("Empty", contains="Tree")

setClass("Internal", contains="Tree",
         representation=representation(elem="ANY", left="Tree", right="Tree"),
         prototype=prototype(left=new("Empty"), right=new("Empty")))

空のツリーを作成するメソッドと、要素と左右の子孫からツリーを作成するメソッドを使用して、ツリーのコンストラクターを作成します。

setGeneric("Tree", function(elem, left, right) standardGeneric("Tree"),
           signature="elem")

setMethod(Tree, "missing", function(elem, left, right) new("Empty"))

setMethod(Tree, "ANY", function(elem, left, right) {
    new("Internal", elem=elem, left=left, right=right)
})

基本的な操作は、要素xをツリーに挿入することですt

setGeneric("insert", function(x, t) standardGeneric("insert"))

setMethod(insert, c("ANY", "Empty"), function(x, t) {
    Tree(x, Tree(), Tree())
})

setMethod(insert, c("ANY", "Internal"), function(x, t) {
    if (x < t@elem) {
        l <- insert(x, t@left)
        r <- t@right
    } else {
        l <- t@left
        r <- insert(x, t@right)
    }
    Tree(t@elem, l, r)
})

別の操作は、メンバーシップをテストすることです

setGeneric("member", function(x, t) standardGeneric("member"))

setMethod(member, c("ANY", "Empty"), function(x, t) FALSE)

setMethod(member, c("ANY", "Internal"), function(x, t) {
    if (x < t@elem) member(x, t@left)
    else if (t@elem < x) member(x, t@right)
    else TRUE
})

この実装の興味深い機能的な特性は、永続的であることです。

> t <- Tree()
> t1 <- insert(10, t)
> t2 <- insert(5, t1)
> t3 <- insert(7, t2)
> t4 <- insert(15, t3)
> which(sapply(1:20, member, t4))
[1]  5  7 10 15
> which(sapply(1:20, member, t2))
[1]  5 10

S4 クラス作成の非効率性と、ツリーの変更 (ノードの追加など) がパス内のすべてのノードを新しいノードにコピーするため、多くの更新がある場合、これは効率的ではありません。別のアプローチでは、ツリーmatrixを左、右、値のトリプルとして表します。インスタンスの更新によって新しいインスタンスが作成され、すべてが複製されるため、S4 実装のパフォーマンスは依然として低くなります。したがって、フィールド「値」（ツリーが保持するはずのベクトルmatrixと左右の関係のベクトル）を持つ参照クラスになります。

于 2011-09-19T19:02:09.423 に答える