次のようなツリー構造の場合
public class Node implements Comparable<Node> {
private List<Node> nodes=new ArrayList<Node>();
private String name="";
private List<String> leaves=new ArrayList<String>();
private Node parent=null;
public List<Node> getNodes() {
return nodes;
}
public void setNodes(List<Node> nodes) {
this.nodes = nodes;
}
public List<String> getLeaves() {
return leaves;
}
public void setLeaves(List<String> leaves) {
this.leaves = leaves;
}
@Override
public int compareTo(Node o) {
return this.getName().compareTo(o.getName());
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public int getDepth() {
int depth = 0;
Node parent = this.getParent();
while (parent != null) {
depth++;
parent = parent.getParent();
}
return depth;
}
}
leaves ノードから、そのノードのすべての個別の直接および間接リーフ（上記の場合は文字列がリーフになります）をソートされた順序で返すメソッドが必要です。
上記は、テストとデモンストレーションを容易にするために非常に分解されたデータ構造です。私は次の3つのアプローチを試しました。
アプローチA深さが約20の場合、非常に遅くなります。これは、最も深い葉がその祖先ごとに1回ずつ、数回トラバースされるため、同じパスが複数回トラバースされるためです。
public List<String> getLeavesDeep1() {
Set<String> leaves = new TreeSet<String>();
leaves.addAll(getLeaves());
for (Node node : getNodes()) {
leaves.addAll(node.getLeavesDeep1());
}
return new ArrayList<String>(leaves);
}
平均：12694ミリ秒/並べ替え/区別なし>平均：471ミリ秒
アプローチBノードの数がリーフよりも比較的少ないため、Aより少し速く、アプローチAを使用しますが、ノードに対して、次に各ノードに対して、直接リーフのみを取得します。
private List<Node> getNodesDeep2() {
Set<Node> nodes = new TreeSet<Node>();
nodes.addAll(getNodes());
for (Node node : getNodes()) {
nodes.addAll(node.getNodesDeep2());
}
return new ArrayList<Node>(nodes);
}
public List<String> getLeavesDeep2() {
Set<String> leaves = new TreeSet<String>();
leaves.addAll(getLeaves());
for (Node node : getNodesDeep2()) {
leaves.addAll(node.getLeaves());
}
return new ArrayList<String>(leaves);
}
平均：4355ミリ秒/並べ替え/区別なし>平均：2406ミリ秒
アプローチCTreeSetを避け、ArrayListを使用し、戻る直前にソートおよびフィルター処理（ただし、ソート/区別するための最良の方法ではありません）
private List<Node> getNodesDeep3() {
List<Node> nodes = new ArrayList<Node>();
nodes.addAll(getNodes());
for (Node node : getNodes()) {
nodes.addAll(node.getNodesDeep3());
}
return new ArrayList<Node>(new TreeSet<Node>(nodes));
}
public List<String> getLeavesDeep3() {
List<String> leaves = new ArrayList<String>();
leaves.addAll(getLeaves());
for (Node node : getNodesDeep3()) {
leaves.addAll(node.getLeaves());
}
return new ArrayList<String>(new TreeSet<String>(leaves));
}
平均：4400
より高速なものを探していると、使用できる特定のツリートラバーサルがあることはわかっていますが、存在する場合はもっと単純なものを使用したいと思います。PSこれらは、現時点では検索のユースケースではありません。私の実際のクラスでは、葉が単純な文字列ではなくPOJOであるため、構造がはるかに複雑であるため、時間は上記の場合の約3倍になります。
以下は私が時間を取得するために使用したテストです
private static final int NODES = 5;
private static final int LEAVES = 25;
private static final int DEPTH = 8;
public void addChildren(Node parent) {
List<Node> nodes = new ArrayList<Node>();
List<String> leaves = new ArrayList<String>();
for (int i = 0; i < LEAVES; i++) {
leaves.add(String.format("%s_leaf_%s", parent.getName(), i));
}
for (int i = 0; i < NODES; i++) {
Node child = new Node();
child.setParent(parent);
child.setName(String.format("%s_%s", parent.getName(), i));
nodes.add(child);
if (child.getDepth() < DEPTH) {
addChildren(child);
}
}
parent.setNodes(nodes);
parent.setLeaves(leaves);
}
@Test
public void testCase() {
long start, tot=0;
long t = 0;
List<String> leaves;
Node target = new Node();
target.setName("Root");
addChildren(target);
for (int i = 0; i < 10; i++) {
start = System.currentTimeMillis();
leaves = target.getLeavesDeep5();
t = System.currentTimeMillis() - start;
tot += t;
System.out.println(leaves.size() + " " + t);
}
System.out.println("Avg: " + (tot / 10));
}
ソリューションをその言語に緊密に結び付けない限り、疑似コードを含むすべての言語での回答が受け入れられます（例外：純粋なJavaコードは2番目の句から禁止されています）