save dictionary to a file without brackets.

[Steven D'Aprano]

O(n) for all other entries in the dict which suffer a hash collision
with the searched entry.

True, a sensible choice of hash function will reduce n to 1 in common
cases, but it becomes an important consideration for larger datasets.

I'm glad you're wrong for CPython's dictionaries. The only time the
lookup would degenerate to O[n] would be if the hash table had only one
slot. CPython sensibly increases the hash table size when it becomes
too small for efficiency.

Where have you seen dictionaries so poorly implemented?

In vanilla CPython up to version (I think) 3.3, where it's possible to
DoS the hash generator. Hash collisions are always possible, just
ridiculously unlikely unless deliberately exploited.

Not so unlikely actually.

py> hash(3)
3
py> hash(2**64 + 2)
3

py> hash(-1)
-2
py> hash(-2)
-2


By its very nature, a hash function cannot fail to have collisions. The
problem is that in general you have an essentially unlimited number of
objects being mapped to a large but still finite number of hash values.

 

[88888 Dihedral]

Steven D'Apranoæ–¼ 2012å¹´8月11日星期六UTC+8下åˆ7時26分37秒寫é“：

On 08/09/2012 06:03 PM, Andrew Cooper wrote:
O(n) for all other entries in the dict which suffer a hash collision
with the searched entry.

True, a sensible choice of hash function will reduce n to 1 in common
cases, but it becomes an important consideration for larger datasets.

I'm glad you're wrong for CPython's dictionaries. The only time the
lookup would degenerate to O[n] would be if the hash table had only one
slot. CPython sensibly increases the hash table size when it becomes
too small for efficiency.

Where have you seen dictionaries so poorly implemented?

In vanilla CPython up to version (I think) 3.3, where it's possible to

DoS the hash generator. Hash collisions are always possible, just

ridiculously unlikely unless deliberately exploited.

Not so unlikely actually.



py> hash(3)

3

py> hash(2**64 + 2)

3



py> hash(-1)

-2

py> hash(-2)

-2





By its very nature, a hash function cannot fail to have collisions. The

problem is that in general you have an essentially unlimited number of

objects being mapped to a large but still finite number of hash values.

Steven D'Apranoæ–¼ 2012å¹´8月11日星期六UTC+8下åˆ7時26分37秒寫é“：

On 08/09/2012 06:03 PM, Andrew Cooper wrote:
O(n) for all other entries in the dict which suffer a hash collision
with the searched entry.

True, a sensible choice of hash function will reduce n to 1 in common
cases, but it becomes an important consideration for larger datasets.

I'm glad you're wrong for CPython's dictionaries. The only time the
lookup would degenerate to O[n] would be if the hash table had only one
slot. CPython sensibly increases the hash table size when it becomes
too small for efficiency.

Where have you seen dictionaries so poorly implemented?

In vanilla CPython up to version (I think) 3.3, where it's possible to

DoS the hash generator. Hash collisions are always possible, just

ridiculously unlikely unless deliberately exploited.

Not so unlikely actually.



py> hash(3)

3

py> hash(2**64 + 2)

3



py> hash(-1)

-2

py> hash(-2)

-2





By its very nature, a hash function cannot fail to have collisions. The

problem is that in general you have an essentially unlimited number of

objects being mapped to a large but still finite number of hash values.

Lets check the basic operations of a hash table or so-called a dictionary first.

If the dictionary is implemented toward faster in searching items,
then it is slightly different in the insertion and the deletion operations of
(key, value) pairs.

 

[alex23]

Well whatever you do *DON'T* mention Cython. I mentioned it just now but
I think I've got away with it.

While I'm not against threads straying off topic, you're beginning to
come across as a bit of an asshole now.

Just let it go.

 

[Steven D'Aprano]

While I'm not against threads straying off topic, you're beginning to
come across as a bit of an asshole now.

Just let it go.

Chill out Alex, it's all good. Mark was channelling a famous scene from
"Fawlty Towers", staring Monty Python's own John Cleese, hence it is on-
topic, for the sillier definitions of on-topic.

After making a German tourist cry with his repeated insensitive comments
about World War Two, Basil Fawlty (Cleese) -- who is an obnoxious git at
the best of times but is currently suffering from a concussion -- remarks
to his staff, "Don't mention the war, I mentioned it once but I think I
got away with it."

 

[rusi]

Chill out Alex, it's all good. Mark was channelling a famous scene from
"Fawlty Towers", staring Monty Python's own John Cleese, hence it is on-
topic, for the sillier definitions of on-topic.

Ha! Thanks for that connection.
Watched and enjoyed Fawlty towers as a kid but have never seen a Monty
Python.

 

[alex23]

Why on your say so?

My mistake, I didn't realise you wanted to sound so tedious. Knock
yourself out.

 

[alex23]

Chill out Alex, it's all good. Mark was channelling a famous scene from
"Fawlty Towers", staring Monty Python's own John Cleese, hence it is on-
topic, for the sillier definitions of on-topic.

Thank you, yes, I get that. However, Mark has repeatedly been
directing this dickishness at Stefan Behnel ever since he was asked to
not stray off topic. While Mark doesn't have to listen to anyone else
about his behaviour, he can't expect not to be called a dick when
acting like one.

 

[Mark Lawrence]

My mistake, I didn't realise you wanted to sound so tedious. Knock
yourself out.

Yes m'lud. Do I lick your boots or polish them?

 

[alex23]

http://mail.python.org/pipermail/pypy-dev/2012-February/009277.html

Yeah, you're really coming across as holding the moral high ground
here.

Plonk.

 

[Steven D'Aprano]

Yes m'lud. Do I lick your boots or polish them?

Children children, if you won't play nice don't play at all. You're
scaring away the people who are here to learn about Python.

 

[Mark Lawrence]

Children children, if you won't play nice don't play at all. You're
scaring away the people who are here to learn about Python.

Steven thanks for your comments, seriously for once, you've helped get
my feet back on the ground where they belong.

Everybody please accept my apologies for having gone OTT once again
In my defence for mitigating circumstances I offer a combination of
Asperger Syndrome and a new girl friend.