List1->LoadFromFile(Path1);
List4->LoadFromFile(Path1);
ProgressBar1->Max=List1->Count;
ProgressBar1->Step=1;
for(i=0;i<List1->Count;i++)
{
int count=0;
for(j=i+1;j<List1->Count;j++)
{
if(List1->Strings.UpperCase()==List1->Strings[j].UpperCase())
{
count++;
}
}
if(count>=1)
{
fputs(List1->Strings.c_str(),f3);
fputs("\n",f3);
}
ProgressBar1->StepIt();
}
ProgressBar1->Position=0;
Как ускорить сравнение строк
У меня такая проблема - есть текстовый файл, я создаю два TStringList'а, в оба загружаю этот самый файл. После этого каждую строку первого List'a я сравниваю с остальными строками второго, с целью найти совпадающие. В Базе около 6000 строк и процесс сравнения занимает около минуты, как можно его ускорить?
Код:
а в какой кодировке текст?
[QUOTE=proc]В Базе около 6000 строк и процесс сравнения занимает около минуты, как можно его ускорить?[/QUOTE]
Если не важна последовательность строк - выставить Sorted = true. Если важна, придумать, как это обойти, чтобы поиск велся методом деления надвое.
Если не важна последовательность строк - выставить Sorted = true. Если важна, придумать, как это обойти, чтобы поиск велся методом деления надвое.
Можно, написать все это без кучи лишних объектов, используя функции POSIX и будет тебе счастье. (И кроссплатформенный исходник)
fopen, fgets, strcmp
Если строк много, то я бы рекомендовал использовать CRC32 хеши для увеленичения скорости сравнения. Только хеши нужно вычислять в момент добавления строки в файл. Но это если строк много, а 6000 - это совсем мало.
fopen, fgets, strcmp
Если строк много, то я бы рекомендовал использовать CRC32 хеши для увеленичения скорости сравнения. Только хеши нужно вычислять в момент добавления строки в файл. Но это если строк много, а 6000 - это совсем мало.
[QUOTE=proc]У меня такая проблема - есть текстовый файл, я создаю два TStringList'а, в оба загружаю этот самый файл. После этого каждую строку первого List'a я сравниваю с остальными строками второго, с целью найти совпадающие. В Базе около 6000 строк и процесс сравнения занимает около минуты, как можно его ускорить?
[/QUOTE]
1. В коде я увидел лишь загрузку во второй List, работы с его содержимым нет. Этог опечатка в приведенном коде?
2. Работу сильно замедляют обращения к элементам GUI, конкретно операции с прогрессбаром.
3. Если тебе просто надо найти дубликаты строк, то ты выбрал неоптимальный алгоритм. Я бы сначала провел сортировку списка, т.о. одинаковые слова стали бы стоять рядом. Потом сравнил бы последовательно рядомстоящие слова. Т.о. сложность становиться Nlog(N), вместо предложенного тобой N^2. А это при наборе в 6000 строк примерно в 200 раз быстрее.
Реализацию алгоритма можно ещё немного ускорить, если на втором шаге сравнивать не сразу слова, а сначала их длины, если они совпадают, то сравниваем слова, если нет - пропускаем. Работает в том случае, если длина строки храниться, а не вычисляется каждый раз.
[/QUOTE]
1. В коде я увидел лишь загрузку во второй List, работы с его содержимым нет. Этог опечатка в приведенном коде?
2. Работу сильно замедляют обращения к элементам GUI, конкретно операции с прогрессбаром.
3. Если тебе просто надо найти дубликаты строк, то ты выбрал неоптимальный алгоритм. Я бы сначала провел сортировку списка, т.о. одинаковые слова стали бы стоять рядом. Потом сравнил бы последовательно рядомстоящие слова. Т.о. сложность становиться Nlog(N), вместо предложенного тобой N^2. А это при наборе в 6000 строк примерно в 200 раз быстрее.
Реализацию алгоритма можно ещё немного ускорить, если на втором шаге сравнивать не сразу слова, а сначала их длины, если они совпадают, то сравниваем слова, если нет - пропускаем. Работает в том случае, если длина строки храниться, а не вычисляется каждый раз.
Можно еще UpperCase вычислить предварительно. Хотя, при однопроходном сравнении это не скажется на скорости.
Судя по коду, ты хочешь вывести строки-дубли. Для этого достаточно и одного TStringList.
Код:
AnsiString str;
TStringList *List1 = new TStringList();
List1->LoadFromFile(Path1);
for(int i=0; i<List1->Count; i++)
{
List1->Strings = List1->Strings.UpperCase();
List1->Objects = (TObject *)i;
}
List1->Sorted = true;
ProgressBar1->Max=List1->Count;
ProgressBar1->Step=1;
int n = List1->Count - 1;
for(int i=0;i<n;i++)
{
if(List1->Strings==List1->Strings[i+1])
{
str.Format("%05d: %s\n", ARRAYOFCONST(((int)List1->Objects, List1->Strings)));
fputs(str.c_str(),f3);
}
ProgressBar1->StepIt();
}
ProgressBar1->Position=100;
TStringList *List1 = new TStringList();
List1->LoadFromFile(Path1);
for(int i=0; i<List1->Count; i++)
{
List1->Strings = List1->Strings.UpperCase();
List1->Objects = (TObject *)i;
}
List1->Sorted = true;
ProgressBar1->Max=List1->Count;
ProgressBar1->Step=1;
int n = List1->Count - 1;
for(int i=0;i<n;i++)
{
if(List1->Strings==List1->Strings[i+1])
{
str.Format("%05d: %s\n", ARRAYOFCONST(((int)List1->Objects, List1->Strings)));
fputs(str.c_str(),f3);
}
ProgressBar1->StepIt();
}
ProgressBar1->Position=100;
Обнаружен мощный "тормозистор" в этой строке
"if(List1->Strings.UpperCase()==List1->Strings[j].UpperCase())"
Вопрос - зачем внутри вложенного цикла каждый раз производить чтение одной и той же строки, изменяющейся во внешнем цикле.
Кроме того, каждая строка постоянно приводится к верхнему регистру перед сравнением - лучше использовать другие функции.
Попробую оптимизировать
"if(List1->Strings.UpperCase()==List1->Strings[j].UpperCase())"
Вопрос - зачем внутри вложенного цикла каждый раз производить чтение одной и той же строки, изменяющейся во внешнем цикле.
Кроме того, каждая строка постоянно приводится к верхнему регистру перед сравнением - лучше использовать другие функции.
Попробую оптимизировать
Код:
AnsiString Str1; // Временная переменная для хранения первого значения
int Comparies = 0; // Кол-во совпадений
for(int i=0, Count1 = List1->Count ;i < Count1; i++) // Сравнение двух стековых переменных быстрее, чем стековое со свойством объекта в куче
{
Str1 = List1->Strings ; // Сохранение первой сравниваемой строки
for(int j = i+1; j < Count; j++)
{
if (Str1.AnsiCompareIC (List1->Strings[j]) == 0) //Сравнение с игнорированием регистра
{
// Вывод сообщения о совпадении
}
}
}
int Comparies = 0; // Кол-во совпадений
for(int i=0, Count1 = List1->Count ;i < Count1; i++) // Сравнение двух стековых переменных быстрее, чем стековое со свойством объекта в куче
{
Str1 = List1->Strings ; // Сохранение первой сравниваемой строки
for(int j = i+1; j < Count; j++)
{
if (Str1.AnsiCompareIC (List1->Strings[j]) == 0) //Сравнение с игнорированием регистра
{
// Вывод сообщения о совпадении
}
}
}