Encode Python lists as indexes of unique values

Question

I'd like to represent an arbitrary list as two other lists. The first, call it values, containing the unique elements in the original list, and the second, call it codes, containing the index in values of each element in the original list, in such a way that the original list could be reconstructed as

orig_list = [values[c] for c in codes]

(Note: this is similar to how pandas.Categorical represents series)

I've created the function below to do this decomposition:

def decompose(x):
    values = sorted(list(set(x)))
    codes = [0 for _ in x]
    for i, value in enumerate(values):
        codes = [i if elem == value else code for elem, code in zip(x, codes)]
    return values, codes

This works, but I would like to know if there is a better/more efficient way of achieving this (no double loop?), or if there's something in the standard library that could do this for me.

---

Update:

The answers below are great and a big improvement to my function. I've timed all that worked as intended:

test_list = [random.randint(1, 10) for _ in range(10000)]
functions = [decompose, decompose_boris1, decompose_boris2,
             decompose_alexander, decompose_stuart1, decompose_stuart2,
             decompose_dan1]
for f in functions:
    print("-- " + f.__name__)
    # test
    values, codes = f(test_list)
    decoded_list = [values[c] for c in codes]
    if decoded_list == test_list:
        print("Test passed")
        %timeit f(test_list)
    else:
        print("Test failed")

Results:

-- decompose
Test passed
12.4 ms ± 269 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
-- decompose_boris1
Test passed
1.69 ms ± 21.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
-- decompose_boris2
Test passed
1.63 ms ± 18.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
-- decompose_alexander
Test passed
681 µs ± 2.15 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
-- decompose_stuart1
Test passed
1.7 ms ± 3.42 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
-- decompose_stuart2
Test passed
682 µs ± 5.98 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
-- decompose_dan1
Test passed
896 µs ± 19.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

I'm accepting Stuart's answer for being the simplest and one of the fastest.

Answer 1

I’m quite happy with this solution, although I am still trying to find a better one.

---

Code

def decompose(original_list: List[Any]) -> Tuple[List[int], Dict[int, Any]]: 
    code_to_elem = dict(enumerate(set(original_list)))
    elem_to_code = {v: k for k, v in code_to_elem.items()}
    encoded_list = [elem_to_code[elem] for elem in original_list]
    return encoded_list, code_to_elem

---

Test run

# t_list for test_list
t_list = [1, 2, 19, 3, 2, 19, 2, 3, 19, 1, 1, 3]

t_encoded, t_decoder = decompose(t_list)

t_decoded = [t_decoder[curr_code] for curr_code in t_encoded]

Here are the contents of the important variables:

• t_list: [1, 2, 19, 3, 2, 19, 2, 3, 19, 1, 1, 3]
• t_encoded: [1, 2, 3, 0, 2, 3, 2, 0, 3, 1, 1, 0]
• t_decoder: {0: 3, 1: 1, 2: 2, 3: 19}
• t_decoded: [1, 2, 19, 3, 2, 19, 2, 3, 19, 1, 1, 3]

---

Let me know if you have any questions :)

Answer 2

This would count as an answer even if it is merely an improvement on Boris's answer.

I would use index_of_values.append(values.setdefault(elem, len(values))) as the loop body as that reduces three dict lookups to one and keeps the branch outside the interpreter. One might even create locals for the two methods to not repeatedly do lookups for them. But it seems that the savings of doing both is only 7%.

But using the insane looking values = defaultdict(lambda: len(values)) gives a 23%.

from collections import defaultdict

def decompose(x):
    values = defaultdict(lambda: len(values))
    index_of_values = []
    _append = index_of_values.append
    for elem in x:
        _append(values[elem])
    return list(values), index_of_values

It is even better if the loop is replaced by a map:

def decompose(x):
    values = defaultdict(lambda: len(values))
    index_of_values = list(map(values.__getitem__, x))
    return list(values), index_of_values

Gives 57%. I would have caught that if I had been looking at the output of the function. Also get evidently doesn't trigger the factory. I don't know why it doesn't.

If the dict does not retain insertion order:

return sorted(values, key=values.get), index_of_values

Answer 3

You can do this, IIUC, with cummin:

df['newgroup'] = df.reset_index().groupby('group')['index'].cummin()                                                                                                                            

In [1579]: df                                                                                                                                                                                              
Out[1579]: 
    group  newgroup
0       5         0
1       4         1
2       5         0
3       6         3
4       7         4
5       8         5
6       5         0
7       3         7
8       2         8
9       5         0
10      6         3
11      7         4
12      8         5
13      8         5
14      5         0

Answer 4

You can use a simple index lookup:

def decompose(x):
    values = sorted(set(x))
    return values, [values.index(v) for v in x] 

If more time-efficiency is needed (because x is very large) then this can be achieved (in exchange for some memory overhead) by representing values as a dictionary:

def decompose(x):
    values = sorted(set(x))
    d = {value: index for index, value in enumerate(values)}
    return values, [d[v] for v in x]

If sorting is not needed (or not possible for some reason) then replace sorted with list in the above.

Answer 5

Create a dictionary where the keys are the unique values and they map to their index in the keys (dictionaries keep order starting with CPython 3.6). You do this by iterating over the list, if an element is not in the dictionary, you add it to the dictionary and map it to the length of the dictionary at the time you added it. Then you look up the element's index in the dictionary and append it to the list. Then you return just the keys, along with the list of indexes.

def decompose(x):
    values = {}
    index_of_values = [values.setdefault(elem, len(values)) for elem in x]
    return list(values), index_of_values

This is linear time and space complexity. Use it like this:

>>> decompose([2, 1, 1, 1, 131, 42, 2])
([2, 1, 131, 42], [0, 1, 1, 1, 2, 3, 0])

---

Using the side effect of a list comprehension is generally frowned upon, so you might want to write it out this function more explicitly:

def decompose(x):
    values = {}
    index_of_values = []
    for elem in x:
        if elem not in values:
            values[elem] = len(values)
        index_of_values.append(values[elem])
    return list(values), index_of_values

Answer 6

If you need some thing like pandas.Caterogical

arbi_arr=[1, 2, 3, 1, 2, 3]

value=list(dict.fromkey(arbi_arr))
code=list(range(0, len(arbi_arr)))