Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster Than Dijkstra?

systemsapproach.org

Post reply on HN
Print view View original

81–90 of 90 posts

Re: Faster Than Dijkstra?

#81

Post by hiimkeks »

chowells wrote: post #74
fsckboy wrote: post #72

Earlier quoted context omitted.

> logs don't matter. O(log(n)) and O(1) are effectively the same thing. ever heard of a hashtable? that's because O(c) is better than O(log(N)). if they were the same, you would only have heard of binary search.

Please explain to me how you can hash n distinct strings into O(n) buckets in O(1) time. Please note that this process needs to work as n goes to infinity . Hash tables are O(log n) structures when you don't hand-wave away the "compute a hash" part. The thing is, search trees are far worse than that in practice and you aren't hand-waving away the "compare two elements" part. That's where the real speed savings come f…

What I think you are saying is that computing the hash needs to process the entire string, and the length of that string roughly corresponds to log n, therefore it's O(log n). Not sure I am entirely convinced by that reasoning, but let's roll with it for now.

Because if you apply it to binary search, you need to compare the strings at every step, and by that logic, each of these operations is O(log n), which means your binary search is now O(log^2 n).

I guess the crux is that we are still comparing apples to oranges (or multiplication operations to comparison operations), and at the end what probably makes hashing faster is that we are not branching.

Still I don't think it makes sense to think of both hash tables and binary search as O(log n).

Re: Faster Than Dijkstra?

#82

Post by layer8 »

thfuran wrote: post #75
layer8 wrote: post #71

Earlier quoted context omitted.

> Already, we have a factor of O(log(n)) here. Doesn’t that mean that O(log(n)) is really O(log²(n))?

You have to define what n is.

It’s clear from the parent comment that the number of bits needed to represent the input is meant here.

Re: Faster Than Dijkstra?

#83

Post by charleslmunger »

hinkley wrote: post #33
vprcic wrote: post #17

Each time a discussion about sorting starts, I'm reminded of a "lively debate" I had with my boss/friend about the most optimal sorting approach. He claimed it's O(n) pointing to counting sort as an example. This didn't sit well with me. A sorting algorithm, I insisted, should be defined something like "a function taking an unsorted array of elements and returning a sorted one". But it seems there is no agreed upon d…

I can’t think of a single time I’ve needed a sorted list of only numbers. It’s always numbers and something else, like names or dates. Maybe for median calculations, but I don’t even use those that much either. Especially in telemetry, where mean is easy and median is not.

You have a list of IDs, and want to make them compact for storage or transport - fast and simple way is to sort and delta encode.

Re: Faster Than Dijkstra?

#84

Post by justinhj »

shoo wrote: post #54

The underlying argument this article seems to be making is that an appropriate algorithm for any given application isn't always the one with the most efficient asymptotic performance for sufficiently large n -- for a given application (in this case routing), we have data on typical values of n that appear in reality and we can choose an algorithm that offers good enough (or optimal) performance for n in that constrai…

All of Knuth's Art of Computer Programming covers this too.

Re: Faster Than Dijkstra?

#85

Post by hinkley »

krackers wrote: post #59
hinkley wrote: post #58

Graph Theory and AI have been forever linked because it turns out the human brain is ridiculously good at finding a path through a graph that is somewhere in the neighborhood of 97% optimal, and we can do it in minutes while a computer would take weeks or until the heat death of the universe to do it better. It's vexatious how good we are at it, and it's exactly the sort of problem that Science likes. We know it's tr…

>while a computer would take weeks or until the heat death of the universe to do it better. I don't buy this, approximation algorithms are an entire field of CS, if you're OK with an approximate solution I'm sure computers could do that quickly as well.

Approximations are often good enough, and even annealing tended to give you a better answer if you were willing to wait. Exhaustive search is NP. But part of TSP is that once you have a good answer, you can backtrack on a larger number of bad ones. So there is value to doing both.

And for some geometries, Djikstra and friends give you bounds on what the shortest path can be, within a factor of two, so you can start to carve out the problem space even before you’ve found a decent one.

Re: Faster Than Dijkstra?

#86

Post by hinkley »

lscharen wrote: post #50
pvillano wrote: post #40

Earlier quoted context omitted.

To be pedantic, median is cheaper than sorting. O(n) with a quicksort-like algorithm. Also, if you're taking an average of floating point numbers, you might want to sort it first and add from smallest to largest, to better preserve precision

An aside, but I recently learned -- if one is willing to use a very modest amount of memory -- summing floating-point numbers with no loss of precision is effectively a solved problem with the XSUM algorithm. https://glizen.com/radfordneal/ftp/xsum.pdf

That’s great for mean, but you don’t need to sort for mean.

Re: Faster Than Dijkstra?

#87

Post by hinkley »

charleslmunger wrote: post #83
hinkley wrote: post #33

Earlier quoted context omitted.

I can’t think of a single time I’ve needed a sorted list of only numbers. It’s always numbers and something else, like names or dates. Maybe for median calculations, but I don’t even use those that much either. Especially in telemetry, where mean is easy and median is not.

You have a list of IDs, and want to make them compact for storage or transport - fast and simple way is to sort and delta encode.

Hmm. That’s fair, though I’d probably use set operations instead. What you find though is that for most other problems besides diffing, ID order is not chronological order, so you need to sort by a date stamp instead. But I’m typically letting the database do that, so I’m a consumer of sorted numbers, but not an implementor. Because what I sort is nearly always compound sorts. By field A, then field B and field C if those two still don’t cut it.

Re: Faster Than Dijkstra?

#88

Post by hinkley »

vlovich123 wrote: post #42
hinkley wrote: post #33

Earlier quoted context omitted.

I can’t think of a single time I’ve needed a sorted list of only numbers. It’s always numbers and something else, like names or dates. Maybe for median calculations, but I don’t even use those that much either. Especially in telemetry, where mean is easy and median is not.

If the primary key is the number, it still works (and dates are just numbers by the way) because you can sort a heterogenous dataset by a single numeric key pretty trivially. But sorting by arbitrary strings like names can’t avoid comparison sort.

That data structure isn’t an array of numbers, it’s an array of pointers to objects.

Re: Faster Than Dijkstra?

#89

Post by tpoacher »

pelcg wrote: post #57
tpoacher wrote: post #22

Earlier quoted context omitted.

You reminded me of "Sleep Sort" [0] [0] https://news.ycombinator.com/item?id=2657277

Don't know about if Sleep Sort even is a valid sorting algorithm? Is this even real?

it's real (in that it works) but obviously it's a programming joke rather than anything anyone would ever use in a real system.

Re: Faster Than Dijkstra?

#90

Post by GuB-42 »

fsckboy wrote: post #72
GuB-42 wrote: post #65

Earlier quoted context omitted.

I came to realize that logs don't matter. O(log(n)) and O(1) are effectively the same thing. The reason is that real computers have memory, accessing memory takes time, and bigger n needs more memory, simply to store the bits that represent the number. Already, we have a factor of O(log(n)) here. But also each bit of memory takes physical space, we live in a 3D world, so, best case, on average, the distance to a memo…

> logs don't matter. O(log(n)) and O(1) are effectively the same thing. ever heard of a hashtable? that's because O(c) is better than O(log(N)). if they were the same, you would only have heard of binary search.

Hash tables are indeed O(1) in theory while binary search is O(log(N)) in theory, no problem with that.

But in practice, accessing a physical memory cell is not O(1), it is O(cuberoot(N)).

For a binary search, you need O(log(N)) operation, but each operation (accessing a memory cell) is O(cuberoot(N')) where N' is the number of elements up to the level of the tree you are at, ending at N for the last iteration. So that's O(sum(0, log(N), cuberoot(N/exp(n))), which simplifies to O(cuberoot(N)), exactly the same!

In real practice, the choice of binary search vs hash table depends on considerations like cache behavior. Hybrid methods combining hash tables with hierarchical data structures are often used when N is large. But that's my point, you won't choose a hash table over a binary search because one is O(1) and the other is O(log(n)), you chose one over the other because of how it fits your hardware architecture.

Contrast with, say, O(n.log(n)) over O(n^2). When n is large, barring space-time tradeoffs, you should always pick the O(n.log(n)) algorithm, because the reduction in complexity will always beat any sane hardware considerations.

Post reply on HN