1
votes

Le moyen le plus rapide de trouver toutes les positions de chaque caractère distinct dans une chaîne

Supposons que nous ayons une chaîne, disons, "122113" et que nous sommes censés trouver toutes les occurrences de chaque caractère de la chaîne. em >

Une approche naïve sera comme ceci:
string = str( raw_input() )  # for example: "122113"
distinct_char = list( set(string) )
occurrences=[]
for element in distinct_char:
    temp=[]
    for j in range(len(string)):
        if(string[j]==element):
            temp.append(j)
    occurrences.append(temp)
print(occurrences)  # output for "122113" would be [[0, 3, 4], [1, 2], [5]]
                    #because 1 occurrs at : 0, 3, 4
                    #        2 occurrs at : 1, 2
                    #        3 occurrs at : 5
Mais, c'est assez lent si la longueur de la chaîne est grande . Alors, existe-t-il une solution plus rapide?

(Considérez que la chaîne est uniquement composée d'alphabets anglais inférieurs et que la longueur de la chaîne peut être de 10 $ ^ 12 $

string python

2 commentaires

Astuce: parcourez une fois la liste et mettez à jour un dictionnaire qui mappe les caractères aux positions au fur et à mesure

Je seconde cela, il évolue linéairement.

5 Réponses :

2
votes

Vous devez utiliser un defaultdict (avec une liste vide comme valeur par défaut) et mettre à jour la liste des index tout en itérant dans la chaîne:

occurences = [l for l in occurences.values()]

Ensuite, utilisez une compréhension de liste pour obtenir votre liste d'occurrences :

from collections import defaultdict
string = str(raw_input())
occurences = defaultdict(list)
for i, c in enumerate(string):
  occurences[c].append(i)
print occurences

2 commentaires

fonctionnera-t-il assez vite si la ou les longueurs deviennent significativement importantes?

@TuhinKarmakar Eh bien, cela a pris 5 secondes pour une longue chaîne de 10000000 sur mon ordinateur super lent, vous pouvez tester par vous-même si vous voulez voir si c'est rapide ou non.

1
votes

(Désolé, ma réponse précédente a mal compris la question.)

Vous pouvez utiliser un collections.defaultdict pour cela:

{
    "a": [0, 10],
    "b": [1, 11],
    "c": [2, 12],
    "d": [3, 13],
    "e": [4, 14],
    "f": [5, 15],
    "g": [6, 16],
    "h": [7, 17],
    "i": [8, 18],
    "j": [9, 19],
}

indices sera alors un dict qui mappe chaque caractère dans leurs indices (exemple évidemment pas pour le very_long_string ci-dessus, mais un plus court).

import collections

very_long_string = "abcdefghij" * 1000000

indices = collections.defaultdict(list)
for i, c in enumerate(very_long_string):
    indices[c].append(i)

Cela prend environ 3 secondes pour 10 000 000 de caractères sur ma machine.

0 commentaires

0
votes

Une solution possible est de convertir les caractères de chaîne en nombres et d'utiliser le nombre pour incrémenter les valeurs dans un tableau. Le code pourrait être le suivant:

import numpy as np

def alph_to_num(alph):
    return ord(alph.lower())-97

string='alsblnasdglasdaoerngeaglbneronbiwernblnerl'
array=np.zeros(26)

for alph in string:
    index=alph_to_num(alph)
    array[index]=array[index]+1
print(array)

ce qui donne: [5. 4. 0. 2. 5. 0. 3. 0. 1. 0. 0. 6. 0. 6. 2. 0. 0. 4. 3. 0. 0. 0. 1. 0. 0. 0.]

Ici, j'ai créé le tableau de longueur 26 puisque vous savez qu'il ne s'agit que de lettres minuscules anglaises. Cela signifie également qu'il est plus facile d'interpréter la liste résultante.

0 commentaires

0
votes

Aucune solution d'importation - étant donné que vous savez que ce n'est que des minuscules, vous pouvez précréer une liste de listes de taille 26, puis en itérant simplement ajouter l'index de chaque caractère trouvé à la position appropriée.

input_lst="abcdefgaabbfegddsa"
occurence_lst = [[] for i in range(26)]
for index in range(len(input_lst)):
    occurence_lst[ord(input_lst[index]) - 97].append(index)

print(occurence_lst)

[0, 7, 8, 17], [1, 9, 10], [2], [3, 14, 15], [4, 12], [5, 11], [6, 13], [], [], [], [], [], [], [], [], [], [], [], [16], [], [], [], [], [], [], []]

0 commentaires

0
votes

En supposant Python 2.7, option 1 (j'ai fait le dictionnaire pour que l'on puisse dire quelle lettre correspondait aux indices):

s = raw_input()
occurances = {}

for i,let in enumerate(s):
  if let in occurances:
    occurances[let].append(i)
  else:
    occurances[let] = [i]

print(occurances)

temps moyen pour 10000 exécutions sur '122113': 2.55961418152e -06

temps moyen pour 10000 exécutions sur 'a; lkdsfowquebtgafdnga; llkl; uihnbr, afdh; glakhhehjehrjehjeoguhaberna': 2,39794969559e-05

temps moyen pour 500 exécutions sur 'alkdsfowquebtgafdngallkl' * 1000: 0,00993875598907

option 2:

s = raw_input()
occurances = {}
pos = 0

for let in s:
  if let in occurances:
    occurances[let].append(pos)
  else:
    occurances[let] = [pos]
  pos += 1

print(occurances)

durée moyenne de 10000 exécutions sur «122113»: 7,02269077301e-06

moyenne temps pour 10000 exécutions sur 'a; lkdsfowquebtgafdnga; llkl; uihnbr, afdh; glakhhehjehrjehjeoguhaberna': 2,39794969559e-05

temps moyen pour 500 exécutions sur 'alkdsfowquebtgafdngallkl' * 1000: 0,00974810600281

(Temps de test depuis repl.it exécutant python 2.7)

Modifier: Selon exactement comment il est utilisé dans le script, defaultdict peut être plus rapide ou plus lent que d'utiliser simplement dict

0 commentaires