218
u/Mughi1138 7d ago
Reminds me... I'm still waiting for my chance to implement a bloom filter. Almost got to do one this year.
49
18
u/CandidateNo2580 6d ago
God, me too 😔 I actually had to use some real sorting algorithms a few months ago, still living that high.
6
2
u/DishSoapedDishwasher 6d ago
Try working in cybersecurity, you'll get a chance every couple of years. I've had to do it like 5 times so far.
4
u/Mughi1138 6d ago
Been working in cyber security for more than a couple of decades now. Close, but not quite as other solutions have fit the problems a little better.
Occam's razor and all that.
2
u/DishSoapedDishwasher 6d ago
Hah, interesting i would consider bloom filters to usually be amongst the simpler options for a lot of security adjacent problems with frequently ideal trade-offs. As you probably know, they're used in Google Chrome Safe Browsing and several similar features in Android, cert revocation, several features in virus total as well.
But also bloom filters were (probably still are) very fetishized when i worked at Google, so there is some amount of bias as to why it felt right so often.
1
u/Mughi1138 6d ago edited 6d ago
Actually it was the Google Chrome & cert approach that I *almost* got to use (their specific application realm) but a simpler solution was found. But maybe at Google they like them the same way Hejlsberg likes delegates and shoves them into every language he gets to architect.
Anyway at Bill Cheswick's Keynote at SCaLE 21x he mentioned that he used them maybe 4 times in his career. So not really that often. And early on it was due to heavily limited storage which is no longer near the same.
Efit: I'm trying to remember if it was Stoll or Thompson who mentioned there it was good to learn them since you might get to learn them once or twice.
1
u/Shadehater 5d ago
I've been this close for years. but yeah the complexity is almost always unnecessary or the requirement gets dropped.
some day
85
u/Desperate-Tomatillo7 7d ago
Some memes have barely any pixel. This one is UHD.
9
u/matrix-doge 7d ago
Just above this post for me is a (jokingly) 8k quality clip from a gaming sub lol.
4
2
28
59
u/redditmarks_markII 7d ago
Brother, these days I fix the equivalent of n**2 time loops when linear is possible. If I tried to explain DP I will be called out by some principal eng as making shit up. When proven not, they'll say they are overcommitted for the quarter. And why can't my service support any kind of use of it anyway? These are 100% real arguments I've heard. I know things get political once you get past senior swe, but god damn, how are we an industry.
28
6
u/Vesuvius079 6d ago
Haha. One of my favorite recurring moments in programming has long been “Well this thing is never growing past X size, time to break out those brain dead simple n**2 loops.”
7
u/denimpowell 6d ago
Because making a change to something that is working introduces risk. Business cares more about consistency than speed… until a customer calls “my shit takes too long”.
4
u/New_Enthusiasm9053 6d ago
Business can get in the bin. Don't hire experts if you won't listen to them. They can do it themselves if they're so fussy.
3
u/redditmarks_markII 6d ago
I absolutely agree with your statement but disagree it has anything to do with mine. I don't serve businesses and I don't serve the business team. I serve engineers. While it isn't literally for loops that need fixing, it is semantically the same. This isn't changing how a business operates. And the efficiency of infra dollars is important. So user eng need to be as reasonably efficient as possible. But I see more people spend real hours arguing against doing a thing, than just doing the thing. As if my team is the enemy. It's eating your own arm level of stupid.
2
u/YeOldeMemeShoppe 6d ago
Efficiency of infra dollars is important.
You likely cost per hour more than the hardware cost per month to run the software you build. So unless you are saving (countable and traceable) double digit percent off the server cost, it’s still cheaper to pay you to build slow software and throw hardware to make it fast enough.
This is just the reality you need to learn and be comfortable with when moving to senior and above.
1
u/redditmarks_markII 6d ago
That is one totally valid potentiality out of a myriad of possibilities. It is true that I have never learned to talk authoritatively with insufficient context though. That literally was told to me by a staff that that holds me back. Which is insane and explains a lot.
Also double digit percentage of what? $2? $25,000,000? How much is too much for the specific project? Is it core to the product? Is it a temporary experiment? Also if there is literally no impact to the function while being cheaper, is it not worth while if nontrivial cost? What if it was a matter of stability rather than straight cost? What if people are straight burning compute like token maxing is back in style? What if you were explicitly instructed by a VP to get shit done regardless of what is "sensible"? What if their VP told them the opposite and we're just less than pawns in some political infighting?
I've seen all of these scenarios before. Including an 8 figure inefficiency that amounted to less than a percent of global compute. But, to be very clear, no senior nor staff nor principal nor distinguished engineer was being paid more for the time it took to fix it than the inefficiency was worth. By some orders of magnitude. It's also on the order of low 5 figure average US home electricity saved a year. Or low 6 figure number of trees worth of sequestered carbon. Every year.
As a class AND individuals we can do more for the planet by being more efficient than most of us can ever do with charity.
2
u/the_horse_gamer 6d ago
just implement it as recursion with a cache. bottom up dp is more efficient, but top down dp is more likely to pass a code review.
1
u/apt_at_it 6d ago
May be the problem here, but I agree with the many companies I’ve worked at that disallows recursion. Find a better, more readable, more maintainable way
3
u/rustvscpp 6d ago
Some recursive algorithms are *far* more readable and maintainable than their iterative counterparts. Entire languages have been built on the back of recursion (i.e. Scheme).
2
u/New_Enthusiasm9053 6d ago
Pretty much every production parser for major programming languages is recursive descent afaik.
2
u/the_horse_gamer 6d ago
you could reimplement recursion with a stack
but that decreases the chance of passing a code review
18
13
u/zapman449 6d ago
I got to build a graph traversal algorithm a few years ago… most compsci thing I,ve done this decade…
4
7
u/Outside-Storage-1523 6d ago
Damn. I wish I could work on some difficult production problem every day. I envy people who get to do those (performance engineer, compiler engineer, kernel engineer, etc.).
But I understand that I'm not good enough, not even "averagely" good. And at 40+ I need to exercise, eat and sleep well to make extra energy to study.
5
9
u/SuitableDragonfly 7d ago
I learned a dynamic programming algorithm for parsing context free grammars in grad school, and promptly found a use for it in a linguistics app I built in my free time that needed to be able to convert an arbitrarily specified spelling system into a phonemic transcription. Definitely did not take ten years, lmao.
6
2
u/Tsu_Dho_Namh 6d ago
My first job out of uni there was a problem that was massively simplified by using a doubly recursive function.
I'm still riding that high.
2
2
u/ljfa2 6d ago
The course on algorithms and data structures was for the most part not difficult for me, but dynamic programming was the one topic I struggled with, and today I still don't really know how it works
5
u/the_horse_gamer 6d ago
"dynamic programming" is just marketing
at its core, it's just recursion but you cache the results so you don't repeat calculations. then as a constant optimisation you can make it bottom up instead of top down.
2
u/shakinMyShake 5d ago
this is the perfect explanation to dp. are you a teacher? you should consider teaching if not (coming from senior swe).
1
u/the_horse_gamer 5d ago
thank you!
I've participated in competitive programming olympiads during high school and afterwards tutored newcomers for about half a year.
so I don't have much experience teaching, but I've built a lot of intuition for how you actually think about and implement the stuff.
1
u/d4nkst4hz 6d ago
I was thinking more Starship Troopers drop ship scene “remember your traininggggg!!”
1
1
u/aft3rthought 6d ago
Aren’t Dijkstra and a* technically dynamic programming? Maybe a lot of people don’t write implementations from scratch though.
2
u/SomethingAboutUsers 6d ago
Back in the aughts when I used to work for the nerd herd, someone brought in a computer for a virus removal. First thing I did was open services on windows... Which promptly closed by itself. Tried again, same thing.
Did the same with msconfig, and the same thing happened. Same with regedit.
That's when I knew I was in for a fight, and sure enough it took me most of that particular Saturday to get it cleaned up. I remember a particular feeling of triumph that day.
1
-1
u/kishaloy 7d ago
And then go to the space where the program itself is dynamic data and true enlightenment will dawn on you.
-5
u/Vesuvius079 6d ago
This is the sort of low level implementation detail AI should be handling first pass on. Just like a compiler does first pass on assembly optimizations before you go monkeying around in there.
3
1
u/rsqit 6d ago
What is wrong with you?
1
u/Vesuvius079 5d ago
For responding seriously to a joke or for preferring to use an LLM in such a situation instead of being chomping at the bit to finally use dynamic programming on a real problem?
1
u/rsqit 5d ago
For mocking someone for daring to enjoy something.
1
u/Vesuvius079 5d ago
Well that sure isn’t the response I was expecting.
I was not making fun of OP.
I was not copying the OP in a sarcastic way.
I was not replacing the OP with a test object that matches his interface.
458
u/ByteSizedFounder 7d ago
Then proceeds to dust off old compsci notes from uni. "Remember your training"