Python List Optimization: Efficient Management of Duplicate Elements

You pull data from a few sources and end up with several lists. Some values show up in more than one of them. I wanted every value to live in exactly one list, and I wanted it to stay in the smallest list it appeared in, so the lists come out more even.

An example:

lists = [
    [1, 2, 3, 4],
    [3, 4, 5, 6],
    [2, 3, 7, 8],
]

3 is in all three lists. 2 and 4 are in two each. After the cleanup:

[[1, 2, 4], [5, 6], [3, 7, 8]]

How it decides

Values are handled in the order they first appear. For each shared value, look at the lists that hold it and pick the one that is shortest right now. If two lists have the same length, the earlier one wins. The value stays there, it is removed from the others, and their sizes go down.

“Right now” matters. Taking 3 out of the first two lists makes them shorter, and that changes where 4 ends up. So the result depends on order. For splitting work between buckets that is good enough, but it is a greedy rule, not the best possible split.

What was wrong with my first version

I wrote a ListOptimizer class for this a while ago. Reading it again, I found three problems.

It was slow. For every shared value it rebuilt whole lists with a list comprehension. With a lot of shared values that becomes quadratic. Five lists of 20,000 numbers each, with half of every list shared with the next one, took 72 seconds on my server.

It changed the caller’s data. self.lists was the same list object that was passed in, so after optimize() the original variable had changed too. Nothing in the name says it will do that.

The check meant something else. It counted how many times a value appeared, not how many lists it appeared in. A value repeated inside a single list passed the check, and then nothing happened to it because there was only one list to keep it in. No wrong output, just a condition that did not say what it meant.

The new version

Two passes. First decide where each value lives, then build each list once.

from collections import Counter

def spread_out(lists):
    counts = [Counter(lst) for lst in lists]
    sizes = [len(lst) for lst in lists]

    where = {}
    for i, c in enumerate(counts):
        for x in c:
            where.setdefault(x, []).append(i)

    home = {}
    for x, places in where.items():
        best = min(places, key=lambda i: (sizes[i], i))
        home[x] = best
        for i in places:
            if i != best:
                sizes[i] -= counts[i][x]

    return [[x for x in lst if home[x] == i] for i, lst in enumerate(lists)]

where maps each value to the lists that contain it. home is the decision: the one list each value stays in. Counter keeps how many times a value appears in each list, so when it leaves a list the size drops by the right amount, even if it was there twice.

I checked it against the old class on 3,000 random inputs and the output was identical every time. The same five big lists now take 0.38 seconds instead of 72. It returns new lists and leaves the input alone.

Repeats inside one list

spread_out only deals with values shared between lists. If you also want no repeats inside a list, run this on the result:

result = [list(dict.fromkeys(lst)) for lst in spread_out(lists)]

dict.fromkeys keeps the first occurrence of each value and keeps the order.

Limits

The values are used as dictionary keys, so they must be hashable. Numbers, strings and tuples work. Lists and dicts do not; turn them into tuples or pick an ID first.

Where this is useful

Giving tasks to several workers without two of them doing the same item. Cleaning exports from different systems before merging them. Anything where the same ID can land in more than one bucket.

The full code with an example is on GitHub Gist. The old version is still there in the revision history if you want to compare.