4 ms·

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 arra

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.

dwattttt 1y ago
When all you have are arrays, everything looks like a problem you solve with arrays. There are quite a few problems that specialised containers are suited for, that's why they were created.
- monkeyelite 1y ago
  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.
  - dwattttt 1y ago
    You could take away anything you use and say "but we could make it ourselves", that doesn't mean it's helpful.
    - monkeyelite 1y ago
      Except it’s very common for C programs to contain one-off data structures, so it’s not a hypothetical. It’s a concrete programming style.
      - el_pollo_diablo 1y ago
        Sure, but it is also very common for C programs to contain data structures that have one use in the program, and could still be instances of a generic type. You mentioned red black trees, which are a perfect example of that.
      - dwattttt 1y ago
        Do you mean a data structure they only use once? Or one that's never been done elsewhere? If they only use it once, that seems like the worst effort/pay-off ratio you can get writing it yourself. And I don't think there's that many fundamental data structures out there... and even then, why would it be good to be forced to make your bespoke structure out of only arrays, when things like maps exist?
        monkeyelite 1y ago
        > And I don't think there's that many fundamental data structures out there No. There are a few fundamental ones which work well in a generic context. When you tailor make it you find simplifying assumptions. One I am aware of is a hash map that doesn’t need to delete individual keys.
        cb321 1y ago
        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/potential latency). With this approach, there is no real specialized form of "hash tables that can delete". You may already know all of this and not disagreeing with anything. Just a natural follow-up.
        monkeyelite 1y ago
        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?
        dwattttt 1y ago
        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!
  - el_pollo_diablo 1y ago
    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 saved them the trouble of reinventing the wheel. No colleague of mine may need 10 different instances of any of my generic libraries, but I bet that all of them combined do, and that our bosses are happy that we don't have to debug and maintain 10+ different implementations.
    - monkeyelite 1y ago
      Ok you’re telling me the upside which we already know. Now what’s the downside?
      - el_pollo_diablo 1y ago
        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 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.
        monkeyelite 1y ago
        > Yet you dismiss generic red black trees 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.
  - gpderetta 1y ago
    If you can only write programs by banging rocks together, you will only produce programs that can be written by banging rocks together.
    - monkeyelite 1y ago
      And if you're used to writing programs with Dictionary<String, Dictionary<String, Array<String>>> you will do that too.
gpderetta 1y ago
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.
- deleted 1y ago
  [deleted]
- monkeyelite 1y ago
  How do I write a C function which operates on array of type T? Which generic operations does the language provide?
  - gpderetta 1y ago
    Arrays are generic, but of course C doen't provide generic functions. You can generically copy arrays [1], index them, iterate them, compute their size. But that's not the point, the point is that you can instantiate them for any (complete) T. [1] well, C is weird, so you first need to wrap them in a struct.

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.

dwattttt 1y ago

When all you have are arrays, everything looks like a problem you solve with arrays. There are quite a few problems that specialised containers are suited for, that's why they were created.

monkeyelite 1y ago
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.
- dwattttt 1y ago
  You could take away anything you use and say "but we could make it ourselves", that doesn't mean it's helpful.
  - monkeyelite 1y ago
    Except it’s very common for C programs to contain one-off data structures, so it’s not a hypothetical. It’s a concrete programming style.
    - el_pollo_diablo 1y ago
      Sure, but it is also very common for C programs to contain data structures that have one use in the program, and could still be instances of a generic type. You mentioned red black trees, which are a perfect example of that.
    - dwattttt 1y ago
      Do you mean a data structure they only use once? Or one that's never been done elsewhere? If they only use it once, that seems like the worst effort/pay-off ratio you can get writing it yourself. And I don't think there's that many fundamental data structures out there... and even then, why would it be good to be forced to make your bespoke structure out of only arrays, when things like maps exist?
      - monkeyelite 1y ago
        > And I don't think there's that many fundamental data structures out there No. There are a few fundamental ones which work well in a generic context. When you tailor make it you find simplifying assumptions. One I am aware of is a hash map that doesn’t need to delete individual keys.
        cb321 1y ago
        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/potential latency). With this approach, there is no real specialized form of "hash tables that can delete". You may already know all of this and not disagreeing with anything. Just a natural follow-up.
        monkeyelite 1y ago
        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?
        dwattttt 1y ago
        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!
- el_pollo_diablo 1y ago
  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 saved them the trouble of reinventing the wheel. No colleague of mine may need 10 different instances of any of my generic libraries, but I bet that all of them combined do, and that our bosses are happy that we don't have to debug and maintain 10+ different implementations.
  - monkeyelite 1y ago
    Ok you’re telling me the upside which we already know. Now what’s the downside?
    - el_pollo_diablo 1y ago
      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 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.
      - monkeyelite 1y ago
        > Yet you dismiss generic red black trees 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.
- gpderetta 1y ago
  If you can only write programs by banging rocks together, you will only produce programs that can be written by banging rocks together.
  - monkeyelite 1y ago
    And if you're used to writing programs with Dictionary<String, Dictionary<String, Array<String>>> you will do that too.

gpderetta 1y ago

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.

deleted 1y ago
[deleted]
monkeyelite 1y ago
How do I write a C function which operates on array of type T? Which generic operations does the language provide?
- gpderetta 1y ago
  Arrays are generic, but of course C doen't provide generic functions. You can generically copy arrays [1], index them, iterate them, compute their size. But that's not the point, the point is that you can instantiate them for any (complete) T. [1] well, C is weird, so you first need to wrap them in a struct.