Wie kopiere ich eine Liste tief?

148

Ich habe ein Problem mit einer Listenkopie:

Nachdem ich E0von gekommen 'get_edge'bin, mache ich eine Kopie, E0indem ich anrufe 'E0_copy = list(E0)'. Hier E0_copyist wohl eine tiefe Kopie von E0und ich gehe E0_copyhinein 'karger(E)'. Aber in der Hauptfunktion.
Warum ist das Ergebnis '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
Shen
quelle
2
Außerdem ist b = a [:] eine flache Kopie. Siehe stackoverflow.com/questions/16270374/…
Arvind Haran

Antworten:

228

E0_copyist keine tiefe Kopie. Sie erstellen keine tiefe Kopie mit list()(Beide list(...)und testList[:]sind flache Kopien).

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

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

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

Nun sehen Sie die deepcopyOperation

>>> 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]]
Sukrit Kalra
quelle
3
Danke. Aber ich dachte, list () ist eine tiefe Kopie, da id (E0) nicht gleich id (E0_copy) ist. Könntest du erklären, warum es passiert?
Shen
14
list (...) erstellt nicht rekursiv Kopien der inneren Objekte. Es wird nur eine Kopie der äußersten Liste erstellt, während weiterhin auf die inneren Listen der vorherigen Variablen verwiesen wird. Wenn Sie also die inneren Listen mutieren, wird die Änderung sowohl in der ursprünglichen Liste als auch in der flachen Kopie wiedergegeben.
Sukrit Kalra
1
Sie können sehen, dass flaches Kopieren auf die inneren Listen verweist, indem Sie diese ID (a [0]) == ID (b [0]) überprüfen, wobei b = Liste (a) und a eine Liste von Listen ist.
Sukrit Kalra
list1.append (list2) ist auch eine flache Kopie von list2
Lazik
60

Ich glaube, viele Programmierer sind auf ein oder zwei Interviewprobleme gestoßen, bei denen sie gebeten werden, eine verknüpfte Liste tief 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, beispielsweise eine Liste , erstellt Python ein anderes Objekt des gleichen Typs (in diesem Fall eine neue Liste ), jedoch für alles in der alten Liste. nur ihre Referenz wird kopiert

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

Intuitiv könnten wir annehmen, dass deepcopy () dem gleichen Paradigma folgt, und der einzige Unterschied besteht darin, dass wir für jedes Element rekursiv Deepcopy nennen (genau wie die Antwort von mbcoder).

aber das ist falsch!

deepcopy () behält tatsächlich die grafische Struktur der ursprünglichen Verbindungsdaten 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 schwierige Teil. Während des Deepcopy () -Prozesses wird eine Hashtabelle (Wörterbuch in Python) verwendet, um Folgendes abzubilden: "old_object ref auf new_object ref". Dies verhindert unnötige Duplikate und bewahrt somit die Struktur der kopierten zusammengesetzten Daten

offizielles Dokument

watashiSHUN
quelle
18

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 wie:

new_grid = [[i for i in row] for row in grid]
aljgom
quelle
5

Wenn Sie es list elementssind immutable objects, können Sie dies verwenden, andernfalls müssen Sie es deepcopyvom copyModul aus verwenden.

Sie können auch den kürzesten Weg für eine tiefe Kopie listwie diese verwenden.

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]
tailor_raj
quelle
21
Dies ist keine Deep Copy.
Sukrit Kalra
1
Was ist es dann. Es hat zwei verschiedene Wörterbücher (Sie können die IDs jedes Wörterbuchs überprüfen) mit denselben Werten.
tailor_raj
Lesen Sie dies , [:] erstellt nur eine flache Kopie, es werden keine rekursiven Kopien der Objekte in einer erstellt.
Sukrit Kalra
1
Vielen Dank. Sie wollen damit sagen, wenn wir dies verwenden, wird eine neue Liste erstellt, aber alle Elemente der neuen Liste sind nur Kopien. Sie haben dasselbe Objekt (dieselbe ID) wie die vorherige?
tailor_raj
Versuchen Sie es mit einer verschachtelten Liste. Aktualisieren Sie das verschachtelte Element der Liste a. Es wird auch in Liste b aktualisiert. Dies impliziert, dass eine [:] keine tiefe Kopie ist.
AnupamChugh
2

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 im copyModul implementiert .

rnbguy
quelle
4
Es gibt keinen Grund, die Standardfunktion deepcopy()im copyModul neu zu implementieren
Cfreak
1

In Bezug auf die Liste als Baum kann die deep_copy in Python am kompaktesten als geschrieben werden

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

Hier ist ein Beispiel für das tiefe Kopieren einer Liste:

  b = [x[:] for x in a]
AnupamChugh
quelle
0

Das ist mehr pythonisch

my_list = [0, 1, 2, 3, 4, 5]  # some list
my_list_copy = list(my_list)  # my_list_copy and my_list does not share reference now.

HINWEIS: Dies ist bei einer Liste der referenzierten Objekte nicht sicher

Kwaw Annor
quelle
2
Das funktioniert nicht. Ich dachte es könnte aber nur überprüft werden. Versuchen Sie es mit einer Liste von Wörterbüchern als gutem Beispiel
Shashank Singh
@ShashankSingh Ja, dies funktioniert nicht für eine Liste von Wörterbüchern, da die Einträge Referenz-Tags sind (die auf einen Speicherort verweisen). Wenn Sie also eine Wörterbuchliste mit dieser Methode duplizieren, wird eine neue Liste erstellt. Da es sich bei den Einträgen jedoch um Wörterbücher handelt, verweisen sie immer noch auf denselben Speicherort.
Kwaw Annor