Нужен быстрый алгоритм сравнения WIDE-строк
Модератор: motyara
-
- Автор программы
- Сообщения: 3432
- Зарегистрирован: Пт окт 12, 2007 3:26 pm
Нужен быстрый алгоритм сравнения WIDE-строк
По какой-то причине сортировка, алгоритм которой написан на 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, то я был бы весьма признателен за предоставление мне его кода.
Примеры строк, каждая следующая из них согласно такому алгоритму сравнения должна считаться большей чем любая из предыдущих:
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, то я был бы весьма признателен за предоставление мне его кода.
-
- Охотник за багами
- Сообщения: 228
- Зарегистрирован: Чт окт 18, 2007 6:20 pm
- Откуда: г.Таганрог
Re: Нужен быстрый алгоритм сравнения WIDE-строк на Delphi
Код: Выделить всё
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;
}
}
}
Думаю на плюсах все таки побыстрее будет, чем на паскале.
С уважением.
Пантер.
Пантер.
-
- Автор программы
- Сообщения: 3432
- Зарегистрирован: Пт окт 12, 2007 3:26 pm
-
- Сообщения: 109
- Зарегистрирован: Вт янв 29, 2008 4:44 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Это алгоритм не сортировки, а сравнения. Кроме того, меня сомневает, что этот код будет работать с unicode. Ну и оптимизировать его есть куда, прямо скажем.
-
- Охотник за багами
- Сообщения: 228
- Зарегистрирован: Чт окт 18, 2007 6:20 pm
- Откуда: г.Таганрог
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Млин, извините. Код действительно фигня.
С уважением.
Пантер.
Пантер.
-
- Сообщения: 109
- Зарегистрирован: Вт янв 29, 2008 4:44 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
А это действительно все необходимо? В смысле - распознавать вещественные числа и учитывать цифры, которые идут после текста? Если речь идет о сортировке файлов так чтобы "9" шел прежде "10", то имхо, это немного излишне. А может, даже вредно.
По идее, хорошо написанный алгоритм на C будет чуть быстрее хорошо написанного на паскале, поскольку C предоставляет больше возможностей для работы с указателями, что позволяет избежать индексации строк. Однако на практике обычно критику заслуживает не язык, а сам алгоритм - пузырьковая сортировка будет работать медленно, как бы распрекрасно она ни была реализована .
Посему хотелось бы чуть больше подробностей о цели этого алгоритма.
По идее, хорошо написанный алгоритм на C будет чуть быстрее хорошо написанного на паскале, поскольку C предоставляет больше возможностей для работы с указателями, что позволяет избежать индексации строк. Однако на практике обычно критику заслуживает не язык, а сам алгоритм - пузырьковая сортировка будет работать медленно, как бы распрекрасно она ни была реализована .
Посему хотелось бы чуть больше подробностей о цели этого алгоритма.
-
- Охотник за багами
- Сообщения: 228
- Зарегистрирован: Чт окт 18, 2007 6:20 pm
- Откуда: г.Таганрог
Re: Нужен быстрый алгоритм сравнения WIDE-строк
А еще лучше текущий алгоритм, а там можно внести изенения и подправить.
С уважением.
Пантер.
Пантер.
-
- Автор программы
- Сообщения: 3432
- Зарегистрирован: Пт окт 12, 2007 3:26 pm
-
- Сообщения: 109
- Зарегистрирован: Вт янв 29, 2008 4:44 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Да, но зачем такие изыски, как вещественные числа и цифры вперемешку с текстом? Не забудьте еще, что десятичная точка в зависимости от локали бывает "." и "," - это еще добавит путаницы. По-моему, можно и нужно ограничиться лидирующими цифрами. Тогда и алгоритм сравнения будет простым.
Простейший способ вытащить число из начала строки - sscanf(string, "%d", &number), хотя я не уверен, что он будет быстрейшим.
Добавлено:
Хотя... Тут подумал, что каталоги вида
[/b]
Тоже неплохо было бы уметь так сортировать. То есть завершающие числа тоже имеют смысл. Но их тоже выцепить легко.
Простейший способ вытащить число из начала строки - sscanf(string, "%d", &number), хотя я не уверен, что он будет быстрейшим.
Добавлено:
Хотя... Тут подумал, что каталоги вида
Код: Выделить всё
dir1
dir2
...
dir9
dir10
Тоже неплохо было бы уметь так сортировать. То есть завершающие числа тоже имеют смысл. Но их тоже выцепить легко.
-
- Автор программы
- Сообщения: 3432
- Зарегистрирован: Пт окт 12, 2007 3:26 pm
Элементарный код сравнения с учетом величины числа я написал, правда в моей интерпретации он скоростью отличается лишь в сторону ее отсутствия. На входе в небольшой каталог различие чувствуется не очень сильно, а вот для крупных (5000 файлов/каталогов) вполне заметно. Раз в 10. Я не очень люблю выставлять свой код на показ, так как зачастую он написан недостаточно рационально, но в надежде на то, что кто-нибудь найдет в нем оптимизируемые по скорости фрагменты (или ошибки) размещаю его здесь:
[/color]
Код: Выделить всё
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;
}
//---------------------------------------------------------------------------
-
- Сообщения: 109
- Зарегистрирован: Вт янв 29, 2008 4:44 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Ага... А в каких каталогах наблюдаются тормоза - там где много файлов начинающихся цифрами или любых?
Попробуем разобраться. Каюсь, никогда с юникодом не работал, поэтому могу сесть в лужу.
Содержимое свитча я честно говоря, не осилил. Но будем считать что там все хорошо.
case 0:
На мой взгляд тормозные места здесь - это библиотечные функции работы со строками. Они страшно медленные. Спасаться будем указателями.
Вместо
сделать нечто вроде
Здесь нет перевыделения памяти, которое производит Delete. Если строки не дают использовать &st1[a] - использовать &st1.data()[a].
Дальше.
Зачем case 1 и case 2 вызывают функцию сравнения? Ведь понятно же что в первом случае меньше первая, а во втором - вторая строка.
Ну и наконец case 3.
Почему если длина чисел равная, то вызывается lstrcmpi? Разве здесь не числа надо сравнивать, ради чего все и затевалось? Или я чего-то недопонял?
Если длина разная, строки добиваются нулями слева и сравниваются. А если одинаковыми окажутся?
Я бы все это попробовал поменять на примерно следующее:
Как-то так. Сто лет уже на C не писАл . В существовании функции wsscanf я не уверен, но наверняка должен быть какой-то вариант sscanf для юникода.
Попробуем разобраться. Каюсь, никогда с юникодом не работал, поэтому могу сесть в лужу.
Содержимое свитча я честно говоря, не осилил. Но будем считать что там все хорошо.
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)
Дальше.
Зачем 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
Будет отсортировано именно так, что с точки зрения подхода неверно.
Но по-моему, на это можно забить. А если не хочется - то перед сравнением лидирующие цифры отрезать.
*/
-
- Охотник за багами
- Сообщения: 98
- Зарегистрирован: Пт ноя 09, 2007 8:03 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Ну да. Главные тормоза, думаю, сидят в реаллоках в st1.Delete(0, a); и num1=AnsiString::StringOfChar('0', (b-m2)-(a-m1))+num1; плюс перекодировка из юникода в анси: num1=st1.SubString(m1, a-m1); (также с реаллоком).
Думаю, это самое главное, а дальнейших оптимизаций в приведённый код можно очень много наворотить (если есть желание их реализовывать).
Думаю, это самое главное, а дальнейших оптимизаций в приведённый код можно очень много наворотить (если есть желание их реализовывать).
-
- Охотник за багами
- Сообщения: 98
- Зарегистрирован: Пт ноя 09, 2007 8:03 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
А вообще, по-моему, фича не критичная.
-
- Сообщения: 109
- Зарегистрирован: Вт янв 29, 2008 4:44 pm
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Вот, от ностальгии написал свою версию алгоритма. Думал, получится короче, ан нет - длиннее . Зато в ней максимально возможны всего две операции выделения памяти.
Писал после перерыва в несколько лет, не имея под рукой компилятора - так что наверняка ошибок хватает. Но общая идея есть.
Функция сравнивает две строки, учитывая начинающие и завершающие числа.
Если есть вопросы - welcome.
Писал после перерыва в несколько лет, не имея под рукой компилятора - так что наверняка ошибок хватает. Но общая идея есть.
Функция сравнивает две строки, учитывая начинающие и завершающие числа.
Код: Выделить всё
// Возвращаем 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
}
}
-
- Автор программы
- Сообщения: 3432
- Зарегистрирован: Пт окт 12, 2007 3:26 pm
С числами. Причем большими.Diff писал(а):А в каких каталогах наблюдаются тормоза - там где много файлов начинающихся цифрами или любых?
Вообще-то это элементарная конструкция из используемых мной (во время обучения в учебном заведении преподаватель информатики была очень недовольна тем, что в отличие от остальной группы я писал код программы в одну строку вместо привычных ей 5-10 строк). В первых скобках получится 1 в случае если в первой строке знак в позиции "a" является числом (то есть его код между 47 и 58), во вторых скобках также но относительно второй строки... соответственно умножив первые скобки на 1, а вторые на 2 получим либо 0 (когда числа нет в обоих строках), либо 1 (когда число только в первой строке), либо 2 (когда число только во второй строке), либо 3 (когда числа и в первой и во второй строках).Diff писал(а):Содержимое свитча я честно говоря, не осилил.
Действительно, такой вариант быстрее примерно на 50%. Спасибо.Diff писал(а):сделать нечто вродеЗдесь нет перевыделения памяти, которое производит Delete. Если строки не дают использовать &st1[a] - использовать &st1.data()[a].Код: Выделить всё
WChar *p1 = &st1[a]; WChar *p2 = &st2[b]; return lstrcmpiW(p1, p2)
Верно. Я был сосредоточен на двух других кейсах и про этот вариант даже не подумал.Diff писал(а):Зачем case 1 и case 2 вызывают функцию сравнения? Ведь понятно же что в первом случае меньше первая, а во втором - вторая строка.
Числа бывают разные... число "8774531" вполне можно сравнить с числом "6785375" через int, а если у чисел длина 800 знаков?Diff писал(а):Почему если длина чисел равная, то вызывается lstrcmpi? Разве здесь не числа надо сравнивать, ради чего все и затевалось? Или я чего-то недопонял?
Если длина разная, строки добиваются нулями слева и сравниваются. А если одинаковыми окажутся?
Согласно предыдущему пункту (про размер числа) нельзя использовать int и соответственно wsscanf.Diff писал(а):Код: Выделить всё
int num1; int num2; // Вытаскиваем цифры в числа. Их длина нам совсем неинтересна. wsscanf(st1.data(), "%d", &num1); wsscanf(st2.data(), "%d", &num2);
Хм... без компилятора и соответственно без тестирования - это какой-то вероятно новый уровень программирования (Unreal Commander зачастую содержит ошибки, которые могут навести на мысль что программа сформирована в голове, но фактически это не так - тестирую каждую добавляемую функцию, правда не всегда во всех аспектах, что меня и подводит). Для начала хотелось бы отметить что функция "wsscanf" в стандартной сборке отсутствует (либо я просто не нашел что именно надо заинклудить). Рекурсия для функции сравнения - жесткий подход... сразу скажу результат - заменив wchar на wchar_t (насколько я знаю, он так называется для Wide), поставив sscanf(String(string1).c_str(),"%d", &nNum1); вместо wsscanf(string1, "%d", &nNum1); запуском функции сортировки я отправил компьютер в такие глубокие размышления, что если бы через 10-15 секунд не произошло переполнение буфера, то вероятно пришлось бы отключать приложение принудительно. Было бы неплохо если бы Вы сначала протестировали код... хотя спасибо за старания.Diff писал(а):Вот, от ностальгии написал свою версию алгоритма. Думал, получится короче, ан нет - длиннее . Зато в ней максимально возможны всего две операции выделения памяти.
Писал после перерыва в несколько лет, не имея под рукой компилятора - так что наверняка ошибок хватает. Но общая идея есть.
Функция сравнивает две строки, учитывая начинающие и завершающие числа.