|
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
|
|
|
|
|
MSI is an abomination before all known deities. Before we started using Inno Setup we tried InstallShield, which generated MSI. I spent over a month trying to get our stuff installed properly. When I found out they wanted over $1K for each additional user language to support localized installs, I said screw it and went looking.
After finding Inno Setup, I replicated our product install in in a single day.
Software Zen: delete this;
|
|
|
|
|
|
It was indeed called Orca, and was part of the Platform SDK.
A few links brought me here: Windows SDK - Windows app development | Microsoft Developer
There's no direct link to it however, it looks like you have to download the entire SDK just to get that one file.
[Edit]
Oh, and here. Although this still has no direct link.
|
|
|
|
|
Yes, it's Orca. But that's like doing assembly programing. I wouldn't wish it on my favorite enemy.
Bond
Keep all things as simple as possible, but no simpler. -said someone, somewhere
|
|
|
|
|
I don't remember it being terrible for modifying MSIs as long as you knew how they worked, but I wouldn't use it to build one from scratch.
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
