Data structures in C#

Data structures in C#

• Jason Beard

  This doesn't sound a code syntax tree bu more like a search tree. What are you trying to achive What stack do you use if you use the sytem stack implicitly by use of recursion, the pop and push methods are not that demanding on the performance.
  
  

• PublicError

  I am already using Lists. should I build my tree using breadth first or depth first approach the choice of a stack enables depth first but the pop and push portion is rather taxing on the efficiency performance. do you have any advice or recommendations
  

• Mkennie

  Are you trying to execute these statements Are you building something like an interpreter Than you definitly should go for recursion.

  The articles posted by Indian Ocean are good but are only talking about your basic acadamic datastructures. I'm not sure this is what you want.

  
  
  

• Leed3

  Hi,

  The following would give you good pointers,
  http://msdn2.microsoft.com/en-us/library/ms379573(vs.80).aspx
  http://dotnetjunkies.com/WebLog/debasish/archive/2006/05/27/139143.aspx
  

  HTH,

  
  
  

• LOTG

  I'm sorry but you're mistaken. Recursion uses the system stack, not the heap. And it's by far the fastes way of programming a parser.
  
  

• rofu

  The most efficient way is not to use a data structure at all but a program structure. Most compilers don't build a syntax trees but build the compiled code as they parse source code on the fly. The only structures they require are a few symbol tables and some buffers for their input and output. If you really want to build a syntax tree, create an object for each type of node and create a parse function for every type of node. In the parse function you create an instance of the node and connect it to it's subnodes by calling the right parse functions. In means of time, this is not demanding on the system. Doesn't really matter how deep you're tree is going to be. The speed is only dependend on the size of the source code you're going to parse. The order is O(n) where n is relates to the size of the source.
  
  

• Basalingamma

  it is a tree used to store code in terms of statements and expressions. it is pretty much alike to the binary search tree but not all nodes have 2 edges. what do you mean by implementing the stack implicitly using recursion the stack simply is to handle nested statements like 'while' or 'if'. and the pushing and popping will be taxing if I have 10000 nested whiles. if simply there are other data structures that could cater to nesting the nodes such that after I have constructed a sub tree, i need not pop up till I reached the root of the sub tree to carry on building another subtree from there, I would be all ears.

  
  

• Eighty

  my performance analysis more likely has to do with how fast a query (something like sql query) can analyse a static program (i.e C program). but more likely this efficiency can be achieved through other means. why am I concerned with stack let's say I have a billion lines of static program code which I need to build into a very large tree how fast could i build it using means that are efficient i need to take into account the computation time. and i also know stacking can also perform a bit of trick by matching braces and brackets to evaluate algebra expressions in the program. but for each line of code which is an algebra expression, i need to perform pushing and popping which is taxing. the program can also contain nested while and nested if which we should not forget. sort of like a syntax tree..hope you could picture it =)

  i.e 1 line of code which is x = (1+2)*3+4+(7*8)+....so on

  could you elaborate to me how fast could the pushing and popping means in terms of secs. neway Thanks

  
  

• vijil

  Most of the structures in the collections namespace are highly optimized. But it sounds like you need to build something like an object model. Define your own objects with references to each other and when you need multiple references use the List or List<> objects.
  
  

• lfnovo

  Maybe if i have time this evening I'll write you a little example.
  
  

• Billy2005

  I saw the articles but they are just basic usage of data structures. I am coding a parser cum analyzer of programs. recursion is intuitive but it would cause a lot of memory overheads as it eats up into the heap. so I was thinking if there were any methodology that would optimise the building of a syntax tree, best if I could use some advanced data structures to ease the algorithm part. =)

  
  

• hellosmithy

  well, i would love to avoid unnecessary data structures if need be. right now, the stack is there because of the nesting of the 'whiles' and the 'ifs' cos i need to traverse back to their root nodes in the stack to build onto the existing tree. well, if stack's pushing and popping wouldn't get in the way, i think it is fine. but i can't imagine 10000 nested 'while' statements which i have to push and pop quite significantly. symbol tables do help but not for building the tree physically =S
  

• Nick_Dev

  oh thanks i am mistaken. all along i have the impression recursion uses heap and iterative uses stack which is faster(maybe I got mixed up between the terminologies). but memory allocation aside, is the popping and pushing going to affect its computational efficiency Thanks for clarifying it up
  

• CSharpNewbie22

  Push and Pop from the program stack are very fast operations because the memory for the system stack does not need to be allocated on forhand. it's already allocated and the CLR checks for overflow. Recursion is based on keeping information in paramaters passed in function calls. Function parameters are always passed on the stack. Maybe I can help you a little bit more if you tell me what kind of analysis you're trying to do. Maybe give a little sample of the code you're trying to parse as well.

  
  
  
• Data structures in C#