javascript - 如何比较决策树的单个路径?
问题描述
我想在 javascript 的一个函数中比较决策树的单个路径。
我只知道如何做到这一点,因为节点正在加起来,但那只是比较节点。相反,我想查看一条路径,然后查看下一条路径。
例如:下一个决定应该是range
-3。给出的是数字[9, 8, 6, 5, 3, 2, 0]
。列表的总和是value
。length
需要6的路径biggest value
。
2 - 0
3 <
5< 0
/ 2 - 0
6
/ \ 2 - 0
3<
0
8 2 - 0
\ 3<
/ 5 < 0
2 - 0
9 2 - 0
3 <
5< 0
\ / 2 - 0
6
\ 2 - 0
3<
0
我想比较那些paths
:
[9,6,3,0],
[9,6,3,2,0],
[9,6,5,2,0],
[9,6,5,3,0],
[9,6,5,3,2,0],
[9,8,6,3,0],
[9,8,6,3,2,0],
[9,8,6,5,2,0],
[9,8,6,5,3,0],
[9,8,6,5,3,2,0],
而不是计算每个path
然后同时比较它们,我只想计算第一个path
,然后将它与第二个进行比较,path
如下所示:
[9,6,3,0], //value 18
[9,6,3,2,0]//value 21
|| which one has the nearest length of 6 with the most Value?
\/
[9,6,3,2,0]//value 21
[9,6,3,2,0],//value 21
[9,6,5,2,0] //value 23
|| which one has the nearest length of 6 with the most Value?
\/
[9,6,5,2,0] //value 23
... and so on
如何一次只比较 2 条路径而不是每条路径?
编辑1:
到目前为止我的代码: https ://replit.com/@RubyKanima/BestSumwithlength#index.js
const numbers = [9, 8, 6, 5, 3, 2, 0];
const starting_node = Math.max(...numbers) + 3;
const path = (current_node, memo ={}) => {
if (current_node in memo) return memo[current_node];
if (current_node == 0) return [[]];
let paths = [];
let tmp_nodes = [];
for (n of numbers) {
if (n >= current_node - 3 && n < current_node) {
tmp_nodes.push(n);
}
}
for (let tmp of tmp_nodes) {
const tmp_path = path(tmp);
const tmp_paths = tmp_path.map(way => [tmp, ...way]);
paths.push(...tmp_paths);
}
memo[current_node] = paths;
paths = paths.filter(x => x.length <= 6);
return paths;
};
const bestPath = all_paths => {
all_paths = all_paths.filter(x => (x.length = 6));
let bestValue = 0;
let bestPath = null;
for (let path of all_paths) {
let value = 0;
for (node of path) value += node;
if (value > bestValue) {
bestValue = value;
bestPath = path;
}
}
return bestPath;
};
const path_array = path(starting_node);
console.log(bestPath(path_array));
它完成了这项工作,但如果我得到超过一千个数字,它就会出现堆栈溢出。(在示例中,我减少了一些数字以便于理解,实际上范围是 -360 而不是 -3)
最大的问题:数据太多
如何解决?:一次只比较 2 条路径,然后计算下一条路径。
我想知道的:如何只计算 2 条路径。
解决方案
因此,我编写了一个合并排序算法,并为您的解决方案和合并排序解决方案添加了一些性能时间计算。在这种情况下,合并排序似乎表现更好。它同时比较两个数组,直到达到您需要的数组。在你的数据上试试这个,它应该更大,看看它是否效果更好。
const numbers = [9, 8, 6, 5, 3, 2, 0];
const starting_node = Math.max(...numbers) + 3;
const path = (current_node, memo ={}) => {
if (current_node in memo) return memo[current_node];
if (current_node == 0) return [[]];
let paths = [];
let tmp_nodes = [];
for (n of numbers) {
if (n >= current_node - 3 && n < current_node) {
tmp_nodes.push(n);
}
}
for (let tmp of tmp_nodes) {
const tmp_path = path(tmp);
const tmp_paths = tmp_path.map(way => [tmp, ...way]);
paths.push(...tmp_paths);
}
memo[current_node] = paths;
paths = paths.filter(x => x.length <= 6);
return paths;
};
const bestPath = all_paths => {
all_paths = all_paths.filter(x => (x.length = 6));
let bestValue = 0;
let bestPath = null;
for (let path of all_paths) {
let value = 0;
for (node of path) value += node;
if (value > bestValue) {
bestValue = value;
bestPath = path;
}
}
return bestPath;
};
//-----merge sort algorithm---------
const sumArr = arr => arr.reduce((acc, next)=> acc+next)
function merge(arr1, arr2){
if (sumArr(arr1) > sumArr(arr2)) {
return arr1
} else if(sumArr(arr1) < sumArr(arr2)) {
return arr2
} else {return arr1}
}
function mergeSort(arr){
if(arr.length <= 1) return arr[0];
let mid = Math.floor(arr.length/2);
let left = mergeSort(arr.slice(0,mid));
let right = mergeSort(arr.slice(mid));
return merge(left, right);
}
//-----end of merge sort algorithm------
const path_array = path(starting_node);
const start = performance.now()
console.log(bestPath(path_array));
const end = performance.now()
console.log("bestPath performance ", end-start)
const start2 = performance.now()
console.log(mergeSort(path_array))
const end2 = performance.now()
console.log("mergeSort performance ", end2-start2)
推荐阅读
- linux - 如何从用户空间访问 thread_info
- vue.js - 如何在 vue data mustache 表达式中使用复杂变量作为对象键?
- c# - 如何从带有分隔符的txt文件中读取文件,并将其写回新的txt文件
- odoo-8 - Odoo重复many2many字段
- c# - ajax将一个int列表传递给asp net api控制器,参数为null
- eclipse - 如何制作开始测验的按钮?
- reactjs - 与 componentWilLReceiveProps 等效的挂钩以更新状态
- reactjs - React:当有多个字段要填充时如何设置状态
- reactjs - Typescript 条件渲染,Type 'undefined' is not Assignable to type CompanyStatsProps
- python - 从菜单调用所有文件