Comments by "Anony Mousse" (@anon_y_mousse) on "Computerphile" channel.

@shiinondogewalker2809 The best way is generally to just pick a random element. It can help mitigate a quadratic complexity attack from a carefully crafted array.
6
I guess I didn't notice you writing it that way in the first video, but I've known about this weird way of getting half the distance between two indices for a long time and specifically avoided it because of this known issue. I generally use C and adding a single extra instruction that takes one clock is not a big deal for a compiled language. Even at a billion entries it's more than fast enough to not warrant worrying about it. This is one of those edge cases that can ruin your year and is probably one of the reasons that Knuth came up with that stupid phrase. I guess I should've paid more attention in that first video and chided you for it, but I was fighting my Python installation that didn't want to use numpy. Bad Mike!
5
@simpletongeek Maybe, just account for the possible off by one error depending on whether you're at an even or odd distance.
4
One extra clock per iteration is not too heavy a price to pay, especially considering that it'll only be executed log(N) times.
4
It's a shame there's not a sci-fi show in the US that the overwhelming majority have glommed onto the way those in the UK have for Doctor Who. It's more fringe than mainstream for people here to like sci-fi, and that's sad.
4
RPN is such a cop out. When I was in high school I wrote a BASIC interpreter that had a similar interface to the C64 and I wrote it in C. You have to learn operator precedence to do math, so if you want to do any real programming, just learn it. Given how few operators there are, I don't want to hear any complaints about it being difficult. We should be stamping out laziness in programming, not making it worse.
3
@jmodified I think everyone acknowledges that it's faster. The issue is that it'll yield incorrect results at large values of l and r. It's not exactly onerous to use the correct form of l += ( r - l ) / 2; It's a single extra clock cycle for compiled languages.
2
@shiinondogewalker2809 As long as it's not a predictable element.
2
@shiinondogewalker2809 Yes, but it will also require calling an RNG three times. The fewer calls the better, and an RNG can be quite expensive. Granted, you probably won't notice a performance hit unless you're doing something very wrong in your code, but more complexity does also increase debugging time.
2
@ In practice, unless you know the data type you're dealing with, the pivot would have to be in the array. Consider an array of strings, you can't know what string would fall in the middle without scanning the entire array, especially when you consider that the comparator might be operating on the length first.
2
I agree with the whole list, especially Converge. I would also add every language not mentioned that isn't C. I still hate C, but it's the least awful language of them all.
1
@minilathemayhem No, it's just going to yield an incorrect answer because of integer division, and every compiler I've tested optimizes division by two as a bitshift right by one, even at -O0.
1
@AndreiGeorgescu-j9p Talk about arguing in bad faith.
1
If I told you I wasn't human, would you believe me?
1
@lepidoptera9337 So, your response is that you don't believe me, is this a correct interpretation, butterfly?
1
@lepidoptera9337 Beliefs are useful, it just depends on who holds them and what is done with them. However, about the rest you are correct, Butterfly, as I am smarter than a Chinese Room.
1
@lepidoptera9337 If I told you I wasn't human, would you think I was an artificial intelligence?
1
@OMGclueless This is why I wouldn't trust anyone from Computerphile except for maybe Mike Pound. Too often they get basic facts wrong and advocate for inferior methods.
1
When implementing a hash table, you should use a table size that's a power of two so that you can do a `bitwise and` on the hash code to index the table with, but also you should store the unnormalized hash with the corresponding keys. Everyone always recommends using a prime number for the table size, but that's the wrong approach. You can always make the hashing function more complicated, but the indexing should be as simple as possible. In case you're wondering why you should save the unnormalized hash code, that's so that you can resize the table as necessary when too many or too few collisions occur and rebuild the table without further querying the hashing function. There's a lot of balancing to be done in implementing a hash table, regardless of whether it's a set or map, but these two things should always be a part of the implementation.
1
@quintrankid8045 If you're qualifying the opposite side of that as laziness then perhaps we need to define the terms better for a proper conversation. Tedious tasks should naturally be pared from programming. Tasks that maintain clarity should not. To be more explicit, I frequently define arrays in C using Type a[] = { ... }; and to determine the length of the array, I have a macro that simply does: sizeof( a ) / sizeof( *a );
1
@talideon If a high school student can do it in C without a teacher's help, then surely a university professor can do it using Python, and surely in 20 minutes.
1
@olbluelips No, it's not. It enhances clarity and speeds up interpretation of the language as written. And as I've already said, if a high school student can do it on their own, surely a university professor could as well. Of course, this was pre-internet times, so maybe the internet has just rotted most people's brains.
1
@olbluelips I know none of you have ever bothered to even attempting writing a parser, but it doesn't take 100 to 200 lines of code to deal with operator precedence. Look into recursive descent, maybe find a copy of Jack Crenshaw's tutorial, either way, go learn from a better source than Computerphile. And seriously, if any of this is too much for you, then you're not watching this video to learn, you're doing it for entertainment.
1
@olbluelips That's okay, you'll get better and maybe next time you'll do better than the high school student did.
1
This isn't kernel-less as it's still very much using the kernel.
1
@SimonVaIe The issue isn't whether to do a signed or unsigned shift right, but in the adding of two numbers when the allocation is near the boundary of available memory. When the addition of l and r causes an overflow, ( l + r ) / 2 will yield an incorrect value. One suggested solution is to use a larger integer type, such as 64-bit integers, but it's still recommended that you write your code in a type agnostic and portable way. Since the calculation in question will only run log(N) times, just quit trying to optimize yourself into a failure state and do it correctly from the start. And in case you weren't aware, every single compiler I've tested this on, will optimize n / 2 into n >> 1, or in Java parlance, n >>> 1, even at an optimization level of -O0. Check with Compiler Explorer if you don't believe it.
1
@SimonVaIe I don't think you're understanding what the actual problem is.
1
@mrosskne A better question would be, how do you know that you are sentient? And if we use the word people keep trying to correct others with, how do you know that you're sapient?
1
@jcd-k2s A more accurate statement would've been: I think, therefore I think I am. But I doubt Descartes was doing shrooms so he never would've said that.
1
@CarbonRollerCaco Just because the law isn't only broken for evil purposes doesn't mean it's not the prevailing reason. The overwhelming majority, 99.999999999%, commit crimes for evil purposes. Whether that be to take what others have due to jealousy or to take others life out of anger, and sometimes both, and sometimes for both reasons, and a myriad list of other evil reasons. Don't rush to absolve criminals as though the law is only ever broken due to necessarily righteous reasons.
1
@arik_dev I would argue that even if it had experiences like a human that might not be enough to qualify it as intelligent. And the cat reflection test, which at least one human we know of has clearly failed, would be an example of perhaps not every human being being sentient or sapient or whatever word you want to use.
1
Keys are unique in a hash table, and generally immutable. If you're confusing a multiway hash table, you still only use one instance of a key. In such a case, a key/value pair would be best with the value side of that equation being a balanced tree structure instead of the usual array.
1
@DanieleCapellini If you have a lot of collisions, then it being sorted or not will be the least of your problems. However, in a tiny array, say with 16 or fewer elements, then sorting can be done fastest with an insertion sort algorithm and it'll be faster to lookup and eat less memory as an array. Of course, if you don't resize your table adequately and collision chains back up to an insane degree, then you'd be better off with a tree data structure all around.
1
Being half asleep when watching this, for a moment when he was going over all the steps I thought I was nodding off, but nope, it was just the camera. Perhaps get the camera some coffee in the future.
1
Anyone know what the deal is with these WhatsApp user ID's? Is it some kind of scam?
1
Yeah, clearly the answer is none of them because they all use tabs.
1