The are more compact representations, e.g. you can store the dictionary in a deterministic acyclic minimized finite state automaton (which can be stored in a flat array/slice). This gives you O(n) time lookups, where n is the length of the word, and reduces much of the redundancy in a dictionary.
Words within an edit distance can be found by computing a Levenshtein automaton for the word (which can be done in linear time) and computing the intersection language of the dictionary automaton and the Levenshtein automaton.
This approach is fast and very compact. I have a Java implementation:
For the moment I am looking at the Linkedin approach[0]. Sorry for keeping this semi-offtopic thread alive, but these problems are so interesting that I cannot stop.
I'd bet most of them, although they're almost all closed-source so we will likely never know.
message Foo {
required string a = 1;
required int32 b = 2;
optional int64 c = 3;
}
Generates a struct like: type Foo struct {
a *string
b *int32
c *int64
}
This is not particularly friendly to the garbage collector compared to a POD struct with no pointers.https://developers.google.com/protocol-buffers/docs/referenc...
The flow of data is currently:
various external sources -> merged into protocol buffer struct -> later sent to client
To avoid keeping a heap of protocol buffer structs in the heap, this would need to change to:
various external sources -> merged into some internal datastructure -> later converted into protocol buffer struct and sent to client.
Did you consider keeping strings (serialized messages) in your cache rather than message objects? I do this in C++ code simply for memory efficiency. Here it would also allow you to avoid these extra pointers.
Go does allow fixed size arrays in structs, and they're inline in the struct, so `struct { foo [8]uint }` is 32 bytes, whereas `struct { foo []uint }` is 12 bytes and `struct { foo string }` is 8.
Basically, the garbage collection cost forced me to think about a better data structure for my case. Maybe not that bad all in all.
[0]: http://stevehanov.ca/blog/index.php?id=114 [1]: https://www.chemeo.com/search?q=asparine