[HN Gopher] Undergraduate Upends a 40-Year-Old Data Science Conj...
___________________________________________________________________
Undergraduate Upends a 40-Year-Old Data Science Conjecture
Author : Jhsto
Score : 273 points
Date : 2025-02-10 17:05 UTC (5 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| varjag wrote:
| tl;dr sublinear worst case query and insertion in hash tables.
| bean-weevil wrote:
| Specifically, (log x)^2
| pinoy420 wrote:
| Eli5?
| laweijfmvo wrote:
| 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.
| SilasX wrote:
| 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
| tejohnso wrote:
| 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.
| sam0x17 wrote:
| This is huge, when can we get a rust implementation?
| natpalmer1776 wrote:
| Be the change you want to see in the world!
| maujim wrote:
| claude one-shot it, then open source it, and build from there
| DC-3 wrote:
| Sounds like a really good way to get a robust implementation
| of a fiddly and novel algorithm.
| duskwuff wrote:
| Paper: https://arxiv.org/pdf/2111.12800
| something98 wrote:
| This is the correct (2025) paper.
|
| https://arxiv.org/abs/2501.02305
| qntty wrote:
| A cool result, but it seems like it should be called a computer
| science conjecture
| ayhanfuat wrote:
| Especially considering "data science" is nowhere near 40 years
| old.
| Tetraslam wrote:
| https://www.rcseng.ac.uk/library-and-
| publications/library/bl...
| anthk wrote:
| Statistics are old.
| speed_spread wrote:
| On average.
| frabert wrote:
| I think the article's author may have seen the cs.DS
| classification on the arxiv and assumed it meant Data Science
| instead of Data Structures
| jjallen wrote:
| Is it just me or did the article not go in to how the improvement
| works, just the speed of it?
| pinoy420 wrote:
| It didn't really go in to either. It doesn't have any sort of
| benchmarking or any best/worst case fits?
| jjallen wrote:
| I was very interested in the improvement. That is the crux of
| the subject if you ask me.
| amazingamazing wrote:
| This is a good test because it's recent. Let's see if deep
| research can come up with this result without just copying this.
|
| Edit: gpt4, Gemini 2 and Claude had no luck. Human driven
| computer science is still safe.
| rvz wrote:
| Original thought or additional intuitive improvements such as
| this discovery is what we should be looking for.
|
| This can come from _anywhere_ in the world. The best part is,
| it did NOT discovered from an AI program.
| orlp wrote:
| Skimming the paper [1], the key difference they used is that
| their hash table insertion algorithm will probe further than the
| first empty slot, instead of greedily filling the first empty
| slot it finds. They combine this with a clever probing sequence
| which provably finds empty slots efficiently, even if the table
| is very full.
|
| This means insertions when the hash table is less full are
| slower, but you avoid the worst-case scenario where you're
| probing for the last (few) remaining open slot(s) without any
| idea as to where they are.
|
| [1]: https://arxiv.org/pdf/2501.02305
|
| ---
|
| An interesting theoretical result but I would expect the current
| 'trick' of simply allocating a larger table than necessary to be
| the superior solution in practice. For example, Rust's hashbrown
| intentionally leaves 1/8th (12.5%) of the table empty, which does
| cost a bit more memory but makes insertions/lookups very fast
| with high probability.
| SiempreViernes wrote:
| But you could do some hybrid, where you do greedy fill for a
| while and then switch to this fancier fill once your table is
| approaching full (using some heuristic)?
| gizmo wrote:
| Not really because you have to use the same algorithms during
| subsequent lookups. Imagine you add a bunch of items with
| insert algorithm A, then you cross some threshold and you
| insert some more items with Algorithm B. Then you delete
| (tombstone) a bunch of items. Now you look up an item, and
| the slot is filled, and you're stuck. You have to proceed
| your lookup with both algorithms to find what you're looking
| for (thereby giving up any performance benefits) because the
| current occupancy doesn't tell you anything about the
| occupancy at the time when the item you were looking for was
| inserted.
| layer8 wrote:
| I would assume that you need to start early to be able to
| reap the benefits once the table is almost full.
| elchananHaas wrote:
| No, it has to do with the coupon collectors problem. The key
| idea behind this algorithm is to do more looking for an empty
| spot up front.
| elchananHaas wrote:
| I might be misreading their algorithm, but from my look at the
| paper the key improvement is a non-uniform strategy where they
| divide the array into buckets and focus on different buckets as
| they fill the table. This increases the average number of
| locations to be probed even when the table is emptier. They
| still place the item in the first empty slot they see with this
| strategy.
|
| The "skipping slots" has to do with jumping ahead in the hash
| sequence.
| joe_the_user wrote:
| The theoretical properties of hash table always seemed so
| impressive to me that they bordered on magic (and this just
| extends them). What seemed crazy was how they could be so much
| better than trees, which to me were intuitively the most
| efficient way to store data.
|
| What I realized is that the theory of hash tables involves a
| fixed-sized collection of objects. For this fixed collection, you
| create a hash-function and used that like a vector-index and
| store the collection in a (pre-allocated) vector. This gives a
| (fuzzy-lens'd) recipe for O(1) time insert, deletion and look-up.
| (The various tree structures, in contrast, don't assume a
| particular size).
|
| The two problems are you have to decide size beforehand and if
| your vector gets close to full, you insert etc processes might
| bog-down. So scanning the article, it seems this is a solution to
| the bogging down part - it allows quick insertion to a nearly-
| full table. It seems interesting and clever but actually not a
| great practical advance. In practice, rather than worrying a
| clever way to fill the table, I'd assume you just increase your
| assumed size.
|
| Edit: I'm posting partly to test my understanding, so feel to
| correct me if I'm not getting something.
| vessenes wrote:
| It _looks_ to me like the idea is, as you generally describe,
| that you segment your table into a 2d structure (well
| conceptually) and proceed to fill one 'row' at a time until
| it's about 75% full, at which point you move on to the next
| one.
|
| I don't have time to fully grok the paper, but they claim this
| makes insertion consistently fast (I believe this until we're
| at 75% of total capacity, but maybe they have some other mode
| for filling when they're at 75% in every row?). They also claim
| retrieval is fast, and I didn't read enough to understand how
| even retrieval works, or why it is faster.
|
| I'll put out that there a lot of times that it would be really
| nice to have a nearly full hash table still, you know, work.
| You can't always change the size of one during execution of a
| program. And, in some environments memory counts a lot. That
| said, I would like to see and play with an implementation --
| I'm not sure this is 'worth it' in the general case.
|
| It is also probably cache inefficient, as are most things about
| hash tables, with the exception of linear probing for reading
| out of a fairly full one, in which case, you get to just keep
| pulling stuff directly out of memory to check it. So, it's not
| clear to me that this is performance wise worth it. Anyway, I'd
| like to fully understand it, it seems like an interesting new
| idea.
| hcs wrote:
| Proofs of constant time operations include time taken to resize
| the table. This takes much more time (linear in the size of the
| table), on insertions when the table is resized, but that time
| is amortized over all the insertions already done. It still
| works out to constant average time if you grow the table enough
| each time (once it starts to get too full) so it happens with
| decreasing frequency.
| zelphirkalt wrote:
| I think this is only true in the imperative world, where
| mutation is used. For the functional world it is probably still
| trees.
| MR4D wrote:
| Reading through this article is like reading a description of the
| Monty-Hall problem. [0]
|
| It's as through the conclusion seems to defy common sense, yet is
| provable. [1]
|
| [0] - https://priceonomics.com/the-time-everyone-corrected-the-
| wor...
|
| [1] - 2nd to the last paragraph: "The fact that you can achieve a
| constant average query time, regardless of the hash table's
| fullness, was wholly unexpected -- even to the authors
| themselves."
| darknavi wrote:
| I always really enjoyed the Numb3rs lecture on Monty-Hall
|
| https://www.youtube.com/watch?v=P9WFKmLK0dc
| ryao wrote:
| > "Our brains are just not wired to do probability problems
| very well, so I'm not surprised there were mistakes," Stanford
| stats professor Persi Diaconis told a reporter, years ago.
| "[But] the strict argument would be that the question cannot be
| answered without knowing the motivation of the host."
|
| This is wrong. Let's label the goats A and B to simplify things
| (so we do not need to consider the positions of the doors).
| There are 3 cases:
|
| 1. You pick the right door. The other two doors have goats. The
| host may only choose a goat. Whether it is A or B does not
| matter.
|
| 2. You pick the door with goat A. The host may only choose goat
| B.
|
| 3. You pick the door with goat B. The host may only choose goat
| A.
|
| The host's intentions are irrelevant as far as the probability
| is concerned (unless the host is allowed to tell the contestant
| which door is correct, but I am not aware of that ever being
| the case). 2/3 of the time, you pick the wrong door. In each of
| those cases, the remaining door is correct.
|
| The most strict argument is yet another statistics professor
| got basic statistics wrong.
| CrazyStat wrote:
| I can assure you Diaconis didn't get it wrong.
|
| > "The problem is not well-formed," Mr. Gardner said, "unless
| it makes clear that the host must always open an empty door
| and offer the switch. Otherwise, if the host is malevolent,
| he may open another door only when it's to his advantage to
| let the player switch, and the probability of being right by
| switching could be as low as zero." Mr. Gardner said the
| ambiguity could be eliminated if the host promised ahead of
| time to open another door and then offer a switch.
|
| The hosts's intentions absolutely do matter, because the
| problem (as originally stated) doesn't specify that the host
| _always_ opens a door and offers a switch. Maybe he only
| offers a trade when you initially picked the good door.
| thadt wrote:
| > Maybe he only offers a trade when you initially picked
| the good door.
|
| That would be a rather convenient signal to the player.
| CrazyStat wrote:
| Indeed. But the hosts machinations can be arbitrarily
| more complex; maybe he offers the switch to contestants
| he finds attractive only when they've picked a goat, and
| contestants he finds unattractive when they've picked the
| car.
| the_af wrote:
| You're introducing bizarre ad hoc hypotheses.
|
| This works as a logic puzzle. Assuming the host offers
| different doors depending on contestant attractiveness
| makes absolutely no sense. It's a bizarre assumption.
|
| Maybe the goats can wander from door to door, or maybe
| there is no car, or maybe behind all of the doors there
| are tigers. Which would be absurd and unrelated to this
| puzzle.
| ryao wrote:
| This is like being asked how to solve a (legal) Rubik
| cube configuration and then considering how close you can
| come to a solution if given an illegal configuration. It
| is not relevant since it is not what was presented. You
| can always make things more complex by considering
| variations that are not relevant to the original problem.
| ryao wrote:
| The problem as stated does not give the host such an
| option. If it did, the host opening a door would imply that
| the player picked the right answer, and it would only
| happen 1/3 of the time.
|
| Some of the comments aged fairly well, although not in the
| way that their authors intended:
|
| > There is enough mathematical illiteracy in this country
|
| > If all those Ph.D.'s were wrong, the country would be in
| some very serious trouble.
|
| In the 1800s, Carl Friedrich Gauss lamented about the
| decline in mathematical ability in academia. Despite
| academia since having advanced mathematics farther,
| mathematical ability in academia still has evidence of
| decline. Professors tend to be good at extremely
| specialized things, yet they get the simple things wrong. I
| once had a Calculus professor who failed to perform basic
| arithmetic correctly, during his calculus class. All of the
| algebra was right, but his constants were wrong. This
| happened on multiple occasions.
| CrazyStat wrote:
| The problem as stated, in the article _you_ pulled your
| quote from, puts no limits on how the host decides
| whether or not to offer a switch:
|
| > Imagine that you're on a television game show and the
| host presents you with three closed doors. Behind one of
| them, sits a sparkling, brand-new Lincoln Continental;
| behind the other two, are smelly old goats. The host
| implores you to pick a door, and you select door #1.
| Then, the host, who is well-aware of what's going on
| behind the scenes, opens door #3, revealing one of the
| goats.
|
| > "Now," he says, turning toward you, "do you want to
| keep door #1, or do you want to switch to door #2?"
|
| All you know is that in this particular instance the host
| has opened a door and offered a switch. You cannot
| conclude that the host _always_ opens a door and offers a
| switch.
|
| The problem as stated allows the host to offer switches
| only when the contestant picked the door with the prize,
| or only when the moon is gibbous, or only when the tide
| is going out. Diaconis and Gardner are completely correct
| to point out that the problem as stated is under
| specified and that the _intent of the host matters_.
| ryao wrote:
| The problem as stated has the host open an incorrect door
| and offer the player a chance to change his choice.
| Inferring that another possible variation might exist
| does not change the fact that we are discussing the
| variation that was presented. Both you and Diaconis are
| wrong.
| CrazyStat wrote:
| > The problem as stated has the host open an incorrect
| door and offer the player a chance to change his choice.
|
| Correct, in this one particular instance. You cannot
| conclude from this particular instance that the host
| always opens the door and offers a change.
|
| > Inferring that another possible variation might exist
|
| is totally reasonable, while denying the possibility that
| the host might be able to choose his actions specifically
| to benefit or screw you over is an unwarranted leap.
|
| The problem statement does not put constraints on the
| host. You cannot solve the problem by assuming that those
| constraints exist and then attack those like Diaconis who
| point out that those constraints don't exist and that the
| thing that is unconstrained _matters_.
| ryao wrote:
| The problem statement does put constraints on the host,
| by specifying that the host opened an unselected door
| with a goat behind it, only to ask if the player wants to
| change his choice. The answer to the question of whether
| the player should change the choice is well defined.
| Other variations are irrelevant since they are different
| problems.
|
| Your argument is equivalent to denying that 2 + 2 = 4 is
| correct because the author had the option to write
| something other than a 2 as an operand.
| the_af wrote:
| > _All you know is that in this particular instance the
| host has opened a door and offered a switch. You cannot
| conclude that the host always opens a door and offers a
| switch._
|
| And in this particular instance, it makes sense to
| switch.
|
| I'm sorry, but the problem is well-formed and well-
| specified.
| the_af wrote:
| > _[...] the problem (as originally stated) doesn't specify
| that the host always opens a door and offers a switch.
| Maybe he only offers a trade when you initially picked the
| good door._
|
| That would make no sense. Also, Monty _always_ opens a door
| with a goat. The problem is well-formed, but most people
| misrepresent it in order to object to it.
| CrazyStat wrote:
| > Also, Monty always opens a door with a goat.
|
| Nope! That's you adding a constraint that does not exist
| in the original problem.
|
| > Was Mr. Hall cheating? Not according to the rules of
| the show, because he did have the option of not offering
| the switch, and he usually did not offer it.
|
| From [1].
|
| Constraints matter. Don't play fast and loose with them.
|
| [1] https://www.nytimes.com/1991/07/21/us/behind-monty-
| hall-s-do...
| ryao wrote:
| You have removed a constraint from the original problem.
| What could have happened does not matter since we are
| being asked about what did happen.
|
| Imagine two people playing a game of chess. Various moves
| are played. Then you are asked a question about the state
| of the board. The answer depends on the state of the
| board. It does not depend on the set of all states the
| board could have taken had one player made different
| choices.
| CrazyStat wrote:
| You have hallucinated a constraint that never existed and
| then accused me of removing it.
| ksenzee wrote:
| Did you not read the entire article on how scads of
| intelligent people got this wrong? And the explanation of why
| they got it wrong? It's like following a map that carefully
| routes you around a sinkhole, and then stepping right into
| the sinkhole.
| ryao wrote:
| I read the entire article. They all had defective
| reasoning. The player picked an option with a 1/3 chance of
| being right and a 2/3 chance of being wrong. The host's
| action did not change that. However, the host's action did
| make the remaining door have a 2/3 chance of being right
| and a 1/3 chance of being wrong.
| shkkmo wrote:
| I don't think "motivation of the host" is a great way to
| accurately describe the issue that Diaconis is calling out,
| it is rather intended to be more intuitive.
|
| In a precise way, the reason the question is underspecified
| is because it doesn't say if the probability of the host
| offering you a chance to choose again is dependent on which
| choice you make. If the host offers the choice more twice as
| often when your pick right and when you pick wrong, then
| changing you pick is the incorrect choice.
|
| Now, colloquially, it can makes sense to assume the host
| always offers the choice, but practically, if we're looking
| at how to use statistics in a real world situation, that
| isn't a safe to always assume that probabilities are
| independent.
| default-kramer wrote:
| Not this again...
| https://duckduckgo.com/?q=monty+hall+site%3Anews.ycombinator...
|
| I need to write a blog post or something convincing everyone we
| need to stop talking about the Monty Hall problem and replace
| it with a new problem with all the ambiguities removed. (Unless
| ambiguity is the point, then Monty Hall is fine.)
| the_af wrote:
| There are no ambiguities in the Monty Hall problem. It's
| usually people who skim read and make assumptions about the
| challenge. No new problem is going to stop people from skim
| reading.
|
| For example, going by that ddg search, one result is making a
| fuss about not knowing whether Monty opens a door at random
| and happens to show a goat, or purposefully opens a door with
| a goat behind it. But we do know: it's always on _purpose_ ,
| Monty never opened a door with a car behind it, thus
| prematurely ending the bet. So there's no ambiguity.
|
| The problem is cool because the right answer doesn't seem
| intuitively right, even though it can be formally shown to be
| right.
| chikere232 wrote:
| I imagine one reason people have a hard time with the monty
| hall problem is that they have learnt a rule that _seems_
| to fit but really doesn 't. A person not trained at all in
| math might do better as they haven't learnt that rule.
|
| There's probably a name for that cognitive bias, but I
| don't know it.
| default-kramer wrote:
| > But we do know: it's always on purpose, Monty never
| opened a door with a car behind it
|
| We only know that if the problem tells us. Sometimes it
| doesn't.
|
| > There are no ambiguities in the Monty Hall problem
|
| The problem has been written up thousands of times. I'm
| sure that some writeups are sufficiently unambiguous, but
| many are not. For example, consider the two "variants"
| described by this comment
| https://news.ycombinator.com/item?id=8664550
|
| > The host selects one of the doors with a goat from the
| remaining two doors, and opens it.
|
| > The host chooses one of the remaining two doors at random
| and opens it, showing a goat.
|
| This commenter was trying hard for semantic precision, and
| yet, I think if you encountered the first variant in
| isolation it would be perfectly reasonable to interpret it
| as "The host [randomly] selects one of the doors with a
| goat [although he might have selected the prize]" even
| though this is clearly not what the commenter was
| attempting. If you disagree, that only proves my point:
| this problem is prone to silly and wasteful semantic
| debate, rather than the interesting probability result it
| should be focused on.
| sdenton4 wrote:
| guys it's 2025, let's have a throw-down fight about the monty
| hall problem.
| ascorbic wrote:
| And they wouldn't make him first named author on the paper
| yacin wrote:
| it's common in math/cs theory papers to have the order of
| authors be alphabetical rather than in descending order of
| contribution.
| writebetterc wrote:
| Good, but that can also be noted in a subtitle right below
| the authors (I've seen this in papers myself!)
| mometsi wrote:
| I wonder if there's a significant nominative determinism
| effect--
|
| One might expect some of the most prominent people in math
| and cs theory to have names like Aaronson and Baez...
| chikere232 wrote:
| It would be most fair to hash the names first, especially
| for this paper
| theLiminator wrote:
| Yeah, seems a bit ridiculous that he made the discovery and
| didn't get first authorship.
| anticensor wrote:
| Sibling comment mentions this specific field doesn't have
| author ordering.
| acaloiar wrote:
| The classiest person I ever knew placed me before him on a
| paper just to be nice. Not only was he responsible for getting
| the grants funding our research, but the heft of both the
| theoretical and paper authorship work. I'm no longer in R&D
| and/or academia, but at that point I decided to do the same for
| someone if I ever have the opportunity to write a noteworthy
| paper with someone who is my junior.
| Der_Einzige wrote:
| The best papers have "contribution statements" which clearly
| lays out who did what.
| default-kramer wrote:
| > And for this new hash table, the time required for worst-case
| queries and insertions is proportional to (log x)2 -- far faster
| than x.
|
| > The team's results may not lead to any immediate applications
|
| I don't understand why it wouldn't lead to immediate
| applications. Is this a situation where analysis of real-world
| use cases allows you to tune your hash implementation better than
| what a purely mathematical approach would get you?
| jeffbee wrote:
| Complexity analysis and actual systems programming have been
| diverging for a while. I don't see anything in the paper that
| will inform practice.
| naasking wrote:
| How so?
| zamadatix wrote:
| Even when something isn't a galactic algorithm "how well it
| maps to being done efficiently in real hardware with
| hardware sized data sizes" is more and more often the
| important bit over "slightly better bounds at infinity".
| The former is probing the edge of mathematics while the
| latter is probing the edges of practical construction so
| they rarely seem to align much anymore at these depths.
| gauge_field wrote:
| A contributing factor is how complex/smart the current
| hardware is. It can have cache line size, different forms
| of hardware/software prefetching, different ports for
| different ops, memory latency, simd extensions. These
| leave many opportunities for algorithms to be optimized
| over. There is also the issue of real life scenarios not
| matching with asymptotic ones (due to e.g., size of
| input), which when coupled with previous factors, leads
| to even more potential optimization schemes. Obligatory
| reference: https://agner.org/optimize/
| naasking wrote:
| > Even when something isn't a galactic algorithm "how
| well it maps to being done efficiently in real hardware
| with hardware sized data sizes" is more and more often
| the important bit over "slightly better bounds at
| infinity"
|
| You're just repeating the same claim. _Why_ is that more
| and more often then important bit? Why is it more
| important now? Why is this no captured in complexity
| analysis?
|
| For instance, some complexity analysis assumes random
| access memory of arbitrary size, but memory above a
| certain size is better modelled with logarithmic access
| time. But this too can be captured in complexity
| analysis, so it's not really evidence of any divergence.
|
| And then you have cache-oblivious data structures that
| scale uniformly across all cache sizes, which is a
| product of complexity analysis.
|
| So I'm asking for what exactly is being meant with a
| justification of why you think this matters now more than
| it did before.
| frakt0x90 wrote:
| I haven't read the paper, but sometimes asymptotic improvements
| do not translate to real world improvements due to a large
| multiplicative factor in the complexity that gets factored out
| in the O() analysis. So the dataset required to see speed-up is
| impractically large.
| orlp wrote:
| In this case "x" is 1/d where d is the unused fraction of
| space.
|
| So if you leave 0.1% of your hashtable unused your x is 1000
| - quite problematic. However if you leave 12.5% of your
| hashtable unused your x is 8 - quite reasonable, and not
| something logarithmic behavior would necessarily speed up,
| for reasonable constants.
| echoangle wrote:
| Isn't the problem that the scaling behavior only dominates with
| infinite n?
|
| If you have a constant factor, that doesn't go into the scaling
| rule, so having something scale (log x)2 could still be 100
| times more expensive than something that scales linearly with x
| for all x smaller than 2^100.
| oulipo wrote:
| Most real-world hash table implementations are not
| "theoretical" but depends on "real" parameters like L2 cache,
| assembly instruction sizes, etc
| coulditbeused wrote:
| Could it be used to optimize battery charging speed? Sounds
| like there's some parallel but was interested in an informed
| view.
| layer8 wrote:
| In practice the worst-case operations are avoided by reserving
| a little more space for the hash table. And the new results
| come at the cost of slower "good case" insertions.
| brink wrote:
| Krapivin made this breakthrough by being unaware of Yao's
| conjecture.
|
| The developer of Balatro made an award winning deck builder game
| by not being aware of existing deck builders.
|
| I'm beginning to think that the best way to approach a problem is
| by either not being aware of or disregarding most of the similar
| efforts that came before. This makes me kind of sad, because the
| current world is so interconnected, that we rarely see such
| novelty with their tendency to "fall in the rut of thought" of
| those that came before. The internet is great, but it also
| homogenizes the world of thought, and that kind of sucks.
| aidenn0 wrote:
| > I'm beginning to think that the best way to approach a
| problem is by either not being aware of or disregarding most of
| the similar efforts that came before. This makes me kind of
| sad, because the current world is so interconnected, that we
| rarely see such novelty with their tendency to "fall in the rut
| of thought" of those that came before. The internet is great,
| but it also homogenizes the world of thought, and that kind of
| sucks.
|
| I think this is true only if there is a novel solution that is
| in a drastically different direction than similar efforts that
| came before. Most of the time when you ignore previous
| successful efforts, you end up resowing non-fertile ground.
| layman51 wrote:
| Right, the other side is when you end up with rediscoveries
| of the same ideas. The example that comes to my mind is when
| a medical researcher found the trapezoidal rule for
| integration again[1].
|
| [1]: https://fliptomato.wordpress.com/2007/03/19/medical-
| research...
| Dansvidania wrote:
| there might be a decent amount of "survivorship bias" too.
| meaning you only hear of the few events where someone starts
| from first principles and actually finds, be it luck or
| smarts, a novel solution which improves on the status quo,
| but i'd argue there are N other similar situations where you
| don't end up with a better solution.
|
| That being said, I so disagree with just taking the "state of
| the art" as written in stone, and "we can't possibly do
| better than library x" etc.
| smaudet wrote:
| Plenty of "state of the art", at least a decade ago, that
| was not very state of anything.
|
| I think bias is inherent in our literature and solutions.
| But also, I agree that the probability of a better solution
| degrades over time (assuming that the implementations
| themselves do not degrade - building a faster hash table
| does not matter if you have made all operations
| exponentially more expensive for stupid, non-computational,
| reasons)
| layer8 wrote:
| It's important to think outside the box, and that's easier when
| you're not aware of the box, but we also stand on the shoulders
| of giants, and are doomed to repeat history if we don't learn
| from it. As usual, things aren't clear-cut.
| awesome_dude wrote:
| There's a problem in all human understanding - knowing when,
| and knowing when not to apply pre-existing knowledge to a
| problem.
|
| Have we been grinding away in the right direction and are only
| moments away from cracking the problem, or should we drop
| everything and try something completely new because we've
| obviously not found the solution in the direction we were
| heading.
|
| To put it into a CS type context - Should we be using a DFS or
| BFS search for the solution, because we don't have knowledge of
| future cost (so UCS/Djikstra's is out) nor do we know where the
| solution lies in general (so A* is out, even if you ignore the
| UCS component)
| smj-edison wrote:
| I think of Andre Geim as a great example of balancing the two.
| I couldn't find the exact quote, but he said something to the
| effect of "when I enter a new field, I make sure I learn the
| basics so I don't spend all my time making dumb mistakes. But I
| don't get so into it that I get stuck in the mindshare."
|
| I'll also say I think that diversity in approaches is more
| important than One Right Way. Some people need to set out on
| their own, while others spend decades refining one technique.
| Both have led to extraordinary results!
| shkkmo wrote:
| > I'm beginning to think that the best way to approach a
| problem is by either not being aware of or disregarding most of
| the similar efforts that came before.
|
| Extrapolating a "best way" from a couple of examples of success
| is bad reasoning. There are definitely ways in which it can be
| necessary to ignore the standing wisdom to make progress. There
| are also definitely ways in which being ignorant of the
| knowledge gained by past attempts can greatly impede progress.
|
| I would point out, that it is also possible to question and
| challenge the assumptions that prior approaches have made,
| without being ignorant of what those approaches tried.
|
| Figuring which is which, is indeed hard. Generally, it seems
| like it works well to have a majority of people
| expanding/refining prior work and a minority people going in
| and starting from scratch to figure out which of the current
| assumptions or beliefs can be productively challenge/dropped.
| The precises balance point is vague, but it seems pretty clear
| that going to far either direction harms the rate of progress.
| obelos wrote:
| I think you're forgetting to put "all the times ignorance
| didn't produce a breakthrough" in the denominator.
| causal wrote:
| Yeah. Classic base rate neglect.
| arcxi wrote:
| and compare it to all the times breakthrough is made by
| iteration
| ballenf wrote:
| That misses the point that there may be breakthroughs that
| are much harder or near impossible to make if you're familiar
| with the state-of-the-art.
| sangnoir wrote:
| What's the proportion to breakthroughs that are easier with
| familiarity? How many accidental discoverers do we need to
| match the output of a Terrance Tao or an Erdos?
| wnc3141 wrote:
| I advise anyone with a startup idea to just make a prototype
| you would like, then see if its reinventing the wheel. Repeat
| where necessary
| fmbb wrote:
| Also, making a good game is not a scientific breakthrough.
| There were great deck builders before.
| spacemadness wrote:
| Also there isn't anything that hasn't been done before
| either in Balatro, it's just a nice combination of deck
| builder tricks applied to poker. And the presentation is
| also well done which has nothing to do with the mechanics.
| abetusk wrote:
| I disagree.
|
| Many problems are abstract and so we have to build "cartoon"
| models of what's going on, trying to distill the essence of the
| problem down to a simple narrative for what the shape of the
| problem space is and where the limitations are. That often
| works but backfires when the cartoon is wrong or some
| assumptions are violated about when the cartoon description
| works.
|
| Results like this are pretty rare, nowadays, and I suspect this
| happened because the problem was niche enough or some new idea
| has had time to ferment that could be applied to this region.
| This seems like a pretty foundational result, so maybe I'm
| wrong about that for this case.
|
| A lot of progress is made when there's deeper knowledge about
| the problem space along with some maturity for when these
| cartoon descriptions are invalid.
| SideQuark wrote:
| Picking two examples out of all people approaching problems,
| while ignoring wasted effort and failures to make progress
| because of not understanding current knowledge, is an
| absolutely terrible reason to approach from ignorance.
|
| The biggest gains in theory and in practice are far more often
| obtained by masters of craft, giving much more weight to
| attacking problems from a position of knowledge.
|
| In fact, even in this case, this progress required that the
| author was aware of very recent results in computer science,
| was thinking deeply about them, and most likely was scouring
| the literature for pieces to help. The "Tiny Pointers" paper is
| mentioned directly.
| kbenson wrote:
| It's less that it's the best way to approach a problem, but
| that it optimizes for a different goal. Building on existing
| knowledge is how you find the local maxima for a problem by
| moving along the slop you have. Starting from scratch is how
| you find different slopes, which may lead to higher local
| maximas.
|
| Of course, if you happen to be on a slope that leads to the
| global maxima, starting from scratch is far less effective. We
| don't really know where we are usually, so there's a trade-off.
|
| There was a good article posted to HN years ago that covered
| this and used rocketry as one of the examples, but I don't
| recall what it was. The author was well known, IIRC.
| pjc50 wrote:
| I believe Ramanujan did the same with various maths problems.
| The Cambridge undergrad course sprinkles a few unsolved
| problems in the practice questions just in case someone does
| this again.
| chikere232 wrote:
| Last year's Advent of Code had a task that was NP complete and
| lacked good well known approximation algorithms. I almost gave
| up on it when I realised as that feels impossible
|
| In practice the data was well behaved enough and small enough
| that it was very doable.
| 77pt77 wrote:
| This is nothing but extreme selection/survivor bias.
| dinkumthinkum wrote:
| I get what you are saying but what if the amount of
| breakthroughs by people that did know about what came before
| was orders of magnitude higher than this number, would that
| change your mind?
| dataviz1000 wrote:
| A similar idea came up in Veritasium's latest video today.
| Training AI by DeepMind to predict protein folding greatly
| improved by withholding the most evident information about a
| protein's primary structure -- its linear polypeptide chain
| within the The Structure Model step. [0]
|
| After asking ChatGPT not to agree with me that your comment and
| these two different approaches to solving problems are the
| alike, it concluded there still might be similarities between
| the two.
|
| [0] https://youtu.be/P_fHJIYENdI?feature=shared&t=1030
|
| [1]
| https://chatgpt.com/share/67aa8340-e540-8004-8438-3200e0d4e8...
| ryao wrote:
| <deleted>
| j-scott wrote:
| I think this was meant as a reply to
| https://news.ycombinator.com/item?id=43004919
| dooglius wrote:
| It looks like the result only matters in the case where the hash
| table is close to full. But couldn't one just deal with this case
| by making the table size 10% bigger? (Or, if it is resizeable,
| resizing earlier)
| nhumrich wrote:
| Yes, which is what most real world hash tables do. They resize
| themselves once hash collision is too probable.
| quantum2022 wrote:
| This is neat! I always wondered if there would be a way to
| 'containerize' tables like this. IE a regular table is like a
| bulk carrier ship, with everything stuffed into it. If you could
| better organize it like a container ship, you could carry much
| more stuff more efficiently (and offload it faster too!)
| trebligdivad wrote:
| Anyone got a simple implementation of 'Tiny pointers'? My mind
| prefers code/pseudo-code first rather than the proof.
| zombiwoof wrote:
| Take that AI :)
| jimnotgym wrote:
| Now we have faster data structures we can fill that extra time by
| writing less efficient code, and loading more pointless
| libraries. This is the march of computer science.
| nickhodge wrote:
| I bet this guy would still fail a first round FAANG developer
| interview requiring a Hash Table solution to move on in the
| process.
|
| "Yeah, sorry. You didn't use the right Hash Table"
| ChrisMarshallNY wrote:
| As the villain in _Scooby Doo_ always said:
|
| _" And I would have gotten away with it, if it hadn't been for
| those meddling kids!"_
___________________________________________________________________
(page generated 2025-02-10 23:00 UTC)