Нужен быстрый алгоритм сравнения WIDE-строк

Если вы разбираетесь в программировании (C++ Builder, Delphi), возможно вы сможете помочь в устранении проблемных мест в программе

Модератор: motyara

Аватара пользователя
Max Diesel
Автор программы
Сообщения: 3131
Зарегистрирован: Пт окт 12, 2007 9:00 pm
Контактная информация:

Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение Max Diesel » Сб фев 16, 2008 12:08 am

По какой-то причине сортировка, алгоритм которой написан на Delphi производится быстрее чем на C++ Builder'е (во всяком случае в моей интерпретации). В программировании на Delphi я разбираюсь слабо, а потому хочу попросить знающих людей помочь в написании алгоритма сравнения строк, содержащих числовые значения. То есть функции сравнения передаются две строки в юникоде (WideString) и возможно в строках есть числовые значения, функция должна независимо от длины числа (хоть двухзначное число, хоть 1000-значное) произвести сравнение строк с учетом того, какое число больше, причем сделать это максимально меньшим количеством операций.
Примеры строк, каждая следующая из них согласно такому алгоритму сравнения должна считаться большей чем любая из предыдущих:

0,12текст7
1текст7
10-123текст10
10текст7
10текст10
10текст20
10текст756845532
11текст6
11текст7
20.37453текст7
973864958324602текст7


Если у кого-то есть возможность написать этот алгоритм (или же он уже есть в наличии) на Delphi, то я был бы весьма признателен за предоставление мне его кода.

Аватара пользователя
panter_dsd
Охотник за багами
Сообщения: 228
Зарегистрирован: Чт окт 18, 2007 6:20 pm
Откуда: г.Таганрог
Контактная информация:

Re: Нужен быстрый алгоритм сравнения WIDE-строк на Delphi

Сообщение panter_dsd » Сб фев 16, 2008 4:02 pm

Код: Выделить всё

int lessThen (char* str1, char* str2)
{
  for (int i=0; i<strlenght(str1); i++)
  {
    if (str1[i].isNumber() && str2[i].isNumber())
    {
       int a,b;
       a=int(str1[i]); b=int(str2[i]);
       if (a<b) return 1;
       if (a>b) return 2;
    }
  }
}
Извините, пишу с большого похмелья, но думаю моя задумка понятна. Сильно не ругайте код, пишу по памяти, которую мало-мало отшибло. :)
Думаю на плюсах все таки побыстрее будет, чем на паскале.
С уважением.
Пантер.

Аватара пользователя
Max Diesel
Автор программы
Сообщения: 3131
Зарегистрирован: Пт окт 12, 2007 9:00 pm
Контактная информация:

Сообщение Max Diesel » Сб фев 16, 2008 8:58 pm

Чего-то в этой интерпретации кода не хватает... кстати сейчас я еще раз написал тестовое приложение для проверки на C++ и оказалось что оно все-таки обходит по скорости вариант на Delphi. Буквально вчера оно по непонятной мне причине отставало в 4-8 раз (чем меня не сильно радовало), странно.

Diff
Сообщения: 109
Зарегистрирован: Вт янв 29, 2008 4:44 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение Diff » Вс фев 17, 2008 2:02 am

Это алгоритм не сортировки, а сравнения. Кроме того, меня сомневает, что этот код будет работать с unicode. Ну и оптимизировать его есть куда, прямо скажем.

Аватара пользователя
panter_dsd
Охотник за багами
Сообщения: 228
Зарегистрирован: Чт окт 18, 2007 6:20 pm
Откуда: г.Таганрог
Контактная информация:

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение panter_dsd » Вс фев 17, 2008 12:35 pm

Млин, извините. Код действительно фигня. :oops:
С уважением.
Пантер.

Diff
Сообщения: 109
Зарегистрирован: Вт янв 29, 2008 4:44 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение Diff » Вс фев 17, 2008 1:51 pm

А это действительно все необходимо? В смысле - распознавать вещественные числа и учитывать цифры, которые идут после текста? Если речь идет о сортировке файлов так чтобы "9" шел прежде "10", то имхо, это немного излишне. А может, даже вредно.
По идее, хорошо написанный алгоритм на C будет чуть быстрее хорошо написанного на паскале, поскольку C предоставляет больше возможностей для работы с указателями, что позволяет избежать индексации строк. Однако на практике обычно критику заслуживает не язык, а сам алгоритм - пузырьковая сортировка будет работать медленно, как бы распрекрасно она ни была реализована :).
Посему хотелось бы чуть больше подробностей о цели этого алгоритма.

Аватара пользователя
panter_dsd
Охотник за багами
Сообщения: 228
Зарегистрирован: Чт окт 18, 2007 6:20 pm
Откуда: г.Таганрог
Контактная информация:

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение panter_dsd » Вс фев 17, 2008 4:39 pm

А еще лучше текущий алгоритм, а там можно внести изенения и подправить.
С уважением.
Пантер.

Аватара пользователя
Max Diesel
Автор программы
Сообщения: 3131
Зарегистрирован: Пт окт 12, 2007 9:00 pm
Контактная информация:

Сообщение Max Diesel » Вс фев 17, 2008 11:02 pm

Алгоритм, при котором 10 идет перед 9, но более быстрый чем раньше, уже внедрен в программу. Хотелось бы как вариант добавить сортировку с учетом величины числа.

Diff
Сообщения: 109
Зарегистрирован: Вт янв 29, 2008 4:44 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение Diff » Пн фев 18, 2008 1:43 am

Да, но зачем такие изыски, как вещественные числа и цифры вперемешку с текстом? Не забудьте еще, что десятичная точка в зависимости от локали бывает "." и "," - это еще добавит путаницы. По-моему, можно и нужно ограничиться лидирующими цифрами. Тогда и алгоритм сравнения будет простым.
Простейший способ вытащить число из начала строки - sscanf(string, "%d", &number), хотя я не уверен, что он будет быстрейшим.

Добавлено:
Хотя... Тут подумал, что каталоги вида

Код: Выделить всё

dir1
dir2
...
dir9
dir10
[/b]

Тоже неплохо было бы уметь так сортировать. То есть завершающие числа тоже имеют смысл. Но их тоже выцепить легко.

Аватара пользователя
Max Diesel
Автор программы
Сообщения: 3131
Зарегистрирован: Пт окт 12, 2007 9:00 pm
Контактная информация:

Сообщение Max Diesel » Вт фев 19, 2008 12:36 am

Элементарный код сравнения с учетом величины числа я написал, правда в моей интерпретации он скоростью отличается лишь в сторону ее отсутствия. На входе в небольшой каталог различие чувствуется не очень сильно, а вот для крупных (5000 файлов/каталогов) вполне заметно. Раз в 10. Я не очень люблю выставлять свой код на показ, так как зачастую он написан недостаточно рационально, но в надежде на то, что кто-нибудь найдет в нем оптимизируемые по скорости фрагменты (или ошибки) размещаю его здесь:

Код: Выделить всё

int __fastcall sort_func(TTntStringList *list, int index1, int index2)
{

WideString st1=list->Strings[index1], st2=list->Strings[index2]; // сравниваемые строки, взятые из TTntStringList

int a=1, b=1, a_length=st1.Length()+1, b_length=st2.Length()+1;

while (a<a_length && b<b_length)
	{
	 switch ((st1[a]<58 && st1[a]>47)+(st2[b]<58 && st2[b]>47)*2)
		{
		 case 0: // если обе буквы
				{
				 int znak=st1[a]-st2[b];
				 switch (znak)
					{
					 case 0: // равны
					 case 32:
					 case -32:
							break;

					 default: // не равны
							{
							 st1.Delete(0, a);
							 st2.Delete(0, b);
							 return lstrcmpiW(PWChar(st1.data()), PWChar(st2.data()));
							};
					}
				}
				break;

		 case 1: // первая цифра, вторая буква
		 case 2: // первая буква, вторая цифра
				return lstrcmpiW(PWChar(st1.data()), PWChar(st2.data()));
				break;

		 case 3: // обе цифры
				{
				 String num1="", num2="";
				 int m1=a, m2=b;
				 while (a<a_length && st1[a]<58 && st1[a]>47) a++;


				 while (b<b_length && st2[b]<58 && st2[b]>47) b++;

				 num1=st1.SubString(m1, a-m1);
  				 num2=st2.SubString(m2, b-m2);

				 switch ((a-m1)-(b-m2))
					{
					 case 0: // значит числа одинаковой длины
							{
							 short r1=lstrcmpi(PChar(num1.data()), PChar(num2.data()));
							 if (r1!=0)
								return r1;
							}
							break;

					 default: // длина разная
							{
							 if ((a-m1)<(b-m2))
								 num1=AnsiString::StringOfChar('0', (b-m2)-(a-m1))+num1;
								 else num2=AnsiString::StringOfChar('0', (a-m1)-(b-m2))+num2;
							 return lstrcmpi(PChar(num1.data()), PChar(num2.data()));
							}
							;
					}
				}
				break;
		}

	 a++;
	 b++;
	}

return 0;

}
//---------------------------------------------------------------------------
[/color]

Diff
Сообщения: 109
Зарегистрирован: Вт янв 29, 2008 4:44 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение Diff » Вт фев 19, 2008 3:06 am

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

case 0:
На мой взгляд тормозные места здесь - это библиотечные функции работы со строками. Они страшно медленные. Спасаться будем указателями.
Вместо

Код: Выделить всё

st1.Delete(0, a);
st2.Delete(0, b);
return lstrcmpiW(PWChar(st1.data()), PWChar(st2.data()));
сделать нечто вроде

Код: Выделить всё

WChar *p1 = &st1[a];
WChar *p2 = &st2[b];
return lstrcmpiW(p1, p2)
Здесь нет перевыделения памяти, которое производит Delete. Если строки не дают использовать &st1[a] - использовать &st1.data()[a].

Дальше.
Зачем case 1 и case 2 вызывают функцию сравнения? Ведь понятно же что в первом случае меньше первая, а во втором - вторая строка.

Ну и наконец case 3.
Почему если длина чисел равная, то вызывается lstrcmpi? Разве здесь не числа надо сравнивать, ради чего все и затевалось? Или я чего-то недопонял?
Если длина разная, строки добиваются нулями слева и сравниваются. А если одинаковыми окажутся?
Я бы все это попробовал поменять на примерно следующее:

Код: Выделить всё

int num1;
int num2;
// Вытаскиваем цифры в числа. Их длина нам совсем неинтересна.
wsscanf(st1.data(), "%d", &num1);
wsscanf(st2.data(), "%d", &num2);
if (num1 != num2) return num1>num2?1:-1; // или что там вернуть надо.
//А вот если числа оказались равны - придется сравнивать строки. Проще всего - не мудурствуя:
return lstrcmpiW(PWChar(st1.data()), PWChar(st2.data()));
/*Такой поход может обернуться не совсем корректной сортировкой в случае типа такого:
07 - zzzzz
7 -aaaaa
Будет отсортировано именно так, что с точки зрения подхода неверно.
Но по-моему, на это можно забить. А если не хочется - то перед сравнением лидирующие цифры отрезать.
*/
Как-то так. Сто лет уже на C не писАл :). В существовании функции wsscanf я не уверен, но наверняка должен быть какой-то вариант sscanf для юникода.

Аватара пользователя
maXmo
Охотник за багами
Сообщения: 98
Зарегистрирован: Пт ноя 09, 2007 8:03 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение maXmo » Вт фев 19, 2008 6:01 pm

Ну да. Главные тормоза, думаю, сидят в реаллоках в st1.Delete(0, a); и num1=AnsiString::StringOfChar('0', (b-m2)-(a-m1))+num1; плюс перекодировка из юникода в анси: num1=st1.SubString(m1, a-m1); (также с реаллоком).
Думаю, это самое главное, а дальнейших оптимизаций в приведённый код можно очень много наворотить (если есть желание их реализовывать).

Аватара пользователя
maXmo
Охотник за багами
Сообщения: 98
Зарегистрирован: Пт ноя 09, 2007 8:03 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение maXmo » Вт фев 19, 2008 6:15 pm

А вообще, по-моему, фича не критичная.

Diff
Сообщения: 109
Зарегистрирован: Вт янв 29, 2008 4:44 pm

Re: Нужен быстрый алгоритм сравнения WIDE-строк

Сообщение Diff » Ср фев 20, 2008 1:32 am

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

Код: Выделить всё

// Возвращаем 1 если больше string1, -1 если string2 и 0 если равны.
// нас интересуют лидирующие и завершающие числа, т.е.
// имена типа 07-name и Name07.
int compare_string(wchar * string1, wchar * string2){

   wchar *p1 = string1;
   wchar *p2 = string2;
   bool bLead = true;
   int nNum1, nNum2;

   // пока строки равны, идем до первого различия.
   while (*p1 && *p2 && *p1 != *p2){
        // следим, является ли число лидирующим - потом пригодится.
        if (bLead) bLead = iswdigit(*p1);
        ++p1;
        ++p2;
   }

   // дошли до конца обеих строк - значит они равны.
   // такое может произойти при рекурсивном вызове (см дальше)
   if (*p1 == 0 && *p2 == 0) return 0;

   // Если дошли до конца одной из строк, значит больше вторая - она длиннее.
   if (*p1 == 0) return -1;
   if (*p2 == 0) return 1;

   //теперь смотрим различия. если там буквы или цифра и буква то все просто
   if ( iswdigit(*p1) ){
     if ( !iswdigit(*p2) )
       //цифра - буква
       return -1;
     else{
          // самое интересное - обе цифры
          // это лучше пропустить при первом прочтении и курить потом :)
          if(bLead){
            // Лидирующее число. Читаем и сравниваем.
            wsscanf(string1, "%d", &nNum1);
            wsscanf(string2, "%d", &nNum2);
            // если числа не равны - то вуаля
            if (nNum1 != nNum2) return nNum1>nNum2?1:-1;

            // числа равны - случай типа 027name1 и 27name2.
            // придется пойти на жертвы. Но этот случай вряд ли
            // будет случаться часто.

            // пробегаем до первой буквы
            while ( iswdigit(*p1) ) ++p1;
            while ( iswdigit(*p2) ) ++p2;

            // и вызываем себя рекурсивно чтобы не заморачиваться.
            return  compare_string(p1, p2);
          }
          else{
               //Не лидирующее число. Надо узнать, является ли оно завершающим
               // для этого пробегаем до конца складываем цифры в буфер.
               wchar * buf1 = new wchar(256);
               wchar * buf2 = new wchar(256);

               wchar *pbuf1 = buf1;
               wchar *pbuf2 = buf2;
               wchar *ptr1 = p1;
               wchar *ptr2 = p2;

               while ( iswdigit(*ptr1)){
                    *pbuf1 = *ptr1;
                    ++pbuf1;
                    ++ptr1;
               }
               // не дошли до нуля(конца строки), значит число не завершающее
               if (*ptr1 != 0) return lstrcmpiw(p1, p2);

               while ( iswdigit(*ptr2)){
                    *pbuf2 = *ptr2;
                    ++pbuf2;
                    ++ptr2;
               }
               // не дошли до нуля(конца строки), значит число не завершающее
               if (*ptr2 != 0) return lstrcmpiw(p1, p2);

               // если мы еще здесь - числа завершающие.
               // И они оба сидят в буферах
               // Возможно, есть более простой способ преобразовать строку в
               // число, но я сейчас помню только scanf.
               wsscanf(buf1, "%d", nNum1);
               wsscanf(buf2, "%d", nNum2);
               delete buf1;
               delete buf2;

               // Не равны?
               if(nNum1 != nNum2) return nNum1>nNum2?1:-1;

               // Ну, значит равны
               return 0;
          }
     }
   }
   else{
     if ( iswdigit(*p2) )
       //буква - цифра
       return 1;
     else
       // обе буквы, по условию алгоритма - разные.
       return  *p1>*p2?1:-1
   }
}
Если есть вопросы - welcome.

Аватара пользователя
Max Diesel
Автор программы
Сообщения: 3131
Зарегистрирован: Пт окт 12, 2007 9:00 pm
Контактная информация:

Сообщение Max Diesel » Ср фев 20, 2008 2:25 am

Diff писал(а):А в каких каталогах наблюдаются тормоза - там где много файлов начинающихся цифрами или любых?
С числами. Причем большими.
Diff писал(а):Содержимое свитча я честно говоря, не осилил.
Вообще-то это элементарная конструкция из используемых мной (во время обучения в учебном заведении преподаватель информатики была очень недовольна тем, что в отличие от остальной группы я писал код программы в одну строку вместо привычных ей 5-10 строк). В первых скобках получится 1 в случае если в первой строке знак в позиции "a" является числом (то есть его код между 47 и 58), во вторых скобках также но относительно второй строки... соответственно умножив первые скобки на 1, а вторые на 2 получим либо 0 (когда числа нет в обоих строках), либо 1 (когда число только в первой строке), либо 2 (когда число только во второй строке), либо 3 (когда числа и в первой и во второй строках).
Diff писал(а):сделать нечто вроде

Код: Выделить всё

WChar *p1 = &st1[a];
WChar *p2 = &st2[b];
return lstrcmpiW(p1, p2)
Здесь нет перевыделения памяти, которое производит Delete. Если строки не дают использовать &st1[a] - использовать &st1.data()[a].
Действительно, такой вариант быстрее примерно на 50%. Спасибо.
Diff писал(а):Зачем case 1 и case 2 вызывают функцию сравнения? Ведь понятно же что в первом случае меньше первая, а во втором - вторая строка.
Верно. Я был сосредоточен на двух других кейсах и про этот вариант даже не подумал.
Diff писал(а):Почему если длина чисел равная, то вызывается lstrcmpi? Разве здесь не числа надо сравнивать, ради чего все и затевалось? Или я чего-то недопонял?
Если длина разная, строки добиваются нулями слева и сравниваются. А если одинаковыми окажутся?
Числа бывают разные... число "8774531" вполне можно сравнить с числом "6785375" через int, а если у чисел длина 800 знаков?
Diff писал(а):

Код: Выделить всё

int num1;
int num2;
// Вытаскиваем цифры в числа. Их длина нам совсем неинтересна.
wsscanf(st1.data(), "%d", &num1);
wsscanf(st2.data(), "%d", &num2);
Согласно предыдущему пункту (про размер числа) нельзя использовать int и соответственно wsscanf.
Diff писал(а):Вот, от ностальгии написал свою версию алгоритма. Думал, получится короче, ан нет - длиннее :). Зато в ней максимально возможны всего две операции выделения памяти.
Писал после перерыва в несколько лет, не имея под рукой компилятора - так что наверняка ошибок хватает. Но общая идея есть.
Функция сравнивает две строки, учитывая начинающие и завершающие числа.
Хм... без компилятора и соответственно без тестирования - это какой-то вероятно новый уровень программирования (Unreal Commander зачастую содержит ошибки, которые могут навести на мысль что программа сформирована в голове, но фактически это не так - тестирую каждую добавляемую функцию, правда не всегда во всех аспектах, что меня и подводит). Для начала хотелось бы отметить что функция "wsscanf" в стандартной сборке отсутствует (либо я просто не нашел что именно надо заинклудить). Рекурсия для функции сравнения - жесткий подход... сразу скажу результат - заменив wchar на wchar_t (насколько я знаю, он так называется для Wide), поставив sscanf(String(string1).c_str(),"%d", &nNum1); вместо wsscanf(string1, "%d", &nNum1); запуском функции сортировки я отправил компьютер в такие глубокие размышления, что если бы через 10-15 секунд не произошло переполнение буфера, то вероятно пришлось бы отключать приложение принудительно. Было бы неплохо если бы Вы сначала протестировали код... хотя спасибо за старания.

Закрыто