我能使用比树更快的数据结构吗？（问题标题）

Question

7

我有一个二叉决策树。它将输入作为浮点数数组，并且每个分支节点在输入索引和值上进行拆分，最终将我带到一个叶子节点。

我正在对这棵树执行大量查找操作（根据性能分析约占执行时间的17％（编辑：优化其他区域后现在接近40％）），并且想知道是否可以/应该使用不同的数据结构来提高查找速度。

某种哈希表无法使用，因为输入不能直接映射到叶子节点，但我想知道是否有人对我可以使用的方法和数据结构有任何建议，以代替树（或与之并用）以提高查找速度。

内存是一个问题，但速度的问题比内存更重要。

代码当前是用C#编写的，但显然可以应用任何方法。

编辑：代码太多了，但我会提供有关树的更多详细信息。

该树是使用信息增益计算生成的，它不总是50/50的拆分，拆分值可以是任何浮点值。单个输入也可以多次拆分，从而增加该输入的分辨率。

我在此处发布了有关迭代器性能的问题：

但我认为我可能需要查看数据结构本身以进一步提高性能。

我在这里的目标是尽可能地提高性能。我正在研究一种新的机器学习方法，该树使用反馈循环自行生长。对于我正在处理的过程，我估计它将运行数个月，因此每次仅节省几个百分点就非常重要。最终目标是在不使用过多内存的情况下实现速度。

- Will Calderwood

具有排序功能的字典，可以是映射。 - Ryan Fung

1

你说你有一棵二叉树，每个节点的输入是一个浮点数 - 你选择子节点的依据是基于 input < 0.5 还是有更复杂的情况？你能发布一些代码吗？此外：17% 的执行时间并不是很具体化 - 这可能非常快！你有一个目标吗，或者有更多关于性能分析的细节可以分享吗？ - Dan Puzey

谢谢丹，我已经添加了有关树和目标的更多详细信息。 - Will Calderwood

它是否有固定的深度？ - Will

浮点数需要什么精度？例如，在0和1之间只有256个刻度是否足够？ - Will

显示剩余2条评论

2个回答

1

假设决策有50/50的机会：

想象一下，你有两个二进制决策；可能的路径是00、01、10、11。

想象一下，如果不是树形结构，而是一个包含四个结果的数组；你可以将你的浮点数数组转换成一个二进制数字，该数字将作为索引指向这个数组。

- Will

有趣的想法。如果我理解正确的话，我仍然需要遍历树来生成二进制数以获得数组中的索引。我不明白如何在不遍历树的情况下生成数字。 - Will Calderwood

@WillCalderwood 是的，我假设了一个50/50的概率，这意味着你不需要访问节点就能知道分割。你现在扩展了问题。 - Will

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adrian McCarthy · Accepted Answer

如果我理解正确，您有浮点数范围需要映射到一个决策。类似这样：

       x <= 0.0      : Decision A
 0.0 < x <= 0.5      : Decision B
 0.5 < x <= 0.6      : Decision C
 0.6 < x             : Decision D

一棵二叉树是处理该问题的一个不错的方式。只要树保持平衡且输入值在范围内均匀分布，您可以期望O(log₂ n)次比较，其中n是可能的决策数。

如果树不平衡，则可能会进行比必要的更多比较。最坏情况下：O(n)。因此，我会查看树的深度。如果同一棵树反复使用，则重新平衡的成本可能会分摊到许多查找中。

如果输入值不均匀分布（并且您提前知道这一点），则可能希望特殊处理比较的顺序，以便尽早检测到最常见的情况。您可以通过操作树或在实际检查树之前添加特殊情况来完成此操作。

如果您已经尝试了算法改进但仍需要优化，则可以考虑使用比一般二叉树更好的局部性数据结构。例如，您可以将分区边界放入连续的数组中，并对其执行二进制搜索。（如果数组不太长，则甚至可以尝试在数组上进行线性搜索，因为它可能对缓存和分支预测更友好。）

最后，我建议考虑构建一个粗略索引，以便我们可以快速进入树（或数组）。例如，使用输入值的几个最高有效位作为索引，并查看是否可以截断树的前几层。这可能比您想象的要有帮助，因为跳过的比较可能很难得到正确的分支预测。