Discussion :

[manaliac]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[dividee]

euh...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

indices = range(len(liste))

non ?

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

Sélectionner tout - Visualiser dans une fenêtre à part

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 !

[wiztricks]

Un truc comme çà?

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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]}

[Zavonen]

Ou comme ça ?

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Sélectionner tout - Visualiser dans une fenêtre à part

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

[wiztricks]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Zavonen]

Alors qu'on peut faire cela en une ligne

On croirait du Haskell !

[wiztricks]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Sélectionner tout - Visualiser dans une fenêtre à part

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 ]

[Zavonen]

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

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[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.
-W

[dividee]

Ma version en détails:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]

[Zavonen]

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.

[dividee]

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).

[Zavonen]

Il me semble que l'instruction:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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
"""

[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 . 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.

[manaliac]

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

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

Merci encore pour toutes vos réponses !!

M.

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

Sélectionner tout - Visualiser dans une fenêtre à part

print " ancienne liste",anc_liste

Ma liste est modifiée !!

M.

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

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
import copy
L=[1,2,3]
Q=copy.copy(L)
Q[0]=0
print L

[dividee]

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

Sélectionner tout - Visualiser dans une fenêtre à part

Q = L[:]