java - JTree, 优化算法, Java

Question

我和我的合作伙伴，我们正在努力优化频率流程...

我们希望在 JTree 中尽可能简化我们的问题.

如您所见，每个 node或 leaf有一个 numResampleOperations每个节点/叶都涉及。

L -> Increment or multiplication
M -> Decrement or division

我们如何计算这些值？

Target = Source*L/M
numResampleOperations = filterSize * Source * Integer.max(L, M);

我们只想为 JTextField 中显示的每个频率获取一个值，删除不需要的分支。

对于这个例子，我们只使用了 5 个有序的 Target频率(只允许整数值)，但可以增长到 50 个频率值。

JTree 必须至少保留每个包含的 Target频率为 150Hz，至少为 160Hz、..、210Hz 之一。

最高优先级是涉及的最小金额为numResampleOperations

如何删除不需要的分支 ( those whose sum is very high )、节点或叶子，同时保证至少有一个(JTextField 上要求的频率)，但所有 numResampleOperations 的总和是最小值吗？

您对我们有什么建议？

我们从 Generate List with Combination of Subset of List, Java 开始但由于尺寸的原因，该解决方案不可行。

编辑 1

我的类(class)

public class NodeResample {

  private int incrementL;
  private int decrementM;
  private int sampleRateSource;
  private int sampleRateTarget;
  private double maxPassFreq;
  private Integer filterSize;
  private Integer numResampleOperations;

  public NodeResample(int incrementL, int decrementM, int sampleRateSource, int sampleRateTarget, double maxPassFreq, Integer filterSize, Integer numResampleOperations) {
    this.incrementL = incrementL;
    this.decrementM = decrementM;
    this.sampleRateSource = sampleRateSource;
    this.sampleRateTarget = sampleRateTarget;
    this.maxPassFreq = maxPassFreq;
    this.filterSize = filterSize;
    this.numResampleOperations = numResampleOperations;
  }

  public int getIncrementL() {
    return incrementL;
  }

  public void setIncrementL(int incrementL) {
    this.incrementL = incrementL;
  }

  public int getDecrementM() {
    return decrementM;
  }

  public void setDecrementM(int decrementM) {
    this.decrementM = decrementM;
  }

  public int getSampleRateSource() {
    return sampleRateSource;
  }

  public void setSampleRateSource(int sampleRateSource) {
    this.sampleRateSource = sampleRateSource;
  }

  public int getSampleRateTarget() {
    return sampleRateTarget;
  }

  public void setSampleRateTarget(int sampleRateTarget) {
    this.sampleRateTarget = sampleRateTarget;
  }

  public double getMaxPassFreq() {
    return maxPassFreq;
  }

  public void setMaxPassFreq(double maxPassFreq) {
    this.maxPassFreq = maxPassFreq;
  }

  public Integer getFilterSize() {
    return filterSize;
  }

  public void setFilterSize(Integer filterSize) {
    this.filterSize = filterSize;
  }

  public Integer getNumResampleOperations() {
    return numResampleOperations;
  }

  public void setNumResampleOperations(Integer numResampleOperations) {
    this.numResampleOperations = numResampleOperations;
  }

  @Override
  public String toString() {
    return "NodeResample{" + "L=" + incrementL + ", M=" + decrementM
        + ", Source=" + sampleRateSource + ", Target=" + sampleRateTarget
        + ", filterSize=" + filterSize + ", numResampleOperations=" + numResampleOperations + "}   ";
  }

}

现在，我注意到某些分支是必不可少的，例如 First (Top) 包含 210 的分支，因为树的其他分支不包含它。

首先，我需要一个代码来找到包含该值 (200) 的分支'或最便宜的'。将找到的分支添加到另一个 Target JTree。这部分的一些代码？

我还注意到其他分支的值仍然是200 ，但是，添加另一个分支的成本大于继续使用第一个“基本”分支的成本，因为这是 only adding two nodes ，其总和小于添加另一个分支。

其次，我需要知道这些 two nodes numResampleOperations -> (267960 + 1091720) 的值(value)，以及另一个分支的值，以进行比较并将最佳选项添加到另一个 Target JTree。 这部分的一些代码？

Answer 1

我解决了我的问题...

我想改进我的所有方法，尤其是 searchNodeResamplePerValue 和 getOptimizedTree。

我创建了一个填充方法... https://pastebin.com/LvCefdc4

您可以复制粘贴并执行。

树 -> 未优化!

treeOut -> 优化!

public class OptimizationResample {

  public static void main(String[] args) {

    final JTree tree = new JTree();
    tree.setRootVisible(false);
    removeAllTreeNodes(tree);
    fillTreeNestedListNodeResample(tree, filler());
    expandAllNodes(tree);

    List<Integer> listSampleRateFinal = Arrays.asList(210, 200, 180, 160, 150);
    JTree treeOut = getOptimizedTree(tree, listSampleRateFinal);
    expandAllNodes(treeOut);
    final JTextField textField = new JTextField(listSampleRateFinal.toString());//listSampleRateFinal .collect(Collectors.joining(","));

    JSplitPane splitPane = new JSplitPane();
    splitPane.setOrientation(JSplitPane.VERTICAL_SPLIT);
    splitPane.setTopComponent(new JScrollPane(tree));
    splitPane.setBottomComponent(new JScrollPane(treeOut));
    splitPane.setDividerLocation(350);
    JPanel panel = new JPanel();
    panel.setLayout(new BoxLayout(panel, BoxLayout.PAGE_AXIS));
    panel.add(textField);
    panel.add(splitPane);

    JFrame frame = new JFrame("Optimization NodeResample");
    frame.setContentPane(panel);
    frame.pack();
    frame.setSize(new Dimension(600, 700));
    frame.setVisible(true);

  }

  private static JTree getOptimizedTree(JTree tree, List<Integer> listSampleRateFinal) {
    JTree treeOut = new JTree();
    treeOut.setRootVisible(false);
    removeAllTreeNodes(treeOut);
    listSampleRateFinal.forEach(target -> {
      List<List<NodeResample>> nestedListPerValue = searchNodeResamplePerValue(tree, target);
      Long lastMinimum = Long.MAX_VALUE;
      List<NodeResample> minimumlistPerValue = null;
      for (List<NodeResample> listPerValue : nestedListPerValue) {
        // I can't easily copy all nodes from treeOut to tempTree (I had problem with new JTree(treeOut.getModel());)
        List<List<NodeResample>> nestedListNodeResample2 = getNestedListNodeResampleFromTree(treeOut);
        JTree tempTree = new JTree();
        tempTree.setRootVisible(false);
        removeAllTreeNodes(tempTree);
        fillTreeNestedListNodeResample(tempTree, nestedListNodeResample2);
        addNodeResampleToTree(tempTree, listPerValue);

        List<DefaultMutableTreeNode> listNodes = getListNodesFromTree(tempTree);
        Long accumulator = listNodes.stream()
            .filter(leaf -> leaf.getUserObject() instanceof NodeResample)
            .map(leaf -> (NodeResample) leaf.getUserObject())
            .map(nodeResample -> (long) nodeResample.getNumResampleOperations())
            .mapToLong(Long::longValue).sum();
        if (accumulator < lastMinimum) {
          lastMinimum = accumulator;
          minimumlistPerValue = listPerValue;
        }
      }
      if (minimumlistPerValue != null) {
        System.out.println("\nminimumlistPerValue:" + Arrays.toString(minimumlistPerValue.toArray()) + "\n");
      } else {
        System.out.println("\nminimumlistPerValue:" + null + "\n");
      }

      addNodeResampleToTree(treeOut, minimumlistPerValue);
    });
    return treeOut;
  }

  private static List<List<NodeResample>> searchNodeResamplePerValue(JTree tree, int value) {
    List<DefaultMutableTreeNode> listNodes = getListNodesFromTree(tree);
    List<DefaultMutableTreeNode> listNodesWithValue = listNodes.stream()
        .filter(node -> node.getUserObject() instanceof NodeResample)
        .filter(node -> value == ((NodeResample) node.getUserObject()).getSampleRateTarget())
        .collect(Collectors.toList());

    List<List<NodeResample>> out = new ArrayList<>();
    Long lastSumNumResampleOperations = Long.MAX_VALUE;

    for (DefaultMutableTreeNode leaf : listNodesWithValue) {

      List<NodeResample> listNodeResample = new ArrayList<>();
      listNodeResample.add((NodeResample) leaf.getUserObject());
      TreeNode treeNode = leaf.getParent();
      while (treeNode != null) {
        DefaultMutableTreeNode parent = (DefaultMutableTreeNode) treeNode;
        if ((parent).getUserObject() instanceof NodeResample) {
          listNodeResample.add(0, (NodeResample) parent.getUserObject());
        }
        treeNode = parent.getParent();
      }

//      Long totalNumResampleOperations = listNodeResample.stream()
//          .map(nodeResample -> (long) nodeResample.getNumResampleOperations())
//          .mapToLong(Long::longValue).sum();
//      if (totalNumResampleOperations < lastSumNumResampleOperations) {
//        lastSumNumResampleOperations = totalNumResampleOperations;
//        //out = listNodeResample;
//      }
      out.add(listNodeResample);
    }
    return out;
  }

  private static void removeAllTreeNodes(JTree tree) {
    DefaultMutableTreeNode rootTreeNode = (DefaultMutableTreeNode) tree.getModel().getRoot();
    if (rootTreeNode != null) {
      rootTreeNode.removeAllChildren();
    }
    reloadTree(tree);
  }

  private static void reloadTree(JTree tree) {
    DefaultTreeModel treeModel = ((DefaultTreeModel) tree.getModel());
    DefaultMutableTreeNode rootTreeNode = (DefaultMutableTreeNode) treeModel.getRoot();
    treeModel.reload(rootTreeNode);
  }

  private static void expandAllNodes(JTree tree) {
    expandAllNodes(tree, 0, tree.getRowCount());
  }

  private static void expandAllNodes(JTree tree, int ini, int rows) {
    try {
      if (tree != null) {
        for (int i = ini; i < rows; ++i) {
          tree.expandRow(i);
        }

        if (tree.getRowCount() != rows) {
          expandAllNodes(tree, rows, tree.getRowCount());
        }
      }
    } catch (ArrayIndexOutOfBoundsException ex) {
    } catch (Exception ex) {
    }
  }

  private static void fillTreeNestedListNodeResample(JTree tree, List<List<NodeResample>> nestedListNodeResample) {
    nestedListNodeResample.stream()
        .forEachOrdered(listNodeResample -> {
          addNodeResampleToTree(tree, listNodeResample);
        });
  }

  private static void addNodeResampleToTree(JTree tree, List<NodeResample> listNodeResample) {
    try {
      DefaultTreeModel treeModel = ((DefaultTreeModel) tree.getModel());
      DefaultMutableTreeNode rootTreeNode = (DefaultMutableTreeNode) treeModel.getRoot();
      DefaultMutableTreeNode nodeResampleTreeNode = rootTreeNode;
      if (listNodeResample != null) {
        for (NodeResample nodeResample : listNodeResample) {
          nodeResampleTreeNode = getDefaultMutableTreeNode(nodeResampleTreeNode, nodeResample, true);
        }
      }
      treeModel.reload(rootTreeNode);
    } catch (Exception e) {
      throw e;
    }
  }

  private static DefaultMutableTreeNode getDefaultMutableTreeNode(DefaultMutableTreeNode parent, NodeResample newChild, Boolean isLeaf) {
    if (parent != null) {
      DefaultMutableTreeNode child;
      for (int i = 0; i < parent.getChildCount(); i++) {
        child = (DefaultMutableTreeNode) parent.getChildAt(i);
        if (child.toString().equals(newChild.toString())) {
          return child;
        }
      }
      child = new DefaultMutableTreeNode(newChild, isLeaf);
      parent.add(child);
      return child;
    } else {
      return null;
    }
  }

  private static List<List<NodeResample>> getNestedListNodeResampleFromTree(JTree tree) {
    List<List<NodeResample>> nestedListNodeResample = new ArrayList<>();
    List<DefaultMutableTreeNode> listLeafDefaultMutableTreeNode = getListLeafsFromTree(tree);
    listLeafDefaultMutableTreeNode.stream()
        .filter(node -> node.getUserObject() instanceof NodeResample)
        .forEach(leaf -> {
          List<NodeResample> listNodeResample = new ArrayList<>();
          listNodeResample.add((NodeResample) leaf.getUserObject());
          TreeNode treeNode = leaf.getParent();
          while (treeNode != null) {
            DefaultMutableTreeNode parent = (DefaultMutableTreeNode) treeNode;
            if ((parent).getUserObject() instanceof NodeResample) {
              listNodeResample.add(0, (NodeResample) parent.getUserObject());
            }
            treeNode = parent.getParent();
          }
          nestedListNodeResample.add(listNodeResample);
        });
    return nestedListNodeResample;
  }

  private static List<DefaultMutableTreeNode> getListLeafsFromTree(JTree tree) {
    DefaultTreeModel treeModel = ((DefaultTreeModel) tree.getModel());
    DefaultMutableTreeNode rootTreeNode = (DefaultMutableTreeNode) treeModel.getRoot();
    List<DefaultMutableTreeNode> listLeafDefaultMutableTreeNode = new ArrayList<>();
    getLeafs(rootTreeNode, listLeafDefaultMutableTreeNode);
    return listLeafDefaultMutableTreeNode;
  }

  private static void getLeafs(DefaultMutableTreeNode parent, List<DefaultMutableTreeNode> listLeafDefaultMutableTreeNode) {
    if (parent.isLeaf()) {
      listLeafDefaultMutableTreeNode.add(parent);
    } else {
      for (int i = 0; i < parent.getChildCount(); i++) {
        DefaultMutableTreeNode child = (DefaultMutableTreeNode) parent.getChildAt(i);
        getLeafs(child, listLeafDefaultMutableTreeNode);
      }
    }
  }

  private static void getListNodesFromTree(TreeNode treeNode, List<DefaultMutableTreeNode> out) {
    DefaultMutableTreeNode nodeResampleTreeNode = (DefaultMutableTreeNode) treeNode;
    out.add(nodeResampleTreeNode);
    if (treeNode.getChildCount() >= 0) {
      for (Enumeration e = treeNode.children(); e.hasMoreElements();) {
        TreeNode n = (TreeNode) e.nextElement();
        getListNodesFromTree(n, out);
      }
    }
  }

  private static List<DefaultMutableTreeNode> getListNodesFromTree(JTree tree) {
    TreeNode root = (TreeNode) tree.getModel().getRoot();
    List<DefaultMutableTreeNode> out = new ArrayList<>();
    getListNodesFromTree(root, out);
    return out;
  }

  private static List<List<NodeResample>> filler() {
    List<List<NodeResample>> nestedListNodeResample = null;//Look in Paste bin 

    return nestedListNodeResample;
  }

}