Szybkość kopiowania bufora w języku Python - dlaczego tablica jest wolniejsza od łańcucha?

Question

Mam obiekt bufora w C++, który dziedziczy po std::vector<char>. Chcę przekonwertować ten bufor na ciąg znaków w języku Python, aby można go było wysłać przez sieć za pośrednictwem protokołu Twisted's protocol.transport.write.

dwojako myślałem w ten sposób są (1) podejmowania ciąg i wypełnienie go char przez char:

def scpychar(buf, n): 
    s = '' 
    for i in xrange(0, n): 
     s += buf[i] 
    return s 

i (2) podejmowania tablicę char (ponieważ wiem, jak duże bufor jest) , wypełnienie go i przekształcenie go na ciąg

def scpyarr(buf, n): 
    a = array.array('c','0'*n) 
    for i in xrange(0, n): 
     a[i] = buf[i] 
    return a.tostring() 

myślałem, że (1) musi zrobić nowy obiekt string za każdym razem s += buf[i] nazywa i skopiuj zawartość starego łańcucha. Spodziewałem się więc (2), że jest szybszy niż (1). Ale jeśli przetestuję to używając timeit, stwierdzam, że (1) jest w rzeczywistości około dwa razy szybszy niż (2).

Zastanawiam się, czy ktoś może wyjaśnić, dlaczego (1) jest szybszy?

Punkty premiowe za jeszcze skuteczniejszy sposób konwersji z std::vector<char> na ciąg znaków w języku Python.

Answer 1

CPython może czasami zoptymalizować ciąg znaków +=, aby był w miejscu, jeśli może stwierdzić, że nikt nie utrzymuje odniesienia do starego ciągu. Algorytm (1) prawdopodobnie spowodował optymalizację, więc nie cierpiał na kwadratowy czas pracy, który w przeciwnym razie by nie powstał. Jednak takie zachowanie nie jest gwarantowane, a inne implementacje Pythona mogą go nie obsługiwać.

Spróbuj

''.join(buf) 

To powinno oferować wydajność liniowego czasu na dowolnej implementacji Pythona, w odróżnieniu od (1), i szybciej niż (2).

Answer 2

importuj dis i spójrz na dis.dis (scpyarr) i dis.dis (scpychar). scpychar ma mniejszą liczbę operacji interpretera.

>>> import dis 
>>> def scpyarr(buf, n): 
...  a = array.array('c','0'*n) 
...  for i in xrange(0, n): 
...   a[i] = buf[i] 
...  return a.tostring() 
... 
>>> dis.dis(scpyarr) 
    2   0 LOAD_GLOBAL    0 (array) 
       3 LOAD_ATTR    0 (array) 
       6 LOAD_CONST    1 ('c') 
       9 LOAD_CONST    2 ('0') 
      12 LOAD_FAST    1 (n) 
      15 BINARY_MULTIPLY  
      16 CALL_FUNCTION   2 
      19 STORE_FAST    2 (a) 

    3   22 SETUP_LOOP    37 (to 62) 
      25 LOAD_GLOBAL    1 (xrange) 
      28 LOAD_CONST    3 (0) 
      31 LOAD_FAST    1 (n) 
      34 CALL_FUNCTION   2 
      37 GET_ITER    
     >> 38 FOR_ITER    20 (to 61) 
      41 STORE_FAST    3 (i) 

    4   44 LOAD_FAST    0 (buf) 
      47 LOAD_FAST    3 (i) 
      50 BINARY_SUBSCR  
      51 LOAD_FAST    2 (a) 
      54 LOAD_FAST    3 (i) 
      57 STORE_SUBSCR   
      58 JUMP_ABSOLUTE   38 
     >> 61 POP_BLOCK   

    5  >> 62 LOAD_FAST    2 (a) 
      65 LOAD_ATTR    2 (tostring) 
      68 CALL_FUNCTION   0 
      71 RETURN_VALUE   
>>> def scpychar(buf, n): 
...  s = '' 
...  for i in xrange(0, n): 
...   s += buf[i] 
...  return s 
... 
>>> dis.dis(scpychar) 
    2   0 LOAD_CONST    1 ('') 
       3 STORE_FAST    2 (s) 

    3   6 SETUP_LOOP    37 (to 46) 
       9 LOAD_GLOBAL    0 (xrange) 
      12 LOAD_CONST    2 (0) 
      15 LOAD_FAST    1 (n) 
      18 CALL_FUNCTION   2 
      21 GET_ITER    
     >> 22 FOR_ITER    20 (to 45) 
      25 STORE_FAST    3 (i) 

    4   28 LOAD_FAST    2 (s) 
      31 LOAD_FAST    0 (buf) 
      34 LOAD_FAST    3 (i) 
      37 BINARY_SUBSCR  
      38 INPLACE_ADD   
      39 STORE_FAST    2 (s) 
      42 JUMP_ABSOLUTE   22 
     >> 45 POP_BLOCK   

    5  >> 46 LOAD_FAST    2 (s) 
      49 RETURN_VALUE   
>>> 

Porównaj go:

  51 LOAD_FAST    2 (a) 
     54 LOAD_FAST    3 (i) 
     57 STORE_SUBSCR 

Plus

>> 62 LOAD_FAST    2 (a) 
     65 LOAD_ATTR    2 (tostring) 
     68 CALL_FUNCTION   0 

vs

  38 INPLACE_ADD   
     39 STORE_FAST 

obciążenia jest powolny. CALL_FUNCTION jest powolny.

Widziałem w pytaniu, miesiąc temu, że ''.join(b) był najszybszym sposobem, aby połączyć tablicę znaków w jeden ciąg znaków.