Каков лучший алгоритм для этой проблемы сравнения массива?

Я сделал прямую тривиальную реализацию на C алгоритма, предоставленного оригинальным постером. Она находится здесь

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

EDIT: Я несколько раз менял код на C, потому что даже такой простой, как он есть, кажется, есть проблемы при JIT компиляции или выполнении его на CUDA (и CUDA, кажется, не очень разборчива в ошибках). Поэтому в приведенном ниже куске кода используются глобалы... и это только тривиальная реализация. Мы еще не достигли скорости. Это многое говорит о преждевременной оптимизации. Зачем стремиться к скорости, если мы даже не можем заставить это работать? Я полагаю, что все еще есть проблемы, поскольку CUDA, похоже, накладывает много ограничений на код, который вы можете заставить работать, если я верю статье в Википедии. Также, возможно, нам стоит использовать float вместо int ?

#include <stdio.h>

int D1[6] = {3, 4, 5, 6, 7, 8};
int D2[6] = {3, 4, 5, 6, 7, 8};
int D3[6] = {3, 4, 5, 6, 7, 8};
int D4[6] = {3, 4, 5, 6, 7, 8};
int D5[6] = {3, 4, 5, 6, 7, 8};
int D6[6] = {3, 4, 5, 6, 7, 9};
int ST1[1] = {6};
int ans[6] = {1, 4, 5, 6, 7, 9};
int * D[6] = { D1, D2, D3, D4, D5, D6 };

/* beware D is passed through globals */
int algo(int * ans, int ELM){
    int a, e, p;

    for (a = 0 ; a < 6 ; a++){ 
        for (e = 0 ; e < ELM ; e++){
            for (p = 0 ; p < 6 ; p++){
                if (D[p][e] == ans[a]){
                    goto cont;
                }
            }
        }
        return 0; //bad row of numbers found
    cont:;
    }
    return 1;
}

int main(){
    int res;
    res = algo(ans, ST1[0]);
    printf("algo returned %d\n", res);
}

Вот это интересно, потому что мы можем понять, что делает код. Кстати, выполняя эту работу по упаковке, я исправил несколько странностей в исходном вопросе. Я считаю, что это были опечатки, так как в глобальном контексте это было совсем не логично. - goto всегда перескакивает на 2 (должно было прогрессировать) - последний тест проверял ans[0] вместо ans[5]

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

Код делает следующее: для каждого значения в ans проверяется, присутствует ли оно в двухмерном массиве. Если какое-либо число пропущено, возвращается 0. Если все числа найдены, возвращается 1.

Чтобы получить действительно быстрый код, я бы реализовал его не на C, а на другом языке, например, python (или C++), где множество является базовой структурой данных, предоставляемой стандартными библиотеками. Затем я бы построил набор со всеми значениями массивов (это O(n)) и проверил, присутствуют ли искомые числа в наборе или нет (это O(1)). Окончательная реализация должна быть быстрее, чем существующий код, по крайней мере, с алгоритмической точки зрения.

Пример на Python ниже, так как он действительно тривиален (вместо 1/0 выводится true/false, но вы поняли идею):

ans_set = set(ans)
print len(set(D1+D2+D3+D4+D5+D6).intersection(ans_set)) == len(ans_set)

Вот возможная реализация на C++ с использованием множеств:

#include <iostream>
#include <set>

int algo(int * D1, int * D2, int * D3, int * D4, int * D5, int * D6, int * ans, int ELM){
    int e, p;
    int * D[6] = { D1, D2, D3, D4, D5, D6 };
    std::set<int> ans_set(ans, ans+6);

    int lg = ans_set.size();

    for (e = 0 ; e < ELM ; e++){
        for (p = 0 ; p < 6 ; p++){
            if (0 == (lg -= ans_set.erase(D[p][e]))){
                // we found all elements of ans_set
                return 1;
            }
        }
    }
    return 0; // some items in ans are missing
}

int main(){
    int D1[6] = {3, 4, 5, 6, 7, 8};
    int D2[6] = {3, 4, 5, 6, 7, 8};
    int D3[6] = {3, 4, 5, 6, 7, 8};
    int D4[6] = {3, 4, 5, 6, 7, 8};
    int D5[6] = {3, 4, 5, 6, 7, 8};
    int D6[6] = {3, 4, 5, 6, 7, 1};

    int ST1[1] = {6};

    int ans[] = {1, 4, 5, 6, 7, 8};

    int res = algo(D1, D2, D3, D4, D5, D6, ans, ST1[0]);
    std::cout << "algo returned " << res << "\n";
}

Мы делаем некоторую гипотезу о производительности: содержимое ans должно быть отсортировано или мы должны построить его иначе, мы предполагаем, что содержимое D1...D6 будет меняться между вызовами algo. Поэтому мы не утруждаем себя построением множества для него (так как построение множества в любом случае O(n), мы ничего не выиграем, если D1...D6 будут меняться). Но если мы вызываем algo несколько раз с одними и теми же D1...D6 и они меняются, мы должны поступить наоборот и преобразовать D1...D6 в одно большее множество, которое мы будем держать доступным.

Если я буду придерживаться C, я могу сделать это следующим образом:

• скопировать все числа в D1... D6 в один уникальный массив (используя memcpy для каждой строки)
• отсортировать содержимое этого массива
• использовать дихотомический поиск, чтобы проверить, доступно ли число

Поскольку размер данных здесь очень мал, мы также можем попробовать микрооптимизацию. Это может принести больше пользы. Не знаю точно.

EDIT2: есть жесткие ограничения на подмножество C, поддерживаемое CUDA. Самое строгое из них - нельзя использовать указатели на основную память. Это придется принять во внимание. Это объясняет, почему текущий код не работает. Самое простое изменение - это, вероятно, вызывать его для каждого массива D1...D6 по очереди. Чтобы сделать его коротким и избежать затрат на вызов функции, мы можем использовать макрос или встроенную функцию. Я опубликую предложение.

Меня немного смутил ваш вопрос, но я думаю, у меня его достаточно, чтобы помочь вам начать работу.

#define ROW 6
#define COL 6

int D[ROW][COL]; // This is all of your D arrays in one 2 dimensional array.

Далее вам, вероятно, следует использовать вложенные циклы for. Каждая петля будет соответствовать размеру D . Помните, что порядок ваших индексов имеет значение. Самый простой способ сделать это прямо в C - это помнить, что D [i] является допустимым выражением, даже если D имеет более одного измерения (и будет оценивать указатель на row: подмассив).

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

Затем вы можете использовать оператор break для выхода из внутреннего цикла после того, как вы определили, что текущий D [i] не соответствует ans .

При наличии всего 36 значений для сравнения наиболее эффективным подходом было бы вообще не использовать CUDA.

Просто используйте цикл CPU.

Если вы измените свои исходные данные, я изменю свой ответ.