Trie节省空间，但如何？ [英] Trie saves space, but how?

问题描述

我很困惑的Trie实现如何节省空间&以最紧凑的形式存储数据！

I am confused as to how the Trie implementation saves space & stores data in most compact form!

如果你看下面的树。当您在任何节点存储字符时，您还需要存储对该字符的引用。因此对于字符串的每个字符，你需要存储它的引用。
当一个通用字符到达时，我们保存了一些空间，但是我们在存储对该字符节点的引用时失去了更多的空间。

If you look at the tree below. When you store a character at any node, you also need to store a reference to that & thus for each character of the string you need to store its reference. Ok we saved some space when a common character arrived but we lost more space in storing a reference to that character node.

的结构开销来维护这棵树本身？相反，如果使用TreeMap来代替这一点，我们可以说实现一个字典，这可以节省更多的空间，因为字符串将被保存在一块，因此没有浪费在存储引用的空间，不是吗？

So isn't there a lot of structural overhead to maintain this tree itself ? Instead if a TreeMap was used in place of this, lets say to implement a dictionary, this could have saved a lot more space as string would be kept in one piece hence no space wasted in storing references, isn't it ?

>

推荐答案

您可能推断，它节省空间是在一个理想的机器上，每个字节被有效地分配。然而真正的机器分配对齐的内存块（Java上为8字节，某些C ++上为16字节），因此可能无法保存任何空间。

You might deduce that it save space is on a ideal machine where every byte is allocated efficiently. However real machines allocate aligned blocks of memory (8 bytes on Java and 16 bytes on some C++) and so it may not save any space.

Java字符串和集合添加相对较高的开销，因此百分比差异可能非常小。

Java Strings and collections add relatively high amount of over head so the percentage difference can be very small.

除非你的结构非常大，你的时间的价值加权使用最简单，最标准和最容易维护的集合的内存成本是更重要的。例如你的时间可以非常容易地值1000x或更多的你尝试保存的记忆的价值。

Unless your structure is very large the value of your time out weights the memory cost that using the simplest, most standard and easiest to maintain collection is far more important. e.g. your time can very easily be worth 1000x or more the value of the memory you are try to save.

例如。说你有10000个名称，你可以通过使用一个特里结构每个保存16个字节。 （假设这可以证明不需要更多的时间）这相当于16 KB，这在今天的价格是0.1美分。如果你的时间花费你的公司每小时30美元，编写一行测试代码的成本可能是1美元。

e.g. say you have 10000 names which you can save 16 bytes each by using a trie. (Assuming this can be proven without taking more time) This equates to 16 KB, which at today's prices is worth 0.1 cents. If your time costs your company $30 per hour, the cost of writing one line of tested code might be $1.

如果你想到了更长的眼睛为了节省16 KB，它不太可能值得为一台PC。 （移动设备是不同的故事，但相同的参数适用于IMHO）

If you have think about it a blink of an eye longer to save 16 KB, its unlikely to be worth it for a PC. (mobile devices are a different story but the same argument applies IMHO)

编辑：您启发我添加更新 http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of- main-memory.html

You have inspired me to add an update http://vanillajava.blogspot.com/2011/11/ever-decreasing-cost-of-main-memory.html

这篇关于Trie节省空间，但如何？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！