Циклическая или иерархическая словарная структура данных в Python (или в CS в целом)?

Question

Я в настоящее время в растерянности, так как у меня огромный Pandas DataFrame (более 1 миллиона строк), и я смотрю на 3 столбца, а именно:

Company_Name     Business_ID    Location
ABC, Inc.         BY2389AS        MTV
ABC, Inc.          100020         LMD
XYZW               010012         MTV
XYZW               010012         LMD
XYZW              AB23JKF         QAT
                  BA23F3              
SomethingCo        2342
SomethingCo                       ALD

Как видно иногда некоторые поля отсутствуют. Я хочу проверить это с данным реестром (он содержит миллионы триплетов в формате CSV (Company_Name, Business_ID, Location), и, если есть уникальное совпадение, попробуйте вернуть пропущенные поля (если существует уникальное совпадение) .

Реестр будет выглядеть примерно так в формате CSV:

Company_Name, Business_ID, Location
ABC, Inc., BY2389AS, MTV
ABC, Inc., 100020, LMD
XYZW, 010012, MTV
XYZW, 010012, LMD
XYZW, AB23JKF, QAT
DLCComp, BA23F3, PLT
DLCComp, 234XYZ, QAT            
SomethingCo, 2342, COD
SomethingCo, 2020 , ALD

Как видно выше, в этом файле CSV ничего не пропущено.

Предупреждение выполнение группы данных DataFrame, сводной таблицы, стека / unstack или даже логического поиска и выбор подмножества кадра данных замедляет это (поскольку просмотр всего реестра занимает много времени. У меня есть набор логик c для go и, если некоторые поля отсутствуют, просматривают реестр для обработки уникальных совпадений и заполняют пропущенные поля, в противном случае просто возвращают как есть, если уникальное совпадение не может быть идентифицировано.

Похоже, что поиск по словарю идеально - но так как любая комбинация из 3 полей может отсутствовать, я не могу создать словарь из этого гигантского реестра aframe (который я читаю в память для текущих целей) и создаю ключ по одному из столбцов.

Я пытаюсь придумать, какой тип данных будет идеальным для обработки, и подумал о циклических или иерархических словарях ( если таковые существуют), но это также становится немного сложнее, так как поиск должен был бы приспособиться к различным парам ключ-значение в зависимости от того, какое значение отсутствует в базе данных по сравнению с реестром. Стоимость реорганизации или поднабора фрейма данных на основе доступных значений столбца занимает некоторое время - и я пытаюсь выяснить, существует ли хорошая структура данных или алгоритм, который может решить эту проблему. Я также пытаюсь понять, может ли Pandas иметь очень эффективный способ подстановки кадра данных с помощью логических операций (что я сейчас и делаю) следующим образом:

# Example for if Business_ID is populated, but both Company_Name and Location are not:
def specific_case_func_for_demo_purposes(company_name, business_id, location):
    if not company_name and business_id and not location:
        subset_df = registry_df[registry_df[Business_ID] == business_id_im_looking_for]

        if len(subset_df) == 0:
            return company_name, business_id, location
        elif len(subset_df) == 1:
            return subset_df['Company_Name'], business_id, subset_df['Location']
        else:
            # handle case when there are multiple business_id matches by seeing if company name is unique, since company name can be identified by business ID:
            if len(subset_df['Company_Name'].unique()) == 1:
                return subset_df['Company_Name'].iloc[0], business_id, location
            else:
                # can't possible know if there is a unique match - so just return the empty company_name and location
                return company_name, business_id, location

Это просто функция для обрабатывать этот конкретный конкретный c случай, когда Business_ID заполнен, а Company_Name и Location - нет. Это может стать запутанным, как можно видеть. В настоящее время я занимаюсь всеми 8 случаями (некоторые из которых можно сократить до дубликатов или, по сути, одного и того же случая, то есть в целом около 4 случаев с парой подсистем), но это кажется крайне неэффективным как в плане дизайна, так и в плане производительности. При использовании подмножества данных CSV реестра с числом строк = 800 000 и выполнении этого типа логики c на ~ 400 точках данных, это заняло 35 с при stdev 128 мс с использованием% timeit. Я использовал df.apply, используя основную функцию, которую я разработал, чтобы рассчитать это время.

Я хотел бы знать структуру данных, которая может обеспечить хороший поиск и время установки при применении этого к гораздо большим фреймам данных - я знаю должен быть гораздо более эффективный способ, будь то эффективное использование Pandas методов или различных структур данных, таких как словари взаимного поиска (или циклические или иерархические словари, если такие понятия существуют), потенциально основанные на деревьях методы или другие вещи. Я приветствую любые комментарии по этому вопросу.

Answer 1

Решение 1 - Для оптимизации поиска по фреймам данных

import sys
import time
import timeit
import random
import pandas as pd

# Creating dummy data for 1 million rows
number_of_rows = 1000000 # 1 million
list_Temp = [('abcdefghi_'+str(i), 'jklmnopqrs_'+str(i), 'tuvwxyz_'+str(i)) for i in range(number_of_rows)]

# This is your registry_df
df = pd.DataFrame(list_Temp, columns = ['A' , 'B', 'C']) 
print('Dummy registry_df size =', (sys.getsizeof(df)/1000000), 'MB')
df.head()

Вывод:

Dummy registry_df size = 217.666774 MB

        A               B             C
0   abcdefghi_0   jklmnopqrs_0    tuvwxyz_0
1   abcdefghi_1   jklmnopqrs_1    tuvwxyz_1
2   abcdefghi_2   jklmnopqrs_2    tuvwxyz_2
3   abcdefghi_3   jklmnopqrs_3    tuvwxyz_3
4   abcdefghi_4   jklmnopqrs_4    tuvwxyz_4

>

# Creating 'n' random numbers for searching in registry_df
n = 100
list_random_numbers = [random.randrange(0, number_of_rows) for i in range(n)]

# Time taken for searching for n values in registry_df. You need to select one of the best from option

%timeit for number in list_random_numbers: df_Temp = df.loc[df['A'] == 'abcdefghi_'+str(number)]
%timeit for number in list_random_numbers: df_Temp = df[df['A'] == 'abcdefghi_'+str(number)]
%timeit for number in list_random_numbers: df_Temp = df[df.A.eq("'abcdefghi_"+str(number)+"'")]
%timeit for number in list_random_numbers: df_Temp = df.query(('A == ' + ("'abcdefghi_"+str(number)+"'")))
%timeit for number in list_random_numbers: df_Temp = df.eval("A == 'abcdefghi_"+str(number)+"'")
%timeit for number in list_random_numbers: df_Temp = df[df.A.isin( ["A == 'abcdefghi_"+str(number)+"'"])]

Вывод:

11.9 s ± 338 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
11.4 s ± 441 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
13 s ± 756 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
5.57 s ± 384 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
5.22 s ± 122 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
3.99 s ± 140 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Решение 2 - Если у вас есть немного дополнительной памяти. Сохранение индексов в соответствующем столбце словаря * Вывод:

2.99 s ± 278 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Как видно при поиске в фрейме данных, наиболее оптимизированный метод занял ~ 4 секунды для поиска всего 100 значений . В то время как поиск по индексам занял ~ 3 секунды для всех 10000 значений

Также, если у вас есть 2 значения и 1 пропущенное значение, чтобы найти. Вам нужно найти индексы из соответствующего словаря и использовать функцию ниже, чтобы получить общие индексы и, наконец, получить subset_df из списка общих индексов

def Get_Common_List_Values(list1, list2):
    if (list1 is None) and (list2 is not None): return list2
    if (list2 is None) and (list1 is not None): return list1

    if (list2 is not None) and (list1 is not None):
        return [row_Index for row_Index in list1 if row_Index in list2]

Примечание: Все время рассчитывается на фиктивных данных , Ваше фактическое время будет варьироваться