Реализация алгоритма однопроходного поиска столбца к столбцу с использованием структуры данных min heap - PullRequest
Новая
       20

Реализация алгоритма однопроходного поиска столбца к столбцу с использованием структуры данных min heap

0 голосов
/ 12 февраля 2019

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

Некоторые подробности о обрабатываемых мной базах данных:
- нет таблиц: 200
- общий размер: 3 ГБ

Input: attributes: set of attribute objects with their sorted values and their
       respective refs sets (the IND candidates)

Output: Set of satisfied INDs.

Min-Heap heap := new Min-Heap( attributes )
while heap != ∅ do
    //getattributes with equal min.value
    att := heap.removeMinAttributes()
    foreach A ∈ att do
        // update list A.refs
        A.refs := A.refs ∩ att
        // process next value
        if A has next value then
            A.moveCursor()
            heap.add(A)
        else
            foreach B ∈ A.refs do
                INDs := INDs ∪ { A ⊆ B }
    return INDs

Определения:
- attributes: столбцы, в которых хранятся только уникальные значения, и они сортируются в порядке возрастания
- att: все столбцы, в которых они имеют одинаковые минимальные значенияв куче
- IND: пара столбцов, например, столбец A и столбец B, где все значения в столбце A указаны в столбце B
- A.refs: список всех столбцов, которые содержат значениястолбец A

Структура данных кучи должна выглядеть примерно так: 

A    B    C
1    1
3         3
5    5    5
          7

Моя текущая структура данных выглядит как 

    A    B    C
1   1    1    nan
3   3    nan  3
5   5    5    5
7   nan  nan  7

Итак, моя реализация алгоритмазаключается в том, что для каждого индекса фрейма данных получают имена столбцов с таким значением.

Это правильный способ реализации min heap?Если нет, то как мне это сделать?

РЕДАКТИРОВАТЬ Ниже приведен мой код для реализации 

ind_dict = {'A': ['B', 'C'],
            'B': ['A', 'C'],
            'C': ['A', 'B']}

dataframe = pd.DataFrame(data={'A': [1, 3, 5, np.nan],
                               'B': [1, np.nan, 5, np.nan],
                               'C': [np.nan, 3, 5, 7]},
                         index=[1, 3, 5, 7])


def algorithm(self, dataframe, ind_dict):
    # for each cursor value, get all columns that has it
    for cursor, i in zip(dataframe.index, range(0, len(dataframe.index))):

        # columns that contain the current cursor value
        column_containing_cursor = [i for i, x in enumerate(dataframe.iloc[i]) if x == cursor]

        atts = [list(dataframe.iloc[i].index)[n] for n in column_containing_cursor]

        # for each column in ind_dict.keys(), intersect its values with atts to get the remaining att.refs
        # if the current column value is null, then do nothing
        for key in ind_dict.keys():
            column_val = dataframe.loc[cursor, key]

            if (column_val == column_val) & (column_val != ''):
                ind_dict[key] = list(set(ind_dict[key]).intersection(atts))

1 Ответ

0 голосов
/ 25 февраля 2019

Пересмотрев статью и потратив некоторое время на рассмотрение теории heap, я наконец-то понял, как реализовать ее с использованием библиотеки heapq.

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

Ниже приведен код реализации.

По сути, все значения из всех столбцов хранятся в структуре tuple и помещаются в min heap.Сначала мы извлекаем наименьший элемент на основе значения, а затем выполняем итерацию для всех кортежей с одинаковым значением.

Когда итерация завершится, мы получим att (все столбцы), которые имеют текущий наименьшийзначение.Затем мы обновляем ind_dict и переходим к следующему наименьшему значению, пока min heap не станет пустым. 

import heapq

col_vals = {'A': [1, 2, 3, 4],
            'B': [2, 4],
            'C': [1, 2, 4, 5]}

ind_dict = {'A': ['B', 'C'],
            'B': ['A', 'C'],
            'C': ['A', 'B']}

min_heap = []

for column in col_vals:
    vals = col_vals[column]

    for val in vals:
        tup = (val, column)
        heapq.heappush(min_heap, tup)

while min_heap:
    # get the smallest value in the heap
    att = []

    current_smallest, var = heapq.heappop(min_heap)
    att.append(var)

    # pop all the elements and put them in a list where value is equal to current smallest value
    while min_heap and min_heap[0][0] == current_smallest:
        next_var = heapq.heappop(min_heap)[-1]
        att.append(next_var)

    # update ind att.refs
    for a in att:
        ind_dict[a] = list(set(ind_dict[a]).intersection(att))
...