deepcopy i python-wskazówki, jak go unikać?

Question

deepcopy i python-wskazówki, jak go unikać?

Mam bardzo prostą procedurę Pythona, która polega na przejechaniu listy około 20 000 współrzędnych szerokości i długości geograficznej i obliczaniu 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, używając dokładnie tego samego podejścia, i działa tam dobrze, i jest w zasadzie natychmiastowy dla nPoints

Najpierw przeportowałem go bez Oświadczenia deepcopy, które teraz pieprz metodę, a to spowodowało, że wyniki są "dziwne", lub częściowo niepoprawne, ponieważ niektóre z punktów były po prostu kopiowane jako referencje(chyba? Tak myślę?) -- ale i tak był prawie tak szybki jak Wersja C.

Teraz z dodanymi wywołaniami deepcopy, rutyna wykonuje swoje zadanie poprawnie, ale poniosła ekstremalną karę wydajności i teraz zajmuje kilka sekund, aby wykonać to samo zadanie.

To wydaje się dość powszechne zadanie, ale najwyraźniej nie robię tego w sposób pythoniczny. Jak mam to zrobić, aby nadal uzyskać prawidłowe wyniki, ale nie muszę wszędzie uwzględniać deepcopy?

EDIT:
Trafiłem 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 robię kompletną kopię danych wejściowych i dodaję nową wartość-odległość od punktu odniesienia. Następnie po prostu zastosuję "posortowane" do wynikowej listy, określając, że klucz sortowania powinien być właściwością distance Obiekt PointDistance.

Jest to o wiele szybsze niż używanie deepcopy, chociaż przyznaję, że nie bardzo rozumiem dlaczego. Chyba chodzi o wydajne implementacje C Pythona "posortowane"?

17

python deep-copy

Author: si28719e, 2010-06-15

Source

2 answers

Rozumiem, że nie odnosi się to bezpośrednio do twojego pytania (i Wiem, że to stare pytanie), ale ponieważ jest trochę dyskusji na temat wydajności, może warto przyjrzeć się operacji append. Warto 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)

Proste timeit uruchomienie tych dwóch metod pokazuje 25% poprawę, jeśli wstępnie przydzielisz tablicę dla nawet umiarkowanych wartości num_elements.

6

Author: tvaughan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-12-05 16:15:30

score 35 · Accepted Answer

Dobra, najpierw najprostsze rzeczy:

deepcopy jest powolny w ogóle, ponieważ musi zrobić wiele wewnętrznej księgowości, aby skopiować patologiczne przypadki, takie jak przedmioty zawierające się w rozsądny sposób. Zobacz na przykład tę stronę lub spójrz na kod źródłowy deepcopy w copy.py, który znajduje się gdzieś w Twojej ścieżce Pythona.
sorted jest szybki, ponieważ jest zaimplementowany w C. znacznie szybszy niż odpowiednik w Pythonie.

Teraz, niektóre więcej o pythonowym zachowaniu zliczania referencji, o co prosiłeś w komentarzu. W Pythonie zmienne są referencjami. Kiedy mówisz a=1, pomyśl o tym, że ma 1 jako obiekt istniejący sam w sobie, a a jest tylko dołączonym do niego znacznikiem. W niektórych innych językach, takich jak C, zmienne są kontenerami (nie znacznikami), a gdy robisz a=1, w rzeczywistości umieszczasz 1 w a. To nie dotyczy Pythona, gdzie zmienne są referencjami. Ma to kilka interesujących konsekwencji, które możesz mieć również

>>> 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]

To zachowanie jest widoczne, ponieważ listy są obiektami zmiennymi : możesz zmodyfikować listę po jej utworzeniu, a modyfikacja jest widoczna podczas uzyskiwania dostępu do listy za pomocą dowolnej zmiennej, która się do niej odnosi. niezmienne odpowiednikami 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 nową krotkę z istniejącej krotki, o której mowa przez a, plus kolejną krotkę (1, 2), która jest konstruowana w locie i a jest dostosowano, aby wskazywać na nową krotkę, podczas gdy oczywiście b nadal odnosi się do starej krotki. To samo dzieje się z prostymi dodatkami liczbowymi, 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 przesuwa a, aby wskazać nową liczbę. W skrócie: liczby, ciągi i krotki są niezmienne; listy, dykty i zestawy są zmienne. Klasy zdefiniowane przez użytkownika są ogólnie zmienne, chyba że wyraźnie zapewnisz, że wewnętrzne stan nie może być zmutowany. I jest frozenset, który jest niezmiennym zbiorem. 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 z listami, ponieważ twoja klasa PointDistance jest również domyślnie zmienna. Alternatywą może być Klasa namedtuple z collections, która konstruuje obiekt podobny do krotki, do którego pól można również uzyskać dostęp za pomocą nazw. Na przykład, mogłeś zrobić to:

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

Tworzy to klasę PointDistance, która ma dwa nazwane pola: point i distance. W głównej pętli for możesz je odpowiednio przypisać. Ponieważ obiekty punktowe wskazywane przez pola point nie będą modyfikowane podczas 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 użycie sorted jest szybsze, ponieważ sorted jest zaimplementowane w C. Możesz również być szczęśliwie z modułem heapq, który implementuje strukturę danych sterty wspieraną przez zwykłą listę Pythona, dzięki czemu pozwala łatwo znaleźć najważniejsze elementy k bez konieczności sortowania pozostałych. Jednak, ponieważ {[33] } jest również zaimplementowany w Pythonie, są szanse, że sorted działa lepiej, chyba że masz dużo punktów.

Na koniec chciałbym dodać, że do tej pory nie musiałem używać deepcopy, więc myślę, że są sposoby, aby tego uniknąć w większości przypadków.