Comment by mooneater | Hacker News Reader

Comment by mooneater | Hacker News Reader

Parent Full thread

If this is perf. critical and your data easily fits in RAM, then your problem does not sound exotic enough to resort to obscure or special-purpose languages. You should be able to whip up efficient data structures for this in python without much trouble. In fact depending on your data set size and query specifics, it may be acceptably fast in any of the listed languages (including Ruby!) assuming you have the right data structures. You really wont know until you have tried it. I would suggest you start in whatever language you know best.

(If it doesnt fit in RAM, I would consider it a much harder problem and I can imagine resorting to an at least partially SQL-based solution).

Btw, for a very similar problem, I used C++ w/STL for pure performance. It worked well. But I'm migrating it to python to shorten dev time. I figure in the same amt of time in python, I can try a variety of approaches and algo optimizations, for the same time it would take to do a single one in C++ w/STL. And for algos on complicated data sets, you want to really understand your data set. That means playing with it a lot, which is easier in python.

The data structures you use often have a much bigger impact on performance, than the language.

Tip for doing this kind of thing, that works in any language:

In some cases, using more that one type of data structure at the same time will allow you to get the best of both worlds in terms of performance. Ie, a spatial index plus a hash table as an index, over the same data, would allow efficient lookups on spatial predicates as well as attributes, over the same set of nodes.

A simple insight maybe, but not one I discovered without a lot of thought. Typically in university they teach you to use a single data structure type at a time, but really that's like teaching kids the alphabet, without the concept of combining the letters into meaningful words.

Brilliant, thanks. Yes, RAM is a good option for me.

I figure 2 GB will last me 4 months. Then I can go up to 4, 8, 16, ...

Pretty good.

mooneater, do you have any suggestions on how to actually store and persist such a data structure in RAM?

Would I use something like a wsgi webserver, that runs as a daemon, and occasionally dumps the data structure to disk?

Or is something like memcached better?

My preferred way of storing into RAM would be of course only storing changes, instead of storing the whole tree into RAM on every write.

Depends how often you are getting new data. If its not too often, you could write directly to SQL. Otherwise writing in batches like you suggest could work too.

After looking at your post again, and depending on data volume, you might be ok with a purely SQL solution too (ie, finding nodes 1 or 2 steps away on a graph is easy in SQL if your adjacency data is all in the db).

Yes, that's true. But I still have a requirement for a schemaless db, so sql doesn't cut it.

By schema-less, do you mean that it's possible that every new record in the database could have a few attribute-values that no other record has, or that you simply don't know what your attributes are at this time but at some point you will know them all?

If by schemaless you mean the arbitrary name/attribute pairs, you could simply use SQL, with an "attribute" table with "name" and "value", and "nodeid" columns.

Reply on news.ycombinator.com