Recherche efficace de chaînes partielles dans les listes Python

Je peux voir à quoi servent les deux commentaires. La grande question est: devons-nous utiliser dans parce que cela n'est nécessaire que si nous ne savons pas où l'id apparaît dans la chaîne de chemin? Si c'est toujours à un endroit particulier, nous pouvons l'extraire et utiliser une recherche à temps constant:

def extract_id(path):
    # todo
ids = {item['id']: item['create_date'] for item in listB}
new_dict = {path: ids[extract_id(path)] for path in listA}

qui est seulement O (N) par opposition à votre O (N ** 2) .

Tout d'abord, voici des listes généralisées pour vous aider à tester:

cpdef dict main():
    cdef int x
    cdef int number
    cdef char j
    cdef dict i

    listA = ['/pathname/abdce_%s.ext' % str(x) for x in range(10000)]

    listB = [{'id': str(number), "create_date": "23/05/2014"} for number in range(10000)]

    hello = {j: i['create_date'] for j in listA for i in listB if i['id'] in j}

    return hello

L'exécution de cela, avec 10 000 valeurs, a pris en moyenne 8,8 secondes à ma machine. (9,5 secondes si j'imprime le dictionnaire après)

Maintenant, si nous compilons ce code en Cython (un sur-ensemble python qui fonctionne sur C), ce temps est descendu à 4,4 secondes pour moi.

Voir le code ci-dessous

listA = ['/pathname/abdce_%s.ext' % str(x) for x in range(10000)]

listB = [{'id': str(number), "create_date": "23/05/2014"} for number in range(10000)]

hello = {j: i['create_date'] for j in listA for i in listB if i['id'] in j}

J'ai écrit un petit banc de test qui génère des données aléatoires qui sont un peu comme les vôtres, et essaie votre compréhension originale du dictionnaire et une version qui a des optimisations telles que la sortie précoce quand il trouve une correspondance et la suppression des balises utilisées.

match (votre original) et match2 (le mien) affichent le nombre de résultats, pour essayer de s'assurer qu'ils fonctionnent de manière équivalente.

Les résultats sont plutôt révélateur ... j'espère que cela vous aidera.

Chiffres pour 5000/10 000 éléments sur mon MBP:

• original: 1.771 / 7.391
• optimisé: 0,054 / 0,203
• sans supprimer les balises utilisées (si ce n'est pas une règle métier acceptable): 0,917 / 3,789

import random
import timeit
import string

random.seed(42)


def genrand(n):
    return "".join(
        random.choice(string.ascii_lowercase + string.digits) for x in range(n)
    )


filenames = []
tags = []

for x in range(5000):
    id = genrand(8)
    filenames.append("/pathname/%s_%s.ext" % (genrand(6), id))
    if random.random() < 0.95:
        tags.append({"id": id, "date": "date for %s" % id})


def match():
    x = {j: i["date"] for j in filenames for i in tags if i["id"] in j}
    print(len(x))


def match2():
    x = {}
    available_tags = tags[:]
    for filename in filenames:
        for tag in available_tags:
            if tag["id"] in filename:
                x[filename] = tag
                available_tags.remove(tag)  # we've used this tag, remove it
                break
    print(len(x))


print(timeit.timeit(match, number=1))
print(timeit.timeit(match2, number=1))