Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Как ускорить сравнение строк

11K
04 октября 2006 года
proc
32 / / 23.07.2006
У меня такая проблема - есть текстовый файл, я создаю два TStringList'а, в оба загружаю этот самый файл. После этого каждую строку первого List'a я сравниваю с остальными строками второго, с целью найти совпадающие. В Базе около 6000 строк и процесс сравнения занимает около минуты, как можно его ускорить?

Код:
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;
5.4K
04 октября 2006 года
Svyatozar
221 / / 11.09.2006
а в какой кодировке текст?
10
04 октября 2006 года
Freeman
3.2K / / 06.03.2004
[QUOTE=proc]В Базе около 6000 строк и процесс сравнения занимает около минуты, как можно его ускорить?[/QUOTE]
Если не важна последовательность строк - выставить Sorted = true. Если важна, придумать, как это обойти, чтобы поиск велся методом деления надвое.
4
04 октября 2006 года
mike
3.7K / / 01.10.2002
Можно, написать все это без кучи лишних объектов, используя функции POSIX и будет тебе счастье. (И кроссплатформенный исходник)

fopen, fgets, strcmp

Если строк много, то я бы рекомендовал использовать CRC32 хеши для увеленичения скорости сравнения. Только хеши нужно вычислять в момент добавления строки в файл. Но это если строк много, а 6000 - это совсем мало.
3
04 октября 2006 года
Green
4.8K / / 20.01.2000
[QUOTE=proc]У меня такая проблема - есть текстовый файл, я создаю два TStringList'а, в оба загружаю этот самый файл. После этого каждую строку первого List'a я сравниваю с остальными строками второго, с целью найти совпадающие. В Базе около 6000 строк и процесс сравнения занимает около минуты, как можно его ускорить?
[/QUOTE]
1. В коде я увидел лишь загрузку во второй List, работы с его содержимым нет. Этог опечатка в приведенном коде?

2. Работу сильно замедляют обращения к элементам GUI, конкретно операции с прогрессбаром.

3. Если тебе просто надо найти дубликаты строк, то ты выбрал неоптимальный алгоритм. Я бы сначала провел сортировку списка, т.о. одинаковые слова стали бы стоять рядом. Потом сравнил бы последовательно рядомстоящие слова. Т.о. сложность становиться Nlog(N), вместо предложенного тобой N^2. А это при наборе в 6000 строк примерно в 200 раз быстрее.

Реализацию алгоритма можно ещё немного ускорить, если на втором шаге сравнивать не сразу слова, а сначала их длины, если они совпадают, то сравниваем слова, если нет - пропускаем. Работает в том случае, если длина строки храниться, а не вычисляется каждый раз.
10
04 октября 2006 года
Freeman
3.2K / / 06.03.2004
Можно еще UpperCase вычислить предварительно. Хотя, при однопроходном сравнении это не скажется на скорости.
3.0K
04 октября 2006 года
Мerlin
267 / / 25.07.2006
Судя по коду, ты хочешь вывести строки-дубли. Для этого достаточно и одного 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;
309
05 октября 2006 года
el scorpio
1.1K / / 19.09.2006
Обнаружен мощный "тормозистор" в этой строке
"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) //Сравнение с игнорированием регистра
           {
// Вывод сообщения о совпадении
           }
     }
}
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог