Balanced trees

[Steven D'Aprano]

On Mon, 10 Mar 2014 08:16:43 +0200, Marko Rauhamaa wrote:

> Steven D'Aprano <steve+comp.lang.python at pearwood.info>:
> 
>> Proof: I create a hash table that accepts unsigned bytes as keys, where
> 
> The O(f(n)) notation has no meaning when n is limited.

It has obvious meaning: O(1) means that look-ups take constant time, not 
(for example) proportional to the number of keys in the table.


> This thing is not just pedantry. 

Yes it is. You're not even being pedantic for the sake of educating 
people and helping them learn. If that were the case, I would completely 
understand. Rather, it looks to me that you're being obnoxiously pedantic 
for the sake of trying to get attention. I think you are trolling. Take 
your comment that started this dispute:

    [responding to Dan Stromberg]
    > This is not just a detail: O(1) tends to be beat O(logn) 
    > pretty easily for large n.

    [to which your entire response was]
    There is no O(1) hash table.


As pedantry, it is an utter failure: it's *wrong*, for starters, but you 
didn't even make a pretence of trying to justify it. It's not 
educational, and it doesn't advance your argument in any way. And just 
*two posts later*, you acknowledged without apology or embarrassment that 
hash tables actually are O(1). So it seems that you didn't even believe 
your claim when you made it. This is why I think you are trolling.

All your comment accomplished was to wrongly contradict a well-
established and often-repeated fact that hash tables are usually O(1):

https://duckduckgo.com/html/?q=big+oh+hash+tables

which is great if your aim is to trick people into giving you attention 
(as I suppose I am giving you attention now) but useless for advancing 
the debate or educating people.

It is as if you had declared "Actually the Allies had lost World War 
Two", and then tried to justify such a ridiculously false statement on 
the basis that while they didn't actually *lose* according to the 
normally accepted meaning of the word, some of the Allies may have failed 
to accomplish every single one of their objectives in the war.


> The discussion was how a balanced tree
> fares in comparison with hash tables. A simplistic O(1) vs O(log n) was
> presented as a proof that balanced trees don't have a chance in practice
> or theory. I wasn't so easily convinced.

If you had wanted to put the case for balanced trees, you could mention 
that in practice they perform comparably to hash tables for reasonable 
sizes of data, and may require less memory. You could have made an 
attempt to teach people about the difference between O and Ω complexity, 
the difference between best case, worst case, average case, and typical 
behaviour. You could have mentioned the difference between amortized and 
non-amortized behaviour, or go into detail about the various assumptions 
made when doing Big Oh analysis (e.g. that all "simple" operations take 
constant time, which is not strictly speaking true).

Any of these things would have helped people understand your position 
better. But you did *none* of these things. It seems to me that your 
stated position is actually irrelevant to you, what you want is not 
better data structures in Python, but for people to respond to your posts.

In other words, I suspect you are trolling.

If I am right, that certainly would explain your apparent inability to 
understand the difference between "is" and == operators, your insistence 
that object IDs are addresses, and your declaration that object identity 
is philosophically untenable.



-- 
Steven D'Aprano
http://import-that.dreamwidth.org/