Каков наилучший алгоритм для этой задачи сравнения массивов?
Какой алгоритм скорости наиболее эффективен для решения следующей задачи?
Дано 6 массивов, D1,D2,D3,D4,D5 и D6, каждый из которых содержит 6 чисел, таких как:
D1[0] = number D2[0] = number ...... D6[0] = number
D1[1] = another number D2[1] = another number ....
..... .... ...... ....
D1[5] = yet another number .... ...... ....
Дан второй массив ST1, содержащий 1 число:
ST1[0] = 6
Дан третий массив ans, содержащий 6 чисел:
ans[0] = 3, ans[1] = 4, ans[2] = 5, ......ans[5] = 8
Использование в качестве индекса для массивов D1, D2, D3, D4, D5 и D6 числа, которое идет от 0, до числа, хранящегося в ST1[0], минус один, в этом примере 6, так что от 0 до 6-1, сравните массив ans с каждым массивом D. Результат должен быть равен 0, если один или несколько номеров ответов не найдены ни в одном D по одному и тому же индексу, и должен быть равен 1, если все номера ответов найдены в некотором D по одному и тому же индексу. То есть, верните 0, если некоторый ans[i] не равенDN[i], и верните 1, если каждый ans[i] равен DN[i].
Мой алгоритм до сих пор:
Я старался держать все как можно более незапертым.
EML := ST1[0] //number contained in ST1[0]
EML1 := 0 //start index for the arrays D
While EML1 < EML
if D1[ELM1] = ans[0]
goto two
if D2[ELM1] = ans[0]
goto two
if D3[ELM1] = ans[0]
goto two
if D4[ELM1] = ans[0]
goto two
if D5[ELM1] = ans[0]
goto two
if D6[ELM1] = ans[0]
goto two
ELM1 = ELM1 + 1
return 0 //If the ans[0] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
two:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[1]
goto three
if D2[ELM1] = ans[1]
goto three
if D3[ELM1] = ans[1]
goto three
if D4[ELM1] = ans[1]
goto three
if D5[ELM1] = ans[1]
goto three
if D6[ELM1] = ans[1]
goto three
ELM1 = ELM1 + 1
return 0 //If the ans[1] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
three:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[2]
goto four
if D2[ELM1] = ans[2]
goto four
if D3[ELM1] = ans[2]
goto four
if D4[ELM1] = ans[2]
goto four
if D5[ELM1] = ans[2]
goto four
if D6[ELM1] = ans[2]
goto four
ELM1 = ELM1 + 1
return 0 //If the ans[2] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
four:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[3]
goto five
if D2[ELM1] = ans[3]
goto five
if D3[ELM1] = ans[3]
goto five
if D4[ELM1] = ans[3]
goto five
if D5[ELM1] = ans[3]
goto five
if D6[ELM1] = ans[3]
goto five
ELM1 = ELM1 + 1
return 0 //If the ans[3] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
five:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[4]
goto six
if D2[ELM1] = ans[4]
goto six
if D3[ELM1] = ans[4]
goto six
if D4[ELM1] = ans[4]
goto six
if D5[ELM1] = ans[4]
goto six
if D6[ELM1] = ans[4]
goto six
ELM1 = ELM1 + 1
return 0 //If the ans[4] number is not found in either D1[0-6], D2[0-6].... D6[0-6] return 0 which will then exclude ans[0-6] numbers
six:
EML1 := 0 start index for arrays Ds
While EML1 < EML
if D1[ELM1] = ans[5]
return 1 ////If the ans[1] number is not found in either D1[0-6].....
if D2[ELM1] = ans[5] return 1 which will then include ans[0-6] numbers
return 1
if D3[ELM1] = ans[5]
return 1
if D4[ELM1] = ans[5]
return 1
if D5[ELM1] = ans[5]
return 1
if D6[ELM1] = ans[5]
return 1
ELM1 = ELM1 + 1
return 0
Как язык выбора, это было бы чисто
4 ответа
Я сделал прямую тривиальную реализацию алгоритма на языке 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 I, я мог бы сделать это следующим образом:
- скопировать все числа в 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.
Далее вам, вероятно, следует использовать вложенные циклы. Каждый цикл будет соответствовать измерению D, Помните, что порядок ваших индексов имеет значение. Самый простой способ сохранить это в C - это помнить, что D[i] является допустимым выражением, даже когда D имеет более одного измерения (и будет указывать на указатель на строку: подмассив).
Если вы не можете изменить независимые D-массивы на один многомерный массив, вы можете легко создать массив указателей, члены которого указывают на заголовки каждого из этих массивов и достигают того же эффекта.
Затем вы можете использовать оператор break, чтобы выйти из внутреннего цикла после того, как вы определили, что текущий D[i] не соответствует ans,
Если сравнить только 36 значений, наиболее эффективным подходом было бы вообще не использовать CUDA.
Просто используйте цикл процессора.
Если вы измените свои данные, я изменю свой ответ.
В случае, если диапазон чисел ограничен, вероятно, было бы проще создать битовый массив, например так:
int IsPresent(int arrays[][6], int ans[6], int ST1)
{
uint32_t bit_mask = 0;
for(int i = 0; i < 6; ++ i) {
for(int j = 0; j < ST1; ++ j) {
assert(arrays[i][j] >= 0 && arrays[i][j] < 32); // range is limited
bit_mask |= 1 << arrays[i][j];
}
}
// make a "list" of numbers that we have
for(int i = 0; i < 6; ++ i) {
if(((bit_mask >> ans[i]) & 1) == 0)
return 0; // in ans, there is a number that is not present in arrays
}
return 1; // all of the numbers were found
}
Это всегда будет работать в O(6 * ST1 + 6). Недостатком этого метода является сначала просмотр до 36 массивов, а затем проверка по шести значениям. Если существует сильное предварительное условие, что числа будут присутствовать в основном, можно отменить тест и обеспечить ранний выход:
int IsPresent(int arrays[][6], int ans[6], int ST1)
{
uint32_t bit_mask = 0;
for(int i = 0; i < 6; ++ i) {
assert(ans[i][j] >= 0 && ans[i][j] < 32); // range is limited
bit_mask |= 1 << ans[i];
}
// make a "list" of numbers that we need to find
for(int i = 0; i < 6; ++ i) {
for(int j = 0; j < ST1; ++ j)
bit_mask &= ~(1 << arrays[i][j]); // clear bits of the mask
if(!bit_mask) // check if we have them all
return 1; // all of the numbers were found
}
assert(bit_mask != 0);
return 0; // there are some numbers remaining yet to be found
}
Это будет выполнено максимум в O(6 * ST1 + 6), в лучшем случае в O(6 + 1), если первое число в первом массиве охватывает все ans (а также ans шесть раз такое же число). Обратите внимание, что проверка на нулевую битовую маску может проводиться либо после каждого массива (как сейчас), либо после каждого элемента (таким образом, требуется больше проверки, но также и более ранняя отсечка, когда найдены все числа). В контексте CUDA первая версия алгоритма, скорее всего, будет быстрее, так как включает меньше ветвей, и большинство циклов (кроме цикла для ST1) можно автоматически развернуть.
Однако, если диапазон чисел неограничен, мы могли бы сделать что-то еще. Поскольку в ans и во всех массивах имеется только до 7 * 6 = 42 разных чисел, можно отобразить их на 42 разных числа и использовать 64-битное целое число для битовой маски. Но, возможно, такое отображение чисел на целые уже было бы достаточно для теста, и было бы возможно вообще пропустить этот тест.
Другой способ сделать это - отсортировать массивы и просто подсчитать покрытие отдельных номеров:
int IsPresent(int arrays[][6], int ans[6], int ST1)
{
int all_numbers[36], n = ST1 * 6;
for(int i = 0; i < 6; ++ i)
memcpy(&all_numbers[i * ST1], &arrays[i], ST1 * sizeof(int));
// copy all of the numbers into a contiguous array
std::sort(all_numbers, all_numbers + n);
// or use "C" standard library qsort() or a bitonic sorting network on GPU
// alternatively, sort each array of 6 separately and then merge the sorted
// arrays (can also be done in parallel, to some level)
n = std::unique(all_numbers, all_numbers + n) - all_numbers;
// this way, we can also remove duplicate numbers, if they are
// expect to occur frequently and make the next test faster.
// std::unique() actually moves the duplicates to the end of the list
// and returns an iterator (a pointer in this case) to one past
// the last unique element of the list - that gives us number of
// unique items.
for(int i = 0; i < 6; ++ i) {
int *p = std::lower_bound(all_numbers, all_numbers + n, ans[i]);
// use binary search to find the number in question
// or use "C" standard library bfind()
// or implement binary search yourself on GPU
if(p == all_numbers + n)
return 0; // not found
// alternately, make all_numbers array of 37 and write
// all_numbers[n] = -1; before this loop. that will act
// as a sentinel and will save this one comparison (assuming
// that there is a value that is guaranteed not to occur in ans)
if(*p != ans[i])
return 0; // another number found, not ans[i]
// std::lower_bound looks for the given number, or for one that
// is greater than it, so if the number was to be inserted there
// (before the bigger one), the sequence would remain ordered.
}
return 1; // all the numbers were found
}
Это будет работать в O(n) для копирования, O(36 log 36) для сортировки, опционально O(n) для копирования unique (где n равно 6 * ST1) и O(n log n) для поиска (где n может быть меньше 6 * ST1, если unique Используется). Таким образом, весь алгоритм выполняется за линейное время. Обратите внимание, что это не требует какого-либо динамического распределения памяти и, как таковое, подходит даже для платформ графических процессоров (необходимо реализовать сортировку и порт std::unique() а также std::lower_bound(), но это все простые функции).