Форум программистов, компьютерный форум, киберфорум
C++ Builder
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
1

Самое быстрое сравнение двух (трех, четырех) столбцов

06.02.2013, 18:04. Показов 2589. Ответов 21
Метки нет (Все метки)

Доброго времени суток. Я хотел бы узнать как можно ускорить процесс сравнения двух Мемо полей на дубликаты? Сравниваю так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 Form1->ProgressBar1->Position = 0;
 Form1->ProgressBar1->Max = Memo1->Lines->Count;
 for(int i = 0; i < Memo1->Lines->Count; i++){
 Form1->ProgressBar1->Position = i;
    Application->ProcessMessages();
    for(int j = 0; j < Memo2->Lines->Count; j++)
    {
      if(Memo1->Lines->Strings[i] == Memo2->Lines->Strings[j]){
        List->Add(Memo1->Lines->Strings[i]);
        Memo3->Clear();
        Memo3->Text = List->Text;
               break;
                }
      }
   }
        Form1->ProgressBar1->Position = 0;
К примеру в Мемо1 6000 записей а в Мемо2 15000 приблизительное время сравнения 15 минут. Есть похожая прога которая те же данные сравнивает за 1 минуту КАК ТАК ??? КАКОЙ ТАМ алгоритм ????. Может все данные згонять в одну кучу, отсортировать, и попарно искать, но как это написать не знаю. У кого какие идеи? Спс.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.02.2013, 18:04
Ответы с готовыми решениями:

Самое быстрое сравнение текстовых файлов
Товарищи, есть вопрос: есть 2 текстовых файла, по 10 мегабайт как максимально быстро сравнить...

Быстрое сравнение двух рисунков
Есть ли какой нибудь метод быстрого сравнения двух рисунков, типа if bitmat1 = bitmap2 then...

Сравнение четырех столбцов с автоматическим подставлением совпадений
Добрый день, перед тем как задать вопрос, пересмотрел похожие темы, но все же у меня немного...

Одна FIFO очередь для двух, трех, четырех потоков?
q = Queue() param_1 = &quot;string 1&quot; param_2 = &quot;string 2&quot; ...

21
1688 / 888 / 203
Регистрация: 25.11.2009
Сообщений: 1,818
06.02.2013, 18:14 2
не могу сказать, как ускорить алгоритм, но точно тебе скажу, что если не использовать прогресбар, то сэкономишь много времени. При каждом изменении позици прогрессбара происходит перерисовка, это сильно замедляет выполнение цикла. Если уж очень нужно отображать ход выполнения, то меняй позицию, например, раз в сто проходов цикла
1
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
06.02.2013, 18:43  [ТС] 3
Цитата Сообщение от Lelik-pahan Посмотреть сообщение
не могу сказать, как ускорить алгоритм, но точно тебе скажу, что если не использовать прогресбар, то сэкономишь много времени. При каждом изменении позици прогрессбара происходит перерисовка, это сильно замедляет выполнение цикла. Если уж очень нужно отображать ход выполнения, то меняй позицию, например, раз в сто проходов цикла
Пробовал! По скорости практически не заметно.
0
Практикантроп
4735 / 2641 / 512
Регистрация: 23.09.2011
Сообщений: 5,672
06.02.2013, 19:15 4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  TStringList *L1 = new TStringList();
  TStringList *L2 = new TStringList();
  TStringList *L3 = new TStringList();
 
  ProgressBar1->Position = 0;
  ProgressBar1->Max = Memo1->Lines->Count;
  L1->AddStrings(Memo1->Lines);
  L2->AddStrings(Memo2->Lines);
  int P1 = L1->Count ;
  int P2 = L2->Count ;
  for(int i = 0; i < P1; i++)  {
    ProgressBar1->Position = i;
    Application->ProcessMessages();
    for(int j = 0; j < P2; j++)  {
      if (L1->Strings[i] == L2->Strings[j])
       { L3->Add(L1->Strings[i]); break; }
    }
  }
   Memo3->Clear();
   Memo3->Text = L3->Text;
   ProgressBar1->Position = 0;
   delete L1;   delete L2;  delete L3;
1
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
06.02.2013, 19:54  [ТС] 5
Цитата Сообщение от nick42 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  TStringList *L1 = new TStringList();
  TStringList *L2 = new TStringList();
  TStringList *L3 = new TStringList();
 
  ProgressBar1->Position = 0;
  ProgressBar1->Max = Memo1->Lines->Count;
  L1->AddStrings(Memo1->Lines);
  L2->AddStrings(Memo2->Lines);
  int P1 = L1->Count ;
  int P2 = L2->Count ;
  for(int i = 0; i < P1; i++)  {
    ProgressBar1->Position = i;
    Application->ProcessMessages();
    for(int j = 0; j < P2; j++)  {
      if (L1->Strings[i] == L2->Strings[j])
       { L3->Add(L1->Strings[i]); break; }
    }
  }
   Memo3->Clear();
   Memo3->Text = L3->Text;
   ProgressBar1->Position = 0;
   delete L1;   delete L2;  delete L3;
Блин только хотел отписаться своим вариантом сравнения 2 х стринг листов а тут меня уже опередили. Целый день ломал голову только дошло. Спасибо всем!!

Добавлено через 32 минуты
А как теперь вывести не совпадения Мемо1 и Мемо2?
C++
1
2
3
4
5
6
7
8
9
10
for(int i = 0; i < Lista->Count; i++){
 Form1->ProgressBar1->Position = i;
    for(int j = 0; j < Listb->Count; j++)
    {
       if( Lista->Strings[i] != Listb->Strings[j]){
        Listr->Add(Lista->Strings[i]);
        Memo3->Clear();
                }
      }
   }
Не катит!
0
1688 / 888 / 203
Регистрация: 25.11.2009
Сообщений: 1,818
06.02.2013, 20:08 6
C++
1
2
3
4
5
6
7
8
9
for (int i = 0; i < Lista->Count; i++)
{
    Form1->ProgressBar1->Position = i;
    for (int j = 0; j < Listb->Count; j++)    
        if ( Lista->Strings[i] != Listb->Strings[j])
            Listr->Add(Lista->Strings[i]);   
}
Memo3->Clear();
Memo3->Lines->AddStrings(Listr);
1
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
06.02.2013, 20:22  [ТС] 7
C++
1
2
3
4
5
6
7
8
9
for (int i = 0; i < Lista->Count; i++)
{
    Form1->ProgressBar1->Position = i;
    for (int j = 0; j < Listb->Count; j++)    
        if ( Lista->Strings[i] != Listb->Strings[j])
            Listr->Add(Lista->Strings[i]);   
}
Memo3->Clear();
Memo3->Lines->AddStrings(Listr);
Нет! Не верные значения.
0
1688 / 888 / 203
Регистрация: 25.11.2009
Сообщений: 1,818
06.02.2013, 20:24 8
ну да, неверные, в ифе надо "==" поставить вместо "!="
я ведь только скопировал код из твоего сообщения )

а, хотя стоп... тебе же надо НЕсовпадения... поторопился я
0
1121 / 792 / 100
Регистрация: 01.02.2011
Сообщений: 1,859
Записей в блоге: 1
06.02.2013, 20:30 9
Если нужен самый быстрый способ сравнения, то тут: Вычисление в цикле
1
1688 / 888 / 203
Регистрация: 25.11.2009
Сообщений: 1,818
06.02.2013, 20:38 10
может так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool overlap;
for (int i = 0; i < Lista->Count; i++)
{
    overlap = false;
    Form1->ProgressBar1->Position = i;
    for (int j = 0; j < Listb->Count; j++)    
        if ( Lista->Strings[i] == Listb->Strings[j])
        {
            overlap = true;
            break;
        }
    if (!overlap)  //если не было совпадения, заносим в список
        Listr->Add(Lista->Strings[i]);   
}
Memo3->Clear();
Memo3->Lines->AddStrings(Listr);
1
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
06.02.2013, 20:49  [ТС] 11
Цитата Сообщение от Lelik-pahan Посмотреть сообщение
может так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool overlap;
for (int i = 0; i < Lista->Count; i++)
{
    overlap = false;
    Form1->ProgressBar1->Position = i;
    for (int j = 0; j < Listb->Count; j++)    
        if ( Lista->Strings[i] == Listb->Strings[j])
        {
            overlap = true;
            break;
        }
    if (!overlap)  //если не было совпадения, заносим в список
        Listr->Add(Lista->Strings[i]);   
}
Memo3->Clear();
Memo3->Lines->AddStrings(Listr);
Спасибище! В точку.

Добавлено через 3 минуты
Хотел спросить по поводу "bool overlap" Это что? Поподробней можно? Спс.
0
Практикантроп
4735 / 2641 / 512
Регистрация: 23.09.2011
Сообщений: 5,672
06.02.2013, 20:50 12
Цитата Сообщение от serg87i Посмотреть сообщение
Не верные значения.
Что значит: неверные. Мы ж не знаем, что у вас в мэмо1 и мэмо2. Вы учитываете, что загрузка текстового файла в мэмо - у которого по умолчанию перенос строк включен - переформатирует исходный текст? Так, что если потом сравнивать результаты по текстам файлов, то результат будет несколько неожиданным, в зависимости от ширины этих мэмо. Правильнее сразу загружать текстовые файлы в стринглисты. В них изначальное форматирование (разбиение на строки) сохраняется.
0
1688 / 888 / 203
Регистрация: 25.11.2009
Сообщений: 1,818
06.02.2013, 20:55 13
Цитата Сообщение от serg87i Посмотреть сообщение
Хотел спросить по поводу "bool overlap" Это что? Поподробней можно? Спс.
bool - булевый тип данных, может принимать значение true (истина) и false (ложь).
условие if (overlap) выполнится, если переменная overlap равна true

почитай об этом хоть на википедии, это одна из основ программирования, информацию найдёшь где угодно.

Не по теме:

и не стоит на каждое сообщение ставить "спасибо", мне кажется это лишне ))

1
435 / 402 / 57
Регистрация: 06.02.2012
Сообщений: 1,384
07.02.2013, 08:35 14
Сравнивать каждую строку с каждой это очень медленно. Так на вскидку:
1. Можно отсортировать все строки по длине и сравнивать строки только со строками равной длины. Или при вашем переборе сначала проверять совпадение длин строк.
2. Можно отсортировать все строки по всему содержимому (или по первым нескольким символам) и уже искать нужную строку в сортированном массиве, это быстрее. Или при вашем переборе сначала проверять совпадение первого символа.
3. Ну естественно многопоточность.
4. Не использовать в цикле Listb->Count, а использовать переменную int LCb=Listb->Count;
5. Вынести из цикла Lista->Strings[i], заменив на переменную S=Lista->Strings[i];

Если вам нужно сравнивать не каждую строку с каждой, а сравнивать с условием, что искомая строка должна лежать ниже ранее найденных, то это еще ускорит процесс.

Если в первый цикл добавить этот код (можно раз в несколько шагов), то будет понаглядней.
C++
1
Application->ProcessMessages();
1
1121 / 792 / 100
Регистрация: 01.02.2011
Сообщений: 1,859
Записей в блоге: 1
07.02.2013, 13:21 15
Цитата Сообщение от gumi250 Посмотреть сообщение
Сравнивать каждую строку с каждой это очень медленно.
Я ему уже давал решение, которое всё сделает за 30-50 миллисекунд, но ему видимо нравится чуть ли не самый медленный способ.
Тема то называется Самое быстрое сравнение двух столбцов, значит и обсуждать нужно самый быстрый способ.
1
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
07.02.2013, 14:38  [ТС] 16
Рябят спасибо я уже решил задачу! Все работает на УРА! Самый быстрый способ это сравнивать сразу 2 StringList а не отдельно каждую строку. А вот ка реализовать сравнение 4 - х StringList и найти совпадения которые попадают во все стриглисты? Вот это задачка!?
0
435 / 402 / 57
Регистрация: 06.02.2012
Сообщений: 1,384
07.02.2013, 14:53 17
Цитата Сообщение от serg87i Посмотреть сообщение
Рябят спасибо я уже решил задачу! Все работает на УРА! Самый быстрый способ это сравнивать сразу 2 StringList а не отдельно каждую строку. А вот ка реализовать сравнение 4 - х StringList и найти совпадения которые попадают во все стриглисты? Вот это задачка!?
И какой нынче у вас временной рекорд вместо 15 мин?
0
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
07.02.2013, 14:59  [ТС] 18
Цитата Сообщение от gumi250 Посмотреть сообщение
И какой нынче у вас временной рекорд вместо 15 мин?
2-3 сек!

Добавлено через 5 минут
Дабы не дублировать тему. Пытаюсь теперь сравнить 3 стринг листа (хотелось бы 4).
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
TStringList *Lista = new TStringList;
TStringList *Listb = new TStringList;
TStringList *Listc = new TStringList;
TStringList *Listd = new TStringList;
TStringList *Listr = new TStringList;
TStringList *Listr2 = new TStringList;
TStringList *Listr3 = new TStringList;
TStringList *RS1 = new TStringList;
TStringList *RS2 = new TStringList;
TStringList *RS3 = new TStringList;
// Сортировка оставляем только уникальные значения
Lista->Sorted = true;
Listb->Sorted = true;
Listc->Sorted = true;
Listd->Sorted = true;
Listr->Sorted = true;
RS1 ->Sorted = true;
RS2 ->Sorted = true;
RS3  ->Sorted = true;
Listr2->Sorted = true;
Listr3->Sorted = true;
// Очистка поля для результатов
Memo5->Clear();
//Заносим данных в СтригЛисты
Lista->Text = Memo1->Text;
Listb->Text = Memo2->Text;
Listc->Text = Memo3->Text;
// Listd->Text = Memo4->Text;
//---Сравниваем данные из Memo1 vs Memo2
 for(int i = 0; i < Lista->Count; i++){
 
    for(int j = 0; j < Listb->Count; j++)
    {
        if( Lista->Strings[i] == Listb->Strings[j]){
        Listr->Add(Lista->Strings[i]);
        Memo5->Clear();
            }
      }
   }
   Form1->Caption = Listr->Text;
 
   //---Сравниваем данные из Memo1 vs Memo3
 for(int i = 0; i < Lista->Count; i++){
 
    for(int j = 0; j < Listc->Count; j++)
    {
        if( Lista->Strings[i] == Listc->Strings[j]){
        Listr2->Add(Lista->Strings[i]);
        Memo5->Clear();
          }
      }
   }
    //---Сравниваем данные из Memo2 vs Memo3
  for(int i = 0; i < Listb->Count; i++){
 
    for(int j = 0; j < Listc->Count; j++)
    {
        if( Listb->Strings[i] == Listc->Strings[j]){
        Listr3->Add(Listb->Strings[i]);
        Memo5->Clear();
          }
      }
   }
 //---Склеиваем результаты сравнений
 
 RS1->Text =  Listr->Text + Listr2->Text;
 RS2->Text = Listr3->Text  ;
 
 //---Сравниваем результаты и то что получилось выводим в Мемо5
 for (int i = 0; i < RS1->Count; i++) {
 
      for (int j = 0; i < RS2->Count; i++) {
 
         if( RS1->Strings[i] == RS2->Strings[j]){
        RS3->Add(RS1->Strings[i]);
        Memo5->Clear();
          }
 
 
      }
 }
    Memo5->Text = RS3->Text;
   Label1->Caption = RS3->Count;
  delete Lista;
  delete Listb ;
  delete Listr;
 delete Listr2;
 delete Listr3 ;
delete  RS1 ;
delete  RS2  ;
delete  RS3  ;
Не хо-хо данные не корректные в чем проблема? Кто подскажет?
0
1688 / 888 / 203
Регистрация: 25.11.2009
Сообщений: 1,818
07.02.2013, 18:42 19
можно уточнить, в чём задача? нужно найти записи, которые есть во всех четырёх списках, или записи, которые встречаются в каких-либо двух списках?
1
12 / 12 / 3
Регистрация: 11.10.2010
Сообщений: 159
07.02.2013, 19:05  [ТС] 20
Цитата Сообщение от Lelik-pahan Посмотреть сообщение
можно уточнить, в чём задача? нужно найти записи, которые есть во всех четырёх списках, или записи, которые встречаются в каких-либо двух списках?
Запись во всех четырех списках
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.02.2013, 19:05
Помогаю со студенческими работами здесь

Получить все числа Армстронга, состоящие из двух, трех и четырех цифр
Здравствуйте, очень нужно решить, помогите пожалуйста! Натуральное число из n цифр является...

Получение всех чисел Армстронга для двух, трех и четырех цифр
Построить алгоритм получения всех чисел Армстронга для двух, трех и четырех цифр.

Получить все числа Армстронга, состоящих из двух, трех и четырех чифр
Натуральное число из N цифр является числом Армстронга, если сумма его цифр, возведенная в N-ю...

Найти все числа Армстронга, состоящие их двух, трех и четырех цифр
Число из n цифр является числом Армстронга, если сумма цифр, возведенных в n-ую степень, равна...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru