Электростальский форум
Hi-Tech => Компьютеры, периферия, мультимедиа и ПО => Тема начата: LEO от 28.02.08, 19:31:21
-
есть задача:
2 массива, ну, скажем строк. разной длинны.
надо найти все пары одинаковых значений, т.е. все i,j : A(i)=B(j)
естественно полный перебор двумя вложенными циклами - не самое рациональное решение...
может кто подскажет литературку по подобным вопросам, и решение этой задачи в частности?
а если это будет статья про такие алгоритмы с использованием классов в .net - вообще шикарно) хотя, конечно, .net к данному вопросу никаким боком...)
п.с. а для 3х массивов?
п.п.с. ... прочитал название своей темы... "алогритическое программирование" ... вроде не употреблял ничо )))
-
Как вариант..
Создание некой логической таблицы или многомерного массива для более сложного случая. Назовем ее таблицой инизиализации 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/ (http://alglib.sources.ru/) - uri к интересному ресурсу по алгоритмам include .NET sources
-
есть задача:
2 массива, ну, скажем строк. разной длинны.
надо найти все пары одинаковых значений, т.е. все i,j : A(i)=B(j)
А если создать множество, закинуть туда парами первый массив и его номера и в одном цикле просканировать второй массив на предмет вхождения очередного элемента в это множество?
Правда объем вычислений скорее всего получится не меньше.
Создание некой логической таблицы или многомерного массива для более сложного случая. Назовем ее таблицой инизиализации InitTable.
Так это и есть двойной цикл в явном виде.
-
А если создать множество, закинуть туда парами первый массив и его номера и в одном цикле просканировать второй массив на предмет вхождения очередного элемента в это множество?
Правда объем вычислений скорее всего получится не меньше.
Так это и будет опять таки двойной вложенный цикл ... ведь в цикл по элементам второго массива придется включить цикл просмотра множества.
-
вы че хоть, проще можно - создать новый массив как 1 + 2 и отсортировать его, после сортировки рядом парные значения будут
-
вы че хоть, проще можно - создать новый массив как 1 + 2 и отсортировать его, после сортировки рядом парные значения будут
Во первых: оцените затраты на создание массива 1 + 2 и затраты на сортировку двух массивов строк.
Во вторых: никто не сказал что строки в пределах одного массива не повторяются => вы получите не только пары, но и тройки, четверки и т.д. одинаковых строк.
-
По-моему линейной трудоемкости тут и так не добьешся.
Все равно нужно сначала эти массивы отсортировать, потом сравнивать. Находятся одинаковые - сравнивается со след элементом - не равны, значит сравнение этих элементов закончилось, сравниваем следующие.
Литературку следует искать по теории алгоритмов и алгоритмизации.
-
можно отсортировать каждый массив в начале. тогда вложенный цикл можно пускать не по всему массиву, а начиная от некоторого начального индекса, который мы узнаем из предыдущего прогона, и до момента, пока B(j) не станет больше A(i).
а для сравнения строк использовать strcomp()
если н элелемнов в А и м элементов в Б, то будет lnн+lnм сравнений при быстрой сортировке + некоторое число сравнений, непосредственно при поиске пар...
-
Если именно для .NET, то для решения таких задач используется LINQ (http://msdn2.microsoft.com/ru-ru/library/bb308959(en-us).aspx).
Единственное ограничение - появился в .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();
}
}
}
-
ого! _Atheist_ ++++!
я когда vs2008 скачал, почти сразу LINQ попробовал, но меня хватило только чтоб его протестить на своей базе, почти на уровне примеров из мсдн... а то что его можно не только для БД юзать - мне как-то в голову не пришло)))
где б статей почитать хороших на русском про .net кроме gotdtnet.ru не подскажете?
-
ого! _Atheist_ ++++!
я когда vs2008 скачал, почти сразу LINQ попробовал, но меня хватило только чтоб его протестить на своей базе, почти на уровне примеров из мсдн... а то что его можно не только для БД юзать - мне как-то в голову не пришло)))
где б статей почитать хороших на русском про .net кроме gotdtnet.ru не подскажете?
ну если бы ты читал http://blogs.gotdotnet.ru/ , то много интересного узнал про LINQ :) Если комп многоядерный, поюзай PLINQ
-
Ускорять для начала нужно cобственно операцию сравнения строк. Каждой строке сопоставляем некое значение, называемое хеш. В простейшем случае, сумма всех ASCII-кодов символов строки. Тогда сравнение строк сведётся к следующей операции. Кеши не равны ? ----> строки однозначно не равны. Кеша равны ? Обычное сравнение. Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp. Соответсвенно, и весь алгортим ускорится до 5 раз и более.
-
ого! _Atheist_ ++++!
я когда vs2008 скачал, почти сразу LINQ попробовал, но меня хватило только чтоб его протестить на своей базе, почти на уровне примеров из мсдн... а то что его можно не только для БД юзать - мне как-то в голову не пришло)))
Так ведь весь смысл как раз в том, что не только для БД. Просто для БД уже давно все SQL пользуются. :)
где б статей почитать хороших на русском про .net кроме gotdtnet.ru не подскажете?
Я бы для начала посоветовал почитать Джеффри Рихтера CLR via C#, если уж по .NET так все интересно.
К gotdotnet я бы еще рекомендовал форумы на sql.ru (http://www.sql.ru). Там не только про SQL :)
Еще, наверное, можно почитать MSDN Magazine (http://msdn.microsoft.com/msdnmag/default.aspx).
Также думаю, можно почитать еще RSDN (http://www.rsdn.ru/).
Ну и Гугл (http://www.google.ru) с Тындиксом (http://www.yandex.ru) тоже полезные источники статей. ;)
-
Ускорять для начала нужно cобственно операцию сравнения строк. Каждой строке сопоставляем некое значение, называемое хеш. В простейшем случае, сумма всех ASCII-кодов символов строки. Тогда сравнение строк сведётся к следующей операции. Кеши не равны ? ----> строки однозначно не равны. Кеша равны ? Обычное сравнение. Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp. Соответсвенно, и весь алгортим ускорится до 5 раз и более.
спасибо.
Object.GetHashCode() - вроде даже работает ))
зы. напишу для чего все это мне нужно...
захотелось мне написать прогу, которая находит TTH для файлов, которые я из DC++ скачиваю.
можно конечно его просто посчитать, но это не очень быстро. на моем компе скорость около 12-15 МБ\с при полной загрузке ЦПУ.
пытался найти опцию, чтобы в лог StrongDC++ заносить TTH скачиваемого файла - не нашел. он даже размер туда часто неправильный заносит.
а поэтому сделал так. прога читает лог, ищет эти файлы на харде, смотрит их размер.
далее из папки диси читает файллист (это XML в архиве). читает просто. создаю DataSet и вызываю DataSet.ReadXML. он это читает, долольно долго кстати для больших файлов. и распихивает все что прочитал по таблицам, среди которых есть и таблица файлов, у которой столбцы - имя, размер и TTH ... вот собственно я эту табличку и сравниваю с массивом струткур, в которой имена и размеры файлов, скачанных с данного юзера.
-
Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp.
есть, есть еще люди помнящие названия функций CRT :) +
но тут на дотнете просили
-
Этот приём ускоряет операцию сравнения строк до пяти и более раз, в зависимости от длины строк, по сравнению со strcmp.
есть, есть еще люди помнящие названия функций CRT :) +
но тут на дотнете просили
да какая разница. String.Compare() - она же)
п.с. наверное неплохо будет если совместить хеши с фишкой на LINQ ... займусь обязательно)
-
Ускорять для начала нужно 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 не лезут правильно. Смотрите атач.
-
...
Разница в два раза. Но у Вас пример не очень хороший. Строки подлиннее сгенерите, почуствуете всё мощь.
...
Круто конечно ... а время выполнения
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);
-
Разница в переделах погрешности измерения.
-
господи, у меня и то разница в 6 раз )