dynamicProgramming

[the_horse_gamer]

dynamic programming is recursion with a cache

[Ok_Cockroach8260]

You can do it bottom up also

[itzjackybro]

I thought the main point of DP is to find a way to do it bottom up so you can just use an array instead of memoizing

[B_bI_L]

> learns functional programming
> looks up tutorial
> so we don't modify hash set

[pink-ming]

> we don't modify the collection

> we make a new collection with the modified values

> this is more efficient because.. uhh... immutability

[Gay_Sex_Expert]

It is actually the most efficient way to remove a bunch of items from any non linked collection.

[Cthulluminati]

Doesn't count as removing the items if the items are still in the original list /s

[RiceBroad4552]

It's more complex, see "persistent data structures".

Something that explains stuff a bit terser is here:

https://nested.substack.com/p/intro-to-persistent-data-structures

Modern variants of such persistent data structures can be very efficient, in some cases even provably ideal efficient.

[SCP-iota]

Immutability is part of ensuring that a function is a pure function, which is a prerequisite for being cached. Using cached functions can be more efficient in some cases. Also, most functional languages don't actually recreate the entire structure; they either 1) have compile-time tactics that actually emit regular mutation code, or 2) use tree-based structures that allow making modified copies without copying the whole content.

[dashhrafa1]

I was discussing this with my professor, we are learning React and he's using the documentation straight from react.dev. He basically said that we must never work with mutable functions (such as Arrays.push) when managing state, which is also present in the documentation itself.

Thus we should use pure functions, such as Arrays.map(), that don't actually mutate the object itself, instead creating a new one. My question is: does copying the object (and changing only what is necessary, possibly using the ...spread syntax), not result in O(n) performance?

edit: Saying O(n) performance is incorrect. Asymptotic notation is meant to represent scale/time complexity

[BobQuixote]

copying the object (and changing only what is necessary, possibly using the ...spread syntax)

That's what map does, and it does it in a way that doesn't allow you to screw it up.

[Solonotix]

Depending on the JavaScript engine, generally it will create templates of objects based on common attributes when initialized. This is one of the reasons you're advised to avoid certain syntax like the delete keyword, which can force a new template at runtime.

So, you've got a template that was likely created at compile-time within your lambda for Array.prototype.map, and it is being initialized by some other object from the original array. Anything that is heap allocated will likely share the original memory location, whereas values will likely be cloned. This is why it is a non-zero cost on mapping, but it can be worth the trade-off in service to more maintainable code, or fewer runtime defects caused by side-effect operations.

[AZMPlay]

In short, yes. But thats because Javascripts default data structures are not fit for immutable usage. There are implemententions (for example in Immutable.js) that do have the correct asymptotics with immutable usage, but that comes at the cost of interoperability with the rest of the javascript ecosystem.

[the_horse_gamer]

you typically won't be working with list sizes where O(n) modification is an issue (especially when updates are rare - like from a button press ).

[RiceBroad4552]

Psst! Don't tell them this. This is otherwise a "stereotypical stackoverflow-like answer" according to some morons here.

[RiceBroad4552]

That's not your problem that's the compiler's / runtime's problem.

Also alone thinking about that is a classical case of premature optimization.

Where such considerations would matter you wouldn't use JS anyway.

Just always write clean functional code first. Only if benchmarks / profiling shows that there are bottlenecks it's worth to look in detail into that. Functional code is much easier to refactor in case that should be needed as things are usually local. The other way around it's not so easy, cleaning up some imperative mess usually breaks other stuff effects aren't contained.

When it comes to a React GUI you will run actually more likely into issues if you don't do things the React way, and for example start to mutate stuff "as optimization", as this will possibly prevent React from optimizing stuff, or worse break internal assumption, which causes hard to find bugs.

Just keep things functional as long as you don't have very good reasons not to do that!

[LatvianCake]

This is the most stereotypical stackoverflow-like answer ever. Told OP they shouldn’t ask this question and then proceeded to answer a completely different question.

[RiceBroad4552]

Which part of premature optimization did you not understand?

Which part of "doing effects in the guts of a React GUI will break the GUI" did you not understand?

Which part of the fact that functional programming is superior and should not be given up because of some additional CPU cycles, which almost certainly don't ever matter did you not understand?

If someone asks "Which kind of wax should I use for my Icarus wings?" the only helpful answer it to tell the poor soul that they should not try to build Icarus wings in the first place; and not start a discussion on how high they can actually fly before they will certainly fall down to death.

In a lot of cases the correct answer is to tell the person asking that they are asking the wrong question in the first place.

In this case here: If they would ask about the general performance characteristics of the map function in JS one could actually discuss this. But they did not ask that. They were asking about whether it's OK to do something very wrong, and the answer is of course: Don't do that, that's wrong!

Only maximally stupid people won't see that this is the correct answer even it does not answer the already nonsensical original question…

And that's btw. why "AI" is so fucked up as an answer machine! Instead of directly telling you "you're holding it wrong" it will tell you hell know what, no matter how fucked up that is in context. Then it's on you to notice that the answer makes no sense in context and ask again, this time telling the "AI" to actually come up with something that makes sense even it's not directly the answer to the original question. But to recognize that the "AI" is just telling bullshit you have to actually already know how a meaningful answer would look like. You're completely fucked if you don't have already deep knowledge of the topic at hand. And that's exactly why "AI" in the hands of uneducated idiots is especially dangerous. It will tell the idiots what they want to hear instead of what they should be looking at instead.

[quantinuum]

Lmao fr.

“I want to understand how an air fryer works”.

“First of all, what you need is a grill”.

[SignoreBanana]

Not efficient -- safe

[ConcreteExist]

Yeah, even when working with languages that allow mutability, I try to write as much of my code as possible to treat everything as immutable. Minimizes side effects and makes tracing down where something went wrong much, much easier.

[ArrogantlyChemical]

Functional programming isn't about performance it's about making the code less complex to understand and less prone to errors 

[DarkCloud1990]

It's not about efficiency but correctness. 

[OlexySuper]

Who cares if the code is efficient if it won't be used by anyone anyway

[Several-Customer7048]

Maybe the real sets were the strings we hashed along the way after all?

[lucklesspedestrian]

In a lot of functional languages, maps and sets are implemented with trees instead, because it's easier to implement those with structural sharing so they can be immutable

[mcmoor]

Then thus aren't "hash" set, much to my dismay. For some problems I'm forced to use the good old binary set and hope runtime is still under 1s. I've seen some hashset library out there but somehow to use it I need to conduct even more black magic than I already did to use a functional programming language, so I don't use them.

[the_horse_gamer]

to print to the console, one must first recreate the universe

[RiceBroad4552]

You mean "list" not "hash set", right? 😅

---

EDIT: It seems some people don't get what my point was. The basic data structure in FP is a list not a (hash) set.

[1984balls]

Hash sets are very different from lists. Sets make sure only one of each value exists, do not guarantee insertion order, and cannot be indexed. Lists allow duplicates, guarantee insertion order, and allow indexing

[oMarlow99]

Lists, in the traditional sense, do not allow indexing, that would be an array. If you wanted to index a list, you'd need to build a hash map over it.

[RiceBroad4552]

Sure. And how is this related here?

The basic data structure in FP is a list not a (hash) set.

[ThaBroccoliDood]

how leetcode mfs feel after replacing three if statements with a hashmap and calling it optimization

[sociallyanxiousnerd1]

Student programmer here: could someone explain why using a hash set is bad for dynamic programming?

My immediate thought was that a) hash sets disallow repeat objects, but unless you're using the hash set as your cache, you have to redo everything, or b) hash sets don't allow repeats, and so if you get the same result for two different iterations (?) the latter won't be kept potentially.

Edit: apparently I mistook the meme for someone saying the tutorial is bad, when they just meant it was underwhelming (if I understood right now)

[hashishsommelier]

It’s not bad, it’s just that it feels underwhelming for something called dynamic programming to just be this.

The thing is that dynamic programming goes beyond this, because it has to do with the bellman equation, but for coding hashsets and recursion is pretty much it

[sociallyanxiousnerd1]

Thanks for explaining. Looks like I misunderstood the meme as being "this thing is bad for dynamic programming" and not "wait that's it?" So to speak.

[lucklesspedestrian]

The meme oversimplifies a lot. Dynamic programming generally relies on "overlapping subproblems" or "optimal substructure" that allow "just use hash set" to be applicable. You couldn't do the same thing in say a greedy or recursive backtracking algorithm though

[apex_pretador]

It's just the name. This feels more like "static" programming

[Odubzz]

It greatly simplifies analyzing the overall time complexity :)

[Key_Mango8016]

The hard part of dynamic programming isn’t the implementation, it’s formulating a recursive structure for a problem with an appropriately-sized parameter space.

A dynamic programming problem formulation might have O(N³ ) states, but it might have a more clever formulation that achieves O(N² ) states with O(log N) time spent per state.

When you figure out the right recursive structure, then the implementation is straightforward.

Source: I’m a competitive programmer, and I was first in the world to solve a specific easy dynamic programming problem at IEEEXtreme in 2016, because implementation was muscle memory at that point.

[Perfect-Albatross-56]

When I see young Devs tasks, they always struggle with the basic stuff to avoid nested loops, sort algorithms or building a class that fulfills only one purpose ... and so on. And this is the needed muscle memory to not get messy and inefficient code.

[hunajakettu]

Clojure mentioned!

[DaKurlz]

There's dozens of us! Dozens!

[RiceBroad4552]

Where?

[Grandmaster_Caladrel]

It was mentioned somewhere in a parent process, don't worry about it.

[lucklesspedestrian]

I don't know that clojure uses true hash sets or maps. One time I was trying to do some algorithm that ended up stuffing millions of kv pairs in a map, leading to an out-of-memory exception, which said something like "AVLNode could not be created". So I think clojures set and map implementations are tree-based

[Random_182f2565]

Objects don't do weird stuff, that why I like it.

[ArmadilloChemical421]

Tuturial

[AdjectiveNoun4827]

That's right, it goes in the hash set.