Efficient searching partial strings in Python lists

user_8560319 0
Viewed 520

Looking for an efficient method to search for partial strings in Python (3.6+) lists.

I have two lists. listA is a list of strings of pathname + a unique filename:

['/pathname/uniquestring.ext', '/pathname/uniquestring.ext', '/pathname/uniquestring.ext' ...]

(created using glob(), filenames are all given and already exist)

listB is a list of dictionaries. Each dictionary has the same set of keys, but unique values.

[{key1:value1, key2:value2}, {key1:value3, key2:value4}, ...]

(also already given)

One key:value pair in each dictionary in listB will have a value that is contained in one unique item in listA.

However, the position of the value as it appears in each item of listA is indeterminate.

What I wanted was: for each item in listB, find the item in listA that contains a substring matching the k:v pair in the dict, and create a new dict (or list of tuples) as a "lookup table" (the goal was to correct a corrupted exif creation date in a set of image files).

Example:

listA = ['/pathname/abdce_654321.ext', '/pathname/a3b4c5_123456.ext', '/pathname/cbeebie_645321_abcde.ext', ...]

listB = [{"id": "123456", "create_date": "23/05/2014"}, ...]

new_dict = {"/pathname/a3b4c5_123456.ext": "23/05/2014, ...}

I've got exactly what I want from a dict comp as follows:

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

But, even for my very small files (~5500 items) this takes 12s on my (admittedly rather old) laptop.

Presumably this is because I have to iterate over the whole of listB ~5500 times using my method.

Is there a more efficient way to do this in Python?

(nb i'm not seeking advice on how to correct exif data with python; this is a generalised q about string lookups in lists)

CORRECTIONS & CLARIFICATIONS

  1. I neglected to place quotes around the value '123456' in my example, implying of course that it is an integer; In the real-world data, it isn't, and nor are any of the equivalent values in the actual data I dealt with.
  2. The 'id' substring as it appears in a listA item is almost always delimited by underscores, but does not always appear in the same position in the whole string; So, performing a split('_') for instance on each item won't always place the 'id' string at position [-1] or [-2] or [-3], although [-1] would take care of ~80% of cases.
  3. All 'id's are unique, they do not appear more than once in either list; each filename is unique in listA; each 'id' never appears in more than one dictionary.

Thanks for the interest from everyone so far btw.

list dictionary python string
3 Answers

I can see what the two comments are getting at. The big question is: do we need to use in because that's only necessary if we don't know where the id appears in the path string? If it's always in a particular place we can extract it and use a constant-time lookup:

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}

which is only O(N) as opposed to your current O(N**2).

user_48194490

First of all, here are generalised lists to help with testing:

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}

Running that, with 10 000 values, took my machine 8.8 seconds on average. (9.5 seconds if I print the dictionary after)

Now if we compile that code to Cython (A python superset that runs on C), That time came down to 4.4 seconds for me.

See code below

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
user_108464670

I wrote a little test bench that generates random data that's kind of like yours, and tries out your original dictionary comprehension and a version that has optimizations such as early-outing when it finds a match and removing used tags.

Both match (your original) and match2 (mine) print out the number of results, to try and ensure they work equivalently.

The results are rather telling... hope this helps.

Numbers for 5000 / 10000 items on my MBP:

  • original: 1.771 / 7.391
  • optimized: 0.054 / 0.203
  • without removing used tags (if that's not an acceptable business rule): 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))
AKX_516850
Related