Python Deep list comparison

10,230

Solution 1

A very crude comparison can be done by comparing the str(). Certainly not the best way to do it, but considering the complexity of your lists it might be alright.

If you want something more solid, you could write a recursive function to take care of it.

Solution 2

You can always pickle the objects up and compare them as strings. Converting them to a JSON string is probably one of the easiest ways. I suspect that there is a more resource-efficient way of doing this, but it works just fine. Here is an example:

>>> from simplejson import dumps
>>> ls1 = [1, [2, 3], [4, [5, 6]]]
>>> ls2 = [1, [2, 3], [4, [5, 6]]]
>>> dumps(ls1) == dumps(ls2)
True
>>>

Solution 3

I'm not sure comparing string representations is the way to go, but if performance is an issue I guess you can benchmark. Here's a quick attempt at an implementation of deep/recursive list comparison:

from itertools import izip

def list_compare(a, b):
    if type(a) != type(b):
        return False
    if type(a) != list:
        return a == b
    if len(a) != len(b):
        return False
    for a_, b_ in izip(a, b):
        if not list_compare(a_, b_):
            return False
    return True

It compares lists recursively and non-list items using the regular equality operator.

Share:
10,230
rgravell
Author by

rgravell

Updated on June 04, 2022

Comments

  • rgravell
    rgravell over 1 year

    I'm currently writing a sudoku solving program in python just for fun. Here's what I currently have:

    #!/usr/bin/env python
    """Reads in a file formatted with nine lines each of which has nine characters
    corresponding to a sudoku puzzle.  A blank is indicated by the value '0'
    Eventually should output a solution to the input puzzle"""
    
    import sys
    
    class cell:
        value = 0
        """Value of 0 means it is undetermined"""
    
        def __init__(self, number):
            self.value = number
            self.possible = [2, 2, 2, 2, 2, 2, 2, 2, 2]
            """Possibility a given value can be the number. 0 is impossible, 1 is definite, 2 is maybe"""
    
    
    
        def selfCheck(self):
            """Checks if the cell has only one possible value, changes the value to that number"""
            if self.value == 0:
                  if self.possible.count(2) == 1:
                    """If there's only one possible, change the value to that number"""
                    i = 1
                    for item in self.possible:
                        if item == 2:
                            self.value = i
                            self.possible[i-1] = 1
                        i+=1
    
    def checkSection(section):
        """For any solved cells in a section, marks other cells as not being that value"""
        for cell in section:
            if cell.value != 0:
                for otherCell in section:
                    otherCell.possible[cell.value-1] = 0
    
    def checkChunk(chunk):
        """Checks a chunk, the set of rows, columns, or squares, and marks any values that are impossible for cells based on that
        chunk's information"""
        for section in chunk:
            checkSection(section)
    
    def selfCheckAll(chunk):
        for section in chunk:
            for cell in section:
                cell.selfCheck()
    
    cellRows = [[],[],[],[],[],[],[],[],[]]
    cellColumns = [[],[],[],[],[],[],[],[],[]]
    cellSquares = [[],[],[],[],[],[],[],[],[]]
    
    infile = open(sys.argv[1], 'r')
    """Reads the file specified on the command line"""
    
    i = 0
    for line in infile:
        """Reads in the values, saves them as cells in 2d arrays"""
        line = line.rstrip('\n')
        for char in line:
            row = i/9
            column = i%9
            newcell = cell(int(char))
            cellRows[row].append(newcell)
            cellColumns[column].append(newcell)
            row = (row/3)*3
            column = column/3
            square = row+column
            cellSquares[square].append(newcell)
            i+=1
    i = 0
    while i<50:
        checkChunk(cellRows)
        checkChunk(cellColumns)
        checkChunk(cellSquares)
        selfCheckAll(cellRows)
    
        i+=1
    
    displayRow = []
    for row in cellRows:
        for cell in row:
            displayRow.append(str(cell.value))
    
    i = 0
    while i < 9:
        output1 = ''.join(displayRow[9*i:9*i+3])
        output2 = ''.join(displayRow[9*i+3:9*i+6])
        output3 = ''.join(displayRow[9*i+6:9*i+9])
        print output1 + '  ' + output2 + '  ' + output3
        if i%3 == 2:
            print
        i+=1
    

    My problem is with:

    i = 0
    while i<50:
        checkChunk(cellRows)
        checkChunk(cellColumns)
        checkChunk(cellSquares)
        selfCheckAll(cellRows)
    
        i+=1
    

    I want to run the code until it detects that there is no change from the previous iteration instead of the currently hard coded 50 times. This could potentially be because there is no longer a logical next step (need to start brute forcing values), or the puzzle is completely solved. Either way, I need a deep copy of one of my current data sets for the puzzle (say cellRows) to compare to what changes may take place to the actual copy when it goes through my checkChunk functions.

    Is anything like this available in Python? (If there's a better way to check if I'm finished, that would also work, although at this point I'm more interested in if I can do a deep comparison.)

    EDIT - I attempted using copy.deepcopy. While this created a good deep copy, checking equality between the two using '==' always returned false.

  • rgravell
    rgravell over 10 years
    I tried copy.deepcopy and that's great for making a deep copy (obviously). However, once I have the deep copy I need a deep comparison. Using '==' between the original and the deep copy returns false. As near as I can tell this is because because it checks the items in the list, but only checks the addresses, not the contents of the structure I made.