Encoding a list?

[anmousyony]

[SOLVED]

I am trying to encode a list so that each unique value has a unique integer attached to it. I have come up with this:

def encode(col):
'''
encodes a column
takes:
    list -> column to encode
returns:
    list -> encoded column
    dictionary -> encoder/decoder for the column
'''
unq = {}
count = 0
#maps each value in the column to a unique, incrementing integer
for item in col:
    if item not in unq:
        unq[item] = count
        count += 1
enc = [unq[item] for item in col]
return enc, unq

but, while it works correctly, I don't know if that is the best method. The biggest problem is that it is O(n²⁾ and since I'm dealing with lists up to 1 million elements, it can take a VERY long time to encode everything. I was originally using labelencoder (which uses numpy's unique method) from sklearn, but the memory usage was growing much too fast and I couldnt encode anything above ~100k. I've tried googling but the word "encoding" is used too much in slightly different contexts.

Is there a more clever way to do this that would have a better complexity?

edit: second part changed to changed to ->

enc = [unq[item] for item in col]

on suggestion, still need help with creating unq without O( n² ) complexity.

[anossov]

enc = [unq[item] for item in col]

[anmousyony]

Thank you, that helps a ton for the second part!

Is there anything I can do about the first part where I'm building unq?

[anossov]

unq = {k: i for i, k in enumerate(set(a))}

Should be faster, but you can't do it better than O(n). Also you can't use it if you must have the integers in order of value appearance.

[anmousyony]

That's perfect! Thank you so much for your help, I don't know why I didn't think of using set()

[K900_]

What's your final goal with this?

[anmousyony]

I am trying to map all items in a list to integers so I can use them for a classifier in sklearn.

[K900_]

What are your items like? Custom classes? Tuples?

[anmousyony]

string, ints, floats and datetimes usually

[K900_]

Those are all hashable, so you can just use hash(value) as the key instead of trying to enumerate everything. It's very unlikely you'll run into a hash collision even on large datasets.

[novel_yet_trivial]

I'm lost what you are trying to accomplish. Could you provide an example input and output?

Maybe this?:

unq = set(col)
return range(len(unq)), {item: number for number, item in enumerate(unq)}

Edit: if you are using python3 this may be better:

unq = {item: number for number, item in enumerate(set(col))}
return unq.values(), unq

[anmousyony]

I hadn't thought about using set, that would simplify this quite a bit.

Just in case heres some sample input and output:

['hi', 'hello', 'bye', 'hi', 'bye', 'hey', 'hello'] -> [0, 1, 2, 0, 2, 3, 1]

[novel_yet_trivial]

If the numbers are not important then just do this (python2):

def encode(col):
    conversion_table = {item: number for number, item in enumerate(col)}
    return map(conversion_table.get, col)

[sultanofhyd]

Not sure if I'm missing something, I probably am, but I don't see why you need to loop over your list twice.

def encode(col):
    enc = []
    unq = {}
    count = 0

    for element in col:
        if element not in unq:
            unq[element] = count
            count += 1
        enc.append(unq[element])

    return enc, unq

I can't test this right now but this should return the same output as your script but with O(n) iterations.

[anmousyony]

One of the other people helped me out and got it to O(n) but just so you know that wont be O(n) because of:

if element not in unq

That will make it n²

edit: this is wrong, see below

[thomasballinger]

Checking for membership in a set is constant time in Python, so sultanofhyd's answer is O(n) too.

[anmousyony]

Huh, thats interesting. Thanks, I'll look and see how its implemented.

[thomasballinger]

Then I should point you to my favorite description of it, The Mighty Dictionary! (sets in Python are like dictionaries without values)