Reimplementing data structures in the real world

Question

The topic of the algorithms class today was the redefinition of data structures, notably ArrayList in Java. The fact that you can customize the structure in different ways has definitely interested me, especially with the add () and iterator.remove () methods.

But is redefining and adjusting the data structure something more interesting for scientists and programmers in the real world? Has anyone overestimated your own version of the data structure in a commercial application / program and why did you choose this route for your specific language implementation?

Answer 1

Knowing how data structures are implemented and can be implemented is definitely of interest to everyone, not just scientists. Although you most likely will not redefine the data structure if the language already provides an implementation with suitable functions and performance characteristics, it is very possible that you will have to create your own data structure by composing other data structures ... or you may need to implement the data structure with slightly different behavior than the well-known data structure. In this case, you will certainly need to know how the original data structure is implemented. Alternatively, you may need a data structure that does not exist or that provides similar behavior for an existing data structure, but the way it is used requires that it be optimized for a different set of functions. Again, this situation will require you to know how to implement (and change) the data structure, so yes, it is interesting.

Edit
I am not advocating that you redefine existing data structures ! Do not do this. I say that knowledge has practical application. For example, you may need to create a bidirectional map data structure (which you can implement by composing two unidirectional map data structures), or you may need to create a stack that tracks a lot of statistics (such as min, max, average) using the existing structure stack data with the type of the element that contains the value, as well as these various statistics. These are some trivial examples of what you might need to implement in the real world.

Answer 2

I have repeatedly updated some of the built-in data structures, functions, and language classes. As an embedded developer, the main reason I will do this is speed or efficiency. Standard libraries and types have been designed to be useful in a variety of situations, but there are many examples where I can create a more specialized version specifically designed to take advantage of the capabilities and limitations of my current platform. If the language does not provide a way to open and modify existing classes (for example, you can in Ruby, for example), reimplementing the class / function / structure may be the only way.

For example, one system I was working on used the MIPS processor, which was fast when working with 32-bit numbers, but slower when working with smaller ones. I re-wrote several data structures and functions to use 32-bit integers instead of 16-bit integers, and also indicated that the fields will be aligned with 32-bit boundaries. The result was a noticeable speedup in the code section, which was the bottleneck of other pieces of software.

So this was not a trivial process. In the end, I had to change every function that used this structure, and I had to rewrite several standard library functions. In this particular case, the benefits outweighed the work. In the general case, however, this is usually not worth the trouble. There is great potential for hard-to-debug problems, and it almost always works more than it seems. If you do not have specific requirements or restrictions that do not correspond to existing structures / classes, I would recommend not reinstalling them.

As Michael notes, it’s really useful to know how to reimplement structures, even if you don’t. In the future, you may find a problem that can be solved by applying the principles and methods used in existing data structures.