Have We Forgotten How To Program?? | Prime Reacts
Вставка
- Опубліковано 28 кві 2023
- Recorded live on twitch, GET IN
/ theprimeagen
original: www.davidhaney.io/npm-left-pa...
MY MAIN YT CHANNEL: Has well edited engineering videos
/ theprimeagen
Discord
/ discord - Наука та технологія
Its obvious that the is-positive-integer would need three dependencies
1. is-number
2. is-positive
3. is-integer
😂
function is-positive-integer(x) {
return !is-negative(x) && !is-zero(x) && is-whole-number(x);
}
I looked into the repo, is-integer and is-positive were actually 2 of the 3 dependecies
you forgot is-is
I bet all of them is written by one guy.... who is just following GNU... do one thing but do it well.. 😂
Now I see why many people are worried about AI taking their jobs.
geePity is BS
Puts it into perspekyive, right? Some are worried for a reason :D
I laughed way too hard at this. 😆
Ayyy lmao
true, sometimes i see code that had to be written drunk or hungover
I've been a C systems programmer my whole career, and if anything, we have the opposite problem where everything is DIY since we don't have a comparable ecosystem with a centralized package manager (not to mention most of the stuff I worked on wasn't FOSS, and incorporating FOSS had its own licensing and logistical concerns, so it was often easier to just roll our own libraries).
At my last company, the architects were super gung-ho about splitting up our old monolithic architecture into a bunch of containers, and they kind of threw the baby out with the bathwater. A bunch of us had a running joke that we were in the process of putting every single line of code into its own container. We were separating things into containers that felt so much more natural left together because they were inter-dependent, and it seemed like we were just doing it to make some business manager somewhere happy.
Even in that environment, we always maintained our own internal repos with approved copies of dependencies, precisely because we wanted to have access to the code in case the original authors abandoned or closed the projects. We would never just depend on an externally hosted FOSS dependency. It blew my mind when I learned that not only is this the standard way of doing things in a lot of modern language ecosystems, but that massive corporations were having hugely popular projects break because tiny little dependencies were disappearing after the maintainers quit the project.
It sounds like those architects were big fans of Erlang without any sensible reasoning, and apparently without recognising WHY Erlang is the way it is and WHY C isn't.
😂 don't worry, rust is coming to slove that problem and create a dependency hell in low level programming
I can feel the stack push/pops making that code slower.
I remember the turbo button, and blazing fast response times running 33MHz.
So what do u guys develop ?
How big is the code you guys are developing ? And how many users it’s serving ?
I come from that same background. And even if I program in something more modern, I am still very wary of just using some external library. I always end up checking their commit history, past issues etc to see how active it still is. And I will always take a copy and make sure I use a version that I built myself. I would never just blindly rely on some online third party hosted repository. People these days seem to think that things will just magically stick around forever...
9:00 Prime spending that long to bench it just for him to lose was hillarious 😂
Knew he would lose after using so many function calls. Actually, he is the noob.
Hahahahahahhaabha... The shame was real!
To be fair he wasn't that much worse. Both solutions were still O(n)
I find it more funny, both seem not to handle the case when the input string is larger than the padding.
@@jjs9473the hidden lambda gave it away. function indirection in a low overhead call is an instant performance killer. it's okay for generic code but performant it is not.
he is dumb for even thinking it's faster
Prime being shocked that his [uses syntactical sugar] version was dominated by a [uses only lowest-level features of JS] version... That was very fun to watch.
Proclaims he isn't a web developer, but any backend guy would know using low level features is almost always faster.
So what exactly is this guy coding? 😂
Where is syntax sugar in his solution? He clearly has CS background and his solution asymptotically scales better (O(n) vs O(n²)). But that's beside the point, it's probably comment bait and he tested it beforehand. At least that's what I would do. Building pad with cycle and concatenating it at the return would outperform library version anyway.
@@dmitryplatonov I don't see how either of the functions are n^2.
@@quack3891 Computers generally can't prepend to strings/arrays very easily. Most growable array data structures are only designed for appending to the end. In that case, each time you prepend an element, it has to shift all the data back to make room in the front of the array.
If you start with an empty buffer and prepend n elements it has to make approximately n copies of n /2 elements on average, which is O(n^2) complexity.
@@pseudo_goose oh duh, I didn't even recognize that left-pad is prepending a character each time in a loop, guess it individual character additions are much faster though.
As a C programmer, I knew immediately that his version was going to have worse performance. It's just common sense that when you're calling 3+ subfunctions, you're going to have to create 3+ stack frames. The functions that you're calling also aren't likely to be close together in memory, so you're more likely to take cache misses. Your lambdas also make use of heap allocated closures, and so every time you use one, you're potentially going to activate the garbage collector.
Hey, mr C programmer. Do you think this same kind of reasoning could be learned by learning something like Rust? Because I was trying to learn a low level language (medical doctor, not programmer here) but seems like rust would be faster to learn. Yet prime knows rust and didn’t see what you saw.
That depends on the language, in c# strings are immutable, so each append of the character will cause a creation of a new string, and that's what he thought was happening (you can hear him say why it's this not using stringbuilder)
@@ertwro There's nothing about Rust in particular that would help. Knowledge like this typically comes from having dipped your fingers into things like inline assembly or implementing your own allocators.
Rust was designed to "fix" C++, but a *lot* of the problems that exist in C++ quite frankly don't exist in C to begin with. For example, when you introduce exceptions into the language, you need to have some way of "rewinding" the state of the program so that you can recover into a proper state. C++ does this via destructors and RAII (Resource Acquisition Is Initialization). The second an object falls out of lexical scope, it gets destroyed. This in turn introduces a much bigger problem, which is that in Object Oriented Programming, it's VERY common for objects to have pointers/references to other objects in memory. So if that object gets destroyed, you have dangling pointers, which become segmentation faults upon use. The naive solution is to make use of reference counters (i.e. shared pointers) and only destroy an object upon the counter reaching 0. But this introduces another problem known as "cycles", where if A refers B and B refers to A, neither will ever be collected. So then C++ introduces weak pointers, which you have to successfully convert into a shared pointer before you can use and don't otherwise affect the reference count. Even then, reference counting doesn't really solve all of your problems. So a second solution is added: copy/move semantics. In copy semantics, every attempt at referencing something creates a new copy of it, which prevents the destructors from destroying the version you're using. On the other hand, move semantics uses a unique pointer to transition the "ownership" of the object, and thereby avoid the destructor from being called in the first place. Problem is, all of this complexity has to be implemented *manually* by the user, and without all this boilerplate, even the most simple and benign code is a footgun waiting to go off. Rust's ownership, borrowing, and lifetimes model is a means of implementing copy/move semantics and guaranteeing that it's correct. The thing is, there's a whole lot of code out there that's actually perfectly correct and safe; it just can't be easily proven to be so. And this is the kind of code that Rust won't let you write without marking it as "unsafe".
Tldr; C++ is crap. If you like OOP, choose a language that has garbage collection like C#. If you don't, use a language like Rust or C.
RAII, reference counting, and garbage collection are all forms of automatic memory/resource management. RAII destroys upon a symbol dropping out of lexical scope and reference counting does it upon the counter reaching 0; but GC works a bit differently. It typically assumes everything is "dead" unless it can be reached from the global object, which is what it's checking during the collection phase. Historically, this often lead to an obnoxious "stop the world" effect while the GC was doing it's business, but modern GCs are usually incremental, which avoids this. The condition that triggers a GC is typically some arbitrary heuristic, but *that check only occurs when you try to allocate more memory.* You do a gcalloc and the function is like, "hey, this is like, the 1000th time he's called this function. there's a pretty good possibility that there's a lot of data that's no longer being used. better start tracing things to see what we can recover."
If you know this, you can see probably see what I'm seeing.
I'm impressed he didn't mention that leftPad is part of the javascript standard library (as String::prototype::padStart)
You beat me to it. padStart and padEnd. I think most people should really learn the language.
But they don't write in JavaScript, they write in React, smh
He does not know? Maybe?
These are the things that shows up with experience. The guys who learn JS from twitter threads won't get it
another thing I want to add is higher-order-functions and methods in JS like map, reduce, fill, pad are slower.
We haven't forgotten how to program. The problem is much more serious. We have lost our way. We spend so much time dealing with bureaucracy (meetings, agile/scrum, marketing, product owners, project managers), politics (corruption, incompetence), and dozens of technical impediments (UX, source control, quality control, unit tests, code reviews, open source, build/deploy systems, hosting, provisioning, database management, security, constantly chasing/learning the new hotness rather than making existing stuff better) that we have no time to focus on actually doing stuff. We become brainwashed by our rituals. Management becomes addicted to the rituals. It's a huge negative feedback loop of failure. Just look at the state of any software/website produced by multi-billion-dollar companies who can afford the best talent (Apple, Microsoft, Google, Netflix, Facebook, Twitter, banks, insurance, media). It's all a fucking joke now. I'm embarrassed to have been a part of it.
I have to admit this rant actually makes sense. Perhaps this is not even a rant, but a comprehensive critique of our modern society
I'm for it, I agree
Things kinda sucked, not everything was waterfall as you are led to believe, stuff was built but dev experience could be better, then came Agile and everything has been a trail of bloody tears ever since. The end.
So many videos I see about tips for getting hired as a software engineer recommend contributing to open-source. This seems like a logical byproduct of that kind of advice. Write an npm "package" and now you are a "maintainer" of open source code.
life pro tip right there
Trust me if you start writing barebones JS, making libraries almost becomes second nature
The reason that the original left pad performs well is that back in the day enough inexperienced programmers wrote code concatenating strings in a loop that the browsers added special case handling for it in their js engines to recognize the pattern and internally turn it into something like a string builder pattern.
yea gotta remember that because of the magic of compilers, sometimes seemingly crappy (but usually more readable) code is the superior way to do things. People seem to forget these are high level languages very separated from the machine code below the hood that the compiler pumps out
Lol so the browsers basically ignored the coders and did it the 'right' way 😂😂😂
@@williamdrum9899, not quite. The browser developers recognized that certain patterns of code exist for *readability* & maintainability reasons, and provided optimizations for those patterns.
In fact, that’s the same reason *any* API or library exists.
As a self taught developer I showed a client a complete game written entirely in Javascript and PHP with basically 0 dependencies (only stripe which I used as a payment system), yet what was their first question? "Uh, which Javascript framework does it use? NODE.JS? Angular?" I said no framework, I built it from scratch. They turned the interview down because I couldn't show that I used a "proper" framework. SO, appearently coding from scratch instead of depending on a framework that would lock down your code makes you a poor programmer. Thats why I gave up looking for web development jobs, especially anything with js involved.
wtf man
Wow fail
That’s actually insane
It really depends though. Cooking up your own framework can also mean a severe lack of experience and the "I can do this better myself" junior mindset, instead of using industry standards with hundreds of thousands of stars on GitHub and thousands of contributors. I've seen it so many times where those cobbled together systems, written by a single person, shatter into pieces and expose massive security vulnerabilities.
Depending in a 11 line function package is dumb, depending on an active solid framework is not (unless your project is so small it would be overkill)
Your life is infinitely better now
For anyone who is curious, here is the fastest performing leftPad I was able to throw together:
const leftPad = (str, len, ch) => (len > str.length) ? (ch ?? ' ').repeat(len - str.length) + str : str;
It's about an 80x improvement over Primes' version for very short strings with very large 'len' values and about a 2x improvement for actually reasonable inputs.
*Slow Clap*
ChatGPT gives the same answer when asking for a fast version. :D
It‘s not equivalent as it only works on non-empty string ch. Though, allowing anything else was insanity to begin with
@@kim15742 Or non-null str arguments. If str is null, 'str.length' fails. I personally would expect leftPad with len < 0 to pad from the right.
@@kevinm8865 why tf you need to put Null in the str argument? This argument must be a string by definition.
Back in the days of ES3, some of these "simple" methods were not so simple. Even figuring out if something was an array -- there was no real reliable way to do that. You couldn't even trust checking the constructor because that would fail cross-frame.
Using duck-typing was really the best approach at the time if you wanted a solid, very reliable, method.
`Array::isArray` is new to the scene and a total blessing.
Every day I come closer to thinking that JavaScript was a mistake of a language.
@@nobleradical2158 Don't worry, you'll get there
i think, even though coding it directly, has its advantages, people tend to feel that the “published” npm package is more sophisticated/faster/safer/has better code. most don’t check what the code in the package is, but just use the functions it exports.
I swear that each time I have to restore a node_modules directory for a project a little piece of my soul dies.
I can physically feel it leave my body as a million disk sectors suddenly cry out in pain and then silent.
Yeah, you always have to have a spare SSD on your table. Just in case :P
I remember being very surprised when this story first broke. My background at this point had primarily been Unity game engine and some Javascript for web-frontend (HTML5 games and a Scratch-like code editor on web) but I had also written 1 microservice in Node for a larger project with multiple server bits (C#) and client bits (Javascript). My Node server had 2 dependencies - 1 for the database and 1 for the socket connections. I was so shocked when the story broke that people were doing shit like this. Like why would you spend more time looking up (and hopefully vetting) a package for code that could be written in a few minutes.
Lmao. They look this stuff up and add you, you think they vet it? Hahahahahah
@@DMitsukirules they should. How would they know that it even does what it claims to do? Even after you add the dependency and download the file you'd at least run some basic checks to make sure the output is correct. Doesn't have to be a full code review or anything.
@@Xankill3r To be fair, these people are working with hundreds of dependencies, and most of the downloads are dependencies of dependencies of dependencies. Their fatal mistake was made long before writing the code that killed them.
Tmi
It would be an interesting exercise (not really) to see what percentage of a non-trivial, business use case driven js solution could be written by just referencing and calling NPM packages. leftPad is pretty granular as to functionality, and that suggests a whole sliding scale of granularity in those multitude of packages, like everything and everything your little heart desires. I realize that much as been superseded by expanding standard library and language functions, but really, I bet well over 50%, maybe 70%?
hahhaa its cool to see that prime is human and his intial leftPad is slower, also cool to see prime able to be like lol i got reckt xD love you prime
no, he also demonstrated that copilot's code is not good (quicksort example), and his code for leftpad is also not good (it's slower), this proves that prime is an ai and not a human, case closed
@@capsey_ Who are you, who are so wise in the ways of science?
@@rewrose2838 Cultured comment 👏
There are padStart and padEnd functions already present on the String prototype as per the ECMA standard.
But your snippet.. I mean library looks promising, just add Typescript support and you're set for at least a million weekly downloads.
Edit: Yes, I know padStart and padEnd were added after this incident, but even then the left-pad package has ~2 million weekly downloads which just proves the point of the article.
Haha
Not back in 2016, they got added after this incident.
@@EwanMarshall Yes I am aware of that but left-pad still has ~2m weekly downloads which means we have learned nothing and just proves the point of this article
@@wlockuz4467 usually web people really don't care about it, and it's a problem i'm actually glad that chatgptie will replace them
@@wlockuz4467 also fill wasn’t supported the code in the article support old browsers as well
His code at 4:44 has an edge case when len < str.length, so leftPad('foo', 2) would throw an exception.
I had a similar reaction when leftpad first happened ("doesn't anyone know how to code?"). But after seeing lots of people go "it's so easy to write it yourself, look: *buggy code*", I realized that people really underestimate the effort of implementing even seemingly trivial code.
Of course, introducing thousands of dependencies is still bad for all the reasons mentioned. But at the time it was probably better than re-implementing the entire standard library. Luckily JS has a much more mature std lib these days.
I read on the chat about "is-even" npm package. It only has 270k weekly downloads. What a great time to be alive
That one in particular is quite legendary. It even spawned a whole genre of memes where people tried writing the most ridiculous isEven function.
Wait that wasn't a joke
Hey there. I just recently run across your channel but since then I spent a lot of time here. I really enjoy your content. Your videos are informative and also entertaining. You seem to be a very nice guy who knows his stuff but is also open to new things and tries to understand the thought process of others. And I really like that.
I wish you all the best!
Greetings from Germany 👋
9:17 huge props for doing a performance comparison and speaking out loud that yours performed worse in this particular test. It's one of main reason why I watch your videos: even when your takes are hot, you are honest when it comes to changing pov when for example people's "1s" says otherwise etc. 😄👍
But I would prefer to see a discussion why his version is slower.
@@PurpleDaemon_ his version has more allocations, he though that javascrip worked like c# or jave where strings are immutable so every append is a new copy of the string
@purple Because he is performing more operations than necessary. fill and join methods are more expensive because each will go through the entire array, it's better to do it in a single loop and without extra allocation
@@MrOsefosef ok, I'm more into python, and there the join is the most efficient one, as it allocates space only once, since it knows the length of array.
@@PurpleDaemon_ in terms of memory, yes. But in terms of performance the while() loop solution is the best since it only runs a single loop.
In prime's solution he is basically running two loops: fill the array with the character and then join the array into a string, which does exactly what the while loop solution does.
At the end of the day though, it doesn't really matter. I'd stick with prime's solution because it's simpler more cohesive (would probably not do it in a one liner tho)
Lmao I had a similar experience trying to optimize my code once. I was making a a function to make objects of not specified depth return a flat array of the values. My previous solution using reduce was working fine. Then I learned about the native flatMap array function that seemed to be built for what I wanted. Then after benchmarking my new solution was 5x worse.
hah. there are so many funny things.
javascript is really hard to make it "fast"
I miss the original jsperf site was near perfect for evaluating features for different approaches.
wait wait wait. They have a standard library function that is just worse than writing it yourself? What is even the point of having the library at that point? o.O
Simple rule to always consider when using any language with libraries.
The library was written to be good enough for "everyone" for most conditions.
As someone with 40 years of experience on huge data (genomics and other large data) and maths (ML), if I am required to use a language with many libraries (for example, Java) I spent a lot of time re-writing the libraries for bespoke uses. For example, the java table renderer, I got a 100 fold improvement in performance since I want 2D and 3D graphics as dynamic entities in table cells.
Just be aware that a library is good enough for what you want until you do real heavy data/computation.
We do know that clean code has resulted in a lost performance of 12 years of hardware performance - just think about that for a moment.
My preferred language is C of course since I know how machine code and microcode works and data management - but I am that old and even had to wire-wound my first 3D graphics computer.
Just watched a cppcon talk about something similar.
He reviewed the binary sort function and after doing a lot of probability sums found a faster way of doing the binary sort. Up to 50% increase in performance if working with a larger array.
Then a question from the audience was literally asking about specific known hedge cases where it isn't optimized for it. The answer was your comment : You know the criteria, optimize for your situation. The standard library is a starting point to make it work for most cases.
We lose sight of the context and the boys only care about measuring the length of their, um, functions for no practical reason when their functions get called not very often at all.
I guess calling it Babel was a self-fulfilling prophecy.
NPM is a clear example of dependency hell. I heard a saying from one before : "You want a banana, but you will then also get the gorilla holding the banana + the entire jungle!". That as soon you install any package with NPM no matter how small, it wil depend on at least 300 mb of other stuff like 100s of other NPM packages that needs to also download to your computer for that one thing to work cause it depends upon all that other stuff wich in turn depends on other stuff and as soon one single of thesse dependencies break NOTHING will work anymore. The Left pad case is the prime example of this.
"Reinvent the wheel, not the fucking car!"
If I had a dollar for every time i've come across some grandfathered internal "convenience function" had some major security, performance or correctness flaw... well I wouldn't be able to retire but I sure as shit would have had my coffee paid for. Using a package that had more than 2 people look at can be a good thing sometimes. Having said that, there's a line and I think David mostly gets it right with his Trig package example.
Still, I do love how Prime shows here the exact reason why things like leftpad get included, particularly since i've had to work with programmers who are much MUCH worse than Prime. One of my favourite facepalm moments was finding some code where someone had decided to count the number of characters in a string using a for loop with the loop stopping when the count was equal to "strlen(str)"...
🤦♂️
If you change the order of the benchmark the result changes. This probably happens because of the interpreter that caches the action performed by the other function.
Same thing happens in python.
So on these occasions u should run each code/function individually ( or clear the cache if you want ).
how can you clear the cache programmatically ?
good question
@@rampage_sl you could probably do this by isolating the runtime from a code and after the code runs you kill that runtimer (detaching all variables and their locations in memory).
in python the gc library can do the job.
```
import gc
gc.enable()
gc.freeze()
# preparation here
gc.unfreeze()
# you code goes here
...
# delete all variables created with the del
command
gc.collect()
gc.disable()
# done !
```
@@monjecareca7787 thanks!
Wait, Python caches something automatically?
Your code is the exact reason why it needed an npm package in the first place 😂
Your easy hack also breaks down as soon as you provide the method with an integer, or another type. That's what that str = new String(str) line that you sneered at was fixing. As is often the case with people trying to slam dunk on how ugly or unnecessary some libraries code is, it was probably there for a reason.
well, then you shouldn't be passing an integer where a string is expected. this is why we have languages with static types. but unfortunately because of javascript's piss poor type system we have a generation of programmers who don't respect type safety or even care
@@harleyspeedthrust4013 Ok sure, you are right. However the code still breaks, despite you being right. Turns out when you are a developer, you can't just be right. You need your code to work.
Thanks for live coding it mr. Prime,
You might have created a slower function (for small N),
but to be willing to live code it w/o prep in front of a huge,
largelly anonymous audience, is what we need.
By the way, even tought having a library just for leftpad makes me cry in a corner, using an array to do that is not the most optimal way. Well, it's JS so it's not optimal anyway, but having less lines of code doesn't mean better (at least not always).
Apart from that, really nice article!
Something that is missed is that a lot of these packages flow into the language. Array.isArray only exists, because isArray was a package. Just like how querySelector only exists because jQuery existed. It is a problem that these packages are not properly cleaned up as people might find them instead of the now native solution.
I'm guessing when something is deprecated, you just delete it, without entering a middle 'deprecation' stage?
module.exports = leftpad;
const leftpad = (str, len, ch = ' ') => {
str = String(str);
let i = -1;
len = len - str.length;
while (++i < len) {
str = ch + str;
}
return str;
};
The above is how GPT4 refactored the code when I asked it, in case you are interested.
I think it'd be amazing if you had a series where you refactor bad code! Not sure it's something you'd want to do, but I'd definitely watch it. ;)
* edit: WITH perf tests to see which version wins (after seeing those surprising results). ;)
Surprising if u don’t know JS higher Oder function stuff like fill() is slow AF
How to say you want someone else to refactor your code without saying you want someone else to refactor your code:
The new Array version was broken too, cause it would crash any time the input string length was greater than than the pad length
I was waiting for the benchmark test of essentially tightly-packed (but maybe confusing) raw array manipulation VS a couple naive library calls... and it came lmao.
Sometimes things are going to be a little awkward to read to be performant.
Many of these packages seem to be people who just wrote "something" to learn how packaging works. These "test-packages" then end up in production somewhere.
pypi is even worse: we have to double-check each package we install because there a similarly named packages that are forks of the original, but have malware in it.
I watch this channel for entertainment sometimes, and it always blows my mind the kinds of things you see in the web dev world.
I consider adding a single header library a dependency I have to debate if I want. I couldn't imagine having access to a magic "let's use this persons code" button that let me find a function for every little thing. With the amount of problems I run into just using smaller libraries...why would you even want to live that way? Was it not a joke when people said they program by looking up answers to things on Stack Overflow? Has this big meme I thought was going on around me actually just the current state of things?
I show auto gpt to programmers. If they're junior their eyes get really big and they're speechless. If they're a senior they look and it and feel safe. If you're worried AI is going to take your job you might want to learn new skills or learn to utilize AI.
Every time I watch how fast Prime codes I think "I need to learn Vim" 🙃
Yup, watching Prime fly around the keyboard shortcuts to edit his code -- he is BLAZINGLY FAST!
What really helped me was installing a browser extension which forced me to use vim keybinds to do anything in the browser. Vim is one of those things that you have to use constantly in order to really learn it, you can't only use it when a task "needs" it.
Aside from the weaker benchmark tests, the primeagen alternative returns an error when len < str.length, which the other one doesn't (I tested both).
This is true, but I've been programming longer than you've been alive (or at least probably so given the expected relative frequency of programmers ages in web dev), and I have never seen a programmer pull a solution, yes a little tiny one like this and yes to a trivial problem like this, out of their rear-pointing sphincter as fast as The Pimeagen did right here ... narrating the innards of his brainium the whole time while the delicious nasty code unspooled. Damn impressive. If it mattered, I bet he would have found his error, corrected it, and checked it in faster than most take to remember what icon to click to open the code editor. I don't fawn often, but when I do, I fawn all over the truly worthy.
Ands yes his was slower and less easy to understand and debug, but still, damnnnn. And anyone who is padding left thousands of chars in a loop thousands of times, you're fired.
@@i-see-right-through-you Well if you have been programming for 43 years, then yes.
Have you?
On the other hand, IDK what you assumed was my intention was in that comment, but I can tell you that you're assuming a lot of things about me (or even the primagean, for that matter).
Chill the fuck out, asshole.
The live bench was the best part! It would be fun to actually go through and figure out why.
It should be noted that the current String.padStart() function does not behave in the same way as the leftpad() code shown from the library.
To phrase another way, if you just "dropped in" str.padStart(ch, len) as a replacement for leftpad(str, len, ch) you would get different outputs under certain conditions.
The most obvious thing to notice is that String.padStart() assumes that you have a string.
The less obvious thing to notice is the behaviour when ch is falsey in which case "abc".padStart(null, 5) results in "abc" whereas leftpad("abc", 5, null) will result in " abc".
Also "abc".padStart("something", 5) results in "abc" whereas leftpad("abc", "something", 5) results in "somethingabc".
The dependency explosion makes me glad of Python's "batteries included" approach. Lots of things are available already in Python's stdlib.
the javascript ecosystem is absolute trash compared to other languages. Downloading 100 packages to build a project is ridiculous.
But Python has another problem, which is that it a lot of those "batteries-included" modules are mediocre compared to the community packages. Like, if you're learning how to make HTTP requests in Python, most tutorials will send you to the requests package. Yeah, it has urllib3 in the standard library but nobody uses that.
@@pseudo_goose well I'd say it creates a dependency hell and makes the repo messy. There's nothing wrong with community packages but it is certainly a different approach to the more traditional programming languages.
should we make our own package for helper functions like this tho? I always write this small/basic functions myself at a point that it became iterative. Been thinking about making my own package that I manage myself... what yall think?
20:30 there is inplace merge sort. In fact stable sorting algorithms most often use this.
21:24 you care saying that these functions are creating a copy of the array, but it actually creates a shallow copy which references the same memory, so it is still loosely in-memory if you ignore the extra pointers created.Though since it is an array of numbers rather than objects it probably is effectively the same as a copy since pointers are just numbers... Though slice likely doesn't store a pointer for each position in the array but filter probably has to. Then again it has been a while since I used quicksort but I'm pretty sure quicksort creates pointers too. It's only in memory in the sense that it doesn't exceed the the memory needed to do basic swaps.
Yeah okay, those one-liner packages aside... using a good(!) package for something more complex is probably a good idea! It doesn't have to be as complex as an ORM or something. Even if it's just a single function that you could write in 5 minutes.
Sometimes it's a choice of writing a 5-minute crappy version of it vs. using a tested, battle-proven version that deals with numerous edge-cases and has much more than 5 minutes of thought put into it.
Higher management mandate programmers to reuse _everything_ they can and do not try to reinvent the wheel. It is usually a written corporate policy. Otherwise your working hours were not productive enough. Maybe it is a huge surprise for solo- / startup devs but: RAD is GOD at enterprises where business needs usually overwrites even the basic programming studies.
Something really important to note as well. Since Javascript is executed by different engines, it's implementation can completely vary on browsers. You could spend weeks optimizing your code to work well for every popular browser... or you can just include someone else's who already done the leg work.
This is great. Good example for the fact that in science and technology the gut feeling is not always right.
Beautiful article. Thanks for covering it.
Isn't the real lesson here to use whatever code is available to you but to check whether it actually fulfills all your dependencies making sure that you have an understanding what you use.
After reviewing that code, you can still decide to write something better/more suitable.
It is hilarious that you critiqued that awful left-pad code and that the awful code wasn't really the issue of the left-pad "incident" 🤔🙄
TLDR of the left-pad "incident": the dev basically got mad about something -> then he yoinked the package off of NPM (yes you can do that in NPM) -> the whole NPM/JavaScript ecosystem went down
lmao
That's not the topic of concern. The topic is that many developers reach for packages for the most basic of things all the time with zero concern for if that thing is decent.
> "yes you can do that in npm"
not anymore, they fixed it (presumably after this incident)
Great reaction as usual - little nitpick, but in-place quicksort is O(log(n)) memory because of the recursion (or when done non-recursively it needs a stack). I have heard there is a variant of quicksort that is really O(1) memory, but nowhere its found (there is some paper about it) and to my knowledge its slower than quicksort.
For totally O(1) extra memory heapsort can do O(nlogn) time but is also slower than quicksort. I am also working on an O(n*loglogn) runtime algorithm that is totally inplace and have an unimplemented (on paper existing) O(n) runtime O(1) space alg too, which however might be slower in practice than the nloglogn variant (from the latter there is two variants and one is closer to O(n) but has one more run over input data though).
So O(1) space sorting is actually tricky and most in-practice used quicksort algorithms do the O(logn) space either with recursion or a stack. The O(1) space variant of quicksort has to mark ends of the separation points with a marker value in the array and this incurs further runtime cost (not algorithmically I think, but a bigger constant factor). Also the logn is nearly as good space-wise as O(1) in most cases and where its not, they just tend to use something like heapsort...
wait... you have to be assuming some sort of constraint since sorting is proved that it can't be faster than O(n lg n)
@@VivekYadav-ds8oz No this is wrong. What is proven is that you cannot do faster than than that many comparisons. Basically nlogn is constraint for comparison sorts, but not other sorting!
So my algs are just more other non-comparison sort algs, but there are many such things. Most of O(n) or better than nlogn (like this nloglogn) sorts are some bucket sorting variants - you can argue stuff like "hey you don't count length of keys, not factoring that in! but reality is that you do neither when doing comparison (which is also related to key length, just also supported by hardware so you do not think of that usually).
Pretty easy to do these kind of sorts. The magic - and the harder part - is making the constant factor that little that you can be faster on small input too. For example my magyarsort (my current internal state of the art one) starts to beat C++ std::sort around 64 element array and is already pretty much the same runtime on 32 element arrays. Then the bigger input and mine is outragously faster. Like 8x faster or 20x faster on bigger data sets usually. Just to put this in context: sorting 100 million integers only takes 6-7 times the time of memcpy over them, so its pretty well optimized code and also algorithmically fast.
Magyarsort is also faster than ska_sort (around 1.5 times faster on my machine) - which is current state of the art O(n) runtime sort algo.
I do not really expect my new variant being faster than my magyarsort for integer keys, but likely will be faster for floating point and string keys, also longer integers .. maybe regular int too, but that needs measurement as I am only pretty sure it will work for strings and float well... In any ways after finishing implementation I expect to have sort for int, long, float, double and string keys (objects being anything). Also again I trade runtime performance for the O(1) space so I did not start write the O(1) space variant because it literally will involve me coding the inner loop less efficiently (same algorithmic complexity, but slower than the version that does the copy)
Anyways: my main point is that usually the O(1) space even when achievable is not always the best to aim for unless you really need that, because a bit more temporary space (like at least log(n) really usually gives more performance than what you lose by having that need for that small amount of extra memory. All that being said merge sort needs not logn, but O(n) temporary space (it can be n/2 space if you do it well though) and it, and its just bit more complexity makes it slower than quicksort yes. Actually magyarsort does not to do O(n) space copy and still faster than introsort (quicksort-ish alg) in C++ and faster than both the O(n) space needing and the O(1) space needing ska variants. But it can have spikes, when sometimes it slows down to the C++ version in huge data sets - not sure why that happens but because of memory patterns... Still the general rule of thumb is that lowering the space complexity introduce usually some constant factor overhead at least...
@@VivekYadav-ds8oz Only comparison-based sorting algorithms are limited by the average-case Ω(n log n).
heapsort also takes exactly the same time to run n elements every time, how well sorted they are at the begining doesn't really matter it will always complete in the same O(n log n) this is usefull in real time systems where you want the predictability not sometimes we'll sort quicker and sometimes slower.
@@TheJocadasa I am curious, could you name other approaches for sorting? Until now I thought that ordering items requires comparison in the mathematical sense
Just found out your channel through this video being suggested. I was expecting some pedantry, but this was interesting and hilarious.
This is what I feel about many packages in Python to grab data from some API.
It is faster to read the API documentation an write a function with requests than reading the package documentation.
On anything remotely modern you can use string.repeat() and string.slice()
function leftpad(str,len,ch=' ') {
return str.length >= len ? str : (ch.repeat(len-str.length)+str).slice(-len)
}
but I guess if we go back far enough, say IE7 or something, perhaps we don't have these functions available.
Might be a stupid question: What is slice for here? Isn't it always the size of len?
4 years from now devs are going to npm i chat-gpt-companion and then do something like
async function leftPad(str, len, ch) {
const chatGpt = new ChatGPT();
return chatGpt.query(`Can you pad the following string to the left by ${len} spaces with the ${ch} character?: ${str}`);
}
"Have we forgotten how to program?" No, web developers never knew how to program in the first place.
A few years ago, as a junior dev, I was working on a project with several other devs, and one of them (a senior) wanted to download a package just to be able to iterate over a range of numbers. A for loop obviously doesn't cut it, it's so 70s. After I threw a tantrum, and was (fortunately) backed by another senior dev, he backed down and agreed to use the function I wrote instead of pulling a 4kb package. A side note - 4 kb for iterating over a range?!?!? - end side note. Here's my function:
export const range = x => [...Array(x).keys()];
Javascript. I love it.
Here you go:
const leftPad = (str, len, char = ' ') => char.repeat(Math.max(str.length - len, 0)) + str;
Now benchmark it
🤪🤪🤪
String(5).padStart(5)
@@emilianoruizcarletti9381 your version is incorrect though it overpads
@@aftalavera I did not know that existed lol. Well anyways the point is any competent programmer could come up with something like that in a min or 2
I remember hearing about this and reading the article when I first started coding and it really turned me off the NPM ecosystem a lot.
This video inspired me to remove react-currency-formatter from our company's repo, which was installed years before I started working there. The usage of the package would've make sense, if we didn't support *just one* currency!
It took me 15 minutes to write the code including hiding it behind a feature flag (just in case)
Its fun seeing the origin story for your tweets play out days later.
As a Button styling "engineer" I can confirm this is true
The reason js developers are using micro packages and stitching them together is demonstrated by prime's own leftpad function that was dominated by the micro packages. If js developers wrote all their own functions as prime did all these slowdowns stack and compound. So it's best for js developers to use highly used and optimized micro packages to keep performance up. It's not that they can't code these things it's just that others have done them better and they are ready to use, so why not use them.
Because if you build your framework with hundreds of micro package dependencies, there is hundreds of people who can just close their project and kill your framework.
@@lamjeri that's true for any package you rely on. If you depend on solidjs for example, Ryan tomorrow could be hit by bus or decide he wants to pull the plug. Sure it's open source and others are contributing as well, but if Ryan was gone the project would take a serious hit for while and might not recover.
These smaller packages are pretty easy reimplement if they go wrong vs solid. I could spend lots of time implementing all these micro packages myself or just use them and reimplement or fork them if something goes wrong with one.
That's the risk and benefit of open source.
javascript developers, famously known for loving performance
@@fakenameforgoogle9168 haha
How hard is it though for such a small function, to code it and figure out yourself why is it slower and how can you do it faster? There are also cases where someone said to me "don't reinvent the wheel, if you use that function or library an expert made, it will be much faster and safe than you can ever do". And then it was proven that I could do it my own way and tailored to my needs, and could achieve more speed than the official function people said are build by experts and you can't do better.
I think one of the reasons those "micro-function" packages became popular is that, until fairly recently, tree-shaking was just... Not a thing.
In the "trigonometry" example, if you wanted to have a cosine function, you'd have to ship the entire trigonometry library to users.
Although, to be fair, both underscore and lodash (kitchen sink libraries) are split into single-function modules (but are still one package).
I tested some more and it seems that creating a new String or Array in your case is the slow part. They took the argument fromt he function and added the stuff in front of it. The while loop seems also to be a bit faster than a normal for loop.
Watching programmers from the 80s and how they go about coding, and watching modern day programmers, I’d say most people can’t program these days. The key difference is computers are so powerful now, that your code can be sloppy and you can get away with it. Add to that IDE which corrects syntax errors and makes suggestion, people really are taking shortcuts. As it gets better, this is where AI could take over where it is fed code and asked to simplify it. Resulting in smaller programmes and less resources being used when code is executed.
I think the way bigger issues is that programmers have been writing all of these 'fundamentals' and the incredibly complex packages that make some incredible things possible, and yet here we still are re-writing(or copy&pasting) sloppier versions of these fundamentals in these high-level languages....The only people who should still be writing any type of low level code with hardware control, should be the people who are creating new types of hardware. I mean, what in the world is the point of having all these abstracted languages that are meant to replicate normal human constructs, but we still have to start out a new application by writing code for issues that should have been solved decades ago.
At this point I think we should destroy all "developer" terminology and actually separate out the low-level and high-level concerns. Then we won't have anyone who writes any type of applications that don't deal with strictly low-level code, using things like VIM and using the terminal for everything when it's entirely unnecessary with the Desktop GUI having existed for about half a century now.
I suppose that assistance could be misused, but it saves those of us who know what they're doing a lot of time. Everyone makes typing errors. Everyone has to type out certain code. When the editor can highlight the error it saves us time. If it can intelligently complete code it saves us time. I started in a time when we had only primitive tools and it slowed us down significantly. When it comes to speed of delivery versus optimal performance most companies want the software delivered sooner and they'd rather throw more hardware at it than wait for improved performance. That's not my preference. On top of that software does more today and is more complex.
@@loganmedia1142 I agree with most of that, but don’t believe the programmes are generally more complex. The key differences is that when you had limited resources you were forced to hit hardware directly and that could be quite complicated, you’d be surprised what people did to get sound on 8 bit computers down to a size that wouldn’t take up all the memory. Now computers aren’t all standard so hitting the hardware isn’t really possible. And I think IDEs are great tools, but if a company was to embed an AI learning algorithm into an IDE I’d start to wonder how long it would be before the AI advanced enough that it could take simple text to code. Note there are many limitations still, so no programmer has to worry, but for the first time ever I feel computers are powerful enough that they will be able to learn and it won’t be long before we have text to code that is usable and reliable for simple tasks. The next stages would be an intermediate one, where it can review your code, and create a simplified version that does exactly the same thing but uses a fraction of the time and resources. It’s going to be interesting to see how it evolves over the next decade.
Reasons they could program like that in the 80s:
-They had 3 years to develop a product.
-Requirements won't change in those 3 years.
-They could write in one language (C or Assembly) which everyone knows.
-Libraries had full documentation.
-Dependency hell didn't exist yet.
-If they wanted to understand code written 10 years ago, the guy who wrote it is still at the company.
-Codebases were tiny because they didn't have enough memory to make them any bigger.
-Auth0? GUI? The internet? What's that?
-You're paid enough to support a family
The problem is that our world is different now, but still has the programming philosophy of the 80s.
@@LowestofheDead many games were produced in months, the demand was high and some were under incredible pressure more so than today. Don’t know where you got the 3 years from try months. Computers advanced significantly in three years if that was your development cycle you’d have been out of business. GUI existed refer to GEOS as an example. I have seen modern programmers and in my opinion 90% of them are cut and paste monkeys, most of the old school programmer were geniuses in comparison, spending hours to make code as small as possible. And really using unique solutions.
12:31 this problem is going to get WAY worse with AI. I mean seriously, who would invest the time necessary to learn to actually code when you can just copy and paste from chat gippity. In fact, soon chat gippity will write the files too. I don't know but coding is going to become more efficient cut coders are going to lose something.
@john doe i wish more people realized that training AI results in poorer results than the training set. Feed it back and you get even worse shit.
@john doe
That's means more opportunity for us , professionals to fix $hit and make more $$$s.
Be on the positive side.
If that was the case then wouldn't there be developers who just copied and pasted from stack overflow? Such a preposterous situation would never occur!
The amount of specific npm packages that I've downloaded for developing on react that either don't work as expected, are not maintained, or are very hard to extend is astonishing. It's like everything depends on everything and nothing is "clean" and light.
I see me reviewing the code of a package to get the snippets I'm not familiar with (or that I'm lazy to write) more than installing things. Every time I just install a package, for example in work wen we are near the deadline, it's a coinflip if I uninstall it in the next 5 minutes or not.
I just finished a slider for a range selector and just read articles on how to do it natively instead of installing one, and in the same hour I would've wasted installing any number of packages to see what fits, I got my own implementation, and I know how to do it now
Would love to have the link to whatever is discussed in the video description to take a further look!
When I see things like this, the first thing I think is always "why would someone take this decision".
Performance is the first thing that came to my mind. If padleft is used often, you might want to optimize it, not just make it work. Rather than spend time making an optimized padleft, they decided to use one someone already made. They probably benchmarked it quickly just like Prime did here.
I was curious if it was a similar case for is-positive-integer, which seems ridiculous by itself, and took a look. And there is actually a decent amount of effort put into it. Though not enough to make it a package imo. They don't just "return i % 1 === 0 && i > 0" they check it is a number in the first place. They also consider whether or not it is a safe integer. But that's about it.
In the end, it's more likely that the people using these packages would be experienced programmers on big projects rather than noob programmers. There is no interest in thinking about small performance gains for new programmers or smaller projects, anything that works can do. There was just a period in which danger was not taken into account, and only time was, allowing dependency usage to grow beyond what it should have.
Spaces in a function declaration separate different parts of the declaration, . Deleting the space between the name and the param-list makes it look like a function call, which it's not. If spaces are bad, we would have written the declaration like this: functionfun(a,b){...}
The reason why people prefer to use other packages even for simple things, because there is a very high chance, that those packages have the most optimized version with all the edge cases accounted for, like for 'leftpad' the package takes care of the case where padding character is '0', and if some developers implements it manually, they are likely to miss some of these edge cases, so using some trusted package is "more reliable".
Also if that part of code needs to be fixed for some reason, there is a chance the package maintainer might do it first.
10:35 The dependencies were probably “is-integer”, “is-negative”, and “is-number” 😂
functions as a dependency... FaaD
20:07 ChatJippity isn't a threat. It literally doesn't understand what it is outputting (LLMs have no mind/brain and they won't ever get any either because that's not how LLMs work, they're just a "random but human-like" text autocompleter), AND it was trained on horrible code. Our jobs are safe.
För quite some time now, I've been mainly programming in a language called fennel which is a dialect of lisp that is basically equivalent to lua,
The funny thing with lua is that it's extremely small, so I have to write a lot of things myself, I mostly get things from luarocks if I need to, as an example, read/write yaml/json/toml in which case I will want to use a rock that is partly written in C,C++ or even rust or golang, this because I want that code to be extra speedy, and I have no idea how to write yaml myself 😂
I've understood that many people import large libraries to get extra stuff, but I know that my code will work, even on systems with slow or no network as long as It's got lua and fennel, I basically write fennel instead of bash...
14:30 To be fair: This mindset is true if we are talking about a compiled program. If I execute a 5Mb program or a 5.2Mb program doesn't really make that much of a difference. But even for a "Hello World" in C, including blows the app up to several kilobytes.
But with JavaScript we don't compile the code and optimize imports to cut out unused functionality. We just send it as-is to be interpreted. A trigonometry dependency might be a lot of trigonometric functions that are being sent for no reason at all which makes the page take longer to load. Imagine that for several scripts within the website and a simple load might go on for 5x as long as it should with 70% of the loaded stuff being dead code.
The consideration for what you do with the app is just a very different one.
I was thinking the same thing. Google will make your page score go down for every js parsing so sending only needed functions has become a priority. Those issues that are a result of some of the decisions that were taken. For example, npm is the only one package manager I know that allows different packages require the same dependency in different versions and it will work. In most cases is PackageA requires PackageX in version ^3.0 and PackageB in version
You know what would be dope? To explain why the code that you think is bullshit is bullshit and how it could be improved. I know it is a stream and you are a snarky fellow, but it is not helpful when a knowledgeable person is not sharing their knowledge. I understood it has something to do with memory management, but what exactly I am not sure.
yeah I feel like String from the leftpad package is doing some memory magic that Array isn't doing. Plus .fill() and .join() is also filling the function call stack.
@@luminousmonkey4512 No, that is another point (which I am fully aware of, thank you very much). I am talking about the "I hate this code" line repeated a few times during the reading of the function. You are conflating the general reason why this package is a bad idea with the quality of the code itself and I am asking about the latter.
performance aside, here was my reaction (not I am no JS geek)
> str = String(str)
this is just unnecessary. Yes JavaScript has no type safety-but that doesn’t mean you should make type checks at runtime everytime especially for a function that clearly is suppose to take a string especially when the user has to specifically search for this package online… surely no one intends to pass on a non string and expects the function to automatically turn it into a string.
> var i = -1
> while (++i < len)
var-you should like never use this. It’s obsolete. It scopes variable to the entire function, doesn’t matter if you declare it in a loop or so. Terrible, shouldn’t be used.
Why do it on this line? The loop is a few lines below…
Why would you assign -1 to i and do the while condition like that??? If you want to loop len amount of time there are more idiomatic ways to do this…
Simple one being `for (let i = 0; i str = ch + str
+ operator usually creates a whole new string, cloning the data from ‘ch’ and ‘str’ especially when prepending. So it copies the str at least len times.
When mutating with strings a lot, you should also use the stringbuilder that makes it easier to avoid copying data and,well, is made for things like these.
Mutating like this is just not idiomatic, probably not efficient, and just not recommended
I'm not in his head, but one thing that's really weird is
// this
var i = -1;
...
while (++i < len) {... /* no use of i btw */}
// could be this
...
var i = -1;
while (++i < len) {...}
//or this
...
for (let i = -1; ++i < len;) {...}
//or this
...
for (let i = 0; i < len; i++) {...}
another thing is mutating the string iteratively
ideally this whole thing could be the equivalent of one realloc, memmove and memset to use c terms but here I believe it's reallocating and shifting the array every iteration
The package allocates an extra string that isn't needed. A string is allocated with only empty space and combined with the original string, the combining creates a third string which is the result that is returned. Instead, one can directly create a string of the desired length and fill it with the spaces first, followed by the original string. The string with only empty spaces neither needs to be allocated nor garbage collected.
str = String(str); 😂😂😂😂😂
Type Safety bro
@@akshay-kumar-007 I know. But I’d prefer renaming that ‘str’. Why would it be named str if it’s not already a string.
When the caller passes a Number.
What weak dynamic typing does to a mf:
Interesting. Did some google search and it turned out in JS, string concatenation is highly optimized (either str = str.concat('a') or str = str + 'a') and is faster than doing array join.
I guess this is why so many leetcode questions are about optimising arrays, which are pretty fast in C++ now.
2:00 yup! strings are constants, they are not meant to be done like that. instead, a much better thing (and with less code) would be to just add the stuff to join to an array then return the joined array. i can just imagine how many memory reallocations that script is making the kernel do.
First one here... yay. By the way Prime, I'm learning Rust 🦀
a fine padawan you will make
gross
🦀 is ❤
Quite often code which is quicker to write isn't quicker to run. But its often a worth-it trade-off.
The thing is if you are reading the code used from NPM then you can kind of see the point of some of these packages as being similar to a public code snippet library. What do you think?
I really relate to this.
Even vetted programmers, anyway, make mistakes ; in fact, I found an error within the source code of google APIs on flutter thanks to looking at it with the dev responsible for the commons functionality. Long story short, on a specific call , the headers were not vetted properly on partial downloads, and the code ran an error on browser-based flutter but worked on any other compilation that wasn't web (because of specific browser headers). The request would work, but the package itself thought it had failed and threw an error.
Considering the logic that existed in my app, this bug would have never in a million years happened if I directly made the http requests, simply because I knew I was going to have a browser environment.
I read that article way before that mishap happened, but I think it illustrates quite well this issue.
Meanwhile in my C++ job, I reimplemented the variant and option data structures with all the template progamming because we are running c++14.
20:45 writing mergesort with O(n) memory is rather trivial and usually happens by default - every subsequent level is half of the previous one.
Padding is already built into javascript...
'hello world'.padStart(15,'-') // ----hello world
'hello world'.padEnd(15,'-') // hello world----
Ackchyually, JavaScript string concatenation is reasonably efficient since it relies on the rope data structure. It offers performance roughly on par with array.join.
I tried to use pnpm once. It failed to resolve my dependencies. It wasn't a complicated project. I have no time to debug the package manager so I stayed at npm.
that last block in the article had me nearly rolling off my chair laughing, Absolutely Savage, no quarters given, shoot to maim
Looks like complexity that comes from having to write code that needs to run on a bunch of JS environment. I don't do web so I admit that I am spoiled by having an extremely well-controlled runtime environment for the programs I write.
That's one of the problems I see whenever I implement something myself and someone else says "don't reinvent the wheel. just get a package someone already created".
Prime didn’t notice that his leftpad doesn’t work if len < str.length
Most people fail to realise some things here, every npm package published was probably benchmarked properly and the author would ensure every character in that code makes it completely compatible with all future imports (or else it will be deprecated atleast) as well as be the fastest code around to do so. When you're writing a framework like React, you need to ensure you're squeezing every millisecond of optimization possible, so you're bound to search for every single functionality on a universal manager for optimized packages.
You have “developer experience” to thank for this madness.
prompt: "what is the issue with this algorithm
response:
The provided quicksort function is a basic implementation of the Quicksort algorithm, and it should work correctly for sorting arrays of numbers. However, there are some potential issues and optimizations to consider:
In-place sorting: The given implementation creates new arrays at each recursive step, which can be inefficient in terms of memory usage. An in-place version of the Quicksort algorithm could be implemented to improve memory efficiency.
Choosing the pivot: In this implementation, the first element of the array is always chosen as the pivot. This may lead to poor performance in certain cases (e.g., when the input array is already sorted). A better approach would be to choose the pivot using a more advanced strategy, such as picking the median of the first, middle, and last elements of the array.
Handling duplicates: The provided implementation doesn't handle duplicate elements optimally. Duplicates will always end up in the right array, which could lead to an imbalance between the left and right arrays and, consequently, a suboptimal partitioning. To handle duplicates more efficiently, you could create a separate array for elements equal to the pivot and concatenate this array between the left and right arrays in the final result.
Tail call optimization: In some cases, the Quicksort algorithm can be optimized to use tail recursion, which can help prevent stack overflow errors for large input arrays. This optimization is not implemented in the provided function.
prompt: make a better sorting algorithm
Response:
function quicksort(arr: number[], left: number = 0, right: number = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quicksort(arr, left, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr: number[], left: number, right: number): number {
const pivotIndex = Math.floor((left + right) / 2);
const pivotValue = arr[pivotIndex];
// Swap pivot value with the last element
[arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];
let storeIndex = left;
for (let i = left; i < right; i++) {
if (arr[i] < pivotValue) {
[arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
storeIndex++;
}
}
// Move the pivot value back to its final position
[arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];
return storeIndex;
}
EDIT:
I asked for some benchmark:
// Original Quicksort implementation
function quicksortOriginal(arr: number[]): number[] {
if(arr.length === 0) {
return [];
}
const pivot = arr[0];
const left = arr.slice(1).filter(x => x < pivot);
const right = arr.slice(1).filter(x => x >= pivot);
return quicksortOriginal(left).concat([pivot]).concat(quicksortOriginal(right));
}
function quicksortOptimized(arr: number[], left: number = 0, right: number = arr.length - 1) {
if (left < right) {
const pivotIndex = partition(arr, left, right);
quicksortOptimized(arr, left, pivotIndex - 1);
quicksortOptimized(arr, pivotIndex + 1, right);
}
return arr;
}
function partition(arr: number[], left: number, right: number): number {
const pivotIndex = Math.floor((left + right) / 2);
const pivotValue = arr[pivotIndex];
// Swap pivot value with the last element
[arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];
let storeIndex = left;
for (let i = left; i < right; i++) {
if (arr[i] < pivotValue) {
[arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
storeIndex++;
}
}
// Move the pivot value back to its final position
[arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];
return storeIndex;
}
function generateRandomArray(size: number): number[] {
const arr = new Array(size);
for (let i = 0; i < size; i++) {
arr[i] = Math.floor(Math.random() * 1000);
}
return arr;
}
function measureExecutionTime(fn: (arr: number[]) => number[], arr: number[]): number {
const startTime = performance.now();
fn(arr);
const endTime = performance.now();
return endTime - startTime;
}
const testCases = [1000, 5000, 10000, 20000, 50000];
testCases.forEach(testCase => {
const arr1 = generateRandomArray(testCase);
const arr2 = [...arr1];
const timeOriginal = measureExecutionTime(quicksortOriginal, arr1);
const timeOptimized = measureExecutionTime(quicksortOptimized, arr2);
console.log(`Array size: ${testCase}`);
console.log(`Original Quicksort: ${timeOriginal} ms`);
console.log(`Optimized Quicksort: ${timeOptimized} ms`);
});
These are the results:
Array size: 1000
inline.component.ts:88 Original Quicksort: 5 ms
inline.component.ts:89 Optimized Quicksort: 6 ms
inline.component.ts:87 Array size: 5000
inline.component.ts:88 Original Quicksort: 9 ms
inline.component.ts:89 Optimized Quicksort: 2 ms
inline.component.ts:87 Array size: 10000
inline.component.ts:88 Original Quicksort: 11 ms
inline.component.ts:89 Optimized Quicksort: 1 ms
inline.component.ts:87 Array size: 20000
inline.component.ts:88 Original Quicksort: 20 ms
inline.component.ts:89 Optimized Quicksort: 2 ms
inline.component.ts:87 Array size: 50000
inline.component.ts:88 Original Quicksort: 52 ms
inline.component.ts:89 Optimized Quicksort: 9 ms