4 ms·

Most people who take data structures courses or perform tech interviews don't end up working on kernels, drivers, or embedded systems though. To me, it sounds l

by saghm 2y ago

Most people who take data structures courses or perform tech interviews don't end up working on kernels, drivers, or embedded systems though. To me, it sounds like the point being made is that there are a large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world, and I think it's accurate.

dmitry_dygalo 2y ago
This was my intention
- SoftTalker 2y ago
  Agree, I can't recall using anything more complicated than lists/arrays or hash tables (key/value stores) in practice, in many years of (mostly web application) programming. And even those I'm not coding from scratch, I'm using classes or functions that my programming language gives me. For anything more complicated than that, I'm using a database, which of course is using many data structures under the covers but I don't directly touch those.
  - sumtechguy 2y ago
    I used to use them all the time. However, now? I would be hard pressed to not use one of the many built in vector/list/dict/hash items in many languages now. I would have to be truly doing something very low level or for speed to use one.
    - josephg 2y ago
      As a counterpoint, I’ve been working on collaborative text editing. I ended up implementing a custom b-tree because we needed a few features that I couldn’t find in any off the shelf library: - My values represent runs of characters in the document. - Inserts in the tree may split a run. - Runs have a size - 0 if the run is marked as deleted or the number of characters otherwise. The size changes as we process edits - Every inserted character has an ID. I need to be able to look up any run by its ID, and then edit it. (Including querying the run’s current position in the tree and editing the run’s size). It’s an interesting data structure problem, and it took a few weeks to have a good solution (and a few weeks more later rewriting it in safe rust & improving performance in the process). I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time!
      - sumtechguy 2y ago
        > I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time! Absolutely! That is one of the places you want to use that style of programming. As the base classes and built in structs do not really cover it yet. Also as a counterpoint sometimes the built in ones have some very interesting degenerate cases. I had one in an old library that basically doubled its memory footprint every time you exceeded its buffer. That was a point to change it to be a fixed allocation or something else. If i had no idea of the fundamentals I would have been totally in the weeds and no idea why it was doing it.
samatman 2y ago
You need a linked list to write hello world in any Lisp, though. Seems like the glaring exception to the rule!
- kazinator 2y ago
  No, you don't need to use linked lists to send a string to the standard output port in most Lisps. You just call a function.
  - samatman 2y ago
    (write-string "hello world") has linked list semantics, the fact that compilers can be smart enough to ignore this is not the point I'm making. (write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.
    - kazinator 2y ago
      > has linked list semantics Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers). Syntax isn't semantics. The semantics is that a function write-string is called, with a string as its argument. The second expression has linked list processing in its semantics because you stuck in a cdr, as well as a quote which makes a piece of the program available as run-time list datum. (This is semantics that could be easily optimized away in the executable form, but I would say that it has linked list processing in its abstract semantics.)
      - samatman 2y ago
        > Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers) We're looking at the same string and seeing different things. You're seeing `(write-string "hello world")` as a program, I'm seeing it as an expression. It has linked list semantics, which you can preserve until runtime like this `'(write-string "hello world")`. Note that I didn't change the string, I changed its context. If the original were living in a string, and you called read on it, it would become a linked list. If you called eval on that list, it would become a function call. This is basic stuff which I'm well aware you know, so I'm not sure what all the quibbling is about. You literally need a linked list to write a program in a language in which the code becomes linked lists. And you're going to have a bad time writing Lisp if you don't get the hang of cons cells, early and often. Is "code is data" true, or false? You're trying to have it both ways here. The "large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world" include approximately zero programmers who have wielded Lisp in anger, is my point. I thought that was pretty clear from context, but I guess not.

by saghm 2y ago

dmitry_dygalo 2y ago

This was my intention

SoftTalker 2y ago
Agree, I can't recall using anything more complicated than lists/arrays or hash tables (key/value stores) in practice, in many years of (mostly web application) programming. And even those I'm not coding from scratch, I'm using classes or functions that my programming language gives me. For anything more complicated than that, I'm using a database, which of course is using many data structures under the covers but I don't directly touch those.
- sumtechguy 2y ago
  I used to use them all the time. However, now? I would be hard pressed to not use one of the many built in vector/list/dict/hash items in many languages now. I would have to be truly doing something very low level or for speed to use one.
  - josephg 2y ago
    As a counterpoint, I’ve been working on collaborative text editing. I ended up implementing a custom b-tree because we needed a few features that I couldn’t find in any off the shelf library: - My values represent runs of characters in the document. - Inserts in the tree may split a run. - Runs have a size - 0 if the run is marked as deleted or the number of characters otherwise. The size changes as we process edits - Every inserted character has an ID. I need to be able to look up any run by its ID, and then edit it. (Including querying the run’s current position in the tree and editing the run’s size). It’s an interesting data structure problem, and it took a few weeks to have a good solution (and a few weeks more later rewriting it in safe rust & improving performance in the process). I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time!
    - sumtechguy 2y ago
      > I love this stuff. I think it’s pretty rare to find a reason to code your own collection types these days, but it certainly comes up from time to time! Absolutely! That is one of the places you want to use that style of programming. As the base classes and built in structs do not really cover it yet. Also as a counterpoint sometimes the built in ones have some very interesting degenerate cases. I had one in an old library that basically doubled its memory footprint every time you exceeded its buffer. That was a point to change it to be a fixed allocation or something else. If i had no idea of the fundamentals I would have been totally in the weeds and no idea why it was doing it.

samatman 2y ago

You need a linked list to write hello world in any Lisp, though. Seems like the glaring exception to the rule!

kazinator 2y ago
No, you don't need to use linked lists to send a string to the standard output port in most Lisps. You just call a function.
- samatman 2y ago
  (write-string "hello world") has linked list semantics, the fact that compilers can be smart enough to ignore this is not the point I'm making. (write-string (cdr '(write-string "hello-world"))) also has to work, so it's pretty easy to materialize that semantics at any point.
  - kazinator 2y ago
    > has linked list semantics Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers). Syntax isn't semantics. The semantics is that a function write-string is called, with a string as its argument. The second expression has linked list processing in its semantics because you stuck in a cdr, as well as a quote which makes a piece of the program available as run-time list datum. (This is semantics that could be easily optimized away in the executable form, but I would say that it has linked list processing in its abstract semantics.)
    - samatman 2y ago
      > Nope; it has linked list syntax (that certainly isn't ignored even by very good compilers) We're looking at the same string and seeing different things. You're seeing `(write-string "hello world")` as a program, I'm seeing it as an expression. It has linked list semantics, which you can preserve until runtime like this `'(write-string "hello world")`. Note that I didn't change the string, I changed its context. If the original were living in a string, and you called read on it, it would become a linked list. If you called eval on that list, it would become a function call. This is basic stuff which I'm well aware you know, so I'm not sure what all the quibbling is about. You literally need a linked list to write a program in a language in which the code becomes linked lists. And you're going to have a bad time writing Lisp if you don't get the hang of cons cells, early and often. Is "code is data" true, or false? You're trying to have it both ways here. The "large number of programmers who have learned about linked lists but haven't run into many cases where they needed them in the world world" include approximately zero programmers who have wielded Lisp in anger, is my point. I thought that was pretty clear from context, but I guess not.