Я сделал прямую тривиальную реализацию C алгоритма, предоставленного оригинальным постером. Это здесь
Как и предполагали другие, первое, что нужно сделать, это свернуть код. Развертывание не очень хорошо для скорости, поскольку это приводит к промахам кэша кода. Я начал с раскручивания внутренних петель и получил это . Затем я свернул внешний цикл, удалил ненужные gotos и получил код ниже.
РЕДАКТИРОВАТЬ : я несколько раз менял код 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);
}
Теперь это интересно, потому что мы можем понять, что делает код. Кстати, выполняя эту упаковочную работу, я исправил несколько странностей в первоначальном вопросе. Я считаю, что это были опечатки, поскольку это не было логичным вообще в глобальном контексте.
- Перейти всегда прыгать до двух (это должно было прогрессировать)
- последний тест проверял ans [0] вместо ans [5]
пожалуйста, Марк, поправьте меня, если я ошибаюсь в приведенных выше предположениях о том, что должен делать исходный код, а ваш оригинальный алгоритм не содержит опечаток.
Что код делает это для каждого значения в ANS, проверьте, присутствует ли оно в двумерном массиве. Если какое-либо число пропущено, возвращается 0. Если все числа найдено, возвращается 1.
Чтобы получить действительно быстрый код, я бы не реализовал его на C, а на другом языке, таком как python (или C ++), где set - это базовая структура данных, предоставляемая стандартными библиотеками. Затем я бы собрал набор со всеми значениями массивов (то есть O (n)) и проверил, присутствуют ли искомые числа в множестве или нет (то есть O (1)). Окончательная реализация должна быть быстрее существующего кода, по крайней мере, с алгоритмической точки зрения.
Пример Python приведен ниже, так как он действительно тривиален (выведите true / false вместо 1/0, но вы поняли идею):
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 по очереди. Чтобы сократить его и избежать затрат на вызов функции, мы можем использовать макрос или встроенную функцию. Я опубликую предложение.