181–190 of 196 posts
Earlier quoted context omitted.
And you can write them when you need them. The situation where you need a red black tree with 10 different key/value combos isn’t real.
If you can only write programs by banging rocks together, you will only produce programs that can be written by banging rocks together.
Earlier quoted context omitted.
There's a reason carpenters use nail guns. Try it and you'll see!
Well, obviously speed when one is on the clock. All power tools have trade offs vs the manual alternates, often tipping towards their use, but not always. I have had success on an occasion using a belt fed screw gun when fitting plaster boards, especially for ceiling boards. However I don't do joinery often enough to justify the use of a nail gun.
Another thing - a hammer requires 3 hands: 1 for the hammer, one for the nail, one for holding the piece in position. A nail gun only requires 2 hands.
Earlier quoted context omitted.
This is true of the common tombstone approach to deletions in hash tables { which also require rehashing (like in resizing) if there are too many tombstones }. Somehow dissemination of Knuth v3,chapter6.4 Algorithm D has been weak, though it has lately become known as "backshift deletion" - unsure who coined that. It is limited to linear probing (but then these days that also creates the least memory traffic/potentia…
If we look at the major standard libraries for hash tables, you're telling me there will be no overhead to supporting the ability to delete keys? Isn't resizing logic already a counterexample?
If you _do_ know how many entries you're going to be adding upfront, you probably don't even want a hash table, you're probably better off with an array!
Earlier quoted context omitted.
> referring to passed values as distinct from received values. That’s not the distinction being made by those terms. “Parameter” refers to a named variable in a function definition. “Argument” refers to an actual value that’s passed to a function when it’s called. It’s exactly the same as the distinction between variables and values (which you probably see the use for), just applied to the special cases of function s…
Well, I certainly would not interpret the terms that way, but you do you.
Earlier quoted context omitted.
If, by "situation", you mean the development of a small program with so many constraints that using existing libraries is out if the question, then yes. Otherwise, that seems unwise to me. Not every user of a generic type has to be generic. A major selling point of generic types is that you write a library once, then everyone can instantiate it. Even if that is the only instance they need in their use case, you have…
Ok you’re telling me the upside which we already know. Now what’s the downside?
Experienced programmers know when to reuse a generic library and when to roll out their own. We all know that.
Yet you dismiss generic red black trees because there is no realistic single program that uses 10 key/value combinations. Not only is this false, but as I illustrated in my reply, a single program is not the relevant scope to decide whether to use a generic implementation. And as someone who has written a red black tree library, I am definitely in favor of reusing an implementation unless you have an excellent reason, which "I do not need 10 different instances in my program" or "my favorite language and its standard library only have arrays built in" most definitely are not.
Earlier quoted context omitted.
Ok you’re telling me the upside which we already know. Now what’s the downside?
You mean the downside that we also already know, i.e. that there are some situations where a custom data structure would be superior for various reasons (e.g. smaller footprint)? Experienced programmers know when to reuse a generic library and when to roll out their own. We all know that. Yet you dismiss generic red black trees because there is no realistic single program that uses 10 key/value combinations. Not only…
I use generic data structures all the time. That’s the default in programming. We know their advantages.
I am trying to say there is a world out there that doesn’t look like ours and it works just fine and has other advantages.
Are you saying the only real way to program is with generic data structures? I’m saying no because nobody did prior to the late 80s.
> I am definitely in favor of reusing an implementation unless you have an excellent reason
Let me try one more time. If you examine a program you won’t find 10 different red black trees. Data tends to follow a particular path and there is probably 1 red black tree and it’s a core feature of the application.
If that’s true then it’s not a big deal to write that core feature of your application.
It avoids premature optimization and code bloat because you tend to use complex data structures when they have a need.
Array is a good default. It’s how computer memory works, not just what happens to be lying around.
Earlier quoted context omitted.
If we look at the major standard libraries for hash tables, you're telling me there will be no overhead to supporting the ability to delete keys? Isn't resizing logic already a counterexample?
Resizing has to happen regardless of the ability to delete a key, unless you know upfront how many entries you're going to add; I'd be much more worried about a home grown hash table's tuning to rebalance itself at say, 80% buckets full. If you _do_ know how many entries you're going to be adding upfront, you probably don't even want a hash table, you're probably better off with an array!
> I'd be much more worried about a home grown
This is rhetorical framing.
As a knuth reader you should know then when you look inside the box you find some other idiot’s home grown thing who never read the research.
Another way is to not try to write generic data structures. When you tailor them to the use case you can simplify. The #1 data structure in any program is array.
The irony is that arrays in C are in fact generic. As that is the simplest generic solution that doesn't require boiling the ocean first, that's what many programmers reach for.
Another way is to not try to write generic data structures. When you tailor them to the use case you can simplify. The #1 data structure in any program is array.
The irony is that arrays in C are in fact generic. As that is the simplest generic solution that doesn't require boiling the ocean first, that's what many programmers reach for.
Which generic operations does the language provide?