0

来自 C++ 背景，我错过了一个很好的排序容器，它仅基于比较并且不需要哈希。

有人知道平衡树的良好实现吗？或者在（标准）库中是否有同样易于使用的替代排序容器？

这是我现在尝试解决的用例：A 有一个文件描述了带有三角形的表面。每个三角形都有三个节点，许多节点都是相同的。我需要重建这个表面并且需要知道哪些节点是相同的。不幸的是，在 ASCII 输入中，即使它们属于同一个节点，打印的浮点数之间有时也会存在细微差别。所以我不能使用简单的文本比较来查看它们是否相等。

在 C++ 中，我的解决方案是制作一个 std::map 来存储具有“softcompare”的节点，如果它们之间的距离很小，则将节点视为相等。然后我可以在解析文件时添加节点并使用索引来构建表面。

但是在 Python 中，我正在努力以一种直接的方式同样有效地做到这一点。

谢谢，卢克

感谢大家的贡献！

对 goncalopp 来说：排序不是一个好的选择，因为每次插入都是 O(n log(n)) 最坏的情况。对等也一样。它在搜索时很好，但在插入时不好。它维护一个不平衡的树，在最坏的情况下是 O(n)，然后列表中的以下插入是 O(n)。

致 Aaron：我完全同意你的目标是编写优雅的代码。对我来说，选择正确的容器（数据结构）通常是做到这一点的第一步。您的解决方案是 O(n)，它比平衡树还要快，非常好，我喜欢使用 round() 的技巧。我没有想到这一点，现在我意识到它可以在 python 中工作，因为 int 的无限精度。所以我会和你的建筑一起去。

致 MrE：感谢 bintree 的链接，它看起来像是我问题的解决方案（平衡树）。我之前找到了 blist ，但它使用内部字典和哈希进行查找，所以这不起作用，但 bintree 看起来好多了。

4

1 回答 1

0

在 C++ 中，一切都与效率有关。在 Python 中，美观同样重要：Python 人首先尝试找到一种优雅的算法，在少数情况下它实际上太慢，我们会花几分钟时间优化几行代码以使其足够快。

在您的情况下，您需要找到彼此靠近的点。一种方法是您描述的方法。以下是我将如何解决这个问题：

确定坐标需要有多准确。您想要/需要/必须保留多少个小数？1、2？

在读取输入时，将坐标截断或四舍五入到适当的小数位数，从中创建一个元组键。现在你可以使用标准的 Python 字典了：

def round(x):
    return int(round(x*100)) # Keep 2 decimal places, return int for precision (and speed)

filter = {}
filteredPoints = []
for x,y,z in points:
    x,y,z = round(x),round(y),round(z)
    key = (x,y,z)
    index = filter.get(key, None)
    if index is None:
        index = len(filteredPoints)
        filteredPoints.append(key)
        filter[key] = index
于 2013-09-27T14:33:17.877 回答