Есть ли более эффективный способ получить результат (O (n + m), а не O (n * m))?

Question

Origin data, как показано ниже, каждый элемент имеет метку типа, например interests, family, behaviors, etc, и я хочу сгруппировать по этому полю типа.

return_data = [
{
      "id": "112",
      "name": "name_112",
      "type": "interests",
    },
    {
      "id": "113",
      "name": "name_113",
      "type": "interests",
    },
      {
      "id": "114",
      "name": "name_114",
      "type": "interests",
    },
      {
      "id": "115",
      "name": "name_115",
      "type": "behaviors",
    },
         {
      "id": "116",
      "name": "name_116",
      "type": "family",
    },
         {
      "id": "117",
      "name": "name_117",
      "type": "interests",
    },
    ...
]

И expected ouput формат данных как:

output_data = [

    {"interests":[
        {
          "id": "112",
          "name": "name_112"
        },
        {
          "id": "113",
          "name": "name_113"
        },
        ...
        ]
    },
    {
        "behaviors": [
            {
                "id": "115",
                "name": "name_115"
            },
            ...
        ]
    },
    {
        "family": [
            {
                "id": "116",
                "name": "name_116"
            },
            ...
        ]
    },
    ...
]

А вот мое испытание:

type_list = []
for item in return_data:
    if item['type'] not in type_list:
        type_list.append(item['type'])

interests_list = []
for type in type_list:
    temp_list = []
    for item in return_data:
        if item['type'] == type:
            temp_list.append({"id": item['id'], "name": item['name']})
    interests_list.append({type: temp_list})

Очевидно, что мое испытание малоэффективно, так как это O (n * m), но я не могу найти более эффективный способ решения проблемы.

Есть ли более эффективный способ получить результат? Любые комментарии приветствуются, спасибо.

Answer 1

Используйте defaultdict для хранения списка элементов для каждого типа:

from collections import defaultdict

# group by type
temp_dict = defaultdict(list)
for item in return_data:
    temp_dict[item["type"]].append({"id": item["id"], "name": item["name"]})

# convert back into a list with the desired format
output_data = [{k: v} for k, v in temp_dict.items()]

Выход:

[
    {
        'behaviors': [
            {'name': 'name_115', 'id': '115'}
        ]
    }, 
    {
        'family': [
            {'name': 'name_116', 'id': '116'}
        ]
    }, 
    {
        'interests': [
            {'name': 'name_112', 'id': '112'},
            {'name': 'name_113', 'id': '113'},
            {'name': 'name_114', 'id': '114'},
            {'name': 'name_117', 'id': '117'}
        ]
    },
    ...
]

---

Если вы не хотите импортировать defaultdict, вы можете использовать ванильный словарь с setdefault:

# temp_dict = {}

temp_dict.setdefault(item["type"], []).append(...)

Ведет себя точно так же, хотя и немного менее эффективно.

Answer 2

см. словарь Python для карты.

for item in return_data:
typeMap[item['type']] = typeMap[item['type']]  + delimiter + item['name']