时间戳

首页 > 解决方案 > 多渠道联系人问题：根据信息查找相关工单

algorithm - 多渠道联系人问题：根据信息查找相关工单

问题描述

问题描述

以下问题描述取自 Shopee Code League 2021。

对于每个工单，识别每个用户的所有联系人（如果他们具有相同的联系信息）。这些票证中的每一个都通过或直接或间接相关Email，因此每个票证属于同一用户。例如：PhoneOrder ID

票 ID 电子邮件 订单编号 电话 联系人
一种 0 john@gmail.com 12345678 不适用 5
乙 1 不适用 12345678 682212345 2
C 34567 wick@gmail.com 不适用 682212345 4
D 78999 wick@gmail.com 不适用 不适用 3

在这个例子中，这个用户总共有 14 个Contact。此用户的 ticket_trace/contact 对将是0-1-34567-78999, 14.

对于每张票，识别ID属于同一用户的所有其他票，按升序排序，以及Contact用户拥有的总数。生成具有csv以下格式的 2 列的文件：

ID ticket_trace 和联系方式
0 0-1-34567-78999, 14
1 0-1-34567-78999, 14
⋮</td> ⋮</td>

请注意，有 500,000 行数据。在短时间内以最少的时间复杂度和内存使用量解决此问题的最有效方法是什么？

问题数据集

输入文件示例contacts.json：

[
   {
      "Id":0,
      "Email":"gkzAbIy@qq.com",
      "Phone":"",
      "Contacts":1,
      "OrderId":""
   },
   {
      "Id":1,
      "Email":"",
      "Phone":"329442681752",
      "Contacts":4,
      "OrderId":"vDDJJcxfLtSfkooPhbYnJdxov"
   }, // more data
]

单击此处获取问题数据集和更详细的描述。

标签： algorithmdata-structuresrelationshipkaggle

解决方案

这是我使用 Python3 的解决方案。我使用了 2 个字典来存储票连接。第一个字典按价值存储连接的票证。第二个字典存储每个 id 连接（跟踪）。最后，使用第二个字典中的跟踪计算联系人。是的，也是一个非常缓慢的方式。它需要3个循环。计算 Kaggle 内核中的所有 500.000 行最多需要 15 秒。

Kaggle 内核

# Import tools
import numpy as np
import pandas as pd

# Load data
df = pd.read_json('/kaggle/input/scl-2021-da/contacts.json')
npdata = df.values

# Initialize memory
memory = {}
connections = {}

# Store connected tickets by value
def add_to_memory(ticket_id, value):
    if value != "":
        if value in memory:
            memory[value].add(ticket_id)
            return
        memory[value] = {ticket_id}

for row in npdata:
    ticket_id = row[0]

    # Order Id
    add_to_memory(ticket_id, row[4])

    # Email
    add_to_memory(ticket_id, row[1])

    # Phone
    add_to_memory(ticket_id, row[2])

# Calculate Trace
for ids in memory.values():
    current_connection = set(ids)

    for uid in ids:
        if uid in connections:
            current_connection.update(connections[uid])

    for uid in current_connection:
        connections[uid] = current_connection

# Calculate contacts and add to list
output = []
for ticket_id, trace in sorted(connections.items()):
    contacts = np.sum(npdata[list(trace), 3])
    trace = "-".join([str(_id) for _id in sorted(trace)])
    answer = "{}, {}".format(trace, contacts)
    output.append({"ticket_id": ticket_id,  "ticket_trace/contact": answer})

# Convert to pandas DataFrame & save to csv
output_df = pd.DataFrame(output)
filename = "output.csv"
output_df.to_csv(filename, index=False)

参考

推荐阅读