I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.
Perhaps use the SortedList class instead of the Dictionary class.
For example, this blog entry says,
Best memory footprint we see in the SortedList, followed by Hashtable, SortedDictionary and the Dictionary has highest memory usage. Despite all that, we have to note, that the differences are not significant and unless your solution requires extreme sensitivity about the memory usage you should consider the other two parameters: time taken for the insert operations and time taken for searching a key as more important.
Other optimizations might include:
- Don't allocate Node.Children until/unless the AddChild method is called.
- Use the Dictionary constructor which lets you specify the initial capacity (and specify a very low initial capacity)
- Add a
KeyValuePair<char,Node> OnlyChildmember to Node, and use it (instead of creating Dictionary) when the first child is added (delete it and create a dictionary when the second child is added) to optimize the case where a Node has only exactly one child
Beware that the above are 'micro-optimizations' which don't change the algorithm; changing the algorithm (I don't understand Artur Mustafin's comment Artur Mustafin's comment) might result in bigger savings.
I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.
Perhaps use the SortedList class instead of the Dictionary class.
For example, this blog entry says,
Best memory footprint we see in the SortedList, followed by Hashtable, SortedDictionary and the Dictionary has highest memory usage. Despite all that, we have to note, that the differences are not significant and unless your solution requires extreme sensitivity about the memory usage you should consider the other two parameters: time taken for the insert operations and time taken for searching a key as more important.
Other optimizations might include:
- Don't allocate Node.Children until/unless the AddChild method is called.
- Use the Dictionary constructor which lets you specify the initial capacity (and specify a very low initial capacity)
- Add a
KeyValuePair<char,Node> OnlyChildmember to Node, and use it (instead of creating Dictionary) when the first child is added (delete it and create a dictionary when the second child is added) to optimize the case where a Node has only exactly one child
Beware that the above are 'micro-optimizations' which don't change the algorithm; changing the algorithm (I don't understand Artur Mustafin's comment) might result in bigger savings.
I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.
Perhaps use the SortedList class instead of the Dictionary class.
For example, this blog entry says,
Best memory footprint we see in the SortedList, followed by Hashtable, SortedDictionary and the Dictionary has highest memory usage. Despite all that, we have to note, that the differences are not significant and unless your solution requires extreme sensitivity about the memory usage you should consider the other two parameters: time taken for the insert operations and time taken for searching a key as more important.
Other optimizations might include:
- Don't allocate Node.Children until/unless the AddChild method is called.
- Use the Dictionary constructor which lets you specify the initial capacity (and specify a very low initial capacity)
- Add a
KeyValuePair<char,Node> OnlyChildmember to Node, and use it (instead of creating Dictionary) when the first child is added (delete it and create a dictionary when the second child is added) to optimize the case where a Node has only exactly one child
Beware that the above are 'micro-optimizations' which don't change the algorithm; changing the algorithm (I don't understand Artur Mustafin's comment) might result in bigger savings.
I'm sure the tree can be replaced by something else more efficient, but I'm struggling with figuring that out. I've heard a linked list might work, but I'm not sure how.
Perhaps use the SortedList class instead of the Dictionary class.
For example, this blog entry says,
Best memory footprint we see in the SortedList, followed by Hashtable, SortedDictionary and the Dictionary has highest memory usage. Despite all that, we have to note, that the differences are not significant and unless your solution requires extreme sensitivity about the memory usage you should consider the other two parameters: time taken for the insert operations and time taken for searching a key as more important.
Other optimizations might include:
- Don't allocate Node.Children until/unless the AddChild method is called.
- Use the Dictionary constructor which lets you specify the initial capacity (and specify a very low initial capacity)
- Add a
KeyValuePair<char,Node> OnlyChildmember to Node, and use it (instead of creating Dictionary) when the first child is added (delete it and create a dictionary when the second child is added) to optimize the case where a Node has only exactly one child
Beware that the above are 'micro-optimizations' which don't change the algorithm; changing the algorithm (I don't understand Artur Mustafin's comment) might result in bigger savings.