Comments URL: https://news.ycombinator.com/item?id=8991535

Points: 3

# Comments: 0

And yes, of course, at some point, constant factors break into applications. Would it be better if add in a short comment on "practically O(1) for non-HPC applications", or would you phrase it differently to give it better context?

And this is the problem. As you yourself say, most programmers usually associate/assume "Big-O notation is intended to describe how the time required for an operation grows as the number of items being handled gets large".

But formally, this is not the case at all. O(g(x)) tells you the that the worst case input to the algorithm will require less operations (usually operations, sometimes memory or other things) than the function g multiplied by some positive constant. g is usually determined by the size of the input. (This definition is also simplified somewhat, but it illustrates the problem)

We can say that ArrayLists.add have O(n) runtime and that quicksort have O(n²) runtime, but they both also have O(n³) and O(n!) runtime.

In addition, Big-O does not describe how the algorithm runs in the average case, or how frequent the worst case is. In and of itself, the Big-O notation tells us almost nothing about an algorithm – you barely conclude anything from it. I guess that is part of why it has become this very simplified term with a very wibbly-wobbly definition from time to time.

So when you're saying that calling it "practically O(1)" is lying, I agree if this was in an academic context. But for the average programmer (regardless of language!), O(g(x)) is usually thought of as the "worst case runtime for an algorithm". Since the actual runtime is – well – effectively constant, I considered it okay.

---

That being said, I have formally explained the persistent vector if you're interested in the academic version. The background chapter in http://hypirion.com/thesis.pdf should cover it.

Comments URL: https://news.ycombinator.com/item?id=8260329

Points: 15

# Comments: 1

I can always sort a 32-bit int array in worst case linear time using counting sort, which in theory is better than the worst case runtime of quicksort, O(n²). Is it better in practise? Of course not, the constant factor is just too high, both for time and memory.

However, it's false that Clojure doesn't have a company behind it: Cognitect is certainly backing up Clojure by developing ClojureScript and Clojure itself, Clojure consulting, the Datomic database and the Pedestal "framework".

    And if you ask me, its just so good that we haven't needed a revision in 20 years.

Comments URL: https://news.ycombinator.com/item?id=6968545

Points: 4

# Comments: 0

Ordering for free is valuable, I guess, but it sort of depends on the situation. Sometimes face cards are worth 10, other times they are worth 11, 12, 13. If you use val King = 10;, then it suddenly is impossible to distinguish between face cards and tens.

> Rich goes through this in one of his talks but I don't recall which.

If you figure out which, I'd love to know! :)

If you have a reference to a paper explaining something similar (or the actual implementation), I'd love to put it in the post for others.

Comments URL: https://news.ycombinator.com/item?id=6269125

Points: 2

# Comments: 0

[1]: http://www.youtube.com/watch?v=cidchWg74Y4

  (->> (string/split s #"\s+")
       frequencies
       (sort-by val >)
       (take 10))

Generics may not be the correct solution, but I would really like a way to make collections which are general enough to be used by any datatype. As of now, I cannot do that without doing the typical `interface{}` approach.

The built-in data structures + channels are able to handle this, but if I just want a set of elements, what do I do? Make a `map[foo] bool`? If I see such a piece of code in an unfamiliar code base, I have no idea whether to test for key existence or whether I have to test whether the bool is true. A generic set would leave me puzzled and type unsafe[1]: What types could possibly exist in this set? A set of foos is not that hard to comprehend, and is in fact very much more straightforward to understand than a generic set, which in unfamiliar code may contain anything, or a mapping from foos to bools.

[1]: Rob Pike mentions in http://www.youtube.com/watch?feature=player_detailpage&v... that type safety is of high importance for Golang, but how does one achieve that if all the different datatypes I implement/need use `interface {}` where I have to cast all values afterwards? That seems very type unsafe, from where I stand.

Whereas you have to host a Minecraft server yourself (or host a world on a LAN) in order to play multiplayer, Skycraft doesn't require you to do that. All you have to do is share a link with your friends. In addition, you can "[i]nvite anyone to fly or walk around in your world in spectator-mode", which I optimistically intepret as "walk around in my world without buying the game". (Of course, that's my take on it.)