Hacker News new | past | comments | ask | show | jobs | submit | varjag's comments login

Lowkey mad at the lady dragging her hand luggage.

“We don't rise to the level of our expectations, we fall to the level of our training” – Archilochus

People like to imagine how they would act in an extreme situation that is unique and beyond anything they have ever experienced before. But the reality is people do very poorly most of the time without regular training. In a crash, the adrenaline is flooding your body, and most people are not “thinking” much at all. You know you need to get out but your brain is barely processing, so what do you do when you exit a plane? You grab your luggage and head for the door.

Flight attendants giving simple, clear, easy to follow instructions is partly because people are not thinking and processing properly and need help doing things that would be easy in a non-emergency situation.


Airline pilots I've worked with have said that this is also why when evacuating the jet in an emergency, they put on their uniform hat. So they're immediately mentally flagged as "authority figure."

Also, there was an emergency a few years ago where a jet lost cabin pressure, and people were getting dragged on social media afterwards for not putting the oxygen masks over their noses.


While it’s clearly wrong to drag your bags out, I try to give people doing this some leeway.

They are in shock and acting on instinct. I’d like to believe I’d do better but who knows.


Just for a different point of view, my wife is Type 1 Diabetic - no way she’d be leaving her medical stuff.

It’s probably not that, but is possible.


No medical condition has higher priority than getting out of a burning plane as fast as possible.

You may not survive a day without insulin, but the people behind you might not survive the next few seconds if they can't get out in time because you were fumbling with a bag


I hate your opinion not because leaving one's bag isn't a fair take most of the time but it is underpinned by a the fundamental contempt for the decision making of people who are actually there. It's like when a child gets a math problem right but the shown work makes it clear they're very wrong.

You don't know what's in that luggage. Maybe it's hard to source medication. Maybe it's very important legal documents. It's clearly not big enough to be typical low value personal belongings. The plane isn't even full of smoke yet.


I get that folks are going to make suboptimal choices in the heat of the moment, and I could see myself similarly making a dumb choice in the rush of an airplane evacuation. I don't think we should judge anyone's character too harshly, but that doesn't keep us from discussing what the actual optimal choices are.

>The plane isn't even full of smoke yet

The plane previously had some pretty impressive flames in the process of landing, and depending one what sort of fire gets going there might not be time for everyone to get out. That being said, insulin isn't actually a valid excuse nor are very important legal documents. Every second counts, and could be the difference between life and death for passengers and crew not yet evacuated. There's a reason that air traffic controllers ask pilots in emergencies for the number of "souls on board" referring to living humans and not important legal documents or medicine.


Optimal for who and in what situation? What is the optimal default practice for a single variable (lives saved) in the general case is not necessarily optimal in all cases.

In the case of this aircraft not only were the maximum number of lives saved but the some people also got their luggage reducing the sum total of BS and PITA the passengers involved had to endure. This is a superior overall solution than following the "rules" because that solution would have saved the same number of lives and increased the overall PITA because a greater number of passengers would have been without their luggage.

Basically the people involved rightly judged they could allocate some resources away from GTFOing and allocate them toward PITA reducing and we're all screeching about it like idiots because had the situation been different they would not have been able to make such a tradeoff and get the same results.

This entire topic of comments is in the same category as complaining about people ignoring the speed limit on empty highways or hopping some queue control ropes to skip a bunch of zig zagging when the queue is short enough they're not cutting anyone by doing so.


If adamanonymous' opinion was worth the pixels it was printed on, he wouldn't need to post it anonymously. Ditto for me.

I don’t know much about T1 diabet so please excuse me if I’m asking the obvious: don’t you expect to find everything necessary in an international airport like Toronto? I mean in pharmacies but also with the airport medic team? My first though in a similar crash would be to get out ASAP to avoid me or someone else roasting, although it may be so stressful that rational thinking may not be at its best.

My wife is also T1 diabetic. In principle, yes, a major airport's medical team should have everything that a diabetic needs to survive. However, depending on the person's blood sugar level at any given moment, it may be necessary to give them either insulin or sugar immediately or they will become disoriented, unable to move reliably, and maybe pass out. Hypoglycemia and hyperglycemia can quickly become medical emergencies. Given all that, it makes sense for a diabetic to be highly protective of their insulin and sugar supplements. In a crash, the medical team is probably going to be pretty busy and might not provide optimal treatment to a diabetic right away.

A "pancreas kit" can fit in a bag small enough to be carried in one hand, so it shouldn't be necessary to hold up an evacuation by carrying something large. As others have mentioned, this is also likely an instinctive reaction, and it's hard to criticize someone for reacting that way in such a stressful situation.


If the bag is this essential, then it should be carried at all times and not in an overhead locker or similar.

Maybe you’ll find everything you need readily available at the airport, or maybe everyone will be busy dealing with the current situation and won’t be able to help you on time. Maybe they’ll need to send someone back for your bag and that’s going to take hours or days before they give it back to you. Maybe you having to wait makes you miss on other care.

People die in hospital waiting rooms. Why risk it when you know you have everything you need right on hand? At this time in the video the situation looked to already be fairly under control. Worrying about recording a video on your phone to post to social media before you’re even out seems worse.


> People die in hospital waiting rooms. Why risk it when you know you have everything you need right on hand?

Because people also die in incomplete airplane evacuations. In the Aeroflot Flight 1492 crash, 41 of 78 occupants died while folks were seen evacuating with their bags. Some of them would have died no matter what, but somebody slowing down an evacuation from a serious airplane crash for even just seconds to quickly grab their insulin kit out from under the seat in front of them (let alone to film for social media or whatever else) could cost someone else their life.

The situation might look "fairly under control", but the plane is upside down, leaking flammable jetfuel, and surrounded by firefighting foam that no one wants to spend more time around than they have to. Leaving behind medical supplies in a crash has a real impact on a diabetic or similar, but any slowdown to the evacuation also has a real impact on all of the other passengers.


> Just for a different point of view, my wife is Type 1 Diabetic - no way she’d be leaving her medical stuff.

Perhaps a fanny pack would be a better idea:

* https://en.wikipedia.org/wiki/Fanny_pack


A fanny pack is actually where my reserve insulin is at all times. And the pack is attached to me most of the time. There's also some sugar in there too.

People with T1 either have insulin pumps attached, or long-lasting insulin injected. They are not going to keel over from lack of insulin on most days, even if their pack is gone. Except if the pump stopped working hours ago, or they forgot to inject. Then they may be close to collapse already. And being away from sugar can become life-threatening quickly for people who shoot insulin. So overall they have a pretty good reason to always carry their stuff, even in an emergency. And yes, better always attached than in some bag than can get lost easily.


I flew out of Toronto Pearson the day before this crash (after moving my flight a day forward because of the storms :-/ ), and noticed that flight attendants require passengers to remove any cross body fanny-pack type bags during takeoff and landing. I'm not sure if this applies to wearing it on the waist or not. I would imagine not.

This might not be new or exclusive to Canada - it's just the first I've noticed it.


> This might not be new or exclusive to Canada - it's just the first I've noticed it.

Not Canada-only:

> So sorry for the disappointment with the carryon requirements. Please know that your fanny pack is considered a personal item and must be stowed properly during taxi, takeoff, and landing. Still, we understand the frustration and have documented your concern.

* https://twitter.com/SouthwestAir/status/1796641027924889819

* https://viewfromthewing.com/stupid-airline-carry-on-rules-if...

It may be a case of people abusing things and instead of a 'small' pack, they have a 'regular' purse and are trying to call it fanny pack. Then actually have a purse / personal item and a carry-on.


Yes, better use a fanny pack and have it on you at all times. Don’t even remove it and store it in your bag temporarily when on an airplane, you never know if it’ll capsize on landing and you’ll need to avoid people on the internet criticising you.

It also goes without saying that you should keep in on while showering and sleeping too, you never know when your hotel could catch on fire.


> Don’t even remove it and store it in your bag temporarily when on an airplane, you never know if it’ll capsize on landing and you’ll need to avoid people on the internet criticising you.

You'll need to first avoid succumbing to smoke inhalation or flames if you don't get out in time (or cause someone else to not get out because your fumbling).

The take-offs and landings (and perhaps add approach) phases of flight constitute ~5% of flight time, but the vast majority of the fatalities:

* https://flightsafety.org/asw-article/loc-i-accidents-led-oth...


Do you see lots of smoke and flames in this video? There are several people outside already, with backpacks too. It is incredible how people feel entitled to, based on a split second from a video, judge so harshly another human being who just went through a traumatic experience. We weren’t there. The situation looks under control. For all you know this person gave their turn to others inside the plane so they could get out before her.

I'm not judging harshly: adrenaline dumps are a real thing. And even though it looks under control, a few passenger interviews have indicated that many folks didn't have time to think.

But the whole point of all those procedures about turning stuff off and putting things is away is situations like this: you may or may not have time to think, and you may or may not have to deal with smoke or flames. And just because there weren't smoke/flames right at that moment, you can't tell if they would arrive "soon": planes have been completely engulfed in fire with-in 90 seconds in the past.

The idea behind suggesting a fanny pack, and perhaps having all your cards and papers (and medicine) on your person, is so that if such a thing should happen you do not have to think to make sure you have what you need. So that in a panic you already have it with you if you get out just by the fact you got out and it was physically attached to you.


On a second read, my original comment was unkind and I regret it. I lumped you in with all the other comments which I saw as unfairly criticising a situation most of us will never be in and responded with mockery, but that is neither an excuse nor fair to you.

Your points are well reasoned—and I believe well-intentioned—and I should’ve done better. I apologise.


Heaven hath no fury like someone who works a desk job and lives the apartment/condo/nice subdivision life and is generally free from any physical danger judging other people's risk assessment.

It’s better to be outside the aircraft, alive and without your stuff than inside and dead. You can get insulin in any western city.

I'm not sure it's so easy, I travel a lot, and western cities are the hardest to get any medication.

In Hawaii we were robbed with my girlfriend and went to a pharmacy and to doctor with no papers and we weren't able to refill our contraception pill (pharmacy told us to go to doctor, doctors said we need a lot of tests even though she was already taking the medication and we had police reports). Generally it's not advised to skip a day, and skipping 2 is not allowed, but doctors didn't care.

(after a lot of search we found out that Amazon online clinic is much better and even cheaper with prescriptions).

In latin america or Thailand or anywhere else in the world we could just go to a pharmacy and get what we want.


I carry a very small cross body pack with my essentials (passort, meds, emergency card and cash) that I strap on before descent and at any other time there's a chance I'll get separated from my bags.

And person making movie on their smartphone.

I wouldn't have enough context to be mad. That sounds stressful and unhealthy.

To be fair, it had all her stuff, so she couldn't just leave it behind. /s

Sarcasm aside, while still not acceptable, some people might not have the means to buy new items to replace what they lost in a crash. So it is understandable for some people to make the choice of taking their luggage with them in such an event, as they might not have the wealth and/or insurance necessary to replace those items afterwards.

Of course the solution would be to make airlines liable to replace passengers' luggage in the event of a crash and inform the passengers that they will do so, but that's not how the world works currently.


> liable to replace passengers' luggage

Aren’t they? AFAIK it’s standard (if not required?) for airlines to have insurance which includes passenger legal liability.

Were there any recent crashes where passengers weren’t compensated? e.g. after US Airways 1549 everyone received at minimum $5k (or higher depending on damages) for lost luggage.

edit: https://www.law.cornell.edu/cfr/text/14/205.5


In general the airlines just ask you to leave your luggage. If they were legally obliged to replace all your items, they would inform you of such.

On international flights, an airline is liable for up to $1700 per the Montreal Convention. This might cover say half of one's laptop, which no matter how stupid it sounds, makes taking your luggage with you the only financially sensible choice in a crash (unless you have insurance). Now obviously such an event has other priorities than just financial ones, but it's no surprise if people choose to take their luggage with them.

On US domestic flights the amount is somewhat higher, $4700. However even this might not be enough for some. On EU domestic flights it's 1800€.

Airlines however are free to pay any amount they want, but they are not legally required to pay more than the limits set by law. So it is possible you will be reimbursed in full, but you wouldn't know that beforehand.


> This might cover say half of one's laptop

$3400 is a pretty pricey laptop for someone short on cash.

Also, am I correct in understanding that these requirements are the base requirement for any crash and don't actually absolve the airline of the full liability in case they are found to be responsible for the crash?


> This might cover say half of one's laptop, which no matter how stupid it sounds, makes taking your luggage with you the only financially sensible choice in a crash (unless you have insurance).

If there's no smoke, no visible flames, and you can do so safely without obstructing other passengers' egress? I can see the argument, sure.

Obviously if the cabin is filling with smoke or there are visible flames or other obvious dangers, the financially sensible choice is to evacuate ASAP as funerals often cost more than laptops.


> If there's no smoke, no visible flames, and you can do so safely without obstructing other passengers' egress? I can see the argument, sure.

While there are no smoke/flames now or initially, that doesn't mean they won't appear "soon": planes have been completely engulfed with-in 90 seconds.


I don't think a stressed rando inside the plane is in position to evaluate how soon it will combust. Not even the firemen on the outside often have a clue.

Eh, I'd defer to them over some rando on the internet who's only seen a video that shows a short snippet of what went on.

The best anyone here can do is screech about not following the default suggested practice of leaving the luggage but the person who took the bag was actually there. Perhaps they had to pick it up because it was on the floor (ceiling) in their way. Not much harm in carrying it if it's something that small anyway.


I'm not arguing it's right. Frankly, I think it's stupid the way things are. But I can understand why some people make such choice.

I guess my argument mainly is that people who take their luggage are not stupid, instead their behavior may be highly rational, however we have the means to change it with by making such choice irrational and I wish we will.


> people who take their luggage are not stupid

I agree with your parent’s post explaining its a sensible financial choice. However as you noted there’s other things One could consider like other’s passagers survival chances or firefighter taking dangerous steps during their work.

Taking your language is financially sensible but socially dumb and selfish. It seems an acceptable choices in the countries that values individual liberties and financial independence, but the other half of the world look very bad at that behavior.


If people's response to COVID didn't convince us that selfishness has taken over the world, I don't know what will.

In terms of explaining the passenger's behaviour, though - presumably they didn't know this, and didn't have time to research it on their phone during the crash.

Airline customer service standards are very low; I can see how a person making the decision based on just their experience with airlines would conclude it was better to grab their carry-on if it was safe to do so.


Anyone that disregards explicit instruction by cabin crew, regarding safety, is an idiot, regardless.

I give zero shits if you think you’re going to lose your stuff. And you should give zero shits if I’m going to lose mine.

Don’t act like this is a class / means thing. It isn’t. This is just Americanism.


People who interact with the public and work for BigCo routinely bark orders that are non-optimal for the customers individually but convenient for the company.

Customers have been trained to stop and think twice when someone tells them what to do. That's just the reality of the world we live in.


Everyone thinks they are the main character of the story. I should get to keep my bag because I am the protagonist, but everyone else is supposed to leave theirs, so that we can escape faster! The rules don't apply to me specifically because I am the only person in my life that matters.

This isn’t an Americanism. It’s a ‘people not explicitly trained for this scenario’ ism.

If you think this is bad, I guarantee you could play out this scenario in roughly 3/4 of the world and it would be worse.


> I give zero shits if you think you’re going to lose your stuff.

Yeah, last time an airline lost my bag they said pretty much the same thing.

The way I see it, there are two types of idiot:

You're an idiot if you delay the evacuation of a crashed plane. Shit's on fire, yo.

And you're an idiot if you expect an airline will make you whole. Airlines are in the business of delivering the worst customer service they can get away with - they don't even guarantee that a person who has booked a seat on a flight will have a seat on the flight.


>Airlines are in the business of delivering the worst customer service they can get away with

The DMV is pure customer service.

Airlines are "applied" customer service since they actually deliver a service there is demand for.


Not just an idiot, but also a criminal...

> Sarcasm aside, while still not acceptable, some people might not have the means to buy new items to replace what they lost in a crash. So it is understandable for some people to make the choice of taking their luggage with them in such an event, as they might not have the wealth and/or insurance necessary to replace those items afterwards.

One person's means are not more important than the lives of the people on board. Stuff can be replaced; get everyone to safety first, then worry about stuff.

And yeah airlines are liable to replace stuff in the event of a crash and pay for damages if it's their fault. If it's the fault of the airplane manufacturer, they will have to; Boeing paid out billions to all parties involved in accidents and groundings of the 737 max:

> On January 7, 2021, Boeing settled to pay over $2.5 billion after being charged with fraud over the company's hiding of information from safety regulators: a criminal monetary penalty of $243.6 million, $1.77 billion of damages to airline customers, and a $500 million crash-victim beneficiaries fund.

https://en.wikipedia.org/wiki/Financial_impact_of_the_Boeing...


They might even need clean underwear and have that in mind. Probably the most scary experience of their lives and people act strangely.

Still not a rational decision. Poopypants > crispy skin.

You really only have to keep your important papers in your pants pockets.

Would be easier if airplane seats weren't as cramped.

It had approved the budget for USAID which was slashed wholesale.

Most people reading this will switch careers from IC before that happens.

Independent Contributor?

I guess the NSA was really behind the commits all along

It certainly isn't. Getting even C code written by human with best effort for addressing standards and conventions accepted is challenging enough.

To be fair cost per launch was in that ballpark already ($$0.15-0.05) with Ariane, Atlas and Soyuz non-reusable vehicles. SpaceX maintains the cost just about to undercut the competition.

I think they maintain the price there. They'll want to drive the cost as low as possible, because price - cost = profit for them. A penny saved is a penny earned.

tl;dr sublinear worst case query and insertion in hash tables.

Specifically, (log x)^2

Eli5?

If you're trying to find an available cubby hole for your boots, you'll find one very quickly if they're almost all empty. But if they're almost all full, it will take longer for you find one. This discovery shows that it won't take as long as previously thought.

hash tables are most famous for their O(1) lookup time, but then you have to deal with collisions. There's many famous ways of dealing with collisions and you can convince yourself of their [worst case] lookup time. The article is discussing a new upper bound on that worst case.

This is always a point of frustration for me. Under the normal big-O model, hashtables aren't, and can't be O(1) lookup, even for the mythic perfect hash function! You can only get the O(1) figure by breaking the big-O model and bolting on some in-practice assumptions[1] that are used nowhere else in discussion of asymptotic complexity.

Specifically, as you resize the table, you need a function with a bigger output space to give you more places to store the item. To have a bigger output space, you unavoidably have to do more computations. If you go from a function with n possible outputs to one with 2n possible outputs, as n goes to infinity, you eventually have to use a function with more steps.

[1] elaborated on in this earlier discussion: https://news.ycombinator.com/item?id=9807739

Specifically this comment about the extra assumptions: https://news.ycombinator.com/item?id=9813524


Your sense of frustration seems to stem from thinking about something which is similar to big-O, but not actually being big-O.

All of the points you raise are valid if you want to have a good understanding of actual runtime cost of an algorithm.

None of it is relevant if you want to compare algorithms according to big-O, in order to find one which doesn't lead to failure[1] when faced with large amounts of data.

Perhaps you should define your own big-R notation for what you're after.

[1]: https://arstechnica.com/information-technology/2013/12/expon...


What are you taking about? By the actual standards of big-O that allow you to derive the constant run time? See the second linked comment which establishes that it only becomes constant when you add in practical hardware considerations.

No bounded run time function can have an infinite output space (while still halting, anyway).


What you are saying in that post is that a hashmap should be O(log(n)) because if you have a word size w you need k_w = log(n)/w operations to compute the hash of a key that's large enough to not have collisions.

However by that logic the comparison function should also have a similar factor, since by the same argument the key values need to be large enough not to collide. Ie if the key values are just the natural numbers up to n for example, you'll need k_w words to store them and hence comparison takes O(k_w) = O(log(n)).

Thus a binary tree should also have an additional log(n) factor due to this, and hence be O(log(n)^2)).

However the point of big O is to compare, and since both have this log(n) factor you could just cancel that in both, leaving you with the familiar O(1) and O(log(n)) respectively for the hashmap and binary tree.

Is it sloppy to do that prematurely? Kinda yes, but it makes comparisons much easier as you don't have to go cancelling those log(n) factors all the time. And the point of big O is to compare the algorithms, not accurate running time.


Okay, so some communication tips:

1) You should have led with that to get to the point immediately instead of cryptically alluding to the existence of such a point and adding an irrelevant example.

2) Your point was already made in an initial reply[A]. You didn't need to make your comment at all, and if you were going to lazily allude to the existence of an argument, you could have just linked that one. Or, just upvote it. Comment sections don't need repeats of points already made unless you have something to add.

To address the point you did add:

3) You're still conceding the core point that you have to go outside the usual big-O model to get hashtables being O(1). In no other case does anyone take big-O to mean asymptotic complexity relative to comparable solutions for the same problem -- not unless that's explicitly stated. You can't have a data structure with constant-time lookup, period.

[A] https://news.ycombinator.com/item?id=43006957


I actually kind of get where you're coming from, I think. I'm trying to understand your argument, I think it goes something like this:

1. "But if the universe grows too big, then the integers get too big!". Fair point.

2. You concede that the Word-RAM model does accurately describe an O(1) hashing operation.

3. We now define a new computation model, where hashing is just O(1).

4. "this is still wrong, because this doesn't model the behavior as keys grow to infinity"

The important thing here is that the hashing oracle isn't defined to even care about integer arithmetic complexity. I think one thing you may be confused about is that it seems like the hashing oracle can only be implemented with integer-sized keys, actually the thing that epeople are trying to minimize in hashtable research is calls to that oracle. That oracle can be some genie in a lamp, my deadbeat cousin, or a computer program.

---

I think you even get that though on a logical level, so the crux probably goes something like, "The word-RAM model forces me to be of bounded size, but for higher level intuition, I just forget that? What? And then I stitch them back together? I mean sure, given that it's O(1), I get it, but there's no way this 'stitches together' cleanly, it's not actually O(1)!"

I didn't even know this term, but it seems like people have invented a term for this, the trans-dichotomous model. Basically, word size (integer size) scales with problem definition size. So I imagine that it's just taken for granted that trans-dichotomy sort of just "propagates up" your stack of logic, informally, if you want to understand each and every operation.

I mean, for me, the first paragraph was mostly fine enough for me - analyzing abstract models asymptotically w.r.t. various kinds of cost is already something I'm familiar with, so just saying hashing is an O(1) cost by definition makes sense.

The proofs doesn't have to know about what the hashing oracle actually is - the "integer" in the Word-RAM model is not the same as the "integer" produced by the hashing oracle, even though they both have "O(1)" cost within their respective models. I think viewing it as hooking them up together hurts you.

Word-RAM Integer is O(1) because it's trans-dichotomous, and in this specific hashtable analysis, the hashing oracle is O(1) just because it is by definition, we only care about # of calls to that function.

Even though the intuition is that they're hooking up together - recall that your hashing oracle backend can be your drunk cousin at 3am spouting out a consistent uniform random number mapping in the range [0...n-1], we're not really particularly interested in anything else.

Oh, and also, the oracle must take in two parameters, (key, size of space), and the assumption is that, for each size of space, the key is randomly uniformly consistently mapped. Although in the paper they don't even need to deal with variable hashtable resize schemes so they don't even need to re-define this.

But like again, like, we make these "constants" by saying, "I don't care how the hash function is performed, as long as it satisfies these properties; all I'm gonna try to do is implement an algorithm that does the minimal hashing possible". That's not nefarious, that's standard abstraction practice.

I did try to sit with your doubt for a while though and this is the best explanation I can come up with. If I didn't understand, oh well.

https://en.wikipedia.org/wiki/Word_RAM https://en.wikipedia.org/wiki/Transdichotomous_model


The problem is, big-O doesn't use the word-RAM model mentioned in the comment. That's something you have to bolt on to the get the O(1) hashtable result. Which is the very point I was making originally, that you have to go outside standard big-O and incorporate practical considerations, which isn't done anywhere else as a matter of course.

> That's something you have to bolt on to the get the O(1) hashtable result.

No, you brought that on by claiming not considering it was an error.

In standard big-O you take as an assumption that memory operations are O(1), comparisons are O(1) and calculating hash values are of the same order as making a comparison (and vice versa).

Once you do that, then a hash table becomes O(1) on average, as it's just a O(1) calculation followed by a O(1) memory lookup (assuming no collisions on average).


>In standard big-O you take as an assumption that memory operations are O(1)

No. If it look up big-O in a math book, it's not going to say anything about that. You can add assumptions on, but that's not big-O anymore, but something different. That's the point.


Again, Big-O is only relevant w.r.t a specific cost analysis.

Hashtable analyses don't care how you get the hash function - it can take exactly 72 hours to arrive, but as long as the oracle satisifes some probability distribution guarantee, it's good. That is an O(1) operation, a single hash.

Like, there's no going "outside" for big O, there's no "standard". It's always backed by some notion of what you are computing. There's pointer machines, turing machines, automata, circuits, for your complexity. Pointer machines can't directly address at offsets, Word-RAM can. Different tradeoffs for different analyses - pointer machines often model GC-collected languages and heavy pointer data structures, while Word-RAM deals with more compact data structures.

Again, as mentioned in the paper, Big O isn't used as a notion for number of total operations, it's only trying to *minimize the number of calls to the hashing oracle*. So your analyses can get even more fine-grained.

You might even be excited to learn about the External Memory Model. In that model, you have two blocks of memory; one block where *every single operation* is free, and one block in which you can't access, you must fetch into memory. You fetch blocks of size B, your local memory is B << N, and external memory is N << M. Even operation in block N is free, but and the only thing you can do on block M is read/write a block of size B. The question then is, to fetch the minimum number of blocks for your specific algorithm.

I've been originally confused by algorithms in this model, too - sometimes the "real number" of operations would be an order of magnitude more than the number of block accesses, but we just don't even count them? How does that make sense?

Turns out this actually models real hardware surprisingly well - it's often faster to simply recompute and do extra computation in order to minimize memory accesses. It's used a lot in databases. Although I can't find the exact wording "External memory model", the FlashAttention paper uses the wording "IO/Aware" and analyzes block transfers like this on the GPU, so... yeah.

So going 'higher up' in the abstraction stack doesn't necessarily sacrifice practicality either; in fact, it can sometimes help.

Sure, we can view the intuition as chaining together layers of abstraction, I get that view. But each layer functions perfectly logically, independently of the others. It's just like good decoupled software practice.

> you have to go outside standard big-O and incorporate practical considerations, which isn't done anywhere else as a matter of course.

Hopefully I've explained it better. Different models of computation are a fundamental part of theoretical computer science, since of course, as you've pointed out, you have to be very careful about defining operations. At the same time, part of the great part about CS (and math in general) is, that you can specify, "Assuming these conditions, what can I logically derive?" and that's just done everywhere.


>Hashtable analyses don't care how you get the hash function - it can take exactly 72 hours to arrive, but as long as the oracle satisifes some probability distribution guarantee, it's good. That is an O(1) operation, a single hash.

The problem is that, as n goes to infinity, you're not using the same hash function -- you can't. So even if you can assumed that one hash function has constant time, the later ones you need as you scale up wouldn't be.

And I don't know why you think you need to bring up probability distribution properties -- I made clear by now that the above points apply even to the mythic perfect hash function.

>Hopefully I've explained it better. Different models of computation are a fundamental part of theoretical computer science, since of course,

And it's fine to use different models! It's not fine to silently switch between them in an ad hoc way, which is what's necessary to make the exceptions that get you O(1) lookup for hashtables. I have never seen anyone expect the relevant caveats when quizzing coders for the correct answer on that question. That makes this part of computer science more like memorization or stamp collecting than a genuine mathematical model from which you consistently derive answers.


To be fair, in tree tables, we also assume that comparison is a constant time operation as well when it also necessarily needs to be O(log(n)) for an arbitrary sized table, making it an O(log(n)^2) data structure by this standard.

You don't need to compare the whole key most of the time. I think the amortized cost for a comparison is in O(1).

Not in a balanced tree, since the further down the tree you go, the longer the shared prefix between the search key and node key becomes.

So the complexity becomes something like 1 + 2 + 3 + .. + log n = O(log^2 n).


Good point. Perhaps we could store the length of the common prefix from the last time we went left as well as from the last time we went right. The minimum of those two should remain a common prefix with the search key for the rest of the lookup and should therefore be safe to skip during subsequent comparisons.

But that would actually help it because you can store how far down the match is by that point in the tree, and know how few digits you have to actually compare.

O(1) lookup is bullshit that ignores the memory hierarchy.

IMO it's more reminiscent of Red Guards from Cultural Revolution era China.

And university students during the Iranian Revolution.

The TAoCP itself is a side project from his original goal of writing a book on compilers.

Did he complete the compilers book, or even start it? I know he has worked on TAoCP for a huge amount of time, and on TEX too.

From what I understand, TAoCP is building up to that compilers book! When initially tasked with writing about compilers, he realized all the background necessary for building them and planned out these books as an overview of computational techniques that would be helpful to use.

See the "future plans" section of his website: https://www-cs-faculty.stanford.edu/~knuth/taocp.html has volumes 6 and 7 as being on compilers.


danke, freund

Gotta shave some Yaks

I dunno most people I know here do appear to have iphones. And many of those who have an Android seemingly have an iPhone as work or personal device in addition. So 60+ percent doesn't sound unlikely.

This is great! Thanks for sharing it.


Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: