Login | Register For Free | Help
Search for: (Advanced)

Mailing List Archive: Python: Bugs

[issue15503] concatenating string in dict unexpected performance

 

 

Python bugs RSS feed   Index | Next | Previous | View Threaded


report at bugs

Jul 30, 2012, 7:20 AM

Post #1 of 4 (80 views)
Permalink
[issue15503] concatenating string in dict unexpected performance

New submission from Petri Heinilä:

In concatenating string in dict somehow radically depends the added string size.

code

----
import timeit

s1 = """
text = ""
for i in range(1,50000):
text += "12345678901234567890"
"""
print("str cat 20: {0}s".format(timeit.timeit(s1,number=1)))

s2 = """
d = dict()
d["text"] = ""
for i in range(1,50000):
d["text"] += "12345"
"""
print("dict cat 5: {0}s".format(timeit.timeit(s2,number=1)))

s3 = """
d = dict()
d["text"] = ""
for i in range(1,50000):
d["text"] += "1234567890"
"""
print("dict cat 10: {0}s".format(timeit.timeit(s3,number=1)))


s4 = """
d = dict()
d["text"] = ""
for i in range(1,50000):
d["text"] += "12345678901234567890"
"""
print("dict cat 20: {0}s".format(timeit.timeit(s4,number=1)))

----

gives:

str cat 20: 0.011670112609863281s
dict cat 5: 2.994051933288574s
dict cat 10: 6.61974310874939s
dict cat 20: 34.230541944503784s

----------
assignee: collinwinter
components: Benchmarks
files: string_cat.py
messages: 166901
nosy: collinwinter, hevi
priority: normal
severity: normal
status: open
title: concatenating string in dict unexpected performance
type: performance
versions: Python 3.2
Added file: http://bugs.python.org/file26603/string_cat.py

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue15503>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Jul 30, 2012, 7:51 AM

Post #2 of 4 (79 views)
Permalink
[issue15503] concatenating string in dict unexpected performance [In reply to]

Alex Gaynor added the comment:

Actually, I would argue that it's concatentation of a local variable which has unexpected performance. Logically it should be O(n**2), however due to hacks in CPython it isn't.

----------
nosy: +alex

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue15503>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Jul 30, 2012, 7:57 AM

Post #3 of 4 (79 views)
Permalink
[issue15503] concatenating string in dict unexpected performance [In reply to]

Serhiy Storchaka added the comment:

Yes, the total time of repeated string concatenation is O(N**2). s3 is twice larger s2, therefore s3 time about twice large s2 time.

In the first case Python use a special optimization which allows O(N) in some cases. You can deactivate it:

s5 = """
text = ""
for i in range(1,50000):
text2 = text
text += "12345678901234567890"
"""
print("str cat 20: {0}s".format(timeit.timeit(s5,number=1)))

It's not a bug, it's feature.

----------
nosy: +storchaka

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue15503>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com


report at bugs

Jul 30, 2012, 8:14 AM

Post #4 of 4 (83 views)
Permalink
[issue15503] concatenating string in dict unexpected performance [In reply to]

Antoine Pitrou added the comment:

It's a FAQ entry:
http://docs.python.org/dev/faq/programming.html#what-is-the-most-efficient-way-to-concatenate-many-strings-together

----------
nosy: +pitrou
resolution: -> wont fix
status: open -> closed

_______________________________________
Python tracker <report [at] bugs>
<http://bugs.python.org/issue15503>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/list-python-bugs%40lists.gossamer-threads.com

Python bugs RSS feed   Index | Next | Previous | View Threaded
 
 


Interested in having your list archived? Contact Gossamer Threads
 
  Web Applications & Managed Hosting Powered by Gossamer Threads Inc.