Thread 512933711

>Chinese scientists have developed the best shortest-path algorithm in 41 years! A team from Tsinghua University has broken Dijkstra’s “sorting barrier” — the first improvement since 1984.
I thought chinese science and math breakthroughs were all fake? What now /pol/?: https://x.com/lukOlejnik/status/1955204273421128155?
arxiv.org/pdf/2504.17033

Chink names sound so retarded LMAO
>Tsinghua
>Pinglang
>Zuechong

>>512933711 (OP)
i bet it would use 10-100x more processing power to run in a realtime application though. for example a game couldnt handle it

>>512933711 (OP)
good luck compiling that branching garbage

>>512933782
you dont even have a language you mutt

euromutt

>>512933782
You have one of those funny continental flags so there is a high likelihood your country has some gay teutonic bullshit in your phone books.

and Yugoslavia made the first truly operational railgun and a really good magnetohydrodynamic generator
but both were uneconomical to use
same with this algorithm, minimal gains for massive coding challenge

>>512933711 (OP)
The earth is inherited by the intelligent, and the rest of us are just slaves

>>512933782
Bitch please. The end credits of a Belgian movie read like a French AI trying to make up silly Dutch names from 1850.

>>512934546
psychopathic subhumans are not succesful because they're intelligent, they're mindless predators who can't control their primitive nature who got lucky most humans are exploitable npc cattle. If more humans were autistic they'd be extinct like their Neanderthal ancestors

>>512934014
Gayms use A*

>>512934450
>minimal gain
This could save some companies more than the wages of every person in this thread combined even if we were all multi-millionaires.
This is no "minimal" anything.

Nethack uses dijkstra
So I will continue to use it

>>512933711 (OP)
>chinkazoid cope thread #18264846947
My broke ass country sends charity money to you fish eye'd rice monkeys. We sent you millions this year alone because you can't take care of yourselves. Give me a call when you filthy little subhumans don't need my charity, until then you monkeys need to remember that you were thoroughly inbred cave-dwelling niggers when my ancestors found you and taught you how to make the wheel. Never forget that you are a nigger-tier animal that couldn't invent the wheel, you dirty little piss monkey, now take my charity and fuck off.

>>512933782
True. Their names are almost as retarded as their potato-like faces with their weird round heads and tiny little dysgenic bodies. What a weird pathetic little monkey race of inbred riceniggers.

>>512934942
you assume that changing existing software infrastructure is just a little github commit and boom, it works

>>512934014
This might be the most retarded take I've ever seen on this site

>>512934450
China are the only people with a genuinely functional railgun.

This flowering of technological, artistic and scholarly excellence is what you'd expect of the next global hegemon now the US has decided to become a purely regional power.

>>512935418
>China are the only people with a genuinely functional railgun.
well, I welcome China to 1988 Yugoslavia, then

>>512933711 (OP)
https://arxiv.org/abs/2504.17033

>>512933711 (OP)
https://www.quantamagazine.org/new-method-is-the-fastest-way-to-find-the-best-routes-20250806/

https://news.ycombinator.com/item?id=44812695

seems to be an impressive (yet conditional / YMMV) improvement

>>512935461
>>512934450
I thought the main problem of rail guns were not the cost but rather that their performance is not worth the hassle of having to "recharge" and "cooling" the gun every shot, just to hit a target barely 100-200km away, and in less than a hundred shots you'd need to replace the barrel. When missiles can reach 500-2000km easily, are actually guided and you could fire them one after the other until your missile battery or ship runs out of missiles.

>>512935340
You’re right for the wrong reason. It needs the instruction set to handle this. If they don’t exist yet, this needs to be handled in software which is less efficient. This is how all progress goes. Something is created, we want to do it on computer, no opcodes to handle some part of the algorithm (like new and exotic math), try to work it out with the instruction set you’ve got, fail, do it in software. If you’re old enough you’ll remember software frame rendering before GPUs because older CPUs lacked an FPU and even if you installed co-processor, it might not have the instructions to do that task efficiently either and so you wait for the hardware to be developed that CAN do it efficiently (GPUs). But now we’ve got GPGPU and it’s kind of a silver bullet for shit like this.

>>512936150
Which line of pseudo in OP is not possible on X86 retard

>>512933782
unlike belgian names like Ahmed, Mustafa and Moziekial

>>512935340
>This might be the most retarded take I've ever seen on this site
why? djikstra's algorithm is used in games and the paper says it solved a problem with djikstra's algorithm

>>512933711 (OP)
Here come 300 cope posts about how China will collapse in two more weeks

>>512933711 (OP)
>your node pathways can be faste
>but its only faster if you completely reset your entire infrastructure to work for it
wow, so nothing

>>512936547
If the time complexity is better than dijkstra then it is more efficient period. Even if the implementation ends up being more complex. Why would a more efficient algorithm take 10-100x more processing power?

>>512937145
>If the time complexity is better than dijkstra then it is more efficient period.

In practice, this depends on how big N is.
Time complexity is about the asymptotic complexity of the algorithm.
Sometimes, theoretically worse algorithms can perform better at the scale you need to use them, if they can be implemented more efficiently (to better exploit sequential memory access, caching, etc.)

>>512936329
The fuck should I know. I’m an engineer not a mathematician. But I suppose you are phds in both fields like every Redditor

>>512936150
The whole point of an algorithm is that it uses standart operations. The whole field of numerical analysis puts restrictions on its mathematical basis so algorithms are compatible with computing.

>>512933782
>Djikstra

>>512937380
I have a degree in compsci so dont try to tell me im "right for the wrong reasons" lmao. Why would you make so many assumptions about shit you have no idea about?

>>512935340
He's probably right, especially considering it's from China and therefore probably fake.
The thing about big O notation is that it ONLY measures how the algorithm scales up, but it does not measure the "base" cost of the algorithm.
There are many cases where an O(n^2) algorithm is more efficient to use than an O(n*log(n)) because the quadratic algorithm is very cheap, i.e. the "O" in the quadratic equation is like 1k ops, while the other "more efficient" linearithmic algorithm is some bullshit like 200k ops. In that case, you can go all the way up to n=500-something, and the "less efficient" quadratic algorithm will still be more efficient to run.
This shit comes up constantly with AI, where e.g. Transformer's self-attention mechanism is famously quadratic. There are papers coming out of China every month where they claim to have discovered an algorithm that accomplishes the same thing at vastly lower time complexity, and they're usually technically right, but in real-world use cases they always turn out to be unusable garbage.

>>512937309
True but rare and would have to be a specific use. In general, for the post I replied to referring to games, N IS large and better time complexity is not going to have a negative performance impact

>>512937587
The pseduocode in OP doesn't look that more complex than djikstra, but i haven't read the paper yet. Also >>512937643

>>512935200
If it is exactly the same call then yes, yes it is that simple.
If proven to work in every scenario, all boundaries and weird edge cases, it's trivial to drop it in place.
This is not some fucking giga complicated function with various dependencies and shitty fucking React-tier babbycode, it's a singular function.

A simple A/B test of replacing some of it with the new code will quickly demonstrate its usefulness over a year of use before full deploy.

>>512933711 (OP)
Chinese are actually Hindus.

>>512935710
>quantamagazine
Owned by pajeets

>>512933711 (OP)
China is the future of humanity.

>>512934014
You're out of your depth, my dude.

>>512936657
you see I don't mind this type of grooming
keep your hands off until she's 16 though Chang

>>512933782
To be honest, the western transliterration do a shit job in catching the sound of chinese languages.

>>512935340
There was some anon (Romania flag, iirc) claiming that heavily abstract scientific fields like cosmology, theoretical physics, pure mathematics were useless scams.

>>512934887
A* is basically Dijkstra's with an estimation function.
Dijkstra's is basically A* where the estimation function is 0.
Fun facts:
A* with perfect estimation runs in almost O(k), where k is the length of the path and k < n.
You can't achieve that, but the closer the estimation is, the faster it runs, however the estimation must be lower than the actual path.
If the estimation is higher, you don't get the minimum path anymore, but still decent less optimized ones, however it takes way less time to compute.

>>512933711 (OP)
Dijkstra's algorithm is general
this one only operates on a set of graphs with the property that
>for every incomplete vertex x with d(x)

I hate chinese so fucking much it's unreal

why post this shit on pol
the average poltard doesn't understand any of these words

>>512943299
it's quite simple, anon
Dijkstra found a way to solve a big problem set in reasonable time
chinks found a way to solve a subset of those problems faster
now they're crowing about it like the subhuman liars they are

>>512943299
It's true, the average poltard is a glownigger diversity hire, of course they don't have the brainpower for it.

>>512937731
>>512937587
>>512936657
>>512943487
>>512933711 (OP)
This is 3 month old news

Reddit already deboonked it see it here:

https://www.reddit.com/r/programming/comments/1kxedmp/new_algorithm_beats_dijkstras_time_for_shortest/?sort=top