У нас есть длинный (около 100 000) двумерный массив numpy. Нравиться:
A_in =
[[1, 2, 3, 4, 3, 2, 1, …, 100000],
[2, 3, 3, 5, 4, 3, 1, …, 100000]] (edge_index_cpu в коде)
Здесь вы можете рассматривать один столбец как одну группу. Каждое число означает точку, один столбец означает линию между этими двумя точками.
Нам нужно получить вывод, например:
А_выход =
и индекс этих выходных значений в исходном массиве, например:
IDx_out = [0, 2, 3]
Выходная группа не может пересекаться со всеми предыдущими группами. Кроме того, если предыдущая группа была удалена (например, [[2],[3]] выше), то удаленная группа не будет использоваться для вычисления пересечения (таким образом, [[3], [3]] сохраняется. ).
Его легко реализовать с помощью цикла for. Но поскольку данные слишком велики для «цикла for», мы хотели бы попросить алгоритм, который можно было бы распараллелить для этой задачи.
Я пытался использовать уникальный оператор numpy из плоской версии A_in. ([1, 2, 2, 3, 3, 3, 4, 5, 3, 4, 2, 3, 1, 1, …]). Но это не может соответствовать этому «если предыдущая группа была удалена (например, [[2], [3]] выше), то удаленная группа не будет использоваться для вычисления пересечения (таким образом, [[3], [3] ] хранится)".
Мы хотим обрабатывать граф, содержащий ребра и точки.
edge_index_cpu = edge_index.cpu()
for edge_idx in edge_argsort.tolist():
source = edge_index_cpu[0, edge_idx].item()
if source not in nodes_remaining:
continue
target = edge_index_cpu[1, edge_idx].item()
if target not in nodes_remaining:
continue
new_edge_indices.append(edge_idx)
cluster[source] = i
nodes_remaining.remove(source)
if source != target:
cluster[target] = i
nodes_remaining.remove(target)
i += 1
# The remaining nodes are simply kept.
for node_idx in nodes_remaining:
cluster[node_idx] = i
i += 1
cluster = cluster.to(x.device)
@Spektre Спасибо. Я не понимаю вашу идею, не могли бы вы дать более подробное объяснение? Всего символов 100 (по 10000 вершин на символ), одновременно обрабатывается только 12 символов. Вы могли бы рассмотреть 100 000, а не 1 миллион.
@Spektre Каждый персонаж из компьютерных фильмов или игр, содержащий около 10 000 вершин. Я использую эти вершины для построения графиков и загружаю эти графики в графовую нейронную сеть. С нетерпением жду вашего ответа
Я бы пока не стал распараллеливать, так как ваша проблема может быть решена в O(n)
, что должно быть достаточно быстро.
определения
давайте считать, что мы получили это:
const int pnts=1000000; // max points
const int lins=1000000; // number of lines
int lin[2][lins]; // lines
bool his[pnts]; // histogram of points (used edge?)
int out[pnts],outs=0; // result out[outs]
Я ориентируюсь на C++/GL, поэтому использую индексы, начинающиеся с нуля!!! Я использовал статические массивы, чтобы не путать их с динамическим размещением или шаблонами списков, чтобы их было легко понять.
гистограмма
создать гистограмму для используемых точек. Это просто таблица, содержащая один счетчик или значение для каждого возможного индекса точки. При запуске очистите его. Поскольку нам не нужно знать, сколько раз используется точка, я выбрал bool
, так что это просто значение true/false
, которое говорит нам, используется ли точка уже или нет.
поэтому очистите эту таблицу в начале с помощью false
:
for (i=0;i<pnts;i++) his[i]=0;
данные технологических линий
просто обработайте все точки/линии в их порядке и обновите гистограмму для каждой точки. Итак, возьмите индекс точек p0/p1
из lin[0/1][i]
и проверьте, используются ли уже обе точки:
p0=lin[0][i];
p1=lin[1][i];
if ((!his[p0])&&(!his[p1])){ his[p0]=true; his[p1]=true; add i to result }
если они не добавлены i
к результату и установлены p0,p1
как используемые в гистограмме. Как вы можете видеть, это O(1)
Я предполагаю, что вы использовали линейный поиск цикла для создания своей версии O(n^2)
.
Вот небольшой пример O(n)
C++ для этого (извините, не кодировщик Python):
void compute()
{
const int pnts=1000000; // max points
const int lins=1000000; // number of lines
int lin[2][lins]; // lines
bool his[pnts]; // histogram of points (used edge?)
int out[pnts],outs=0; // result out[outs]
int i,p0,p1;
// generate data
Randomize();
for (i=0;i<lins;i++)
{
lin[0][i]=Random(pnts);
lin[1][i]=Random(pnts);
}
// clear histogram
for (i=0;i<pnts;i++) his[i]=0;
// compute result O(lins)
for (i=0;i<lins;i++) // process all lines
{
p0=lin[0][i]; // first point of line
p1=lin[1][i]; // second point of line
if ((!his[p0])&&(!his[p1])) // both unused yet?
{
his[p0]=true; // set them as used
his[p1]=true;
out[outs]=i; // add new edge to result list
outs++;
}
}
// here out[outs] holds the result
}
время выполнения является линейным, и на моей машине это заняло ~ 10 мс, поэтому нет необходимости в распараллеливании.
В случае, если bool
не является одним битом, вы можете упаковать гистограмму в целые числа без знака, используя ее биты (например, упаковать 32 точки в одну 32-битную переменную int), чтобы сохранить память. В таком случае 1 миллион точек приводит к таблице размером 125000 байт, что в наши дни не является проблемой.
Когда я передаю ваши данные в код:
int lin[2][lins]= // lines
{
{ 1, 2, 3, 4, 3, 2, 1 },
{ 2, 3, 3, 5, 4, 3, 1 },
};
Я получил этот результат:
{ 0, 2, 3 }
Похоже, что существует огромная разница в скорости между python и cpp при обработке большого цикла for. Возможно, мне следует переписать эту часть на C. Спасибо за ответ!
@RuiShi Python - один из самых медленных языков ... IIRC его интерпретируемая скорость достигается за счет использования созданных на C++ материалов (пакетов libs), вызываемых из него. Как насчет разницы результатов, какой из них правильный? мой или ваш, чтобы я мог обновить код, это просто вопрос if
условия
Почему в вашем результате 7? И обратите внимание, что столбец (2, 3) должен быть удален, а столбец (3, 3) сохранен.
когда вы добавляете индекс ребра i в результат, вам нужно убедиться, что обе точки не использовались в предыдущем. Не только один из этих двух. Я думаю, что следующее, что мне нужно сделать, это реализовать код этой части с помощью cpp. Python здесь слишком медленный.
У меня пока нет URL-адреса github. Код является частью метода объединения графов. (Именованный пул краев)
@RuiShi готово ... Вы должны добавить описание того, что оба края не должны использоваться в вашем вопросе (если его еще нет, и я просто не обращаю на это внимания). Время выполнения такое же ~10мс...
предполагая, что 32-битные неотрицательные целые числа индексируют до 1000000 (вероятно, намного меньше), так почему бы не использовать гистограмму, помечающую использованные точки, преобразуя вашу проблему в один цикл
O(n)
for
? Вам просто нужна таблица гистограмм, содержащая одно целое число (или просто бит) для каждого возможного индекса точки, поэтомуhist[1000000]
... Это должно быть быстро, поэтому распараллеливание не требуется ... в C++ на стандартном ПК я ожидаю, что это займет до 1 сек, может быть, даже меньше ... Я не пишу код на Python, поможет ли пример C++?