Συζήτηση
Γεια χαρά, Επισκέπτης
Όνομα χρήστη: Κωδικός: Να με θυμάσαι

ΘΕΜΑ: string concatenation και ταχύτητα εκτέλεσης

string concatenation και ταχύτητα εκτέλεσης 13 Χρόνια 4 Μήνες πριν #1007

  • mgiannakidis
  • Το Άβαταρ του/της mgiannakidis
  • Αποσυνδεμένος
  • p_____
  • Δημοσιεύσεις: 3
Γεια σας,

Σήμερα, καθώς δοκίμαζα πως συμπεριφέρεται η Python όταν κάνεις concatenate strings, παρατήρησα κάποια πράγματα. Έστω το εξής πρόγραμμα:
#!/usr/bin/env python
 
s = ''
l = '00000000000000000000000000000000000000000000000000000000000000000000000000000000'
for i in range(0, 100000):
	s = s + (l + '\n')
 

και ρίξτε μια ματιά εδώ:
wiki.python.org/moin/PythonSpeed/Perform...#StringConcatenation

Το παραπάνω πρόγραμμα (δεν ακολουθεί τα tips) τρέχει πολύ γρήγορα σε Python 2.6.1 και 2.5.x.

Αν αλλάξεις το s = s + (l + '\n') σε s += l + '\n' πάει και πάλι πολύ γρήγορα. Αλλά, αν το κάνεις
s = s + l + '\n'
τότε πάει απελπιστικά αργά.

Υποθέτω πως οι γρήγορες περιπτώσεις είναι γιατί η Python κάνει κάποια optimizations και καταλήγει σε κάτι όπως s +=new_s. Αυτό δε, είναι γρήγορο και αν το γράψεις σε άλλη γλώσσα, πχ C++, για ευνόητους λόγους.

Η πρώτη ερώτηση είναι: γιατί το s = s + l + '\n' δεν μπορεί να το κάνει η γλώσσα να τρέξει τόσο γρήγορα όσο τις παραλλαγές του; Μπορεί να είναι bug που αξίζει να αναφερθεί;

Η δεύτερη ερώτηση: Δοκιμάζοντας τα παραπάνω σε Python3, είδα 7πλασιασμό του χρόνου στις γρήγορες παραλλαγές. Που οφείλετε αυτό; Είναι γενικά η python3 πιο αργή; Δυστυχώς δεν έχω python3 πρόχειρη για να δώσω χρόνους.

Μιχάλης
Τελευταία διόρθωση: 13 Χρόνια 3 Μήνες πριν από pmav99.
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Απ: Απορία για string concatenation και θέμα ταχύτητας 13 Χρόνια 3 Μήνες πριν #1010

  • myle
  • Το Άβαταρ του/της myle
  • Αποσυνδεμένος
  • Admin
  • Δημοσιεύσεις: 467
  • Ληφθείσες Ευχαριστίες 15
O γρηγορότερος τρόπος για να κάνεις concatenate είναι μέσω join πάνω σε μια λίστα από τα strings.

Ο λόγος που οι άλλοι τρόποι είναι αργοί είναι επειδή ο τα strings είναι immutable, το οποίο σημαίνει s_1 + s_2 απαιτεί την δημιουργία ενός τρίτου string s_3 που παίρνει χρόνο O(s_1 + s_2) αντί για τον χρόνο O(1) που θα περίμενε κάποιος χρησιμοποιώντας pointers σε μια γλώσσα όπως C/C++.

Πώς είναι υλοποιημένος ο κώδικας από κάτω δε γνωρίζω. H Python 3 είναι όντως πιο αργή προς το παρόν.
«Αν υποθέσουμε ότι αυτό είναι δυνατό, (να μεταδώσουμε τη σοφία παντού) τότε ειλικρινά ο τρόπος ζωής των θεών θα περάσει στους ανθρώπους. Τα πάντα θα είναι γεμάτα...
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Απ: Απορία για string concatenation και θέμα ταχύτητας 13 Χρόνια 1 Μήνας πριν #1291

  • pmav99
  • Το Άβαταρ του/της pmav99
  • Αποσυνδεμένος
  • Author
  • Δημοσιεύσεις: 684
  • Ληφθείσες Ευχαριστίες 111
Κοιτώντας ΑΥΤΗ τη σελίδα (η οποία με τη σειρά της παραπέμπει ΕΔΩ), είπα να το δοκιμάσω και εγώ.

Υλοποίησα και τις υπόλοιπες μεθόδους που αναφέρονται στο δεύτερο link αλλά ο χρόνος είναι σημαντικά αυξημένος και για αυτό δεν τον μεταφέρω εδώ.

Καθώς μας ενδιαφέρει ο χρόνος του string concatenation, μετέφερα τη δημιουργία της λίστας με τα strings εκτός της συνάρτησης.

Σε python 2, αν το BIG_NUMBER γίνει πολύ μεγάλο, ίσως να μην τρέχει ο κώδικας, γιατι η range θα τελειώνει τη διαθέσιμη μνήμη. If that's the case, αντικαταστήστε τη με την xrange.
import cProfile
 
BIG_NUMBER = 1000000
 
a = ["o" for i in range(BIG_NUMBER)]
 
def string_join(a):
    return "".join(a)
 
def append_string(a):
    text = ""
    for word in a:
        text += word
    return text
 
cProfile.run("string_join(a)")
cProfile.run("append_string(a)")
Αποτελέσματα για Python 2.7
ΒIG NUMBER    : 1000000 / 100000000 
string_join   :   0.022 /     2.235
append_string :   0.101 /     9.000
Αποτελέσματα για Python 3.2
ΒIG NUMBER    : 1000000 / 100000000 
string_join   :   0.023 /     2.245
append_string :   0.107 /     9.700
Τα αποτελέσματα δεν είναι μέσοι όροι. Τα έτρεξα όμως μερικές φορές και δεν υπήρχε σημαντική διασπορά στις τιμές.

Άρα όσον αφορά το string concatenation
* H python 3.2 ΔΕΝ είναι πιο αργή από την python 2.7
* To γρηγορότερο είναι με join
Τελευταία διόρθωση: 13 Χρόνια 1 Μήνας πριν από pmav99.
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Απ: Απορία για string concatenation και θέμα ταχύτητας 13 Χρόνια 1 Μήνας πριν #1292

  • mgiannakidis
  • Το Άβαταρ του/της mgiannakidis
  • Αποσυνδεμένος
  • p_____
  • Δημοσιεύσεις: 3
Αυτό που εγώ παρατήρησα στο αρχικό post, είναι:

ότι το s = s + (l + '\n') και το s += l + '\n' πάνε γρήγορα γιατί η γλώσσα κάνει το σωστό - γρήγορο.

Αλλά το s = s + l + '\n' πάει απελπιστικά αργά.

Και εκεί ήθελα να εστιάσω. Μπορεί να είναι bug που αξίζει να αναφερθεί;

Δεν αναζητώ των γρηγορότερο τρόπο για να κάνω concat τα strings. Αντίθετα, αναζητώ να βρω τους πολύ αργούς και να καταλάβω πότε εμφανίζονται ώστε να μην τους χρησιμοποιώ.

Μιχάλης
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Απ: Απορία για string concatenation και θέμα ταχύτητας 13 Χρόνια 1 Μήνας πριν #1293

  • pmav99
  • Το Άβαταρ του/της pmav99
  • Αποσυνδεμένος
  • Author
  • Δημοσιεύσεις: 684
  • Ληφθείσες Ευχαριστίες 111
Μιχάλη, αυτά που είχα γράψει ήταν περισσότερο σχετικά με αυτά που είχε γράψει ο myle.

Σε σχέση με αυτό που ρωτάς, δες το παρακάτω. Ελπίζω να σε βοηθήσει.
#! /usr/bin/env python
# -*- coding: utf-8 -*-
 
from __future__ import division
import cProfile
 
BIG_NUMBER = 1000000
 
def conc1(s, l):    
    for i in range(int(BIG_NUMBER / 100)):
        s = s + l + '\n'
    return s
 
def conc2(s, l):
    l = l + "\n"
    for i in range(BIG_NUMBER):
        s = s + l
    return s
 
def conc3(s, l):
    l = l + "\n"
    for i in range(BIG_NUMBER):
        s += l
    return s
 
def conc4(s, l):
    for i in range(BIG_NUMBER):
        s += l + '\n'
    return s
 
def conc5(s, l):    
    for i in range(BIG_NUMBER):
        s = s + (l + '\n')
    return s
 
def str_join(l):
    l += "n"
    l = [l for i in range(BIG_NUMBER)]
    l = "".join(l)
    return l
 
s = ''
l = '00000000000000000000000000000000000000000000000000000000000000000000000000000000'
 
cProfile.run("conc1(s, l)")
cProfile.run("conc2(s, l)")
cProfile.run("conc3(s, l)")
cProfile.run("conc4(s, l)")
cProfile.run("conc5(s, l)")
cProfile.run("str_join(l)")

Η conc1 είναι η πιο αργή version από όλες και με μεγάλη διαφορά. Ο λόγος είναι ότι μέσα στο for-loop δημιουργείται ξανά και ξανά ένα καινούριο string.

Η conc2 και η conc3 έχουν την ίδια απόδοση. Και στις δύο δημιουργούμε έξω από το for-loop το string που θέλουμε να κάνουμε concatenate. Εικάζω ότι εσωτερικά, το bytecode που θα δημιουργεί η Python θα είναι το ίδιο για "s += l" και "s = s + l", για αυτό και οι κοινοί χρόνοι.

Η conc4 και η conc5 έχουν και αυτές ουσιαστικά την ίδια απόδοση μεταξύ τους αλλά χειρότερη από της conc2 και conc3. Ο λόγος είναι ότι δημιουργείται εντός του loop ένα νέο string (το 'l + "\n"'). Στη συνέχεια ο κώδικας είναι αντίστοιχος με αυτόν των conc2 και conc3 (βοηθούνε οι παρενθέσεις σε αυτό).

Η str_join είναι ο βέλτιστος τρόπος νομίζω για να κάνεις το string concatenation, αν και ίσως δεν είναι τόσο ευανάγνωστος όσο οι υπόλοιποι.

Τρέχοντας τον παραπάνω κώδικα σε Python3, ο χρόνος της conc1 5πλασιάζεται, ενώ όλων των υπολοίπων περίπου διπλασιάζεται σε σχέση με την Python2.

Όπως φάνηκε από το προηγούμενο post μου, η ταχύτητα με την οποία γίνεται το string concatenation είναι σχεδόν η ίδια τόσο στην Python2 όσο και στην Python3.

Εκεί που εμφανίζεται η διαφορά τους είναι στον χρόνο που θέλουν τα loops για να τρέξουν. Εκεί η Python2 πρέπει να είναι αρκετά πιο γρήγορη από την Python3.

Πέρα από την ταχύτητα εκτέλεσης του for-loop, σημασία έχει και ο τρόπος με τον οποίο δομείται η έκφραση που βρίσκεται εντός του loop. Ουσιαστικά αν δημιουργείς καινούρια strings τότε ο κώδικας σου είναι αργός. Αν οι αλλαγές γίνονται in place, τότε ο κώδικας τρέχει πιο γρήγορα (αυτό που είπε ο myle δηλαδή).

Για διαφορετικές εργασίες από το string concatenation, λένε ότι είναι δυνατόν να πετύχεις ακόμη καλύτερη απόδοση, χρησιμοποιώντας εργαλεία όπως οι built-in συναρτήσεις "map", "reduce", "filter" οι οποίες έχουν υλοποιηθεί σε C, αποφεύγοντας με τον τρόπο αυτό κάποιο for-loop. Δεν έχω προσωπική εμπειρία για τις διαφορές στην απόδοση.

Δε ξέρω αν σε βοήθησα,
Παναγιώτης
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.
Συντονιστές: pmav99
Χρόνος δημιουργίας σελίδας: 0.294 δευτερόλεπτα

Μοιράσου το!

Powered by CoalaWeb

Λίστα Ταχυδρομείου