indexation d'une liste

Version imprimable

Voir 40 message(s) de cette discussion en une page

29/06/2010, 14h44
manaliac

indexation d'une liste

Bonjour,

J'ai une liste dont je souhaiterai avoir les indices, mais quand j'ai deux éléments qui ont la même valeur dans ma liste, mon instruction i

Code:

indice = [liste.index(x) for x in liste]

me renvoie le même index :

exemple :

liste= [2, 4, 36, 2, 5, 4]

index obtenus = [0, 1, 2, 0, 4, 1]

y'a t'il une instruction pour obtenir des index distincts indépendamment de la valeur des éléments de la liste?

Merci
29/06/2010, 15h02
dividee

euh...

Code:

indices = range(len(liste))

non ?
29/06/2010, 15h38
manaliac
oui ça marche très bien, merci !

Par contre j'ai une autre question; avec la meme liste, je souhaite créer une nouvelle liste nv_liste qui regroupe les éléments qui sont répétés :
J'ai donc fait :
Code:

1 2 liste= [2, 4, 36, 2, 5, 4] nv_liste = [x for x in split1 if liste.count(x) >1]
Mais je voudrais aussi inclure l'ancien index de mon élément de la première liste.

et le range(len(liste)) ne me servira pas je pense dans ce cas là à grand chose !

Un truc comme çà?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def xx(li):
    dd = {}
    for index, item in enumerate(li):
        if item in dd:
            dd[item].append(index)
        else:
            dd[item] = [ index ]
    for item in dd.keys():
        if len(dd[item]) == 1:
            del dd[item]
    return dd
 
L = [2, 5, 4, 1, 2]
x = xx(L)
print 'x: %s' % x
## retourne x: {2: [0, 4]}

Ou comme ça ?

Code:

1
2
3
4
5
6
7
def indm1(L):
    R=[]
    Q= [(x, [i for i in range(0,len(L)) if L[i]==x]) for x in L if L.count(x)>1] 
    for x in Q:
        if x not in R:
            R+=[x]
    return R

Ou comme ça (plus efficace):

Code:

1
2
3
4
5
6
7
def indm2(L):
    R=[[],[]]
    for x in L:
        if x not in R[0] and L.count(x)>1 :
            R[0].append(x)
            R[1].append([i for i in range(0,len(L)) if L[i]==x])
    return R

29/06/2010, 17h49
wiztricks

Verbeux Zavonen, verbeux :lol:
Alors qu'on peut faire cela en une ligne :aie:

Code:

ff = lambda L : [ (a, [ c for i, c in zip (L, range(len(L))) if i == a ]) for a, c in [(a, L.count(a)) for a in set(L)] if c > 1 ]

Mais ce n'est pas recommendable
- W
29/06/2010, 17h55
Zavonen

Citation:

Alors qu'on peut faire cela en une ligne

On croirait du Haskell !

Ah ouais Python c'est pour tous les genres...

Une version légèrement différente dans laquelle je n'ai pas replié les 'bouts':
Code:

1 2 3 4 def ff(L): ix = zip (range(len(L)), L) # les 'indices, valeurs' fq = [ a for a in set(L) if L.count(a) > 1 ] # les occurences > 1 return [ (a, [ i for i, c in ix if c == a ]) for a in fq ] # recup des index
On replie les bouts:

Code:

ff = lambda L: [ (a, [ i for i, c in zip (range(len(L)), L) if c == a ]) for a in [ a for a in set(L) if L.count(a) > 1 ] ]

dans la première mouture, je construisais:
fq = [ (a, L.count(a)) for a in set(L) ] : les occurences/fréquences de a dans L
Dans la 2ème version, fq ne contient que les "a" dont l'occurence est > 1
- W

29/06/2010, 18h46
dividee

Pourquoi tu as laissé tombé enumerate(L) wiztricks ? C'est quand-même plus élégant que zip(range(len(L)),L).

Une autre version:

Code:

ff = lambda L : [ x for x in ((a, [ i for i, c in enumerate(L) if c == a ]) for a in set(L)) if len(x[1]) >= 2 ]

Au cas où on voudrait seulement faire un traitement sur les doublons, on peut générer la liste résultat plutôt que de la construire.
Après (quelques) essais infructueux il semble que cela marche:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 def yy(L): n=len(L) def Iter(L): i=0 if i>= n: raise StopIteration DV=[] for j in xrange(i,n): x=L[j] if L[j:n].count(x)==1 or x in DV: continue i=j DV+=[x] yield(x,[h for h in range(j,n) if L[h]==x]) I=Iter(L) for k in xrange(0,n): try: I.next() except StopIteration: break
On est quand même obligé de mémoriser la liste des doublons en variable 'statique' du générateur.
Au point de vue efficacité il y a un + par rapport aux solutions précédentes, pour tout 'nouvel x' on ne recompte (et mémorise) ses occurrences que dans la sous-liste de L qui commence avec lui.
Donc plus on avance et plus ça va vite.

29/06/2010, 21h05
wiztricks
Bravo Dividee,
Je ne l'ai pas laissé tomber...
Mais j'ai des difficultés à penser en Python: donc j'écris des trucs 'en francais' et je les traduis au fur et à mesure.
Dans la deuxième version que j'ai proposé, je me suis attaché a réduire le patatoïdesque calcul de fq qui faisant trop faisait peu.
Le "ix" est plus pervers.
Le monstre sort du chapeau en écrivant:
- calculer la fréquence de chaque élément => fq
- a chaque élément dont la fréquence est >1 associer les index.
Les index, les index allez un coup de zip et on verra plus tard, par contre passer à:
- ix = les index de L
- fq = liste des éléments dont la fréquence est > 1
- à chaque élément de fq associer les index.
améliore l'algo... indépendamment du code.

L'histoire de l'enumerate(L) demande à écrire le code Python:
Première passe:

[ (a, [ i for i, c in ix if c == a ]) for a in fq ]
pas trop choquant...
Deuxième passe, on écrase tout dans le lambda:

[ (a, [ i for i, c in zip (range(len(L)), L) if c == a ]) for a in fq ]
Nous ne sommes plus dans l'algo. mais dans la lecture d'un code Python.
Et là, je dois avouer que je suis généralement un peu vanné de tous les vas et vient entre penser/écrire ou que je ne suis pas encore assez rapide pour sortir la construction qui va bien.:cry:
-W

Ma version en détails:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 def ff(L): # 1. Extraire les éléments uniques de L keys = set(L) lst = [] # 2. Pour chacun de ceux-ci... for elem in keys: # ... retrouver ses positions dans L lst.append((elem,[idx for idx, el in enumerate(L) if el == elem])) # 3. Ne garder que ceux présents plus d'une fois result = [] for key, value in lst: if len(value) >= 2: result.append((key,value)) return result
Au niveau de la complexité asymptotique (en temps), si la liste est de longueur n et qu'elle contient k valeurs distinctes:
Le point 1 est O(n)
Le point 2 est O(kn)
Le point 3 est O(k) (car la fonction len est O(1))
Donc le point 2 domine et l'algo est O(kn).

En fait, au niveau de la complexité asymptotique, c'est la première solution de wiztricks qui est la meilleure: O(n) (en supposant que l'accès au dictionnaire est O(1)).

Comme quoi, l'approche fonctionnelle est élégante et a certains avantages, mais ce n'est pas toujours la plus efficace...
Une variante plus courte du premier code de wiztricks:
Code:

1 2 3 4 5 6 from collections import defaultdict def xx(L): dd = defaultdict(list) for idx, item in enumerate(L): dd[item].append(idx) return [(k,v) for k,v in dd.iteritems() if len(v) > 1]

29/06/2010, 23h52
Zavonen

Citation:

En fait, au niveau de la complexité asymptotique, c'est la première solution de wiztricks qui est la meilleure: O(n)

Cela il faut me l'expliquer car la seule détermination des doublons dans une liste de longueur n est en n(n-1)/2.
30/06/2010, 00h48
dividee

Citation:

Envoyé par Zavonen

Cela il faut me l'expliquer car la seule détermination des doublons dans une liste de longueur n est en n(n-1)/2.

Ben non pas avec un dictionnaire. Il y a un seul parcours de la liste pour remplir le dictionnaire --> O(n), puis un parcours de ce dictionnaire pour ne garder que les éléments qui apparaissent plusieurs fois --> O(k).

Cela suppose que list.append, len(list), et dict.__getitem__ soient tous O(1), mais je crois que c'est le cas (ou au moins O(1) amorti).

Il me semble que l'instruction:

Code:

if item in dd:

est une boucle déguisée, non ?

De fait xx est plus rapide que zz avec un facteur constant qui dépend du nombre d'entiers d'instincts dans L.
Pour moi les algos sont équivalents en complexité. J'attribue ces résultats à l'efficacité des fonctions de gestion des dictionnaires. zz doit être ralenti par les append

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import random
import time
 
def time_this(func):
    """The time_this decorator"""
 
    def decorated(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        print "Ran in", time.time() - start, "seconds"
        return result
    return decorated
 
def alealist(n):
    return [random.randint(0,10) for i in xrange(0,n)]
 
@time_this
def xx(li):
    dd = {}
    for index, item in enumerate(li):
        if item in dd:
            dd[item].append(index)
        else:
            dd[item] = [ index ]
    for item in dd.keys():
        if len(dd[item]) == 1:
            del dd[item]
    return dd
 
@time_this
def zz(L):
    n=len(L)
    DV=[]
    R=[]
    j=0
    for j in xrange(0,n):
        x=L[j]
        if x in DV:
            continue
        DV.append(x)
        H=[h for h in xrange(j,n) if L[h]==x]
        if len(H)>1:
            R.append((x,H))
    return R
 
L=alealist(4000000)
zz(L)
xx(L)  
 
"""
Ran in 4.30417990685 seconds
Ran in 1.07336902618 seconds
"""

30/06/2010, 03h09
dividee

Si dd est une liste, oui c'est une boucle déguisée; mais si dd est un dictionnaire (ou un ensemble), non. Enfin si mais pas vraiment :P. C'est une recherche dans une table de hachage. Normalement, c'est O(1) en moyenne. En théorie le worst case est O(n), mais en pratique c'est extrêmement rare. Personnellement je n'ai jamais rencontré de cas où un dictionnaire se comportait mal.

Au lieu d'une hashtable un dictionnaire Python pourrait être implémenté avec un arbre de recherche qui a un worst case de O(lg N), mais le worst case de l'implémentation par table de hachage est tellement rare que ça n'en vaut pas la peine. En plus, un arbre de recherche demande qu'il y ait une relation d'ordre sur les éléments, ce qui n'est pas nécessaire pour une hashtable.
30/06/2010, 10h21
manaliac

Merci tout le monde !! J'ai eu trop de réponses :mouarf: lol

Je vais essayer chaque méthode et utiliser celle qui me sert le plus !!

Merci encore pour toutes vos réponses !!

M.
30/06/2010, 10h30
manaliac

J'ai une nouvelle question toute bête que je vais aborder dans le même topic même si c'est ne pas relié à ma première question :

Quand je copie une liste dans une autre liste par un nv_liste = anc_liste

et que je fais des changements sur nv_liste est ce que cela affecte aussi anc_liste??

Cela me semble anormal!

( Je fais appel à une fonction qui appelle une liste, je la copie dans une nouvelle pour la garder et après les modifications sur ma nouvelle liste, quand je fais un :

Code:

print " ancienne liste",anc_liste

Ma liste est modifiée :aie: !!

M.
30/06/2010, 10h46
Zavonen
C'est normal, dans l'affectation, il y a passage de paramètres par références.
Après affectation les deux variables pointent sur le même objet.
Si tu veux une copie de ta liste dans Q et non la liste elle-même il faut faire appel à copy.
Eventuellement copy.deepcopy si la liste à copier n'est pas aplatie.
Code:

1 2 3 4 5 import copy L=[1,2,3] Q=copy.copy(L) Q[0]=0 print L
30/06/2010, 11h27
dividee

Citation:

Envoyé par Zavonen

De fait xx est plus rapide que zz avec un facteur constant qui dépend du nombre d'entiers d'instincts dans L.
Pour moi les algos sont équivalents en complexité.

Un facteur constant qui dépend de... :mrgreen:
Je crois que nous sommes violemment d'accord ;)

Si tu définis la "taille du problème" comme le nombre d'éléments d'une liste contenant un nombre constant d'entiers distincts, je suis d'accord (O(kn) = O(n) si k est constant). Mais moi je considérais le cas plus général où le nombre d'entiers distincts était un paramètre du problème.

Pour copier une liste on peut aussi écrire:

Code:

Q = L[:]

Voir 40 message(s) de cette discussion en une page