Страница 3 из 4
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Добавлено: Чт ноя 06, 2008 2:55 pm
GLaz
Вот полный алгоритм сравнения с собственным переписанным wtof. Разделитель по умолчанию - запятая. Можно легко поменять. Внутри строки распознаются флоаты, начинающиеся с цифры (а не с запятой).
Надеюсь, что помог.
Код: Выделить всё
bool is_digit(wchar_t c)
{
return c >= L'0' && c <= L'9';
}
// converts inStr into float. returns float value. length at out is length of float string. point - decimal point character
float w_to_f(const wchar_t* inStr, int* length = NULL, const wchar_t point = L',')
{
const wchar_t* str = inStr;
float value = 0.f;
for (; *str && *str != point && is_digit(*str); ++str)
value = value * 10.f + (*str - L'0');
if (*str == point)
++str;
for (float multiplier = 0.1f; *str && is_digit(*str); ++str, multiplier *= 0.1f)
value += multiplier * (*str - L'0');
if (length)
*length = str - inStr;
return value;
}
// result is the same as strcmp has
int compare_str_with_float(const wchar_t* str1, const wchar_t* str2, const wchar_t point = L',')
{
while (*str1 && *str2)
{
float chr1;
bool chr1float;
if (is_digit(*str1))
{
int length;
chr1 = w_to_f(str1, &length);
chr1float = true;
str1 += length;
}
else
{
chr1 = *str1;
chr1float = false;
++str1;
}
float chr2;
bool chr2float;
if (is_digit(*str2))
{
int length;
chr2 = w_to_f(str2, &length);
chr2float = true;
str2 += length;
}
else
{
chr2 = *str2;
chr2float = false;
++str2;
}
if (chr1float != chr2float)
return chr1float ? -1 : 1;
else
if (chr1 < chr2)
return -1;
else if (chr1 > chr2)
return 1;
}
return 0;
}
Добавлено: Пт ноя 21, 2008 11:32 pm
Max Diesel
Должен признать что этот алгоритм работает быстрее моего ровно вдвое. Впрочем тестирование скорости производилось на списке имен файлов одного из среднестатистических каталогов, в котором акцента на числовые значения не было. Хотя результаты работы этого алгоритма и отличались от результатов работы моего алгоритма (и от сортировки в TC), но тем не менее ярких признаков некорректной сортировки не было видно. Проблемность этого алгоритма в том, что во-первых для дробных чисел ставится некоторый фиксированный разделитель целой и дробной части (впрочем в моем алгоритме дробность чисел вообще не учитывается, что не совсем хорошо) и во-вторых числа типа float имеют ограничение по длине, то есть при сравнении двух строк с 50-значными числами алгоритм на них запнется, соответственно как это ни странно, но нельзя использовать числовые типы переменных.
Re:
Добавлено: Вт ноя 25, 2008 6:44 pm
GLaz
Max Diesel писал(а):... Проблемность этого алгоритма в том, что во-первых для дробных чисел ставится некоторый фиксированный разделитель целой и дробной части ...
Насколько я понимаю разделителем может быть точка или запятая. Любой другой символ смысл вряд-ли будет иметь. Подправить будет не проблема.
Max Diesel писал(а):... и во-вторых числа типа float имеют ограничение по длине, то есть при сравнении двух строк с 50-значными числами алгоритм на них запнется, соответственно как это ни странно, но нельзя использовать числовые типы переменных.
Сравнение таких больших чисел - более интересная задача. Поиграюсь на досуге
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Добавлено: Вт ноя 25, 2008 8:19 pm
GLaz
Вот новый алгоритм, который может сравнивать числа любого размера. В качестве разделителя - точка и запятая. По скорости должен быть приблизительно такой же, как и предыдущий. Если вдруг будет баг с какой-то парой строк - пиши, отдебажу.
Код: Выделить всё
bool is_digit(wchar_t c)
{
return c >= L'0' && c <= L'9';
}
bool is_point(wchar_t c)
{
return c == L',' || c == L'.';
}
int compare_str_with_float(const wchar_t* str1, const wchar_t* str2)
{
while (true)
{
bool is_number = false;
// compare string part
while (true)
{
bool is_digit1 = is_digit(*str1);
bool is_digit2 = is_digit(*str2);
if (is_digit1 && is_digit2)
{
is_number = true;
break;
}
if (!*str1 || *str1 != *str2)
break;
if (is_digit1 && !is_digit2)
return -1;
if (is_digit2 && !is_digit1)
return 1;
++str1;
++str2;
}
if (!is_number)
return static_cast<int>(*str1) - static_cast<int>(*str2);
int number_result = 0;
int number1_size = 0;
int number2_size = 0;
// skip leading zeroes for number
while (*str1 == L'0')
++str1;
while (*str2 == L'0')
++str2;
// compare number before decimal point
while (true)
{
bool is_digit1 = is_digit(*str1);
bool is_digit2 = is_digit(*str2);
if (!is_digit1 && !is_digit2)
break;
if (number_result == 0 && is_digit1 && is_digit2)
number_result = (*str1 > *str2) ? 1 : ((*str1 < *str2) ? -1 : 0);
if (is_digit1)
{
++str1;
++number1_size;
}
if (is_digit2)
{
++str2;
++number2_size;
}
}
if (number1_size != number2_size)
return number1_size - number2_size;
if (number_result != 0)
return number_result;
// if there is a decimal point, compare number after one
if (is_point(*str1) || is_point(*str2))
{
if (is_point(*str1))
++str1;
if (is_point(*str2))
++str2;
while (true)
{
bool is_digit1 = is_digit(*str1);
bool is_digit2 = is_digit(*str2);
if (!is_digit1 && !is_digit2)
break;
if (is_digit1 && !is_digit2)
{
while (*str1 == L'0')
++str1;
if (is_digit(*str1))
return 1;
else
break;
}
if (is_digit2 && !is_digit1)
{
while (*str2 == L'0')
++str2;
if (is_digit(*str2))
return -1;
else
break;
}
if (*str1 != *str2)
return *str1 - *str2;
++str1;
++str2;
}
}
}
}
Добавлено: Вт ноя 25, 2008 10:14 pm
Max Diesel
Алгоритм радует. На этот момент единственный недостаток, который обнаружился, состоит в излишнем внимании к регистру букв - после сортировки первыми идут строки, начинающиеся с больших букв, а потом уже все остальные (то есть с маленьких). То есть "B" выше чем "W" (так и должно быть), но "W" выше чем "a". Сортировка вот этих строк:
ansi
Brother
Watson
watson
дает вот такой результат:
Brother
Watson
ansi
watson
Re:
Добавлено: Ср ноя 26, 2008 12:06 am
GLaz
Max Diesel писал(а):
ansi
Brother
Watson
watson
дает вот такой результат:
Brother
Watson
ansi
watson
Сравнение строк без учета регистра - это уже третья задача
Перевод из верхнего регистра в нижний - очень нетривиальная задача. Если для английского языка это можно сделать достаточно просто (ну и для русского и украинского, т.к. мы на них говорим), то для разминки мозгов можно попробовать перевести из верхнего в нижний, какой-нибудь язык, типа польского. Т.к. мы работаем в юникоде, то нужно для каждого языка знать коды верхних и нижних регистров всех букв.
Как бы то ни было, переводить в один регистр во время сравнения строк - очень накладно и не нужно. Этим может занятся совершенно иной алгоритм. Т.е. мы делаем ассоциацию исходных слов с этими же словами, переведенными в нижний регистр, затем сортируем их в нижнем регистре (используя последний алгоритм сравнения) и восстанавливаем исходные слова.
Остается задача перевода из верхнего регистра в нижний.
Я когда-то делал словарь и использовал в нем юникод. Для того, чтобы сортировать слова в списке без учета регистра, я использовал базу всех символов utf кодировки для всех языков. Сейчас сразу такую ссылку не дам, нужно поискать. Но в любом случае, эта база у меня осталась. Там каждому символу в каждом языке присваивался вес для сортировки без учета регистра. Я раскопаю архивы и как будет что показать - выложу. Или если интересно самому, то можешь посерфить инет.
Добавлено: Ср ноя 26, 2008 3:11 am
Max Diesel
В моем образовании есть небольшие пробелы размером с антарктиду - некоторые конструкции в этом алгоритме мне непонятны. С указателями я обычно стараюсь дел не иметь, предпочитаю строки. Если я правильно понимаю, сравнение с учетом регистра производится здесь:
return static_cast<int>(*str1) - static_cast<int>(*str2);
Я заменил эту строку на:
return WStrLIComp(str1, str2, 1);
а также строку:
if (!*str1 || *str1 != *str2)
подправил до вот такого вида:
if (!*str1 || WStrLIComp(str1, str2, 1)!=0)
и на первый взгляд алгоритм стал работать именно так, как нужно, причем скорость не снизилась. Буду дальше тестировать получившийся вариант алгоритма.
Re:
Добавлено: Ср ноя 26, 2008 8:57 am
GLaz
Max Diesel писал(а):В моем образовании есть небольшие пробелы размером с антарктиду - некоторые конструкции в этом алгоритме мне непонятны. С указателями я обычно стараюсь дел не иметь, предпочитаю строки. Если я правильно понимаю, сравнение с учетом регистра производится здесь:
return static_cast<int>(*str1) - static_cast<int>(*str2);
Я заменил эту строку на:
return WStrLIComp(str1, str2, 1);
а также строку:
if (!*str1 || *str1 != *str2)
подправил до вот такого вида:
if (!*str1 || WStrLIComp(str1, str2, 1)!=0)
и на первый взгляд алгоритм стал работать именно так, как нужно, причем скорость не снизилась. Буду дальше тестировать получившийся вариант алгоритма.
Не уверен, что WStrLIComp будет нормально сравнивать другие языки (об этом я и толковал). Даже уверен, что не будет. Возможно для русского она еще сгодится, т.к. это локальный язык. Попробуй протестить на русском.
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Добавлено: Ср ноя 26, 2008 2:27 pm
GLaz
Вот тот же самый алгорит сравнения, только добавил веса для сравнения без учета регистра для юникод символов 0-65535 (см. аттач). Будет работать для любого языка. Такой статический массив добавляет к исполняемому файлу 128 Кб. Если использовать какой-то упаковщик, то намного меньше (там нулей куча). Как по мне, то это единственно правильный способ беззнакового сравнения без завязки на язык. Энджой.
Код: Выделить всё
#include "unicode_weights.cpp"
bool is_digit(wchar_t c)
{
return c >= L'0' && c <= L'9';
}
bool is_point(wchar_t c)
{
return c == L',' || c == L'.';
}
// returns weight for unicode character for case insensitive compare
int weight(wchar_t c)
{
return unicode_weights[static_cast<int>(c)];
}
int compare_str_with_float_insensitive(const wchar_t* str1, const wchar_t* str2)
{
while (true)
{
bool is_number = false;
// compare string part
while (true)
{
bool is_digit1 = is_digit(*str1);
bool is_digit2 = is_digit(*str2);
if (is_digit1 && is_digit2)
{
is_number = true;
break;
}
if (!*str1 || weight(*str1) != weight(*str2))
break;
if (is_digit1 && !is_digit2)
return -1;
if (is_digit2 && !is_digit1)
return 1;
++str1;
++str2;
}
if (!is_number)
return weight(*str1) - weight(*str2);
int number_result = 0;
int number1_size = 0;
int number2_size = 0;
// skip leading zeroes for number
while (*str1 == L'0')
++str1;
while (*str2 == L'0')
++str2;
// compare number before decimal point
while (true)
{
bool is_digit1 = is_digit(*str1);
bool is_digit2 = is_digit(*str2);
if (!is_digit1 && !is_digit2)
break;
if (number_result == 0 && is_digit1 && is_digit2)
number_result = (weight(*str1) > weight(*str2)) ? 1 : ((weight(*str1) < weight(*str2)) ? -1 : 0);
if (is_digit1)
{
++str1;
++number1_size;
}
if (is_digit2)
{
++str2;
++number2_size;
}
}
if (number1_size != number2_size)
return number1_size - number2_size;
if (number_result != 0)
return number_result;
// if there is a decimal point, compare number after one
if (is_point(*str1) || is_point(*str2))
{
if (is_point(*str1))
++str1;
if (is_point(*str2))
++str2;
while (true)
{
bool is_digit1 = is_digit(*str1);
bool is_digit2 = is_digit(*str2);
if (!is_digit1 && !is_digit2)
break;
if (is_digit1 && !is_digit2)
{
while (*str1 == L'0')
++str1;
if (is_digit(*str1))
return 1;
else
break;
}
if (is_digit2 && !is_digit1)
{
while (*str2 == L'0')
++str2;
if (is_digit(*str2))
return -1;
else
break;
}
if (weight(*str1) != weight(*str2))
return weight(*str1) - weight(*str2);
++str1;
++str2;
}
}
}
}
Добавлено: Ср ноя 26, 2008 9:06 pm
Max Diesel
Я не совсем понял принципа работы этого массива... если взять два случайных юникодных символа (каждый из которых имеет код в промежутке от 0 до 65536) и посчитать по ним это:
int res=weight(*wch1) - weight(*wch2);
то почему-то в большинстве случаев получается 0, а не плюсовое/минусовое значение. Для тех же символов функция WStrLIComp возвращает не ноль... полагаю пояснения лишними бы не были, а то я в недоумении.
Re:
Добавлено: Ср ноя 26, 2008 10:01 pm
GLaz
Max Diesel писал(а):Я не совсем понял принципа работы этого массива... если взять два случайных юникодных символа (каждый из которых имеет код в промежутке от 0 до 65536) и посчитать по ним это:
int res=weight(*wch1) - weight(*wch2);
то почему-то в большинстве случаев получается 0, а не плюсовое/минусовое значение. Для тех же символов функция WStrLIComp возвращает не ноль... полагаю пояснения лишними бы не были, а то я в недоумении.
Я не очень понял вопроса... Функция weight() всего-лишь возвращает значение из массива под заданным индексом. Если будут два случайных символа, то разность будет ненулевой. Она будет нулевая только для больших и маленьких одних и тех же букв. Я вроде как прогнал новый алгоритм и он все правильно отсортировал.
Если wch1 и wch2 имеют тип wchar_t, а не wchar_t*, то разименовывать из при помощи звездочки - нельзя.
Если подробнее опишешь проблему, то чего-нибудь придумаю.
Добавлено: Ср ноя 26, 2008 10:36 pm
Max Diesel
Вот код:
Код: Выделить всё
WideString a_st=L"땥"; // десятичный код этого иероглифа 46437
WideString b_st=L"펜"; // а этого 54172
int res=weight(*a_st) - weight(*b_st);
Насколько я знаю для иероглифов нет разделения по регистрам. Переменная res получится равной 0.
Re:
Добавлено: Ср ноя 26, 2008 11:51 pm
GLaz
Max Diesel писал(а):
Насколько я знаю для иероглифов нет разделения по регистрам. Переменная res получится равной 0.
Проверил. Этих иероглифов действительно нет в массиве. Читаю unicode стандарт и пытаюсь понять, почему.
Добавлено: Чт ноя 27, 2008 12:08 am
Max Diesel
Ну вообще-то функция WStrLIComp вполне корректно обработала иероглифы и национальные символы других стран в именах каталогов при сортировке... так что похоже ей можно доверять.
Re: Нужен быстрый алгоритм сравнения WIDE-строк
Добавлено: Чт ноя 27, 2008 12:42 am
GLaz
Только что нарыл в документации по юникоду, что вся эта система с весами работает хорошо, пока не встречаются исключения. А именно "CJK Ideographs" и "Hangul Syllables". Первое - это что-то китайское, второе - корейский алфавит. Описано каким образом эти иероглифы раскладываются на составные части, чтобы их можно было тоже сортировать. Тут волосы дыбом и становятся.
Если WStrLIComp работала нормально, то твоя правда - лучше ее и использовать, т.к. я не рискнул бы все эти манипуляции с иероглифами делать
Интересно, как ты проверил, что иероглифы сортируются нормально?