5

マルチツリーを検索するより効率的な方法があるかどうか疑問に思っています。私は最近、以下に示すプロジェクトのマルチツリー データ構造を構築しました。 ArrayLists を使用したマルチツリー データ構造

洞窟は、パーティーを配列リストに保持します。さまざまなパーティーがさまざまなクリーチャーを保持します。異なるクリーチャーは異なるアイテムを保持します。

ツリー全体を検索して、オブジェクトをインデックスなどの属性に一致させる方法が必要でした。これは、すべての ArrayList を検索して、パーティー、クリーチャー、宝物、またはアーティファクトのいずれかがインデックスと呼ばれる int と一致するかどうかを確認する私のプログラムのスニペットです。

編集(コードの説明) クラス Party、Creature、Treasure、および Artifact にはすべて、インデックス、名前、タイプなどの属性があります。マルチツリーにはルート ノートとして設定された洞窟があります。Cave には、多数の Party オブジェクトを含むことができる ArrayList があります。各パーティーには、多数の Creature オブジェクトを含むことができる ArrayList があります。各クリーチャーには 2 つの配列リストがあり、1 つは Artifact オブジェクトを保持し、もう 1 つは Treasure オブジェクトを保持します。

以下では、探している特定のインデックスを保持しているパーティー、クリーチャー、アーティファクト、または宝物を確認するために検索しています。これを行うには、パーティーを繰り返し、各パーティーでクリーチャーを調べ、各クリーチャーでアーティファクトと宝物を調べます。そのため、for ループ内に非常に多くの for ループがあります :(.

case 0 :
            int index =                 Integer.parseInt( stat );
            for ( Party p : SorcerersCave.theCave.parties ) {
                if ( index == p.getIndex()) {
                    generateInterface.theGame.printOutput( "\t" + p );
                    break;
                } else {
                    for ( Creature c : p.members ){
                        if ( index == c.getIndex() ){
                            generateInterface.theGame.printOutput( "\t" + c );
                            break;
                        } else {
                            for ( Treasure t : c.inventory ){
                                if ( index == t.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + t );
                                    break;
                                }
                            }
                            for ( Artifact a : c.artifacts ){
                                if ( index == a.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + a );
                                    break;
                                }
                            }
                        }
                    }
                }
            }

このコードは複雑すぎて、従うのが難しいと思います。コードは機能しますが、そうでなければ本当に見栄えの良いコードに醜い汚れがあります。これを行うためのより良い方法、またはそれを改善する方法さえ見つけるために、私は周りを見回してきました。

注* プロジェクトの要件により、すべてのオブジェクトを同じ ArrayList に配置することは禁じられています。

4

7 に答える 7

2

クラスは、次のSearchableByIndexような共通のインターフェースを実装でき、ツリー内のすべてのクラスによって実装されます。

public interface SearchableByIndex {
    public SearchableByIndex searchByIndex(int index);
    public int getIndex();
}

次にCave、次のコードPartyをCreature要求します。

public SearchableByIndex searchByIndex(int index) {
    if (getIndex() == index) {
        return this;
    } else {
        for (Party party : parties) {    // or Creature creature : members etc.
            SearchableByIndex found = party.searchByIndex(index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}

トレジャーとアーティファクトのバージョン:

public SearchableByIndex searchByIndex(int index) {
    return (getIndex() == index) ? this : null;
}

そして、そこにあるネストされたループの代わりに、

case 0:
    int index = Integer.parseInt(stat);
    SearchableByIndex foundItem = SorcerersCave.theCave.searchByIndex(index);
    if (foundItem != null) {
        generateInterface.theGame.printOutput("\t" + foundItem);
    } else {
        // print out that the item was not found
    }
    break;

searchByIndex()すべてのクラスのメソッドは繰り返しのように見えるかもしれませんが、それは OOP の方法です。このようにして、すべてのクラスがすべてのコンテンツを検索します。あなたの場合、すべてのクラスのコードは非常に似ています（唯一の変更は for ループのある行です）が、これは偶然であると考えることができます-どのクラスにも必要なデータが含まれる可能性があり、他のクラスは気にする必要はありませんデータの保存方法について。

将来、クラスの 1 つがより検索可能なデータ ( Treasure、ArtifactおよびHostage?) を保持する場合、またはそのデータの構造を変更したい場合 (可能であれば、 を検討してください!)、メソッドHashMapを変更するだけで済みます。searchByIndex()特定のクラス。

また、データがどのように含まれているかを知っているのは、データを含むクラスだけです。あなたが今持っている方法では、検索を呼び出す他のクラスは、すべてのクラスにデータがどのように格納されているかを正確に知っています-これはすべきではありません。1 つのクラスが変更されると、他のクラスの内部コードが壊れます。たとえば、Caveクラスはドキュメントに、さまざまなPartyインスタンスなどを保持し、 で検索するとそれらの一部を提供できることを述べる必要がありますsearchForIndex()。

于 2013-06-25T06:07:56.203 に答える
0

より規則的な構造を使用できますか? これらの行に沿ったもの（私は疑似コードを使用しています）：

interface INode { ... stuff kept in nodes is described here ... }
interface ITree extends INode { bool HasId(int id); ITree[] Children; }

INode SearchTreeForId(ITree[] children, int id) {
  for each (child in children) {
    match = (child.HasId(id) ? child : SearchTreeForId(child.Children));
    if (match != null) return match;
  }
  return null;
}

// Then...
{
  node = SearchTreeForId(SorcerersCave.theCave.Parties, id);
  if (node != null) generateInterface(...);
}
于 2013-06-25T05:37:40.157 に答える
0

ヘルパー メソッドを使用して深さ優先検索を実行します。

private Interface IndexObject
{
    // Interface will be used in dfsList
    public int getIndex();
}

private Interface ListObject extends IndexObject
{
    // For classes with sublists
    public ArrayList<IndexObject> getList();
}

public void search(int index) {
    Object found = dfsList(parties, index);
}

// Helper method
public Object dfsList(ArrayList<IndexObject> aList, int index) {
    for (IndexObject obj : aList) {
        if (obj.getIndex() == index) {
            return obj;
        }
        else if (obj instanceof ListObject) {
            IndexObject found = dfsList(obj.getList(), index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}
于 2013-06-25T05:58:50.857 に答える