5 ms·

Bloom filters, skiplists, tries, recursive descent, etc. are actually used in many systems and I think it’s important to understand how they work at a high-leve

Bloom filters, skiplists, tries, recursive descent, etc. are actually used in many systems and I think it’s important to understand how they work at a high-level Now, implementing one of them on a whiteboard or without access to internet, knowing all of their intricacies and edge cases…that is stuff I doubt anyone needs to know except a very specific type of developer. If i want an optimized trie I use a library, and when it breaks and i need to fix the low-level implementation, i look it up online

tptacek 4y ago
Recursive descent isn't an oddity; it's a universally useful parsing approach. It isn't the kind of thing where you can "just throw more k8s nodes" at the problem instead; rather, it's one of the simplest ways to throw a parser together quickly. I'm not sure I've ever seen a skip list outside of an algorithms book.
- morelisp 4y ago
  Skip-lists are a common way to implement unflushed data in persistent LSM trees, for example.
  - tptacek 4y ago
    Shows to go you! I'm super weak on durable data structures. This field we're working in, it's pretty neat.
- rad_gruchalski 4y ago
  Redis ordered set is built on top of a skip list: https://github.com/redis/redis/blob/unstable/src/t_zset.c https://github.com/redis/redis/blob/unstable/src/t_zset.c.
- lazide 4y ago
  Having been in the industry for literally decades, I can’t remember ever having reason to write a parser (except for basic CSV type data or web scraping) in real life. shrug I still know how to do it, but I’d have to really stop and ask myself why I thought it was a good idea first. Because it probably wouldn’t be.
  - justinlloyd 4y ago
    Having been in the industry literally decades I have worked on three compilers, two assemblers, a couple of DSLs (before we had some of the newer, fancier tools), a few linkers, a couple of tools that needed to figure out dependencies for assembling a build, a couple of databases and a number of video games that specifically required a recursive descent tree walking algorithm. I consider this class of algorithms to be essential alogrithms in the areas where I have worked, but I also know there are algorithms in use other areas of software development that I have absolutely no practical use for, even though, to reiterate, I have literally been in software for decades. Just because an algorithm is of no use to me, doesn't mean it is no use to you. And vice versa.
    - Jensson 4y ago
      I think you get what you look after. If you don't feel you want to try to push the boundaries of computing and instead prefer working with people then there are way more opportunities there, you don't even have to be good as long as you can connect clients to databases people will pay you. However to me that isn't why I got into programming, that sort of job isn't anything like the jobs I've had, and it is a bit sad to see people in those jobs drowning out most other opinions about programming. Conversely if you love algorithms and are sufficiently good at them then you can spend your entire career with that and never ever talk to non-technical people. Some people here thinks those jobs basically don't exist, but they do exist and are really important and well paid. And once you start working there you can just continue forever since there are so few who have experience working with those. Like, maybe Google asks algorithm questions since they want more people to improve their algorithms? I know they had low hanging fruit everywhere, they just lacked people who were competent enough at algorithms to solve them, their hiring bar is way too low to solve their hard problems. But they can't really raise it either, there aren't enough people that could pass them then.
      - nowherebeen 4y ago
        > Conversely if you love algorithms and are sufficiently good at them then you can spend your entire career with that and never ever talk to non-technical people. I think there are two types of programmers. Ones that are like you that like algorithms for algorithms sake. And the other that like to solve real world problems. I got into software development because I want to solve problems for people. And not all of us likes algo. We prefer to learn stuff that we do use day to day because that has direct impact. For example, I just spent two months understanding functional programming. I use it in my code almost everyday, but it would be worthless in an interview where you are judge by your algo understanding. It’s frustrating when you realize how this standard is forced on every technical role, on companies that don’t even need algo experts because they are too small.
- Jailbird 4y ago
  There was one at work in the 90s. Few of us had heard of it but the search properties against our data in memory were practical and useful (it wasn't just spinning the propeller on our beanies). For years, whenever I'd mention it, no one knew what it was....I suppose it's become more known in the past 10 years.
- armchairhacker 4y ago
  AFAIK skip-lists are in some high-performance systems. See: https://en.wikipedia.org/wiki/Skip_list#Usages https://en.wikipedia.org/wiki/Skip_list#Usages I also thought there were skip-lists used in some part of the kernel or a driver but I don't remember: searching brings up https://lwn.net/Articles/551896/ https://lwn.net/Articles/551896/
dukoid 4y ago
Tries are not mentioned in the OP and I have yet to see an example where they are actually working well.
- metachris 4y ago
  They are very useful and widely used in blockchains.

tptacek 4y ago

Recursive descent isn't an oddity; it's a universally useful parsing approach. It isn't the kind of thing where you can "just throw more k8s nodes" at the problem instead; rather, it's one of the simplest ways to throw a parser together quickly. I'm not sure I've ever seen a skip list outside of an algorithms book.

morelisp 4y ago
Skip-lists are a common way to implement unflushed data in persistent LSM trees, for example.
- tptacek 4y ago
  Shows to go you! I'm super weak on durable data structures. This field we're working in, it's pretty neat.
rad_gruchalski 4y ago
Redis ordered set is built on top of a skip list: https://github.com/redis/redis/blob/unstable/src/t_zset.c https://github.com/redis/redis/blob/unstable/src/t_zset.c.
lazide 4y ago
Having been in the industry for literally decades, I can’t remember ever having reason to write a parser (except for basic CSV type data or web scraping) in real life. shrug I still know how to do it, but I’d have to really stop and ask myself why I thought it was a good idea first. Because it probably wouldn’t be.
- justinlloyd 4y ago
  Having been in the industry literally decades I have worked on three compilers, two assemblers, a couple of DSLs (before we had some of the newer, fancier tools), a few linkers, a couple of tools that needed to figure out dependencies for assembling a build, a couple of databases and a number of video games that specifically required a recursive descent tree walking algorithm. I consider this class of algorithms to be essential alogrithms in the areas where I have worked, but I also know there are algorithms in use other areas of software development that I have absolutely no practical use for, even though, to reiterate, I have literally been in software for decades. Just because an algorithm is of no use to me, doesn't mean it is no use to you. And vice versa.
  - Jensson 4y ago
    I think you get what you look after. If you don't feel you want to try to push the boundaries of computing and instead prefer working with people then there are way more opportunities there, you don't even have to be good as long as you can connect clients to databases people will pay you. However to me that isn't why I got into programming, that sort of job isn't anything like the jobs I've had, and it is a bit sad to see people in those jobs drowning out most other opinions about programming. Conversely if you love algorithms and are sufficiently good at them then you can spend your entire career with that and never ever talk to non-technical people. Some people here thinks those jobs basically don't exist, but they do exist and are really important and well paid. And once you start working there you can just continue forever since there are so few who have experience working with those. Like, maybe Google asks algorithm questions since they want more people to improve their algorithms? I know they had low hanging fruit everywhere, they just lacked people who were competent enough at algorithms to solve them, their hiring bar is way too low to solve their hard problems. But they can't really raise it either, there aren't enough people that could pass them then.
    - nowherebeen 4y ago
      > Conversely if you love algorithms and are sufficiently good at them then you can spend your entire career with that and never ever talk to non-technical people. I think there are two types of programmers. Ones that are like you that like algorithms for algorithms sake. And the other that like to solve real world problems. I got into software development because I want to solve problems for people. And not all of us likes algo. We prefer to learn stuff that we do use day to day because that has direct impact. For example, I just spent two months understanding functional programming. I use it in my code almost everyday, but it would be worthless in an interview where you are judge by your algo understanding. It’s frustrating when you realize how this standard is forced on every technical role, on companies that don’t even need algo experts because they are too small.
Jailbird 4y ago
There was one at work in the 90s. Few of us had heard of it but the search properties against our data in memory were practical and useful (it wasn't just spinning the propeller on our beanies). For years, whenever I'd mention it, no one knew what it was....I suppose it's become more known in the past 10 years.
armchairhacker 4y ago
AFAIK skip-lists are in some high-performance systems. See: https://en.wikipedia.org/wiki/Skip_list#Usages https://en.wikipedia.org/wiki/Skip_list#Usages I also thought there were skip-lists used in some part of the kernel or a driver but I don't remember: searching brings up https://lwn.net/Articles/551896/ https://lwn.net/Articles/551896/

dukoid 4y ago

Tries are not mentioned in the OP and I have yet to see an example where they are actually working well.

metachris 4y ago
They are very useful and widely used in blockchains.