gpt4 book ai didi

java - 像树一样使用父引用对列表进行排序

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:57:33 26 4
gpt4 key购买 nike

情况

我有一个包含数据对象的无序列表,每个对象都有一个对其父对象的引用。该列表应通过引用父项进行排序,最终列表应按顺序排列,就好像它是一棵树一样。 children 应该按名字排序。

数据对象:

/**
* Object with a parent relationship
*/
public static class Node {

Node parent;
String text;
int level = -1;

public Node(Node parent, String text) {
this.parent = parent;
this.text = text;
}

public String toString() {
return text;
}
}

示例树:

/**
* Create example data
* @return
*/
private static List<Node> createExampleList() {

List<Node> list = new ArrayList<>();

Node root = new Node(null, "root");

Node a = new Node(root, "a");
Node b = new Node(root, "b");
Node c = new Node(root, "c");

Node a1 = new Node(a, "a1");
Node a2 = new Node(a, "a2");
Node a3 = new Node(a, "a3");

Node b1 = new Node(b, "b1");
Node b2 = new Node(b, "b2");
Node b3 = new Node(b, "b3");

Node c1 = new Node(c, "c1");
Node c2 = new Node(c, "c2");
Node c3 = new Node(c, "c3");


Node b11 = new Node(b1, "b11");
Node b12 = new Node(b1, "b12");
Node b13 = new Node(b1, "b13");


list.add(root);

list.add(a);
list.add(b);
list.add(c);

list.add(a1);
list.add(a2);
list.add(a3);

list.add(b1);
list.add(b11);
list.add(b12);
list.add(b13);

list.add(b2);
list.add(b3);

list.add(c1);
list.add(c2);
list.add(c3);

return list;
}

问题

我当前的解决方案占用大量内存。我到目前为止的算法:

  • 为每个对象创建一个 DefaultMutableTreeNode 并将其放入映射中
  • 遍历所有对象,获取对象和父对象的 DefaultMutableTreeNode 表示并将节点添加到父对象
  • 使用DefaultMutableTreeNode 的枚举机制来遍历树并将每个项目迭代地添加到列表中

问题

有谁知道更快、内存效率更高的方法吗?

代码

这是我目前的代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import javax.swing.tree.DefaultMutableTreeNode;

/**
* Sort a list of parent-child related items. The resulting list should be ordered as if the list were a tree.
* The algorithm converts the list to an intermediary tree using {@link DefaultMutableTreeNode} as a wrapper.
* That way you can create the final list depending on your needs, i. e. preorder enumeration, breadth first enumeration, etc.
*/
public class Main {

public static void main(String[] args) {

// create example list
List<Node> nodes = createExampleList();

// shuffle
Collections.shuffle(nodes);

logList("shuffled list", nodes);

// convert list -> tree and tree -> sorted list
DefaultMutableTreeNode root = createTree(nodes);
List<Node> sortedList = createList(root);

logList("sorted list", sortedList);

System.exit(0);
}

private static DefaultMutableTreeNode createTree(List<Node> nodes) {

// we want the final sublists sorted by name
Collections.sort(nodes, new Comparator<Node>() {

@Override
public int compare(Node o1, Node o2) {
return o1.text.compareTo(o2.text);
}

});

// create DefaultMutableTreeNode objects for every node
Map<Node, DefaultMutableTreeNode> treeNodeMap = new HashMap<>();
for (Node node : nodes) {
treeNodeMap.put(node, new DefaultMutableTreeNode(node));
}

DefaultMutableTreeNode root = null;

// connect the tree nodes depending on their relation
for (Node node : nodes) {

DefaultMutableTreeNode treeNode = treeNodeMap.get(node);

// find root node
if (node.parent == null) {

root = treeNode;

}
// otherwise attach the node to its parent
else {

// get the parent treenode
DefaultMutableTreeNode parentTreeNode = treeNodeMap.get(node.parent);

// attach the current node to its parent
parentTreeNode.add(treeNode);

}
}

return root;
}

private static List<Node> createList(DefaultMutableTreeNode root) {

List<Node> nodes = new ArrayList<>();

// iterate through the tree in preorder, extract the node object and add it to the list. in addition the level is set as meta information, used later for indenting during logging
Enumeration<DefaultMutableTreeNode> enumeration = root.preorderEnumeration();
while (enumeration.hasMoreElements()) {

// get tree node
DefaultMutableTreeNode treeNode = enumeration.nextElement();

// get node from tree node
Node node = (Node) treeNode.getUserObject();

// update the level
node.level = treeNode.getLevel();

// add to list
nodes.add(node);
}

return nodes;
}

/**
* Log the node list
* @param text
* @param list
*/
private static void logList(String text, Collection<Node> list) {

System.out.println();
System.out.println(text);
System.out.println();

for (Node item : list) {
String paddedString = createString( item.level * 2, ' ');
System.out.println( " " + paddedString + item);
}

}

/**
* Create a string filled with {@code length} times the given {@code character}.
* @param length
* @param character
* @return
*/
public static String createString(int length, char character) {

if (length <= 0)
return "";

char[] array = new char[length];

Arrays.fill(array, character);

return new String(array);
}

/**
* Create example data
* @return
*/
private static List<Node> createExampleList() {

List<Node> list = new ArrayList<>();

Node root = new Node(null, "root");

Node a = new Node(root, "a");
Node b = new Node(root, "b");
Node c = new Node(root, "c");

Node a1 = new Node(a, "a1");
Node a2 = new Node(a, "a2");
Node a3 = new Node(a, "a3");

Node b1 = new Node(b, "b1");
Node b2 = new Node(b, "b2");
Node b3 = new Node(b, "b3");

Node c1 = new Node(c, "c1");
Node c2 = new Node(c, "c2");
Node c3 = new Node(c, "c3");


Node b11 = new Node(b1, "b11");
Node b12 = new Node(b1, "b12");
Node b13 = new Node(b1, "b13");


list.add(root);

list.add(a);
list.add(b);
list.add(c);

list.add(a1);
list.add(a2);
list.add(a3);

list.add(b1);
list.add(b11);
list.add(b12);
list.add(b13);

list.add(b2);
list.add(b3);

list.add(c1);
list.add(c2);
list.add(c3);

return list;
}

/**
* Object with a parent relationship
*/
public static class Node {

Node parent;
String text;
int level = -1;

public Node(Node parent, String text) {
this.parent = parent;
this.text = text;
}

public String toString() {
return text;
}
}

}

输出:

shuffled list

b11
a
b13
c2
b1
b3
b
c1
a3
c
b12
a1
b2
c3
a2
root

sorted list

root
a
a1
a2
a3
b
b1
b11
b12
b13
b2
b3
c
c1
c2
c3

最佳答案

一种可能性是使用流和递归:

public static void main(String[] args) {
// create example list
List<Node> nodes = createExampleList();

// shuffle
Collections.shuffle(nodes);
logList("shuffled list", nodes);

// create tree list
logList("tree list", treeList(nodes));
}

private static List<Node> treeList(final List<Node> nodes) {
return treeAdd(nodes, null, new ArrayList<>(nodes.size()));
}

private static List<Node> treeAdd(List<Node> nodes, Node parent, List<Node> treeList) {
nodes.stream()
.filter(n -> n.parent == parent)
.sorted((n1,n2) -> n1.text.compareTo(n2.text))
.forEach(n -> {
n.level = parent == null ? 0 : parent.level + 1;
treeList.add(n);
treeAdd(nodes, n, treeList);
});
return treeList;
}

请注意,这在性能方面并不是非常高效,因为过滤器调用被调用了 n 次并且是 O(n)。可以通过预初始化 map 以按父查找子项来优化它。

关于java - 像树一样使用父引用对列表进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37893295/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com