deepcopy i python - wskazówki, których należy unikać?

Question

Mam bardzo prosty ruton python, który polega na przechodzenie przez listę z około 20 000 współrzędnych szerokości i długości geograficznej i obliczanie odległości każdego punktu do punktu odniesienia.

def compute_nearest_points(lat, lon, nPoints=5): 
    """Find the nearest N points, given the input coordinates.""" 

    points = session.query(PointIndex).all() 
    oldNearest = [] 
    newNearest = [] 
    for n in xrange(nPoints): 
     oldNearest.append(PointDistance(None,None,None,99999.0,99999.0)) 
     newNearest.append(obj2) 

    #This is almost certainly an inappropriate use of deepcopy 
    # but how SHOULD I be doing this?!?! 
    for point in points: 
     distance = compute_spherical_law_of_cosines(lat, lon, point.avg_lat, point.avg_lon) 
     k = 0 
     for p in oldNearest: 
      if distance < p.distance: 
       newNearest[k] = PointDistance(
        point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance 
        ) 
       break 
      else: 
       newNearest[k] = deepcopy(oldNearest[k]) 
      k += 1 
     for j in range(k,nPoints-1): 
      newNearest[j+1] = deepcopy(oldNearest[j]) 
     oldNearest = deepcopy(newNearest) 

    #We're done, now print the result 
    for point in oldNearest: 
     print point.station, point.english, point.distance 

    return 

początkowo napisałem to w C, stosując dokładnie takie samo podejście, i to działa dobrze tam, i jest w zasadzie chwilowego dla nPoints < = 100. Więc postanowiłem przenieść go do Pythona, ponieważ chciałem użyć SqlAlchemy do robienia innych rzeczy.

Najpierw przeportowałem go bez instrukcji deepcopy, które teraz pieprzą metodę, a to spowodowało, że wyniki są "nieparzyste" lub częściowo niepoprawne, ponieważ niektóre punkty zostały po prostu skopiowane jako referencje (chyba? ?) - ale wciąż było prawie tak szybko, jak wersja C.

Teraz z dodanymi poleceniami deepcopy, rutynowe zadanie wykonuje się poprawnie, ale poniosło ono ekstremalną karę wykonania, a teraz zajmuje kilka sekund wykonanie tej samej pracy.

Wydaje się, że to dość powszechna praca, ale najwyraźniej nie robię tego w sposób pytonowy. Jak powinienem to robić, aby nadal uzyskiwać poprawne wyniki, ale nie muszę wszędzie wprowadzać deepcopy?

EDIT:
mam trafić na znacznie prostsze i szybsze rozwiązanie,

def compute_nearest_points2(lat, lon, nPoints=5): 
    """Find the nearest N points, given the input coordinates.""" 

    points = session.query(PointIndex).all() 
    nearest = [] 

    for point in points: 
     distance = compute_spherical_law_of_cosines(lat, lon, point.avg_lat, point.avg_lon) 
     nearest.append( 
      PointDistance(
       point.point, point.kana, point.english, point.avg_lat, point.avg_lon, distance=distance 
       ) 
      ) 

    nearest_points = sorted(nearest, key=lambda point: point.distance)[:nPoints]  
    for item in nearest_points: 
     print item.point, item.english, item.distance 
    return 

Więc w zasadzie jestem tylko co kompletną kopię wejścia i dodanie nowej wartości - odległość od Punkt odniesienia. Następnie stosuję "posortowane" do wynikowej listy, określając, że klucz sortowania powinien być właściwością odległości obiektu PointDistance.

Jest to znacznie szybsze niż zastosowanie deepcopy, chociaż przyznaję, że tak naprawdę nie rozumiem dlaczego. Sądzę, że to zależy od wydajnych implementacji C "posortowanych" Pythona?

Answer 1

porządku, najprostsze rzeczy pierwsze:

1. deepcopy jest powolny w ogóle, ponieważ musi zrobić dużo księgowych skopiować patologiczne przypadki jak obiektów zawierających się w rozsądny sposób. Zobacz na przykład this page lub spójrz na kod źródłowy deepcopy w copy.py, który znajduje się gdzieś w ścieżce do Pythona.

2. sorted jest szybki, ponieważ jest zaimplementowany w języku C. O wiele szybszy niż podobny sort w języku Python.

Teraz trochę więcej informacji na temat liczenia odwołań Pythona, o które prosiłeś w swoim komentarzu. W Pythonie zmienne są referencjami. Kiedy mówisz: a=1, pomyśl o tym, że ma on 1 jako obiekt istniejący samodzielnie, a a to tylko tag dołączony do niego. W niektórych innych językach, takich jak C, zmienne są kontenerami (nie znacznikami), a gdy wykonujesz a=1, wstawiasz 1 do a. Nie dotyczy to języka Python, gdzie zmienne są odniesieniami.To ma kilka ciekawych konsekwencji, które mogą mieć również potknął się na:

>>> a = []  # construct a new list, attach a tag named "a" to it 
>>> b = a  # attach a tag named "b" to the object which is tagged by "a" 
>>> a.append(1) # append 1 to the list tagged by "a" 
>>> print b  # print the list tagged by "b" 
[1] 

Takie zachowanie jest postrzegane, ponieważ listy są Zmienne obiekty: można zmodyfikować listę po tym, jak ją stworzył, a modyfikacja jest widoczne podczas uzyskiwania dostępu listę za pomocą którejkolwiek ze zmiennych, które się do niej odnoszą. W niezmienne odpowiedniki list są krotki:

>>> a =()  # construct a new tuple, attach a tag named "a" to it 
>>> b = a  # now "b" refers to the same empty tuple as "a" 
>>> a += (1, 2) # appending some elements to the tuple 
>>> print b 
() 

Tutaj a += (1, 2) tworzy nowy krotki z istniejącego krotki określoną przez a, plus kolejny krotki (1, 2) który jest skonstruowany on-the-fly i a jest dostosowany do wskazywania na nową krotkę, podczas gdy oczywiście b nadal odnosi się do starej krotki. To samo dzieje się z prostymi dodatkami numerycznymi, takimi jak a = a+2: w tym przypadku liczba pierwotnie wskazywana przez a nie jest w żaden sposób zmutowana, Python "konstruuje" nową liczbę i przenosi a, aby wskazać nową liczbę. Krótko mówiąc: liczby, łańcuchy i krotki są niezmienne; listy, dyktety i zestawy są zmienne. Klasy zdefiniowane przez użytkownika są generalnie zmienne, chyba że wyraźnie zaznaczysz, że nie można zmutować stanu wewnętrznego. I jest frozenset, który jest niezmiennym zestawem. Plus wiele innych oczywiście :)

Nie wiem, dlaczego Twój oryginalny kod nie działał, ale prawdopodobnie trafiłeś w zachowanie związane z fragmentem kodu, który pokazałem na listach, ponieważ twoja klasa PointDistance jest również zmienna domyślnie. Alternatywą może być klasa namedtuple z collections, która tworzy obiekt podobny do krotki, do którego można również uzyskać dostęp za pomocą nazw. Na przykład, można to zrobić w ten sposób:

from collections import namedtuple 
PointDistance = namedtuple("PointDistance", "point distance") 

To tworzy klasę PointDistance dla Ciebie, który ma dwa nazwane pola: point i distance. W swojej głównej pętli for możesz je odpowiednio przypisać. Ponieważ obiekty punktu wskazane przez pola point nie zostaną zmodyfikowane w trakcie pętli for, a distance jest liczbą (która z definicji jest niezmienna), powinieneś być bezpieczny w ten sposób. Ale tak, ogólnie rzecz biorąc, wydaje się, że po prostu sorted jest szybszy od sorted jest zaimplementowany w C. Możesz również mieć szczęście z modułem heapq, który implementuje strukturę danych sterty wspieraną przez zwykłą listę Pythona, dlatego pozwala znaleźć górne elementy k łatwo, bez konieczności sortowania innych. Jednak od heapq jest również zaimplementowany w Pythonie, jest szansa, że ​​sorted działa lepiej, chyba że masz dużo punktów.

Na koniec chciałbym dodać, że do tej pory nie musiałem korzystać z deepcopy, więc domyślam się, że w większości przypadków można tego uniknąć.

Answer 2

Rozumiem, że nie odpowiada to bezpośrednio na twoje pytanie (i wiem, że to stare pytanie), ale ponieważ jest dyskusja na temat wydajności, warto przyjrzeć się operacji append. Możesz rozważyć "wstępną alokację" tablicy.Na przykład:

array = [None] * num_elements 
for i in range(num_elements): 
    array[i] = True 

kontra:

array = [] 
for i in range(num_elements): 
    array.append(True) 

Prosty timeit run z tych dwóch metod wykazuje poprawę o 25%, jeśli wstępnie przydzielić tablicę nawet dla umiarkowanych wartościach num_elements.