алгоритмическое программирование

[LEO]

есть задача:

2 массива, ну, скажем строк. разной длинны.

надо найти все пары одинаковых значений, т.е. все i,j : A(i)=B(j)

естественно полный перебор двумя вложенными циклами - не самое рациональное решение...

может кто подскажет литературку по подобным вопросам, и решение этой задачи в частности?

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

п.с. а для 3х массивов?

п.п.с. ... прочитал название своей темы... "алогритическое программирование" ... вроде не употреблял ничо )))

[Rob Playford]

Как вариант..

Создание некой логической таблицы или многомерного массива для более сложного случая. Назовем ее таблицой инизиализации InitTable. Содержит true/false значения по одинаковым/разным элементам или какими-либо вхождениям. Получив ее, знаем соотношения по элементам или вхождениям наших массивов.


using System;

class Program
    {
        static void Main(string[] args)
        {
            char[] A = {'L','E','O'};
            char[] B = { 'P', 'L', 'A', 'Y', 'F', 'O', 'R', 'D' };
            bool[,] InitTable = new bool [A.Length,B.Length];
            for (int i = 0; i < A.Length; i++)
            {
                for (int j = 0; j < B.Length; j++)
                {
                    if (A == B[j])
                    {
                        InitTable[i, j] = true;
                    }
                    else
                    {
                        InitTable[i, j] = false;
                    }
                }
            }

#region
        }
    }






http://alglib.sources.ru/ - uri к интересному ресурсу по алгоритмам include .NET sources

[Wizard]

есть задача:

2 массива, ну, скажем строк. разной длинны.

надо найти все пары одинаковых значений, т.е. все i,j : A(i)=B(j)

А если создать множество, закинуть туда парами первый массив и его номера и в одном цикле просканировать второй массив на предмет вхождения очередного элемента в это множество?

Правда объем вычислений скорее всего получится не меньше.

Создание некой логической таблицы или многомерного массива для более сложного случая. Назовем ее таблицой инизиализации InitTable.

Так это и есть двойной цикл в явном виде.

[exBoMBeR]

А если создать множество, закинуть туда парами первый массив и его номера и в одном цикле просканировать второй массив на предмет вхождения очередного элемента в это множество?

Правда объем вычислений скорее всего получится не меньше.

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

[Lelik_*]

вы че хоть, проще можно - создать новый массив как 1 + 2 и отсортировать его, после сортировки рядом парные значения будут

[exBoMBeR]

вы че хоть, проще можно - создать новый массив как 1 + 2 и отсортировать его, после сортировки рядом парные значения будут

Во первых: оцените затраты на создание массива 1 + 2 и затраты на сортировку двух массивов строк.
Во вторых: никто не сказал что строки в пределах одного массива не повторяются => вы получите не только пары, но и тройки, четверки и т.д. одинаковых строк.

[Hitokiri_Rid]

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

[LEO]

можно отсортировать каждый массив в начале. тогда вложенный цикл можно пускать не по всему массиву, а начиная от некоторого начального индекса, который мы узнаем из предыдущего прогона, и до момента, пока B(j) не станет больше A(i).

а для сравнения строк использовать strcomp()

если н элелемнов в А и м элементов в Б, то будет lnн+lnм сравнений при быстрой сортировке + некоторое число сравнений, непосредственно при поиске пар...

[_Atheist_]

Если именно для .NET, то для решения таких задач используется LINQ.
Единственное ограничение - появился в .NET 3.5
Немного переделанный пример из MSDN по .NET 3.5:

Код: [Выделить]

using System;
using System.Collections.Generic;
using System.Linq;

namespace testLinq
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] array1 = new string[]{"a", "b", "c", "d"};
            string[] array2 = new string[]{"d", "e", "f", "c", "m"};
            IEnumerable<string> differenceQuery =
                array1.Intersect(array2);

            // Execute the query.
            Console.WriteLine("The following lines are in array1 and in array2");
            foreach (string s in differenceQuery)
                Console.WriteLine(s);
            Console.ReadKey();
        }
    }
}


[LEO]

ого! _Atheist_ ++++!

я когда vs2008 скачал, почти сразу LINQ попробовал, но меня хватило только чтоб его протестить на своей базе, почти на уровне примеров из мсдн... а то что его можно не только для БД юзать - мне как-то в голову не пришло)))

где б статей почитать хороших на русском про .net кроме gotdtnet.ru не подскажете?

[pantera]

ого! _Atheist_ ++++!

я когда vs2008 скачал, почти сразу LINQ попробовал, но меня хватило только чтоб его протестить на своей базе, почти на уровне примеров из мсдн... а то что его можно не только для БД юзать - мне как-то в голову не пришло)))

где б статей почитать хороших на русском про .net кроме gotdtnet.ru не подскажете?

ну если бы ты читал http://blogs.gotdotnet.ru/ , то много интересного узнал про LINQ Если комп многоядерный, поюзай PLINQ

[Нервный]

 Ускорять для начала нужно cобственно операцию сравнения строк. Каждой строке сопоставляем некое значение, называемое хеш. В простейшем случае, сумма всех ASCII-кодов символов строки. Тогда сравнение строк сведётся к следующей операции. Кеши не равны ? ----> строки однозначно не равны. Кеша равны ? Обычное сравнение. Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp. Соответсвенно, и весь алгортим ускорится до 5 раз  и более.

[_Atheist_]

ого! _Atheist_ ++++!

я когда vs2008 скачал, почти сразу LINQ попробовал, но меня хватило только чтоб его протестить на своей базе, почти на уровне примеров из мсдн... а то что его можно не только для БД юзать - мне как-то в голову не пришло)))

Так ведь весь смысл как раз в том, что не только для БД. Просто для БД уже давно все SQL пользуются.

где б статей почитать хороших на русском про .net кроме gotdtnet.ru не подскажете?

Я бы для начала посоветовал почитать Джеффри Рихтера CLR via C#, если уж по .NET так все интересно.
К gotdotnet я бы еще рекомендовал форумы на sql.ru. Там не только про SQL
Еще, наверное, можно почитать MSDN Magazine.
Также думаю, можно почитать еще RSDN.
Ну и Гугл с Тындиксом тоже полезные источники статей.

[LEO]

Ускорять для начала нужно cобственно операцию сравнения строк. Каждой строке сопоставляем некое значение, называемое хеш. В простейшем случае, сумма всех ASCII-кодов символов строки. Тогда сравнение строк сведётся к следующей операции. Кеши не равны ? ----> строки однозначно не равны. Кеша равны ? Обычное сравнение. Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp. Соответсвенно, и весь алгортим ускорится до 5 раз  и более.

спасибо.
Object.GetHashCode() - вроде даже работает ))

зы. напишу для чего все это мне нужно...

захотелось мне написать прогу, которая находит TTH для файлов, которые я из DC++ скачиваю.
можно конечно его просто посчитать, но это не очень быстро. на моем компе скорость около 12-15 МБ\с при полной загрузке ЦПУ.

пытался найти опцию, чтобы в лог StrongDC++ заносить TTH скачиваемого файла - не нашел. он даже размер туда часто неправильный заносит.

а поэтому сделал так. прога читает лог, ищет эти файлы на харде, смотрит их размер.

далее из папки диси читает файллист (это XML в архиве). читает просто. создаю DataSet и вызываю DataSet.ReadXML. он это читает, долольно долго кстати для больших файлов. и распихивает все что прочитал по таблицам, среди которых есть и таблица файлов, у которой столбцы - имя, размер и TTH ... вот собственно я эту табличку и сравниваю с массивом струткур, в которой имена и размеры файлов, скачанных с данного юзера.

[Lelik_*]

Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp.

есть, есть еще люди помнящие названия функций CRT +
но тут на дотнете просили

[LEO]

Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp.

есть, есть еще люди помнящие названия функций CRT +
но тут на дотнете просили

да какая разница. String.Compare() - она же)

п.с. наверное неплохо будет если совместить хеши с фишкой на LINQ ... займусь обязательно)

[exBoMBeR]

Ускорять для начала нужно cобственно операцию сравнения строк. Каждой строке сопоставляем некое значение, называемое хеш. В простейшем случае, сумма всех ASCII-кодов символов строки. Тогда сравнение строк сведётся к следующей операции. Кеши не равны ? ----> строки однозначно не равны. Кеша равны ? Обычное сравнение. Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp. Соответсвенно, и весь алгортим ускорится до 5 раз  и более.

Примерно так?

Код: [Выделить]

#include <stdio.h>
#include <time.h>

void scan1(char *A[], int nA, char *B[], int nB)
{
  int i, j;

  for(i=0; i<nA; i++)
    for(j=0; j<nB; j++)
      if(!strcmp(A[i], B[j])) printf("A[%i] = B[%i]\n", i, j);
}



int cs(char *s)
{
  int c = 0;
  while(*s)
    c += *s++;
  return c;
}

scan2(char *A[], int nA, char *B[], int nB)
{
  int *cA, *cB;
  int i, j;

  cA = (int*)malloc(nA*sizeof(int));
  cB = (int*)malloc(nB*sizeof(int));

  for(i=0; i<nA; i++)
    cA[i] = cs(A[i]);

  for(j=0; j<nB; j++)
    cB[j] = cs(B[j]);

  for(i=0; i<nA; i++)
    for(j=0; j<nB; j++)
      if(cA[i] == cB[j]) printf("A[%i] = B[%i]\n", i, j);

  free(cA);
  free(cB);
}

int main(int argc, char *argv[])
{

char *A[] = {
  "black",
  "red",
  "green",
  "yellow",
  "white",
  "black",
  "red",
  "green",
  "yellow",
  "white"
  "white",
  "green",
  "blue",
  "red",
  "yellow",
  "white",
  "green",
  "blue",
  "red",
  "yellow"
};
int nA = sizeof(A)/sizeof(char*);

char *B[] = {
  "white",
  "green",
  "blue",
  "red",
  "yellow",
  "white",
  "green",
  "blue",
  "red",
  "yellow"
  "black",
  "red",
  "green",
  "yellow",
  "white",
  "black",
  "red",
  "green",
  "yellow",
  "white"
};
int nB = sizeof(B)/sizeof(char*);

time_t tm;
int tscan1, tscan2;
int k;

  tm = time(0);
  for(k=0; k<100000; k++)
    scan1(A, nA, B, nB);
  tscan1 = time(0) - tm;

  tm = time(0);
  for(k=0; k<100000; k++)
    scan2(A, nA, B, nB);
  tscan2 = time(0) - tm;

  printf("scan1 time: %i\n", tscan1);
  printf("scan2 time: %i\n", tscan2);
}

scan1 - обычный двойной цикл с использованием strcmp()
scan2 - подсчитывает контрольную сумму для строк, а потом сравнивает суммы так же в двойном цикле.
Программа замеряет время в секундах выполнения 100 тысяч вызовов алгоритмов

не получается до 5 раз ... ускорение получилось меньше 4%

[Нервный]

 Милейший. У Вас printf жрёт всё время. Уберите printf и увеличте количество циклов на порядочек.

 ./a.out
scan1 time: 6
scan2 time: 3


 Вообще, что-то Ваша программочка левые результаты показывает. Что-то мне подсказывает, что слажались Вы где-то.

[Нервный]

# include <stdio.h>
# include <string.h>
typedef struct
{
   unsigned short hash;
   unsigned char len;
   char string [20];
   
} hashtype;

char *A[] = {
   "black",
   "red",
   "green",
   "yellow",
   "white",
   "black",
   "red",
   "green",
   "yellow",
   "white"
   "white",
   "green",
   "blue",
   "red",
   "yellow",
   "white",
   "green",
   "blue",
   "red",
   "yellow"
};

int nA = sizeof(A)/sizeof(char*);

char *B[] = {
   "white",
   "green",
   "blue",
   "red",
   "yellow",
   "white",
   "green",
   "blue",
   "red",
   "yellow"
   "black",
   "red",
   "green",
   "yellow",
   "white",
   "black",
   "red",
   "green",
   "yellow",
   "white"
};

int nB = sizeof(B)/sizeof(char*);

hashtype CalculateHash(char * string)
{
   int i;
   int len;
   
   unsigned short hash=0;
   hashtype rv;
   
   
   len = strlen (string);
   for (i=0; i<len; i++)
      hash += string;
   
   rv.hash = hash;
   rv.len = len;
   
   strcpy(rv.string, string);
   
   return rv;
}


__inline__ unsigned long long int rdtsc()
{
   unsigned long long int x;
   __asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
   return x;
}

int main (int argc, char ** argv)
{
   hashtype AH [nA];
   hashtype BH [nB];
   
   int i, j, k;
   int counter = 0;
   
   long long start, end;
   
   
   for (i=0; i<nA; i++)
      AH = CalculateHash(A);
   
   for (i=0; i<nB; i++)
      BH = CalculateHash(B);
   
   
   counter = 0;
   start = rdtsc();
   
   for (k=0; k<100000; k++)
      for (i=0; i<=nA; i++)
         for (j=0; j<=nB; j++)
            if (!strcmp(AH.string, BH[j].string))
               counter++;
            
   end = rdtsc();
   printf ("%d %d \n", (int) (end - start), counter);
   
   counter = 0;
   start = rdtsc();
   
   for (k=0; k<100000; k++)
      for (i=0; i<=nA; i++)
      {
         for (j=0; j<=nB; j++)
         {
            if ((AH.hash != BH[j].hash) || (AH.len != BH[j].len))
               continue;
            
            if (strcasecmp(AH.string, BH[j].string))
               continue;
            
            counter++;
         }
      }
   
   end = rdtsc();
   printf ("%d %d \n", (int) (end - start), counter);
}

======================================================
1183450688 5800000
622860264 5800000
======================================================

 Разница в два раза. Но у Вас пример не очень хороший. Строки подлиннее сгенерите, почуствуете всё мощь.
 В этот форумский движок тексты на C не лезут правильно. Смотрите атач.

[exBoMBeR]

...
 Разница в два раза. Но у Вас пример не очень хороший. Строки подлиннее сгенерите, почуствуете всё мощь.
...

Круто конечно ... а время выполнения

Код: [Выделить]


   for (i=0; i<nA; i++)
      AH = CalculateHash(A);
   
   for (i=0; i<nB; i++)
      BH = CalculateHash(B);

естественно не замеряем и не учитываем?

ради любопытства попробуйте конец программы заменить на

Код: [Выделить]


   start = rdtsc();

   for (i=0; i<nA; i++)
      AH = CalculateHash(A);

   for (i=0; i<nB; i++)
      BH = CalculateHash(B);

   for (k=0; k<100000; k++)
      for (i=0; i<=nA; i++)
      {
         for (j=0; j<=nB; j++)
         {
            if ((AH.hash != BH[j].hash) || (AH.len != BH[j].len))
               continue;
           
            if (strcasecmp(AH.string, BH[j].string))
               continue;
           
            counter++;
         }
      }
   
   end = rdtsc();
   printf ("%d %d \n", (int) (end - start), counter);

чтоб уж было по честному ...