Алгоритмы. Python. 2 больших списка, проставить индексы соответствия

Рейтинг: 0Ответов: 3Опубликовано: 28.03.2023

Пишу на Python Есть 2 списка. Один статический, находится в таблице Excel. Второй список парсится с сайта, парсятся уникальные номера товаров, вида "3593893".

На данный момент я сначала нахожу все уникальные номера на сайте (Порядка 3000 штук). Засовываю их в список. Затем засовываю во второй список все номера из Excel.

И мне нужно найти в какой строке в таблице Excel находится одинаковый номер из первого списка. Из-за того что строк порядка 3000, то моя конструкция работает очень долго, больше часа. Я использую что-то вроде:

for i in range(0, len(ids)):
   if ids[i] in codes_data:
       j = codes_data.index(ids[i])
       #"заполняю строку остальными данными"

Правильно ли я понимаю что программа в данном случае просматривает список "codes_data" дважды?

Первый раз в if ids[i] in codes_data Второй раз в codes_data.index(ids[i])

Если это так, то корректно ли сделать:

for i in range(0, len(ids)):
    try:
        j = codes_data.index(ids[i])
        #"заполняю строку остальными данными"
    except: pass

В таком случае получается список codes_data просматривается один раз и программа будет работать быстрее и лучше?

Можно ли как-то ускорить нахождение индексов? Думал что как-то можно использовать сортировку, чтобы отталкиваться от неё, но не уверен что это самый простой и самый быстрый способ.

Обновление. Проблема была решена. Главная проблема как оказывается была в другом. Я слишком часто сохранял Excel файл, что тормозило работу программы. После того как я сделал отдельный файл для считывания и отдельный для записи, скорость стала молниеносной. Но я также смог улучшить и обработку списков благодаря ответам ниже, что еще больше улучшило пограмму. Спасибо.

python массивы алгоритм индексы индексация
Источник: Stack Overflow на русском

Ответы

▲ 0Принят

Проблема была решена. Главная проблема как оказывается была в другом. Я слишком часто сохранял Excel файл, что тормозило работу программы. После того как я сделал отдельный файл для считывания и отдельный для записи, скорость стала молниеносной.

Но я также смог улучшить и обработку списков благодаря ответам в вопросе, что еще больше улучшило программу. Спасибо.

▲ 0

Оптимизированная версия алгоритма автора:

for i, value in enumerate(ids):
    try:
        j = codes_data.index(value)
    except ValueError:
        j = None

    if j is not None:
        #"заполняю строку остальными данными"
        # используя полученный i

В блоке try код заполнения писать не стоит. Код в блоке try должен быть как можно компактнее.

P.S. Если использовать словарь для данных из Excel, то можно обойтись без поиска j и сразу формировать строку с данными в словаре.

▲ 0

Поиск элемента в списке имеет сложность O(n), а в словаре O(1).

Чтобы сильно не переписывать код, можно сделать по-быстрому маппинг в виде словаря item -> position и использовать его для поиска позиций:

codes_dict = {x: i for i, x in enumerate(codes_data)}

for id_ in ids:
    j = codes_dict.get(id_)
    if j is not None:
        #"заполняю строку остальными данными"
        ...

Метод get возвращает либо значение из словаря, если такой ключ в словаре есть, либо None, если ключа нет. Таким образом, можно достать значение и проверить наличие ключа в словаре одной операцией вместо двух, дополнительная экономия. Хотя при сложности доставания элемента из словаря O(1) это уже будет не так существенно влиять на скорость кода, но всё-таки.

А в вашем коде да - если элемент есть в списке, то список просматривается два раза - один раз при проверке наличия элемента и второй раз чтобы получить индекс этого элемента. Учитывая сложность обеих операций O(n) получается довольно "медленно и печально".