Python - une approche propre à ce problème?

J'ai du mal à choisir la meilleure structure de données pour résoudre un problème.Python - une approche propre à ce problème?

Le problème est comme ci-dessous:

J'ai une liste imbriquée des codes d'identité où les sous-listes sont de longueur variable.
```
li = [['abc', 'ghi', 'lmn'], ['kop'], ['hgi', 'ghy']] 
```
J'ai un fichier avec deux entrées sur chaque ligne; un code d'identité et un numéro.
```
abc  2.93 
ghi  3.87 
lmn  5.96 
```

Chaque sous-liste représente un cluster. Je souhaite sélectionner le i.d. de chaque sous-liste avec le nombre le plus élevé qui lui est associé, ajoutez que i.d. à une nouvelle liste et, finalement, l'écrire dans un nouveau fichier.

Dans quelle structure de données le fichier avec les nombres doit-il être lu?

De même, comment pouvez-vous itérer sur ladite structure de données pour renvoyer le i.d. avec le nombre le plus élevé qui correspond à l'i.d. dans une sous-liste?

Merci, S :-)

Source

2010-06-02 Darren J. Fitzpatrick

Vous pouvez lire le fichier dans un dictionnaire (string => int), puis utilisez une compréhension de la liste pour obtenir le code d'identification le plus élevé de chaque sous-liste.

d = {} 
with open("data", 'rb') as data: 
    for line in data: 
    key, val = line.split(' ') 
    d[key] = float(val) 

ids = [max(sublist, key=lambda k: d[k]) for sublist in li]

Pour Python 2.4, utilisez:

ids = [] 
for sublist in li: 
    subnums = map(lambda x: d[x], sublist) 
    ids.append(sublist[subnums.index(max(subnums))])

Comme il est indiqué, c'est O (n).

Source

2010-06-02 14:51:34

O (n) me semble bon. –

Vous n'êtes pas en train de convertir val en nombre, donc ce code comparera * les chaînes *, pas les flottants, c'est-à-dire '9.1'> '82 .3 '. On peut supposer que @Seafoid veut des valeurs comparées en nombres. –

Merci, @ Jeffrey. –

Ma solution suppose que vous voulez seulement le nombre le plus élevé et non l'id qui lui est associé.

Je lis les codes d'identité et les numéros dans un dictionnaire comme suggéré par Matthew

NEW_LIST = [] 
ID2NUM = {} 
with file('codes') as codes: 
    for line in codes: 
    id, num = line.rstrip().split() 
    ID2NUM[id] = num

J'ai ajouté quelques chiffres pour chaque identifiant a une valeur. Mon ID2NUM ressemble à ceci:

{'abc': 2.9300000000000002, 
'ghi': 3.8700000000000001, 
'ghy': 1.2, 
'hgi': 0.40000000000000002, 
'kop': 4.3499999999999996, 
'lmn': 5.96}

transformons la liste li:

for l in li: 
    NEW_LIST.append(max([d[x] for x in l])) 

>>> NEW_LIST 
[5.96, 4.3499999999999996, 1.2]

Pour écrire la nouvelle liste à un fichier, un numéro par ligne:

with file('new_list', 'w') as new_list: 
    new_list.write('\n'.join(NEW_LIST))

Source

2010-06-02 15:17:40 lmichelbacher

Le tri est O (n log n), il est donc préférable d'utiliser max, qui est O (n). –

Bon point, merci. – lmichelbacher

Que diriez-vous de stockage chaque sous-liste comme un arbre de recherche binaire? Vous obtiendrez des performances de recherche O (log n) en moyenne.

Une autre option serait d'utiliser max-heaps et vous obtiendriez O (1) pour obtenir la valeur maximale.

Source

2010-06-03 20:01:12 Pin

Python - une approche propre à ce problème?

Répondre

Questions connexes