wake-up-neo.com

Wie kopiere ich eine Liste tief?

Ich habe ein Problem mit einer Listenkopie:

Nachdem ich E0 Von 'get_Edge' Erhalten habe, mache ich eine Kopie von E0, Indem ich 'E0_copy = list(E0)' aufrufe. Hier denke ich, dass E0_copy Eine tiefe Kopie von E0 Ist und gebe E0_copy An 'karger(E)' weiter. Aber in der Hauptfunktion.
Warum ist das Ergebnis von 'print E0[1:10]' Vor der for-Schleife nicht dasselbe wie nach der for-Schleife?

Unten ist mein Code:

def get_graph():
    f=open('kargerMinCut.txt')
    G={}
    for line in f:
        ints = [int(x) for x in line.split()]
        G[ints[0]]=ints[1:len(ints)]
    return G

def get_Edge(G):
    E=[]
    for i in range(1,201):
        for v in G[i]:
            if v>i:
                E.append([i,v])
    print id(E)
    return E

def karger(E):
    import random
    count=200 
    while 1:
        if count == 2:
            break
        Edge = random.randint(0,len(E)-1)
        v0=E[Edge][0]
        v1=E[Edge][1]                   
        E.pop(Edge)
        if v0 != v1:
            count -= 1
            i=0
            while 1:
                if i == len(E):
                    break
                if E[i][0] == v1:
                    E[i][0] = v0
                if E[i][1] == v1:
                    E[i][1] = v0
                if E[i][0] == E[i][1]:
                    E.pop(i)
                    i-=1
                i+=1

    mincut=len(E)
    return mincut


if __name__=="__main__":
    import copy
    G = get_graph()
    results=[]
    E0 = get_Edge(G)
    print E0[1:10]               ## this result is not equal to print2
    for k in range(1,5):
        E0_copy=list(E0)         ## I guess here E0_coypy is a deep copy of E0
        results.append(karger(E0_copy))
       #print "the result is %d" %min(results)
    print E0[1:10]               ## this is print2
102
Shen

E0_copy Ist keine tiefe Kopie. Mit list() erstellen Sie keine tiefe Kopie (sowohl list(...) als auch testList[:] Sind flache Kopien).

Sie verwenden copy.deepcopy(...) zum Kopieren einer Liste.

deepcopy(x, memo=None, _nil=[])
    Deep copy operation on arbitrary Python objects.

Siehe folgenden Ausschnitt -

>>> a = [[1, 2, 3], [4, 5, 6]]
>>> b = list(a)
>>> a
[[1, 2, 3], [4, 5, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
>>> a[0][1] = 10
>>> a
[[1, 10, 3], [4, 5, 6]]
>>> b   # b changes too -> Not a deepcopy.
[[1, 10, 3], [4, 5, 6]]

Sehen Sie sich nun die Operation deepcopy an

>>> import copy
>>> b = copy.deepcopy(a)
>>> a
[[1, 10, 3], [4, 5, 6]]
>>> b
[[1, 10, 3], [4, 5, 6]]
>>> a[0][1] = 9
>>> a
[[1, 9, 3], [4, 5, 6]]
>>> b    # b doesn't change -> Deep Copy
[[1, 10, 3], [4, 5, 6]]
176
Sukrit Kalra

Ich glaube, viele Programmierer sind auf ein oder zwei Interviewprobleme gestoßen, bei denen sie gebeten wurden, eine verknüpfte Liste zu kopieren. Dieses Problem ist jedoch schwieriger, als es sich anhört!

in Python gibt es ein Modul namens "copy" mit zwei nützlichen Funktionen

import copy
copy.copy()
copy.deepcopy()

copy () ist eine flache Kopierfunktion, wenn das angegebene Argument eine zusammengesetzte Datenstruktur ist, zum Beispiel eine Liste , dann python erstellt ein anderes Objekt desselben Typs (in diesem Fall eine neue Liste ), aber für alles in der alten Liste wird nur deren Referenz kopiert

# think of it like
newList = [elem for elem in oldlist]

Intuitiv könnten wir annehmen, dass deepcopy () demselben Paradigma folgt, und der einzige Unterschied besteht darin, dass wir für jedes Element rekursiv deepcopy , (just wie die Antwort von mbcoder)

aber das ist falsch !

deepcopy () behält tatsächlich die grafische Struktur der ursprünglichen Verbunddaten bei:

a = [1,2]
b = [a,a] # there's only 1 object a
c = deepcopy(b)

# check the result
c[0] is a # return False, a new object a' is created
c[0] is c[1] # return True, c is [a',a'] not [a',a'']

dies ist der knifflige Teil, während des Prozesses von deepcopy () wird eine Hashtabelle (Wörterbuch in Python) verwendet, um Folgendes abzubilden: "old_object ref auf new_object ref". Auf diese Weise werden unnötige Duplikate verhindert und die Struktur der kopierten zusammengesetzten Daten beibehalten

offizielles Dokument

50
watashiSHUN

Wenn der Inhalt der Liste primitive Datentypen sind, können Sie ein Verständnis verwenden

new_list = [i for i in old_list]

Sie können es für mehrdimensionale Listen verschachteln:

new_grid = [[i for i in row] for row in grid]
10
aljgom

Wenn dein list elements sind immutable objects dann können Sie dies verwenden, ansonsten müssen Sie deepcopy aus copy Modul verwenden.

sie können auch den kürzesten Weg verwenden, um ein list wie dieses tief zu kopieren.

a = [0,1,2,3,4,5,6,7,8,9,10]
b = a[:] #deep copying the list a and assigning it to b
print id(a)
20983280
print id(b)
12967208

a[2] = 20
print a
[0, 1, 20, 3, 4, 5, 6, 7, 8, 9,10]
print b
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
3
tailor_raj

nur eine rekursive Deep Copy-Funktion.

def deepcopy(A):
    rt = []
    for elem in A:
        if isinstance(elem,list):
            rt.append(deepcopy(elem))
        else:
            rt.append(elem)
    return rt

Bearbeiten: Wie Cfreak erwähnt, ist dies bereits in copy Modul implementiert.

2
rnbguy

Betrachtet man die Liste als Baum, kann die deep_copy in python am kompaktesten geschrieben werden als

def deep_copy(x):
    if not isinstance(x, list): return x
    else: return map(deep_copy, x)
1
ShellayLee