4 ms·

I don't like to use tree or linked-list, I prefer arrays and hash tables. I haven't found many problems that couldn't be solved with simple arrays or hash maps

I don't like to use tree or linked-list, I prefer arrays and hash tables. I haven't found many problems that couldn't be solved with simple arrays or hash maps. Same thing about recursive functions, I never use them.

chrisseaton 6y ago
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?
- stephc_int13 6y ago
  Do you mean an AST?
  - chrisseaton 6y ago
    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?
    - stephc_int13 6y ago
      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.
      - codetrotter 6y ago
        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 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 :)
      - chrisseaton 6y ago
        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!
        stephc_int13 6y ago
        https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
    - stephc_int13 6y ago
      I suggest watching this excellent talk on Data Oriented Design from Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
      - chrisseaton 6y ago
        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!
- munchbunny 6y ago
  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.

chrisseaton 6y ago

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?

stephc_int13 6y ago
Do you mean an AST?
- chrisseaton 6y ago
  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?
  - stephc_int13 6y ago
    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.
    - codetrotter 6y ago
      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 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 :)
    - chrisseaton 6y ago
      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!
      - stephc_int13 6y ago
        https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
  - stephc_int13 6y ago
    I suggest watching this excellent talk on Data Oriented Design from Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
    - chrisseaton 6y ago
      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!
munchbunny 6y ago
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.