Random question (from me personally): what interest or need is there for advanced data structures in your code? For example: various trees (red-black, AVL, n-ary, B+...), tries, skip lists, Bloom filters, etc etc. Possibly various algorithms too.
Random question (from me personally): what interest or need is there for advanced data structures in your code? For example: various trees (red-black, AVL, n-ary, B+...), tries, skip lists, Bloom filters, etc etc. Possibly various algorithms too.
It occurred to me that I don't know of reliable, modern-Delphi-style, generic, high quality (eg well unit tested) implementations of these fundamental data structures. I also don't know what the need for them is - ie what the demand is, how many people are writing code that would use them. I've written a couple in the past, one for a customer and a one for interest. The main Delphi source I know of is Julian Bucknall's excellent Tomes of Delphi which covers some of these, but the code is seriously showing its age. Spring4D has many containers but not many data structures; it mostly wraps Delphi's containers.
It occurred to me that I don't know of reliable, modern-Delphi-style, generic, high quality (eg well unit tested) implementations of these fundamental data structures. I also don't know what the need for them is - ie what the demand is, how many people are writing code that would use them. I've written a couple in the past, one for a customer and a one for interest. The main Delphi source I know of is Julian Bucknall's excellent Tomes of Delphi which covers some of these, but the code is seriously showing its age. Spring4D has many containers but not many data structures; it mostly wraps Delphi's containers.
Coming back to the original question about data structures and algorithms that are missing in standard libs:
ReplyDelete- Yes, advanced structures would be useful (balanced trees, bloom filters, tries), provided they are generic.
- Algorithms, too. I think especially of Tim sorting, since the basic sorting algorithm in the Delphi libs is Quicksort, with a non-stable implementation. An efficient implementation of Tim Sort would be nice. If available, it should even become the standard sorting algorithm.
- Other suggestion : I had to implement the Tomita algorithm for finding maximal cliques in a graph, handy for many different use cases once it is available.
I think that availability comes first to trigger the need for special data structures. Developers are not always aware of other possibilities than those available. If more structures were available in libraries, being able to give them an easy trie may lead to using them more often. I surely would.
I personnaly have only used RB-trees for faster insertions from huge data. But I had to partially implement them for that (insertion and lookup).
I vastly prefer improved code generation over a data structures library. We can write data structures, but we cannot improve code generation. And as code generation improves, so will our data structures.
ReplyDeleteI use BTree quite a lot. Its small enough for a lookup table yet scales well to handle a whole AST for a large program. I added support for filters to TW3Dataset the other day and ended up using it there too for the expressions. A bit overkill perhaps but speed is the most important factor when sorting data. As for a good source and well tested, there was a "Delphi fundamentals library" in circulation on Google code a few years back, I would imagine it's on Git now. Probably a lot of time tested code to be found in the JCL too.
ReplyDeleteWhat would be an absolutely knock-out feature, was if such data structures could be more easily represented in code. I know .net is doing this - but I feel they are throwing the baby out with the bath-water to be honest. There is a hair-thin line between time-saving features and time-wasting features. If it can be done with a fair bit of elegance and readability then i would love to see that added on parser level