Как отметил Марк, можно использовать структуру данных, в которой хранятся связанные узлы. Лучше всего использовать булевую матрицу |V|x|V|
. Значения могут быть инициализированы алгоритмом Флойда-Варшалла. Это делается в O(|V|^3)
.
Пусть T(i)
- множество вершин, имеющих путь к вершине i
и F(j)
множество вершин, где существует путь от вершины j
. Во-первых, это истина в i
-й строке, а вторая - в столбце j
.
Добавление края (i,j)
- простая операция. Если раньше i
и j
не были подключены раньше, чем для каждого a
из T(i)
, а каждый b
из F(j)
установил матричный элемент (a,b)
в true. Но операция не из дешевых. В худшем случае это O(|V|^2)
. То есть в случае направленной линии, а добавление края от вершины к начальной вершине приводит к тому, что все вершины соединяются со всеми другими вершинами.
Удаление ребра (i,j)
- это не так просто, но не более дорогостоящая операция в худший случай :-) Если после удаления края есть путь от i
до j
, ничего не меняется. Это проверяется с помощью Dijkstra, меньше O(|V|^2)
. Вершины, которые не связаны больше (a,b)
:
a
в T(i)
- i
- T(j)
, b
в F(j)
+ j
Изменяется только T(j)
с удалением края (i,j)
, поэтому его необходимо пересчитать. Это делается путем любого перемещения графика (BFS, DFS), переходя в противоположном направлении от вершины j
. Это делается менее чем за O(|V|^2)
. Так как установка матричного элемента в худшем случае снова O(|V|^2)
, эта операция имеет такую же худшую сложность, как добавление ребра.
Если вы хотите использовать pd.get_dummies
, есть возможность итеративно включать ваши кодировки для каждой партии.
Для вашей первой партии:
ohe = pd.get_dummies(data_rest, columns=['label_col'])
Для каждой последующей партии:
for b in batches:
batch_ohe = pd.get_dummies(b, columns=['label_col'])
ohe = pd.concat([ohe, batch_ohe], axis=0)
ohe = ohe.fillna(0)
HashingVectorizer
может быть хорошим решением для вашего случая. Он не зависит от количества входных функций, просто установите достаточно большой начальный размер.