Группировка данных по тому, пересекается ли функция данных - PullRequest
Новая
       117

Группировка данных по тому, пересекается ли функция данных

0 голосов
/ 23 октября 2018

Предположим, у нас есть таблица: 

id  | aliases
-------------
0   | ['a0', 'a1', 'a4', 'a11']
1   | ['a3', 'a5']
2   | ['a16', 'a18']
3   | ['a6', 'a8', 'a10']
4   | ['a7', 'a8', 'a9']
5   | ['a3', 'a12', 'a14']
6   | ['a5', 'a16', 'a17']

, и я хотел бы сгруппировать все id вместе, чтобы отобразить в один и тот же aliases;другими словами, конечный результат группирует все id, которые имеют aliases, которые пересекаются, примененные рекурсивно.В приведенном выше случае мы имеем:

  • 0 сопоставляется с ['a0', 'a1', 'a4', 'a11']
  • 1, 2, 5 и 6 сопоставляется с['a3', 'a5', 'a12', 'a14', 'a16', 'a17', 'a18']
  • 3 и 4 отображаются на ['a6', 'a7', 'a8', 'a9', 'a10']

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

Существует наивный подход потоковой передачи строк и проверки того, находится ли каждый элемент aliases в каждой новой строке в aliases, обработанном до сих пор;если это так, то собрать id вместе всех строк с совпадающими aliases и отобразить их в объединение сопоставленных aliases.

Однако этот подход кажется вычислительно нецелесообразным.

1 Ответ

0 голосов
/ 23 октября 2018

Выполнить код сложности O(n*len(groupcount) для этой таблицы не так уж сложно, просто у меня в голове:

Предположим, у вас есть id в качестве списка идентификаторов и aliasesв качестве списка списков вы можете сделать: 

bins = []
sets = []
for i in id: # Assume from (0 - n)
    alias = aliases[i]
    in_set = False
    for j in range(len(sets)):
        if len(sets[j].intersection(set(alias))) > 0:
            sets[j].update(set(alias)) # add alias to set, if any difference
            in_set = True
            bins[j].append(i) # append id to bins
            break
    if not in_set:
        bins.append([i])
        sets.append(set(alias))

bins будет содержать id группы, а соответствующий элемент в sets будет содержать alias группы, вы можете использовать list()преобразовать эти наборы обратно в list.А поскольку все операции над множествами основаны на хэше, это гарантирует, что ваша программа будет запущена за O(n*groupcount) раз.

...