Ein effizienter Weg, um eine Liste der Liste zu transponieren

Question

Ich habe eine Liste von Listen:

x = [ [4, ‘c’, ‘b’, ‘d’], [2, ‘e’, ‘c’, ‘a’], [5, ‘a’, ‘c’] ] 

, die ich konvertieren müssen:

x1 = [ [‘c’, 4, 2, 5], [‘b’, 4], [‘d’, 4], [‘e’, 2], [‘a’, 2, 5] ] 

Erläuterung:

'c' appears in lists starting with 4, 2, 5 
'b' appears in only the list starting with 4 
'd' appears in only the list starting with 4 
... 

offensichtlich Dies ist ein Spielzeugbeispiel, aber meine wirkliche Liste hat ungefähr 30 MB in einer flachen Datei.

Ich habe versucht, mit einem zwei verschachtelten for-Schleifen, aber es dauert etwa 5 Stunden für nur die 5% der Datei in meinem MacBook Pro (8 GB RAM).

Gibt es einen effizienten Weg, dies zu tun?

Answer 1

Ich habe es geschafft, es auch in zwei verschachtelten Schleifen:

from collections import defaultdict 

x = [ [4, 'c', 'b', 'd'], [2, 'e', 'c', 'a'], [5, 'a', 'c'] ] 

d = defaultdict(list) 

for group in x: 
    key = group[0] 
    for item in group[1:]: 
     d[item].append(key) 


print(d) 

# and to convert back to list: 
x1 = [[key]+value for (key,value) in d.items()] 
print(x1) 

Ausgang:

defaultdict(<class 'list'>, {'c': [4, 2, 5], 'b': [4], 'd': [4], 'e': [2], 'a': [2, 5]}) 
[['c', 4, 2, 5], ['b', 4], ['d', 4], ['e', 2], ['a', 2, 5]] 

Ein Hinweis auf die Effizienz:

Auf der Innenseite der äußeren Schleife berechnen I group[1:] . Wenn nun group groß ist, kann es sogar teuer sein, nur die Liste zu kopieren. Wenn dies der Fall könnte die Schleifen wie diese besser sein:

for group in x: 
    it = iter(group) 
    key = next(it) 
    for item in it: 
     d[item].append(key) 

Die Effizienz, dann ist O(n) wobei n die Gesamtzahl der Elemente in allen Listen ist. Ob diese Verarbeitung oder das Lesen der 30MB Dateiinhalte am langsamsten ist, kann ich nicht messen.

Answer 2

Basierend auf @ quamrana der Annahme von dem, was Sie wirklich wollen, erreichen:

x = [ [4, 'c', 'b', 'd'], 
     [2, 'e', 'c', 'a'], 
     [5, 'a', 'c'] ] 

letters = {i for y in x for i in y if isinstance(i, str)} 
y = [[i] + [sub[0] for sub in x if i in sub] for i in letters] 
print(y) # [['e', 2], ['d', 4], ['a', 2, 5], ['b', 4], ['c', 4, 2, 5]]