how to build a tuplelist class in python whch is efficient when searching?-CodePudding

gurobi builds a tuplelist class.see here. It says This is a custom sub-class of the Python list class that is designed to allow you to efficiently build sub-lists from a list of tuples. To be more specific, you can use the select method on a tuplelist object to retrieve all tuples that match one or more specified values in specific fields. I have tested its select method, it's very efficient. Does anyone know how to implement a tuplelist class like gurobi's?

CodePudding user response：

# Search function with parameter list name
# and the value to be searched
def search(Tuple, n):

    for i in range(len(Tuple)):
        if Tuple[i] == n:
            return True
    return False

# list which contains both string and numbers.
Tuple= (1, 2, 'sachin', 4, 'Geeks', 6)


# Driver Code
n = 'Geeks'

if search(Tuple, n):
    print("Found")
else:
    print("Not Found")

CodePudding user response：

The simplest solution would be to pair the list with a dict per entry in your tuples. The key of the dict is a tuple value. The value of the dict is a set of indices into the list. Something like this:

class TupleList:
    def __init__(self):
        self.lst = []
        self.dictlist = []

    def append(self, tup):
        dictlist = self.dictlist
        if dictlist and len(tup) != len(dictlist):
            raise ValueError("All tuples must have same length")
        lst = self.lst
        lst.append(tup)
        tupidx = len(lst)
        if not dictlist: # first entry
            self.dictlist = [{entry: set((tupidx,))} for entry in tup]
            return
        for entry, dict_ in zip(tup, dictlist):
            set_ = dict_.setdefault(entry, set())
            set_.add(tupidx)

    def select(self, *args):
        # TODO: Implement '*' wildcard
        dictlist = self.dictlist
        if not dictlist:
            return []
        if len(dictlist) != len(args):
            raise KeyError("Wrong number of tuple values")
        tupsets = (dict_[arg] for dict_, arg in zip(dictlist, args))
        try:
            intersect = next(tupsets)
            for tupset in tupsets:
                intersect = intersect.intersection(tupset)
        except KeyError: # value not present
            return []
        lst = self.lst
        return [lst[idx] for idx in sorted(intersect)]