Tag: list

Recursion with Python

Python recursion

I had a bug that was difficult to trace down. I had a double list that I removed some of the elements using the remove() method, however, not all of the elements were removed. In fact, the code was removing only every other element. The bug turned out to be the call to remove() would shorten the list by one, and thus cause a skipping effect. For example:

some_lst = [['a','b'],['c','d'],['e','f']]

for i in some_lst:
  if re.match(regexToMatch, i):
     some_lst.remove(i)

I needed to rewind the list if remove() was called. At first, I thought this would be perfect for recursion. As it turned out, with the amount of data I needed the algorithm to search through, recursion was not a the best solution.

A recursive algorithm is one that calls itself. These functions will additionally have a decrementing counter or meet some condition to exit the recursive call. Having an exit condition is required since the function calls itself, otherwise, the function will loop until the system runs out of memory. This is a fast algorithm, however, it is not suited for all conditions. For example, small datasets recursion is best with regards to performance, but as the data grows, performance decreases quickly. This is because memory is consumed and the process incurs a context switch for every function call. The code below worked great on a small subset of data, but did not scale to what was needed for the project.

import re

def remove_processes(the_list: list):
    for (hostname, process) in the_list:
        for line in exclude_processes:
            try:
                if re.search(line.strip(), process):
                    the_list.remove([hostname,process])
                    remove_processes(theList)
            except ValueError:
                continue
    return the_list

Eventually, I replaced the for loop with while() and a counter. When a match is found, count is subtracted by 1 so every element in theList is evaluated. This also removes any duplicates.

def remove_processes(the_list):
    count = 0
    while count <= len(the_list) - 1:
        hostname = the_list[count][0]
        process = the_list[count][1]
        count += 1
    try:
        if re.search(exclude_process, process):
            the_list.remove([hostname, process])
            # reduce the count by 1 which resolves skipping
            # every other element
            count -= 1
    except ValueError:
        continue

    return the_list

Using Recursion with JSON

Here is another example of recursion. recurs() searches for k in a JSON document. If key isn’t found, it continues to the next element until all elements are searched. Once key is found, the function updates the value to “changed”. I used this function to remove passwords in a JSON document so it could be sent externally.

def recurs(k: str, json_doc: dict):
    """
    Takes a string, k and searches through json_doc
    :param k: search string
    :param json_doc: JSON / dictionary to search through for k
    """
    for i in json_doc.keys():
        if isinstance(json_doc[i], list):
            for p in range(len(json_doc[i])):
                json_doc[i][p][k] = 'changed'
        elif isinstance(json_doc[i], str):
           if k in json_doc:
               json_doc[k] = 'changed'
        elif isinstance(json_doc[i], dict):
           json_doc[i][k] = 'changed'
        try:
            for v in json_doc[i].values():
                if isinstance(v, dict):
                   return recurs(k, v)
        except AttributeError:
            pass
    return json_doc

Python – Working with Lists

 

One of the most common data types in Python is the list. A list is basically an array in other languages, however with a list, you can mix different data types in the same list. You can test this in the interactive shell:

>>> a_list = ['dog', 'cat', 1, 3, 1000]
>>> print(a_list)
['dog', 'cat', 1, 3, 1000]
>>> type(a_list[3])
<class 'int'>
>>> type(a_list[1])
<class 'str'>

Working with Python Lists

After declaring a list, we will need to either add data, delete data or assign data to another variable. In order do accomplish these tasks, we will need to use the append() method to add data, pop() or remove() to delete data, and subset the list to retrieve elements or assign to another variable.

Lists are subsetted by using the brackets ([]), a positional number and / or using a colon (:). Using a colon will allow a subset range.

Note: list elements start at 0 not 1.

>>> a_list = ['dog', 'cat', 'bat']
>>> b_str = a_list[0] # Take the first element and assign it to b_str
>>> b_str
'dog'
>>> type(b_str)
<class 'str'>
>>> a_list[-1] # Take the last element from the list 
'bat'
>>> a_list[-2] # Take the second to last element from the list
'cat'
>>> type(a_list[0]) # Lists can contain ints, strings, dictionaries or other lists
<class 'str'>
>>> type(a_list[-1])
<class 'int'>

Using a range with list elements sometimes is prone to defects in code. The number before the colon is the starting point, and the number after is the position to end minus 1. For example, a_list[1:4] starts at element 1 and ends at element 3, not 4. If you’ve developed in other languages, this will take some time to acclimate to Python’s way of list subscripting.

>>> a_list
['cat', 1, 3, 1000]
>>> a_list[0:3] # Take the first element through the second element
['cat', 1, 3]
>>> a_list[1:-1] # Take the second element through the second to last element
'cat', 1, 3]
Here is an example of a list containing another list and dictionary. Lists containing other lists is common in JSON or RESTful development, so becoming familiar with the syntax is important as you develop more complex or web-enabled applications. We still can call dictionary methods like keys() or values().
>>> b_list = ['this', 'new' 'list']
>>> a_list.append(b_list)
>>> a_list
['cat', 1, 3, 1000, ['this', 'newlist']]

>>> my_dct = {'language': 'Python'}
>>> a_list.append(my_dct)
>>> a_list
['cat', 1, 3, 1000, ['this', 'newlist'], {'language': 'Python'}]
>>> a_list[-1].keys() # We can call dictionary methods  
dict_keys(['language'])
>>> a_list[-1].values()
dict_values(['Python'])

 Simple Merge

Here are some examples of using Python lists by merging two lists into one. This simple example appends the values from second_list onto first_list.

firstList = ['dog', 'cat', 'tiger', 'rhnio']
secondList = ['2 x 18g', '250m swap']

for line in secondList:
   firstList.append(line)

Merge Lists Based on A Condition

The following code merges two lists, but will insert the second list after finding a specific string, in this case a hostname. outerList.pop(0) removes the first element from the list, and then inserts the remaining list into firstList.

firstList = ['dog', 'cat', '2', '500', 'daeo', 'DL580', '8', '128']
secondList = [['dog', '2 x 18g', '250m swap'], ['daeo', '4 x 146g', '16g swap']]

try:
    for outerList in secondList:
        systemName = outerList.pop(0)
        for innerList in outerList:
            indexPos = firstList.index(systemName)
            firstList.insert(indexPos + 1, innerList)
except ValueError as err:
    print('ValueError: {}'.format(err))