Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Помоги с упрощением алгоритма

Автор: ReGeDiT 31.8.2006, 17:13

для некоторых целей, мною был создан сложный алгоритм для поиска значений одного массива в другом. Т.е. проверить содержутся ли во 2м массиве элементы первого. До сих пор у меня есть уверенность что сделать всё можно намного проще  Помоги упростить это. Главный минус моего алгоритма - УЖАСНО МЕДЛЕННАЯ СКОРОСТЬ работы. Вот мой алгоритм: Код i = 1; j = 1; cs = 0; // ставим в нужное значение do {     if ((lcm[i]!=ltm[j])&&(lcm[i]!=0)) { j++; printf("lcm[%d/%d]!=ltm[%d/%d] (%d!=%d)\n",i,ds1,j,wsc,lcm[i],ltm[j]); cs = 0;  } // сравниваем элементы 1го массива и 2го массива, также отсеиваем нулевые     else                               { printf("Element %d Exists, All Ok!\n",lcm[i]); i++; j = 1; cs = 1; }; // если нашли то выводим сообшение что нашли     if ((j==wsc)&&(cs!=1))             { printf("Element %d NOT Exists!\n",lcm[i]); // если пробежали весь массив и не нашли ничего то выводим сообщение что нету такого                                          i++; // переходим на следующий элемент массива                                          j = 1; // ставим второй массив на начало, т.е. на первый элемент                                        };    } while (i!=ds1); // ds1 в данном случае количество элементов первого массива

Автор: Earnest 31.8.2006, 17:30

Отсортировать оба.  Если менять нельзя, отсортировать копии, и искать в них.  Если порядок зачем-то нужно сохранить, заведи структуру {значение, исходный индекс}, отсортируй ее по значению (можно еще флаг добавить - "встречается\не встречается"), проверь, выведи все скопом. Как искать совпадения в отсортированных массивах надо объяснять? ЗЫ И не пиши так ужасно код: чего строчки экономишь? Читать же невозможно...

Автор: maxim1000 31.8.2006, 17:36

Ну во-первых существующий алгоритм неплохо было быупростить для понимания человеком - два вложенных цикла смотрелись бы значительно проще, а работали бы так же если рассматривать два произвольно заполненных массива, то сомневаюсь, что можно сделать быстрее однако, можно работать с отсортированными массивами - тогда поиск будет значительно быстрее можно также работать с hash-массивами, хотя мне кажется, что по сравнению с отсортированными разницы не будет P.S. о, не успел

Автор: bsa 31.8.2006, 17:45

Про форматирование... К сожалению, ни в школе, ни в институте не учат правильному форматированию программ. И вот каждый пытается изобрести велосипед... В конце концов, он приходит к одному из общепринятых стилей... Но не сразу. ReGeDiTКак ты думаешь, код в таком виде читается лучше, чем тот, что дал ты? Код // ставим в нужное значение i = 1; j = 1; cs = 0; do {     if ( (lcm[i] != ltm[j]) && (lcm[i] != 0) ) { // сравниваем элементы 1го массива и 2го массива, также отсеиваем нулевые          ++j;          printf("lcm[%d/%d]!=ltm[%d/%d] (%d!=%d)\n", i, ds1, j, wsc, lcm[i], ltm[j]);          cs = 0;     } else { // если нашли то выводим сообшение что нашли          printf("Element %d Exists, All Ok!\n", lcm[i]);          ++i;          j = 1;          cs = 1;     };     if ( (j == wsc) && (cs != 1) ) {          printf("Element %d NOT Exists!\n", lcm[i]); // если пробежали весь массив и не нашли ничего то выводим сообщение что нету такого          ++i; // переходим на следующий элемент массива          j = 1; // ставим второй массив на начало, т.е. на первый элемент     }; } while (i != ds1); // ds1 в данном случае количество элементов первого массива Кстати, обрати внимание на использование оператора ++. Если тебе не нужно получать значение до выполнения инкремента, то лучше использовать ++i, так как гарантированно быстрее работает (а скорость работы i++ сильно зависит от качества и степени оптимизации).

Автор: zkv 31.8.2006, 18:08

Цитата(bsa @ 31.8.2006,  17:45) Про форматирование... К сожалению, ни в школе, ни в институте не учат правильному форматированию программ. И вот каждый пытается изобрести велосипед... В конце концов, он приходит к одному из общепринятых стилей... Но не сразу. у нас препод отказывался проверять прогу, пока она не будет отформатирована как он считал нужным. Можно было  возмущаться по-этому поводу, но прогу все равно приходилсь форматировать  Простите за оффтоп - не мог не вступиться за преподавателей

Автор: Oleg_Ci 31.8.2006, 18:56

Я нечто похожее делал: Цитата Задача 6. Даны две целочисленных таблицы А [1:10] и В[1:15].  Разработать алгоритм и написать программу, которая проверяет,  являются ли эти таблицы похожими. Две таблицы называются похожими,  если совпадают множества чисел, встречающихся в этих таблицах. Решение задачи 6. Мы можем отсортировать оба массива - и A, и B (например, по неубыванию),  далее, если первые элементы массивов A и B совпадают, то ищем и в A, и в  B минимальные элементы, большие данного, и повторяем сравнения;  если же элементы не совпадают, либо один из массивов уже закончился,  а другой еще нет, то массивы не похожие. Здесь "левые" функции, которые русский текст выводят. Код #include<iostream> #include <stdio.h> #include <windows.h> using namespace std; char Buf[1000];   // буфер для переведённого слова в Oem char *ToOem(char*); // переводит строку из Ansi в Oem void Write(char*); // выводит на консоль строку преобразованную AnsiToOem template <typename T, int size> void WrMas( T (&a)[size]);   // выводит на консоль содержимое массива template <typename T, int size> void sort( T (&a)[size]); // сортировка массива bool poisk(int[],int,int&); // поиск в массиве числа ////////////////    MAIN    /////////////// int main() {     int a[]={1,1,2,3,4,14,6,7,7,8};     int b[]={1,1,3,2,4,5,6,7,8,7,11,12,13,14,15};     sort( a );   // сортировка массивов     sort( b );     WrMas( a );  // вывод содержимого массивов     WrMas( b );     int pos1, pos2=pos1=0;     for ( int i=0; i<15; i++ )         if(poisk(b,a[pos1], pos2))         { pos1++; pos2++; }     if (pos1==10) Write("Массивы похожы");     else Write("Массивы не похожы !");     cout << "\n\n\n";     system("pause");     return 0; } ///////////////// END MAIN  ////////////////////////// bool poisk(int b[],int a,int &pos) {   for( ; pos<15; pos++ )     if ( b[pos] == a ) return true;   return false; } //---------------------------------------- char *ToOem(char* ch) {   AnsiToOem(ch,Buf);   return Buf; } //---------------------------------------------- void Write(char*c) {   cout<<ToOem(c); } //----------------------------------------------- template <typename T, int size> void WrMas( T (&a)[size])   // выводит на консоль содержимое массива {   for ( int i=0; i<size; i++ )     cout<<a[i]<<ends;     cout << "\n\n"; } //----------------------------------------------------- template <typename T, int size> void sort( T (&a)[size]) // сортировка массива {   for ( int i=0; i<size-1; i++ )     if (a[i]>a[i+1])     {       T x = a[i];       a[i]=a[i+1];       a[i+1]=x;       if ((i-=2)<0) i=-1;     } }

Автор: ReGeDiT 31.8.2006, 21:29

по поводу форматирования: программа пишется для себя и никуда здаватся не будет. важна только работа. спасибо за подсказки с сортировкой и ++i; а какие есть способы сортировки? я что-то слышал о Quick Sort... Ведь массивы довольно большие... а всякие сортировки дедовским методом пузырька не будут быстрыми...)

Автор: zkv 31.8.2006, 21:50

Цитата по поводу форматирования: программа пишется для себя и никуда здаватся не будет. важна только работа. а если через месяц (год, два) захочешь подправить свой код? Цитата а какие есть способы сортировки? простыми включениями, простым выбором, простым обменом (пузырек), сложным выбором (двоичное дерево),  сложными вставками (Шелла),  сложным обменом (Хоора или Quick Sort) что то из этого есть на этом же форуме в разделе "алгоритмы" если я не ошибаюсь

Автор: kondr 1.9.2006, 11:26

Цитата Отсортировать оба. Зачем, если мы ищем элементы первого массива во втором? Остортировать только второй массив, а потом перебитрать элементы первого и бинарным поиском искать их во втором.

Автор: maxim1000 1.9.2006, 11:44

пожалуй, этот вариант ещё лучше, получатся n*log n+m*log n а в случае двух сортировок - n*log n+m*log m [ну ещё+m+n, но это не так важно] преимущества 2: 1. если размеры массивов разные, то мы можем, как захотим, выбирать, что m, а что n, тогда при сортировке меньшенго массива m*log n будет меньше m*log m 2. быстрая сортировка не гарантирует n*log n, так что сортируя только один массив мы уменьшаем риск (бинарный поиск даёт log n гарантированно), а сортировка слиянием, которая гарантирует n*log n, требует n памяти, так что сортировать только меньший массив тоже выгодно впрочем, на небольших массивах эти различия могут быть незаметны...

Автор: Oleg_Ci 1.9.2006, 14:50

Цитата а какие есть способы сортировки? я что-то слышал о Quick Sort... Ведь массивы довольно большие... а всякие сортировки дедовским методом пузырька не будут быстрыми...) Код #include <algorithm> ... const int size = 10; int mas[ size ]; std::sort( mas, mas + size ); ... Помойму там "быстрая"(так называется) сортировка.

Автор: ReGeDiT 4.9.2006, 22:14

гмммммммммммммммммм....................... ладно. допустим сортировка 1го массива будет эффективней сортировки 2х сразу. тогда, может лучше отсортировать 2 массива, и вычёркивать из второго проверенные элементы?.. т.е. сокращать массив... я просто незнаю как это реализовать. И может ли кто написать какой-нибудь быстрый алгоритм сортировки на C (НЕ C++!!) ТАКЖЕ! допустим имеется 1 массив, как проверить его на повторяющиеся элементы, т.е. допустим есть ли в нём одинаковые... они могут быть совершенно в разных местах? в голову ничего не лезет... З.Ы.: Какие в Microsoft Visual C++ 7.0 есть средства тайминга программ (засекать скорость работы..).

Автор: Greeen 4.9.2006, 22:20

Цитата(ReGeDiT @  4.9.2006,  22:14 ) И может ли кто написать какой-нибудь быстрый алгоритм сортировки на C В разделе "Алгоритмы" поищи... Цитата(ReGeDiT @  4.9.2006,  22:14 ) Какие в Microsoft Visual C++ 7.0 есть средства тайминга программ DWORD GetTickCount(void);

Автор: Mayk 5.9.2006, 14:14

Цитата(ReGeDiT @  5.9.2006,  02:14 ) И может ли кто написать какой-нибудь быстрый алгоритм сортировки на C (НЕ C++!!) qsort из стандартной библиотеки си (не с++)

Автор: ДобренькийПапаша 5.9.2006, 17:54

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

Автор: Mayk 5.9.2006, 17:58

Цитата(ДобренькийПапаша @  5.9.2006,  21:54 ) которые пишутся вручную за две минуты...  То что пишется за две минуты иногда отлаживается за пол часа и даже более.  Гораздо более серьезной проблемой qsort а является то, что он вызывает ф-цию каждый раз для сравнения [std::sort может заinlineить компаратор, а вот qsort очень навряд ли]. Однако в любом случае - не стоит что-либо оптимизировать и переписывать, пока profiler показывает что в этом нет особой нужды.

Автор: Greeen 5.9.2006, 19:05

Цитата(Mayk @  5.9.2006,  17:58 ) компаратор

Автор: Mayk 5.9.2006, 20:49

Цитата(Greeen @  5.9.2006,  23:05 ) компаратор Вообще это англ Comparator. "Сравниватель".  В частности Цитата(qsort(3))        The comparison function must return an integer less than, equal to,  or        greater  than  zero  if  the first argument is considered to be respec‐        tively less than, equal to, or greater than the second.  If two members        compare as equal, their order in the sorted array is undefined.

Автор: ReGeDiT 5.9.2006, 20:55

кхм, ладно, с сортировкой покончили... вот ещё пару вопросов на повестке дня  "Тогда, может лучше отсортировать 2 массива, и вычёркивать из второго проверенные элементы?.. т.е. сокращать массив... я просто незнаю как это реализовать. (можете помочь то...) ТАКЖЕ! допустим имеется 1 массив, как проверить его на повторяющиеся элементы, т.е. допустим есть ли в нём одинаковые... они могут быть совершенно в разных местах? в голову ничего не лезет... (помогите тоже.....)" алгоритм мой в самом первом посте... и как всё-таки таймингом пользоватся то?? можно примерчик то )) я же всё-таки начинающий кодер...

Автор: Earnest 6.9.2006, 06:21

Цитата(ReGeDiT @  5.9.2006,  21:55 ) допустим имеется 1 массив, как проверить его на повторяющиеся элементы Опять отсортировать, тогда одинаковые элементы будут рядом. В STL есть алгоритм unique, который убирает дубликаты.

Автор: ReGeDiT 6.9.2006, 19:46

Earnest, а если элементов 200? =) Может всё-таки кто-нибудь поможет мне..........................? 1) Помогите усовершенствовать мой код выше! У меня такая идея, может лучше отсортировать 2 массива, и вычёркивать из второго проверенные элементы?.. т.е. сокращать второй массив... я просто незнаю как это реализовать. 2) Имеется 1 массив, как проверить его на повторяющиеся элементы, т.е. допустим есть ли в нём одинаковые... они могут быть совершенно в разных местах, и их может быть много? 3) Как пользоватся таймингом? можно примерчик то )) я же всё-таки начинающий кодер -.-

Автор: Earnest 7.9.2006, 07:52

А что 200 - это по-твоему много? Много - это 200 000. А на 200 почти нет разницы - что линейный поиск, что бинарный. Что именно тебе не понятно? В отсортированном массиве одинаковые элементы стоят рядом: бери и проверяй, за один проход. Если речь идет о сравнении 2 отсортированных массивов, то там тоже просто: инкрементируй индекс первого, пока его элементы меньше второго. И наоборот. Если элементы совпадают, инкрементируй оба индекса.  По-моему, кто-то такой код тебе уже писал. Что значит "не знаю как реализовать"? Пока не попробуешь, не узнаешь.

Автор: zkv 7.9.2006, 20:49

Цитата(Earnest @  7.9.2006,  07:52 ) Что значит "не знаю как реализовать"? Пока не попробуешь, не узнаешь. ИМХО тебе могут подсказать, написать прогу за тебя, но пока сам не напишешь, лучше разбираться в языке не станешь!

Автор: ReGeDiT 8.9.2006, 17:21

я имею в виду то что, вдруг будут 200 одинаковых рядом. Массив состоит примерно из 50 000 элементов ;). откуда я знаю сколько раз проверять массив?

Автор: Rockie 9.9.2006, 10:06

ReGeDiT, если я правильно понял вопрос - уничтожаешь следующее число до тех пор, пока не конец массива, либо пока следующее число не станет отлично от данного. это только как один из многих вариантов

Автор: Voldemar2004 9.9.2006, 13:05

На работе была такая же задача: нужно было выбрать из БД все номера ИНН и номера, которые попали на выделение, затем сравнить и получить список тех людей, которые не попали. Вкратце так: Код #include <iostream.h> #include <conio.h> int main(void) { const int k=10, l=6; int a[k] = {1, 3, 76, 34, 654, 7653, 345, 3456, 75, 22}; int b[l] = {1, 34, 654, 3456, 75, 22};        for(int i=0; i<k; i++)        {        bool flag = false;         for(int j=0; j<l; j++)         {          if( a[i] == b[j] ) flag = true;         }          if (!flag) cout << a[i] << '\n' ;        } getch(); return 0; } Делал без сортировки, работает довольно быстро.

Автор: Voldemar2004 9.9.2006, 14:00

Цитата(ReGeDiT @  6.9.2006,  20:46 )  Имеется 1 массив, как проверить его на повторяющиеся элементы, т.е. допустим есть ли в нём одинаковые... они могут быть совершенно в разных местах, и их может быть много? Код #include <iostream.h> #include <conio.h> #include <stdlib.h>  // qsort() int intcmp(const void *, const void *); int main(void) { const int k=20; int a[k] = {1, 99, 9, 3, 0, 34, 654, 34, -345, 3456, 34, -1000, 321, 13244, 0, 654, -100, 1000, -1000, 9};         qsort(&a[0], k, sizeof(int), intcmp); /* Сортировка. */         for(int i=0; i<k-1; i++)         if( a[i] == a[i+1] ) cout << a[i+1] << '\t'; getch(); return 0; } /* Функция сравнения. */ int intcmp(const void *a, const void *b) {  return *(int *)a - *(int*)b; } Можно было бы сделать код сортировки на ASM и вставить методом ассемблерной вставки (только метод сортировки должен быть быстрым, а то даже на ASM "пузырек" будет медленнеe qsort на C). Или другую функцию сортировки, используя inline-подстановку. Можно так же было сделать и без сортировки, но (профи сейчас начнут меня ругать  ) это лишний - перебор + цикл в цикле + сравнения flag = true/false, особенно для 50000 элементов.

Автор: ReGeDiT 9.9.2006, 15:39

спасибо! осталось 2 вопроса  --- посмотрел второй код получше... а там ведь сравнивается просто на 2 одинаковых максимум... а если их больше? сделать цикл по длине массива а внутрь его запихнуть это? тока мне кажется будет бред

Автор: Voldemar2004 9.9.2006, 16:31

Цитата(ReGeDiT @  6.9.2006,  20:46 )  Как пользоватся таймингом? можно примерчик то я же всё-таки начинающий кодер Библиотека time.h. А вообще поконкретней объясни чего ты хочешь. Цитата(ReGeDiT @  9.9.2006,  16:39 ) осталось 2 вопроса Каких?

Автор: Voldemar2004 9.9.2006, 21:39

Цитата(ReGeDiT @  9.9.2006,  15:39 )  а там ведь сравнивается просто на 2 одинаковых максимум... Нет. {1, 99, 9, 3, 0, 34, 654, 34, -345, 3456, 34, -1000, 321, 13244, 0, 654, -100, 1000, -1000, 9}; 34 - встречается 3 раза, выводим - два раза 34 - они "лишние". Хотя, можно еще так: если число встречается > 2 раз, то выводим его столько раз сколько оно встречается в массиве: Код #include <iostream.h> #include <conio.h> #include <stdlib.h>  // qsort() int intcmp(const void *, const void *); int main(void) { const int k=20; int a[k] = {1, 99, 9, 3, 0, 34, 654, 34, -345, 3456, 34, -1000, 321, 34, 0, 654, -100, 1000, -1000, 9};         qsort(&a[0], k, sizeof(int), intcmp);          for(int i=0; i<k-1; i++)         {          if (a[i] == a[i+1]) {          cout << a[i] << '\n';                 do{                 i++;                 cout << a[i] << '\n';                 }                 while(a[i] == a[i+1]);          }         } getch(); return 0; } int intcmp(const void *a, const void *b) {  return *(int *)a - *(int*)b; } Для наглядности я здесь поставил число 34 четыре раза.

Автор: Oleg_Ci 10.9.2006, 08:39

Цитата для некоторых целей, мною был создан сложный алгоритм для поиска значений одного массива в другом. Т.е. проверить содержутся ли во 2м массиве элементы первого. До сих пор у меня есть уверенность что сделать всё можно намного проще  Помоги упростить это. Код #include <stdio.h> void QuickSort( int * a, long N); int main()     {     long const sizeA = 10;     long const sizeB = 15;     int a[ sizeA ] = { 3, 4, 3, 2, 43, 54, 43, 3, 3, 2 };     int b[ sizeB ] = { 3, 2, 43, 54, 4, 3, 2, 21, 45, 3, 23, 2, 3, 3, 32 };     QuickSort( a, sizeA -1 );     QuickSort( b, sizeB -1 ); // поиск значений одного массива (a) в другом (b)     int i = 0, j = 0, count = 0;     while( i < sizeA && j < sizeB )     {         if ( a[i] == b[j] )           {    // вывод одинаковых значений             printf("a[%d] = %3d   ==    b[%d] = %3d\n", i, a[i], j, b[j] );              i++;             j++;             count++;         }         else if ( a[i] < b[j] )  i++;         else j++;    // ( a[i] > b[j] )     }     printf("\n\ncount = %d", count ); // выводим количество найденых элементов     getchar();     return 0; } /////////////////////// END MAIN ///////////////////////////////////////////////////////////// void QuickSort( int * a, long N) //   http://algolist.manual.ru/ {// На входе - массив a[], a[N] - его последний элемент.   long i = 0, j = N;        // поставить указатели на исходные места   int temp, p;   p = a[ N>>1 ];        // центральный элемент   // процедура разделения   do {     while ( a[i] < p ) i++;     while ( a[j] > p ) j--;     if (i <= j) {       temp = a[i]; a[i] = a[j]; a[j] = temp;       i++; j--;     }   } while ( i<=j );   // рекурсивные вызовы, если есть, что сортировать    if ( j > 0 ) QuickSort(a, j);   if ( N > i ) QuickSort(a+i, N-i); } Я вроде понял что надо найти одинаковые числа в двух массивах, и все их собрать в одном массиве (у меня в связанном списке): Код #include<stdlib.h> #include <stdio.h> int intcmp(const void *, const void *); struct number {     int x;     number * n; }*num, *n; int main()     {     long const sizeA = 10;     long const sizeB = 15;     n = num = NULL;     int a[ sizeA ] = { 3, 4, 3, 2, 43, 54, 43, 3, 1, 2 };     int b[ sizeB ] = { 3, 2, 43, 54, 4, 3, 2, 21, 45, 3, 23, 2, 1, 3, 32 };         qsort( a, sizeA, sizeof(int), intcmp );     qsort( b, sizeB, sizeof(int), intcmp ); // поиск значений одного массива (a) в другом (b)     int i = 0, j = 0, count = 0;     while( i < sizeA && j < sizeB )     {         if ( a[i] == b[j] )           {                 if( n == NULL || n->x != a[i] )             {                 if ( n == NULL ) num = n = (struct number*) malloc( sizeof( struct number ));                 else   n = n->n = (struct number*) malloc( sizeof( struct number ));                 n->x = a[i];                 n->n = NULL;                 count++;             }             i++;             j++;         }         else if ( a[i] < b[j] )  i++;         else j++;    // ( a[i] > b[j] )     }     printf("count = %d\n\n", count ); // выводим количество найденых элементов     for ( n = num; n!= NULL; n = n->n ) // выводим одинаковые числа         printf("number = %d\n", n->x );      getchar();     return 0; } /////////////////////// END MAIN ///////////////////////////////////////////////////////////// int intcmp(const void *a, const void *b) {  return *(int *)a - *(int*)b; }

Автор: Oleg_Ci 12.9.2006, 17:58

Простите, не туда записал Всё удалил...

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)