Find string matches count in list using Python
Question: I read a text file for some analysis, each word is appended to a list and
given an id

    
    
    #!/usr/bin/python3
    with fi as myfile:
      for line in myfile:
        for item in line.split(' '):
          db[0].append(id_+1)
          db[2].append(item)
          ...more stuff
    

Then I search for each word through the list to find its matches, and store
the count as **sim1**. If a match is found, I test if the next word matches
the consecutive one as well, and store its count as **sim2**. Similarly for
**sim3**. My code looks like:

    
    
    for i in range(id_-3):
      sim1=0
      sim2=0
      sim3=0
      for j in range(id_-3):
        if i==j:  continue;
        if db[2][i] == db[2][j]:
          sim1 += 1
          if db[2][i+1] == db[2][j+1]:
            sim2 += 1
            if db[2][i+2] == db[2][j+2]:
              sim3 += 1
      db[3].append(sim1)
      db[4].append(sim2)
      db[5].append(sim3)
    

This works, but it's too slow! I believe python provides faster search
methods, but I'm still a Py newbie!


Answer: The slowness in your algorithm mainly comes from the fact that you have an
inner loop which iterates len(db[2]) times contained within an outer loop
which also iterates len(db[2]) times. This means the inner code is executing
len(db[2])^2 times. If your file is large and you are parsing 5000 words, for
example, then the code runs 5000^2 = 25,000,000 times!

So, the angle of attack to solve the problem is to find a way to eliminate or
significantly reduce the cost of that inner loop. Below is an example solution
which only needs to iterate through len(db[2]) one time, and then does a
second separate loop which iterates through a much smaller set of items. There
are a few inner loops within the second iteration, but they run an even
smaller number of times and have almost inconsequential cost.

I timed your algorithm and my algorithm using a text file which weighed in at
about 48kb. Your algorithm averaged about 14 seconds on my computer and my
algorithm averaged 0.6 seconds. So, by taking away that inner loop, the
algorithm is now over 23 times faster. I also made some other minor
optimizations, such as changing the comparison to be between numbers rather
than text, and creating the storage arrays at full size from the start in
order to avoid using append(). Append() causes the interpreter to dynamically
increase the array's size as needed, which is slower.

    
    
    from collections import defaultdict
    
    # Create zero-filled sim1, sim2, sim3 arrays to avoid append() overhead
    len_ = len(db[2]) - 2
    for _ in range(3):
        db.append([0] * len_)
    
    # Create dictionary, containing d['word'] = [count, [indexes]]
    # Do just one full iteration, and make good use of it by calculating
    # sim1 (as 'count') and storing an array of number indexes for each word,
    # allowing for a very efficient loop coming up...
    d = defaultdict(lambda: [0, []])
    for index, word in enumerate(db[2]):
        if index < len_:
            # Accumulate sim1
            d[word][0] += 1 
        # Store all db[2] indexes where this word exists
        d[word][1].append(index) 
    
    # Now loop only through words which occur more than once (smaller loop)
    for word, (count, indexes) in d.iteritems():
        if count > 1:
            # Place the sim1 values into the db[3] array
            for i in indexes:
                if i < len_:
                    db[3][i] = count - 1
                    # Look for sim2 matches by using index numbers
                    next_word = db[2][i+1]
                    for next_word_index in d[next_word][1]:
                        if next_word_index - 1 != i and next_word_index - 1 in indexes:
                            # Accumulate sim2 value in db[4]
                            db[4][i] += 1
                            # Look for sim3 matches
                            third_word = db[2][i+2]
                            if third_word == db[2][next_word_index + 1]:
                                # Accumulate sim3 value in db[5]
                                db[5][i] += 1
    

