Hacker News Reader

Comment by chrisseaton | Hacker News Reader

How would you for example represent a program in memory with simple arrays and hash maps, where most people would use a tree or graph?

View on HN

Sometimes a tree or graph really is the right way, but if you want memory locality, you could have an array of nodes and an array of edges that reference the nodes by index. That’s effectively what the author is proposing (pooling), rather than allocating all of the nodes and edges individually.

Do you mean an AST?

AST, CST, CFG, DFG, PDG, or any other data structure for representing a program. But I can't imagine it being done with a simple array or a hash map. The all end in T or G! How would you approach that with your way of doing things? I guess if you work on game engines this is a relevant problem? Or if not maybe a graphics data structure like a BSP? How do you do that without trees? Or a NPC navigation data structure? How do you do that without graphs?

BSP is a pretty outdated algorithm in the game engine space.

I very often use spatial hashing instead of quad-trees or octrees.

I rarely write interpreters but from memory a simple stack can go a long way.

Scenes are stored as flat arrays of components (ECS style)

Navigation (path finding) is very dependent on the internal level architecture, many tricks can be used to avoid trees or complex computations.

Just wanted to say thank you for this comment. It led me to this paper http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf which introduced some new ideas to me alongside of concepts that I were familiar with so it’s been generally easy but useful reading so far :)

You probably know more than me but I don't really get how you can go from text source code to a stack without going through a tree or with recursion!

https://en.wikipedia.org/wiki/Shunting-yard_algorithm

I suggest watching this excellent talk on Data Oriented Design from Mike Acton:

https://www.youtube.com/watch?v=rX0ItVEVjHc

I've watched this talk before, and I really think it's just about transposition. Column rather than row. If you have a graph and represent it as an adjacency array... lol it's still a graph you're just looking at it differently! You haven't gotten rid of the inherent graph property of the data structure!

Reply on news.ycombinator.com