|
Even though I've been writing code for a long time, I often find that I don't understand things the way I should.
I've been reading Grokking Data Structures[^] (Manning publishers -- I mention because they do a great job on books)
A few years ago I read, A Common-Sense Guide to Data Structures and Algorithms, Second Edition: Level Up Your Core Programming Skills 2nd Edition[^], so along with the experience I have I had a good foundation.
However, this book goes in depth explaining how Data Structures are built on top of UDT (User defined types) and it is absolutely fascinating. The only problem I have with the book is that the samples are written in Python.
I've used a Bag data structure in ASP.NET (ViewBag) but I never really thought about how it is implemented and this book explains that type of stuff.
I'm 70% thru and it's a really great book.
Have you read it?
|
|
|
|
|
raddevus wrote: Have you read it?
Nope, but totally applaud you for peeking underneath the hood to get your learn on.
Jeremy Falcon
|
|
|
|
|
Have not read it. Even though I guess that it wouldn't have taught me very much new stuff, I might have considering buying it, just to pick up the way things are formulated today. But ...
The Amazon sample pages doesn't give me a single sample. I can flip through from the title page, colophon, the brief table of contents, the foreword, the preface, the acknowledgements, the About this book, About the author, and then, finally, eight text lines from the first chapter, which is essentially 'Welcome to this book' (as if all the preceding blurb is not enough of 'welcome'!). There is nothing to show the style of problem discussions, nothing to show the expected knowledge level.
This book is so new that there are no revealing user reviews. The amount of blurb is so large that I honestly do not think this is any sort of directly-to-the-point-with-a-minimum-of-fuzz book for seasoned professionals. So for now, I will not order a copy.
That being said: For the major part of my university, data models (a.k.a. data structures) was an essential part. We spent quite some time on creating database schemas (this was in the CODASYL-relational transition, so we were into both models), we did a lot of work on entity-relationship models (which I still think of as one of the lost pearls of information technology), and class based data modeling.
In our senior year, the last semester, our entire class was split into a number of subproject teams, each assigned to a different main module of a complete software system. The idea was that we should gain experience in cooperating with other teams. The professor in charge had just been caught by some 'functional design' ideas, demanding that all interactions between modules should be through function calls and their parameters, with no common data whatsoever. No data structure design - each module might have some static structures, if they preferred, but none of it should be revealed to others. Seen in a bird's eye perspective, there were no other data than those passed as parameters.
To say that the project failed miserably is to put it in rosy, romantic terms. None of the teams were able to produce anything useful. One significant part of the explanation was that we all had been taught the importance of well designed data structures. Without it, we were lost. But the professor's ideas were coming in like a tsunami, so maybe five years later, when data structures / models teaching had been completely abandoned, those students would have made a greater success.
I have not seen good data modeling returning to the mainstream yet. I still miss it. I still tend to sketch data structures on paper to make clear to myself how complex information sticks together, but whenever I present it to any programmer younger than myself, they are unable to see the data as entities independent of the operations you do on them, but defined by their relationships. Modern programmers immediately start attaching various methods to them, replacing data relationships with one, two or more specific method calls for changing object attributes, pushing aside the relationships of the data model.
From the table of contents of this book, it does not seem to point to data model design. 'Arrays', 'Queues', 'Stacks' is at a very elementary level; it does not suggest system design by data model design. Furthermore, it points towards coding techniques, not modeling techniques.
So I guess that if some youngster comes to me for advice on data structuring, I will have to dig into my basement to find my old textbooks, published 40-50 years ago. Unless someone can suggest newer textbooks on how to do system design based on a data model. Not system implementation and coding - design.
But I guess that doing proper system designs is not agile enough in today's software development environments. System design is intitiated by first typing 'int main(int argc, char **argv){}' and take it from there as ideas and requirements come to mind.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
trønderen wrote: Amazon sample pages doesn't give me a single sample
Oh, that's unfortunate. I'm reading the book from my oreilly.com subscription where I can read all of these books so I didn't notice that.
trønderen wrote: I have not seen good data modeling returning to the mainstream yet.
There is a weird movement (probably caused by Universities getting stuck on the Functional Paradigm) where new devs are literally saying that OOP is evil. It's crazy.
Instead of learning from the past and building on it, they burn everything to the ground & then start out with dirt & say, "We've built the newest thing. It's dirt and we can make the best structures from it with a little water. And also, we are so much smarter than those who came before us."
Yeah, I've noticed the move away from any type of planning too.
Anyways, the book isn't actually written on that it just gets to the basics of Data Structures.
If you're interested, but you probably aren't.
The Manning book site is actually much better.
Check out this link and you can click on chapters[^] in table of contents and read actual chapters.
I just thought the book was interesting. I've discovered over the years that I often believe that other devs ("architects") know all of this foundational stuff and then I discover that they don't know it either.
|
|
|
|
|
trønderen wrote: demanding that all interactions between modules should be through function calls and their parameters,
Ah...the good old days of RPC (Remote Procedure Calls). Everything was a RPC - even get/set. What more could one want from an ideal world?
trønderen wrote: So I guess that if some youngster comes to me for advice on data structuring,
I will stick with "Algorithms" by Sedgewick.
|
|
|
|
|
jschell wrote: I will stick with "Algorithms" by Sedgewick.
That may very well be an excellent book, but from the table of contents and the available pages, it doesn't at all look like a data structure design textbook. More like a data structure implementation textbook. (It may be excellent at that.)
My rule of thumb is that a design can be implemented in any programming language. Hence, it can be presented and described without resorting to any specific programming constructs. An architect presenting a floor plan to you doesn't go into the kind of wood panel that will be used. The exterior drawing, showing the windows and doors, doesn't go into the mechanism of the window hinges. Maybe the exterior shows the outer walls as flat surfaces, like concrete walls, but you may take the drawings to a carpenter who will build you a wooden house.
To me it looks like the Sedgewick book is not primarily aimed at teaching you how to draw neither the exterior of the house nor the floor plan. Nor the placement of the technical installations. When a designer has created a room of 10,000 data elements, Sedgewick can teach you alternative ways to manage those 10,000 data elements - but not why those data elements were placed there. And how they relate to another 1000 elements. And which properties are shared by those 10,000 elements and how to handle the sharing. And so on.
The title is honest: The book describes algorithms, not data structures. Well, trees and lists and arrays are data structures at the coding level, but they are not made for designing information interrelationships at the problem domain level.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
trønderen wrote: Hence, it can be presented and described without resorting to any specific programming constructs
My opinion is that code examples make it more clear.
And the Sedgewick book comes in a number of different languages.
trønderen wrote: When a designer has created a room of 10,000 data elements,
Books that claim to teach you how to design 10,000 elements are no better than books that claim to teach you how to sell or manage people.
trønderen wrote: The book describes algorithms, not data structures.
Do you think you can create a entire book, lets say 400-500 pages about data structures and not discuss algorithms at all? For example how do you discuss, in detail, the algorithmic differences between using a hash/dictionary versus a single link list without discussing searches?
Sedgewick has a lot of discussion about how to create a hash value. You better understand that before you attempt to use a dictionary.
The other book I have specific to the subject is "Data Structures and Algorithms" by Aho, etc. Chapters
Chapter 1 - Design and Analysis of Algorithms
Chapter 2 - Basic Data Types
Chapter 3 - Trees
Chapter 4 - Basic Operations on Sets
So even Chapter 1 is Algorithms and back to those in Chapter 4. But even Chapter 2 has an entire section labeled "Stacks and Recursive Procedures"
|
|
|
|
|
jschell wrote: My opinion is that code examples make it more clear.
Have you ever designed a non-trivial relational database schema? Like, with a few dozen tables interconnected through foreign keys, various constraints, and all in 3NF?
If you have, did you describe the database through SQL code? Did that help making the database design more clear?
I suspect that your answer is "No - I never designed any non-trivial relational database". I also suspect that you never went into any complex organization trying to grasp the kinds of information they are handling, how it interrelates, which is the authoritative value from which other copies can be made, which parts of the information structure is managed by which software system, which actor is the responsible for each (set of) entities, which information needs special consideration e.g. due to confidentiality or security concerns etc. etc. And after doing such an analysis, identifying an interconnected subset of the information elements, and shaped into 3NF to be realized as database relations.
What I am saying is that from your arguments, it sounds as if you have never been even close to such a data modeling and design task. To phrase it somewhat more rudely: It sounds as if you don't have a clue what data design is about. I may be wrong; my only basis for drawing this conclusion is the arguments you have presented here.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
trønderen wrote: Have you ever designed a non-trivial relational database schema? Like, with a few dozen tables interconnected through foreign keys, various constraints, and all in 3NF?
Yes.
trønderen wrote: If you have, did you describe the database through SQL code?
Not sure what you are asking. Perhaps you are asking if I created an actual design document(s) rather than just winging it. Then yes I did do that. Multiple times.
trønderen wrote: I suspect that your answer is "No - I never designed any non-trivial relational database".
oops you guessed wrong.
I have worked as an architect from day zero and day one startups. I have created enterprise designs for entire companies from scratch (designed then coded the database from scratch.) I have been a DBA team lead. I have been working in the database to code layer domain for 40 years. I have been a principle designer, reviewer and process developer for more than 20 years. That includes creating process documents from everything for the entire enterprise down to even integration and unit testing level. I have written so many designs, actual documented designs, that I could not possibly attempt to enumerate the number.
And I have read a lot of technical books at various levels. I have probably about 80 technical books. Those are the ones I kept. I purged at least twice that number a number of years ago. So I do have some expertise in understanding what a book can effectively cover.
So that is my background - what is yours?
trønderen wrote: To phrase it somewhat more rudely: It sounds as if you don't have a clue what data design is about.
Well you got that one wrong. So perhaps some of your other conclusions are also based on incorrect assumptions.
|
|
|
|
|
I've read some more formal work on data structures and algorithms, but primarily I taught myself, and later found out there was already a name for what I produced. "Oh, that's called a linked list" - hazards of learning to code way back when I did and with no guided instruction.
I missed out on a lot. That's the nature of learning the way I did. One thing I did however, was explore parsing and automata theory pretty extensively in order to shore up a lot of my fundamentals.
C++ sort of filled in the rest as I learned about STL containers. Like I said, I had already pretty much implemented all of them at one point and in one language or another. C++ just gave words to what I had built.
I don't know what I don't know ... yet so clearly I have more to learn, but I'm confident that I've covered the basics at this point.
The only time I need more complicated structures than what C++ STL containers allow for is really in optimized relational databases.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
I have a similar experience.
I have also used many of these data structures (ds) but never implemented them.
Then, of course, over the years C# included many data structures & algos in libraries so you just use them but I haven't thought (deeply or deep enough) about why one ds and/or algo is inherently slower but more useful than another.
I find this book quite good in that it reminds me that most all these data structures are built on top of an array (wrapper class with helper methods).
The one ds that I'm interested in is the Tree bec I've used them a bit but never thought about how they're implemented.
|
|
|
|
|
raddevus wrote: it reminds me that most all these data structures are built on top of an array
Many are, until you get into linked lists. That's the main exception. 
There are a lot of different trees out there. B+, AVL, Red-black etc
I provide some in C# here
Bee: A Suite of Self-Balancing Binary Tree Based Dictionaries[^]
Maybe they'd be of some interest.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
honey the codewitch wrote: Many are, until you get into linked lists.
Oh, that is a good point. LinkedList is iterable list of Node (UDT).
Yes, interesting how that is the split that makes data structures different too.
Adding item or retrieving from array is O(1).
But, LinkedList retrieving is O(N) - linear.
Here's the best line I've read in the book so far, "It's easier to code it than to explain or understand it." i'm not kidding, this is in chapter 10 Priority Queues & Heaps and it cracked me up.
I searched Google Books to see if I could find that quote and you can see it here[^].
|
|
|
|
|
honey the codewitch wrote: Many are, until you get into linked lists. That's the main exception.
I beg to differ ...
I've told this story before, but it can take a retelling: In my student years, I was a TA at the introductory programming course for about 1000 students a year in all sorts of engineering disciplines. About half of the departments had switched to Pascal, but the classical disciplines clung to Fortran as the only language that engineering will ever need. The Fortran and Pascal classes were made as similar as they could be, with identical homework assignments.
Except for the last one: The Pascal classes had a problem to be solved using by linked lists. The Fortran classes had a completely different problem; I have forgotten the details.
One of the girls in a Fortran class came to me, slightly annoyed: Why is is that the Pascal student are given a different problem? Are they learning something that we are not supposed to learn?
She was so actively focused on this that I spent a few minutes explaining how Pascal had this pointer mechanism, where a value could be be treated like an array index, treating the entire memory as a huge array. If you handle these array elements 4 at a time, say, for 3 data values and the fourth as the index of the next record, then you can string together records in a list. That is what they are doing for the Pascal problem. Fortran doesn't have this pointer mechanism, therefore you cannot do it in Fortran.
I don't remember how much details she asked from me, how clearly I said that in principle you could use a plain integer similar to a pointer, as an array index. In any case, I was completely unprepared when she next week came to me with a Fortran program, solving the Pascal pointer problem using an array. Is this the way you were saying that it could be done? ... That is not what you expect from a freshman chemistry girl student
I had no critical comments to her solution. She had in a fully satisfactory way implemented a linked list solution based on an underlaying array mechanism. (I really should have taken a note of her name to see where she ended up; unfortunately I didn't. I am quite sure that she must have made it well.)
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
That's not particularly common though. My statement was intended as a generality, not as an exhaustive absolute.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
So let's take another example: Lots of genealogy programs store family trees in a relational database. A database relation is an array - in this case, an array of person records. A person's ancestor or descendants (or both) are stored in the person record as the primary key of the related person.
If you now argue: But that's a tree - I was talking about a linked list! Then: A linked list is a special case of a tree where each node only has a single descendant. There is nothing about this special case that indicates that it requires an implementation different from a general tree.
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
A database index is typically implemented using some kind of b-tree, and if it's stored in a contiguous block, it's on the disk and for performance
When you do this
typedef struct node {
int data;
node* next;
} node_t;
That is a linked list. Typically that is not contiguous. It is not array. You are giving corner cases where it is an array.
I don't care about corner cases when speaking generally.
I'm talking about how data structures are made. There is not a requirement that linked lists be contiguous in memory, or on disk and they are usually not.
I stand by what I wrote.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
Well, of course! If you restrict yourself to ones specific implementation technique for the general concept of a linked list, then you get that specific implementation - with the implication that you cannot store a linked list in a database relation. I think that most programmers can do it.
And while we are at it: 'Array' and 'contiguous in memory' are not synonyms. A language may allow an array to grow and shrink. An implementation may of course choose to copy the entire array to a new location every time the array size changes, or it may allocate space for the array as set of segments, making the array as a whole non-contiguous in memory. As as programmer you wouldn't see the non-contiguousness of the array. Actually, an array may be broken up into segments in any language if it crosses a page border and your machine uses a page based virtual memory system. Then you may of course argue that there is a principal difference between a runtime system splitting the array into disjunct memory segments under the hood, in a manner invisible to you, and the operating system (with the help of some tailor made hardware) splitting the array into disjunct memory segments under the hood, in a manner invisible to you.
If you want do to any decent data modelling, you should not concern yourself with whether the data structures are physically contiguous on disk, contiguous in a linear file space, contiguous in RAM etc. You should be concerned about an array qua array, a list qua list, a queue qua que, a hash table qua hash table.
I believe that doing all design - data structure design or other design - as an integral part of the coding is not going to lead to the best structures, neither data structures nor code structures. But I admit that not starting the data design by typing 'int main(int argc, char ** argv)' is a less agile approach.
Do you consider 'char ** argv' an array?
Religious freedom is the freedom to say that two plus two make five.
|
|
|
|
|
If it's not contiguous in memory it cannot be used for the same thing, and has different performance characteristics than an actual array.
And yes, I WILL concern myself with how data structures are implemented so that I can know what big O performance metrics it has.
Any language that breaks contiguousness of an array doesn't use arrays, but rather it uses a data structure that's not an array that it calls an array.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
modified 9-Sep-24 9:04am.
|
|
|
|
|
Do you consider 'char ** argv' an array?
I consider it a pointer to the first element of an array of pointers.
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
|
I've been buried in legacy maintenance of other people's 💩 for a while, to the point where I really don't want to come in to work  . Among other things I do our installers, which encapsulate several third-party packages. Today, we've discovered a problem that's fixed in a new version of a package. The new package requires that the old one be uninstalled before the new one goes in. While this isn't too hard, the uninstaller isn't silent and the user has to click on a number of buttons for it to do its thing.
Here's the fun part. For a long while I've wanted to have my installer click buttons automatically so that I didn't have to rely on the user doing it. Even when I include detailed and explicit instructions in my installer, they sometimes screw it up. We use Inno Setup[^] which lets you call functions in a DLL of your own from their Pascal script. I use this feature for several things that aren't easily accessible from script.
I'm implementing an auto-click feature in the DLL that spins up a thread that watches for windows with a caption and then clicks a specified button in that window. It looks like it's going to work.
I'm happier than a pig in slop ![Jig | [Dance]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/jig.gif) .
Software Zen: delete this;
|
|
|
|
|
But according to the docs, InnoSetup does also understand the command line Parameters /SILENT and /VERSILENT. They did not work for you?
|
|
|
|
|
This is the case where the encapsulated installers don't support silent installs or uninstalls. I even have one case where a command line installer when run with the silent option still pops up a message box when it completes   .
Software Zen: delete this;
|
|
|
|
|
I used to rip apart MSI files with some MSI decompiler thing that I used to have, and then modify them to make them unattended.
I wish I could remember the tool name. Orca or something?
Check out my IoT graphics library here:
https://honeythecodewitch.com/gfx
And my IoT UI/User Experience library here:
https://honeythecodewitch.com/uix
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
