Существует ли алгоритм, который можно распараллелить для «уникальной» задачи?

У нас есть длинный (около 100 000) двумерный массив numpy. Нравиться:

A_in =

[[1, 2, 3, 4, 3, 2, 1, …, 100000],

[2, 3, 3, 5, 4, 3, 1, …, 100000]] (edge_index_cpu в коде)

Здесь вы можете рассматривать один столбец как одну группу. Каждое число означает точку, один столбец означает линию между этими двумя точками.

Нам нужно получить вывод, например:

А_выход =

Существует ли алгоритм, который можно распараллелить для «уникальной» задачи? (new_edge_indices в коде)

и индекс этих выходных значений в исходном массиве, например:

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)

предполагая, что 32-битные неотрицательные целые числа индексируют до 1000000 (вероятно, намного меньше), так почему бы не использовать гистограмму, помечающую использованные точки, преобразуя вашу проблему в один цикл O(n)for? Вам просто нужна таблица гистограмм, содержащая одно целое число (или просто бит) для каждого возможного индекса точки, поэтому hist[1000000] ... Это должно быть быстро, поэтому распараллеливание не требуется ... в C++ на стандартном ПК я ожидаю, что это займет до 1 сек, может быть, даже меньше ... Я не пишу код на Python, поможет ли пример C++?

Spektre 26.07.2019 10:12

@Spektre Спасибо. Я не понимаю вашу идею, не могли бы вы дать более подробное объяснение? Всего символов 100 (по 10000 вершин на символ), одновременно обрабатывается только 12 символов. Вы могли бы рассмотреть 100 000, а не 1 миллион.

Rui Shi 26.07.2019 10:20

@Spektre Каждый персонаж из компьютерных фильмов или игр, содержащий около 10 000 вершин. Я использую эти вершины для построения графиков и загружаю эти графики в графовую нейронную сеть. С нетерпением жду вашего ответа

Rui Shi 26.07.2019 10:32
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
3
45
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я бы пока не стал распараллеливать, так как ваша проблема может быть решена в O(n), что должно быть достаточно быстро.

  1. определения

    давайте считать, что мы получили это:

    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, поэтому использую индексы, начинающиеся с нуля!!! Я использовал статические массивы, чтобы не путать их с динамическим размещением или шаблонами списков, чтобы их было легко понять.

  2. гистограмма

    создать гистограмму для используемых точек. Это просто таблица, содержащая один счетчик или значение для каждого возможного индекса точки. При запуске очистите его. Поскольку нам не нужно знать, сколько раз используется точка, я выбрал bool, так что это просто значение true/false, которое говорит нам, используется ли точка уже или нет.

    поэтому очистите эту таблицу в начале с помощью false:

    for (i=0;i<pnts;i++) his[i]=0;
    
  3. данные технологических линий

    просто обработайте все точки/линии в их порядке и обновите гистограмму для каждой точки. Итак, возьмите индекс точек 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. Спасибо за ответ!

Rui Shi 26.07.2019 11:08

@RuiShi Python - один из самых медленных языков ... IIRC его интерпретируемая скорость достигается за счет использования созданных на C++ материалов (пакетов libs), вызываемых из него. Как насчет разницы результатов, какой из них правильный? мой или ваш, чтобы я мог обновить код, это просто вопрос if условия

Spektre 26.07.2019 11:12

Почему в вашем результате 7? И обратите внимание, что столбец (2, 3) должен быть удален, а столбец (3, 3) сохранен.

Rui Shi 26.07.2019 11:17

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

Rui Shi 26.07.2019 11:32

У меня пока нет URL-адреса github. Код является частью метода объединения графов. (Именованный пул краев)

Rui Shi 26.07.2019 11:35

@RuiShi готово ... Вы должны добавить описание того, что оба края не должны использоваться в вашем вопросе (если его еще нет, и я просто не обращаю на это внимания). Время выполнения такое же ~10мс...

Spektre 26.07.2019 11:40

Другие вопросы по теме