On Mon, 10 Mar 2014 08:16:43 +0200, Marko Rauhamaa wrote:
> Steven D'Aprano <steve+comp.lang.pyt...@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/
--
https://mail.python.org/mailman/listinfo/python-list
