Python улучшает обработку списка для большего ввода

Question

Идея моего кода заключается в том, что при дублировании одного и того же пользователя с тем же идентификатором device_id он обновляет список (в моем случае создает новый список) и удаляет дублирующиеся записи. Также он возьмет последние id1, id2 и id3 из дублирующейся записи и объединит их в одну запись в новом списке, а также обновит тип с типом дублирования.

Чтобы объяснить это, приведу пример с 4 списками (напечатанными до обновления и после обновления списка)

Мой код работает, однако у меня есть другие списки с примерно 800k списками, где я пытался запустить код, и он работал в течение часа. Как мне лучше подойти к этому вопросу? (невозможно изменить тип ввода, так как это из другого вызова API, я могу только изменить свой код удаления дублирования)

my_list = []
#   [device_id, location, type, name, ph, addr, email, id1, id2, id3]
val1=  ['12345653', 'SOUTH', 'Broadband', 'Mr Glasses', '+123344', 'MY ADDRESS', '880@myemail', '', '']
val2=  ['12345653', 'SOUTH', 'IPTV', 'Mr Glasses', '+123344', 'MY ADDRES', '', '999@myemail', '']
val3=  ['98102344', 'SOUTH', 'Voice', 'Ms Chair', '+99123123', 'Corner Street Behind Door', '', '', '990@securemail']
val4=  ['11023424', 'SOUTH', 'IPTV', 'Mr Tree', '+125324', 'Upwards error 123', '', '47@securemail', '']


my_list.append(val1)
my_list.append(val2)
my_list.append(val3)
my_list.append(val4)

for x in my_list:
    print x

print 'start removing duplication'
print ''
def rm_dupl(my_list):
    fin_list = []
    dev_exist = []

    for x in my_list:
        dev_id = x[0]
        if dev_id in dev_exist:
            # if entry exist, we just update the existing entry with 
            # the value of this current x, and not creating a new entry
            for y in fin_list:
                if dev_id in y[0]:
                    # y is retrieved value
                    # below we update with the duplication one
                    if 'Broadband' in x[2]:
                        y[2] += '_Broadband'
                        y[6] = x[6]
                    elif 'IPTV' in x[2]:
                        y[2] += '_IPTV'
                        y[7] = x[7]
                    elif 'Voice' in x[2]:
                        y[2] += '_Voice'
                        y[8] = x[8]
                else:
                    continue
        else:
            fin_list.append(x)
            dev_exist.append(dev_id)
    return fin_list


updated_list = rm_dupl(my_list)
for x in updated_list:
    print x

Answer 1

Как уже упоминали другие, сканирование списка не только неэффективно, но и O (n), поэтому чем больше ваш список, тем хуже время поиска.

Здесь у вас есть два списка сканирования, одно неявное (dev_id in dev_exist) и одно явное (for y in fin_list: if dev_id in y[0]:).

Решение состоит в том, чтобы использовать dict (или collections.OrderedDict, если порядок вставки имеет значение), чтобы сохранить дедуплицированный результат, с "id" в качестве ключа и строкой в ​​качестве значения - поиск ключа Dict равен 0 (1) (постоянный время) и очень быстро. Этот диктант также заменит список dev_exist.

Также, учитывая данные вашего примера, вы, вероятно, захотите заменить if 'somestring' in x[i] на if x[i] == 'somestring', что является более точным ('foo' in 'foobar' вернет true, вероятно, не то, что вам нужно) и (немного) быстрее (в зависимости от строки длина).

def rm_dupl(my_list):
    results = {} # or `collections.OrderedDict`

    for row in my_list:
        prev_row = results.get(row[0])
        if prev_row:
            # if entry exist, we just update the existing entry with 
            # the value of this current row, and not creating a new entry
            # below we update with the duplication one

            val = row[2] # avoids multiple access to `row[2]`
            if val == 'Broadband':
                prev_row[2] += '_Broadband'
                prev_row[6] = row[6]
            elif val == 'IPTV':
                prev_row[2] += '_IPTV'
                prev_row[7] = row[7]
            elif val == 'Voice':
                prev_row[2] += '_Voice'
                prev_row[8] = row[8]

        else:
            # no matching row found, let's add
            # a new one
            results[dev_id] = row

    # and returns the values
    # NB in py3 you'll want `list(results.values())` instead
    return results.values()

Answer 2

Если вы сделаете свой dev_exist набор, проверка наличия значения станет намного быстрее. В настоящее время каждое значение должно пройти через все значения в списке dev_exist, чтобы проверить, присутствует ли оно уже. Однако проверка наличия значения в наборе выполняется с помощью хеширования и будет намного быстрее.

Это позаботится о значительной части времени.

EDIT: Вы также можете заменить список на подсказку при поиске дубликатов. Dicts также предоставляют быстрые in методы.

my_dict = {}
for val in my_list:
    if val[0] in my_dict:
        print(val[0], "exists already")
        # Your code for replacing an existing entry here
    else:
        my_dict[val[0]] = val[1:]

# To convert back to a list
new_list = []
for key, value in my_dict.items():
    new_list.append([key]+value)