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

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

Модератор: motyara

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

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

Сообщение GLaz » Чт ноя 06, 2008 2:55 pm

Вот полный алгоритм сравнения с собственным переписанным 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;
}

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

Сообщение Max Diesel » Пт ноя 21, 2008 11:32 pm

Должен признать что этот алгоритм работает быстрее моего ровно вдвое. Впрочем тестирование скорости производилось на списке имен файлов одного из среднестатистических каталогов, в котором акцента на числовые значения не было. Хотя результаты работы этого алгоритма и отличались от результатов работы моего алгоритма (и от сортировки в TC), но тем не менее ярких признаков некорректной сортировки не было видно. Проблемность этого алгоритма в том, что во-первых для дробных чисел ставится некоторый фиксированный разделитель целой и дробной части (впрочем в моем алгоритме дробность чисел вообще не учитывается, что не совсем хорошо) и во-вторых числа типа float имеют ограничение по длине, то есть при сравнении двух строк с 50-значными числами алгоритм на них запнется, соответственно как это ни странно, но нельзя использовать числовые типы переменных.

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

Re:

Сообщение GLaz » Вт ноя 25, 2008 6:44 pm

Max Diesel писал(а):... Проблемность этого алгоритма в том, что во-первых для дробных чисел ставится некоторый фиксированный разделитель целой и дробной части ...
Насколько я понимаю разделителем может быть точка или запятая. Любой другой символ смысл вряд-ли будет иметь. Подправить будет не проблема.
Max Diesel писал(а):... и во-вторых числа типа float имеют ограничение по длине, то есть при сравнении двух строк с 50-значными числами алгоритм на них запнется, соответственно как это ни странно, но нельзя использовать числовые типы переменных.
Сравнение таких больших чисел - более интересная задача. Поиграюсь на досуге :)

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

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

Сообщение GLaz » Вт ноя 25, 2008 8:19 pm

Вот новый алгоритм, который может сравнивать числа любого размера. В качестве разделителя - точка и запятая. По скорости должен быть приблизительно такой же, как и предыдущий. Если вдруг будет баг с какой-то парой строк - пиши, отдебажу.

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

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;
      }
    }
  }
}

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

Сообщение Max Diesel » Вт ноя 25, 2008 10:14 pm

Алгоритм радует. На этот момент единственный недостаток, который обнаружился, состоит в излишнем внимании к регистру букв - после сортировки первыми идут строки, начинающиеся с больших букв, а потом уже все остальные (то есть с маленьких). То есть "B" выше чем "W" (так и должно быть), но "W" выше чем "a". Сортировка вот этих строк:

ansi
Brother
Watson
watson


дает вот такой результат:

Brother
Watson
ansi
watson

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

Re:

Сообщение GLaz » Ср ноя 26, 2008 12:06 am

Max Diesel писал(а):
ansi
Brother
Watson
watson


дает вот такой результат:

Brother
Watson
ansi
watson
Сравнение строк без учета регистра - это уже третья задача :) Перевод из верхнего регистра в нижний - очень нетривиальная задача. Если для английского языка это можно сделать достаточно просто (ну и для русского и украинского, т.к. мы на них говорим), то для разминки мозгов можно попробовать перевести из верхнего в нижний, какой-нибудь язык, типа польского. Т.к. мы работаем в юникоде, то нужно для каждого языка знать коды верхних и нижних регистров всех букв.
Как бы то ни было, переводить в один регистр во время сравнения строк - очень накладно и не нужно. Этим может занятся совершенно иной алгоритм. Т.е. мы делаем ассоциацию исходных слов с этими же словами, переведенными в нижний регистр, затем сортируем их в нижнем регистре (используя последний алгоритм сравнения) и восстанавливаем исходные слова.

Остается задача перевода из верхнего регистра в нижний.
Я когда-то делал словарь и использовал в нем юникод. Для того, чтобы сортировать слова в списке без учета регистра, я использовал базу всех символов utf кодировки для всех языков. Сейчас сразу такую ссылку не дам, нужно поискать. Но в любом случае, эта база у меня осталась. Там каждому символу в каждом языке присваивался вес для сортировки без учета регистра. Я раскопаю архивы и как будет что показать - выложу. Или если интересно самому, то можешь посерфить инет.

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

Сообщение Max Diesel » Ср ноя 26, 2008 3:11 am

В моем образовании есть небольшие пробелы размером с антарктиду - некоторые конструкции в этом алгоритме мне непонятны. С указателями я обычно стараюсь дел не иметь, предпочитаю строки. Если я правильно понимаю, сравнение с учетом регистра производится здесь:

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)

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

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

Re:

Сообщение GLaz » Ср ноя 26, 2008 8:57 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)

и на первый взгляд алгоритм стал работать именно так, как нужно, причем скорость не снизилась. Буду дальше тестировать получившийся вариант алгоритма.
Не уверен, что WStrLIComp будет нормально сравнивать другие языки (об этом я и толковал). Даже уверен, что не будет. Возможно для русского она еще сгодится, т.к. это локальный язык. Попробуй протестить на русском.

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

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

Сообщение GLaz » Ср ноя 26, 2008 2:27 pm

Вот тот же самый алгорит сравнения, только добавил веса для сравнения без учета регистра для юникод символов 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;
      }
    }
  }
}
Вложения
unicode_weights.cpp
(234.09 КБ) 198 скачиваний

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

Сообщение Max Diesel » Ср ноя 26, 2008 9:06 pm

Я не совсем понял принципа работы этого массива... если взять два случайных юникодных символа (каждый из которых имеет код в промежутке от 0 до 65536) и посчитать по ним это:

int res=weight(*wch1) - weight(*wch2);

то почему-то в большинстве случаев получается 0, а не плюсовое/минусовое значение. Для тех же символов функция WStrLIComp возвращает не ноль... полагаю пояснения лишними бы не были, а то я в недоумении.

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

Re:

Сообщение GLaz » Ср ноя 26, 2008 10:01 pm

Max Diesel писал(а):Я не совсем понял принципа работы этого массива... если взять два случайных юникодных символа (каждый из которых имеет код в промежутке от 0 до 65536) и посчитать по ним это:

int res=weight(*wch1) - weight(*wch2);

то почему-то в большинстве случаев получается 0, а не плюсовое/минусовое значение. Для тех же символов функция WStrLIComp возвращает не ноль... полагаю пояснения лишними бы не были, а то я в недоумении.
Я не очень понял вопроса... Функция weight() всего-лишь возвращает значение из массива под заданным индексом. Если будут два случайных символа, то разность будет ненулевой. Она будет нулевая только для больших и маленьких одних и тех же букв. Я вроде как прогнал новый алгоритм и он все правильно отсортировал.

Если wch1 и wch2 имеют тип wchar_t, а не wchar_t*, то разименовывать из при помощи звездочки - нельзя.

Если подробнее опишешь проблему, то чего-нибудь придумаю.

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

Сообщение Max Diesel » Ср ноя 26, 2008 10:36 pm

Вот код:

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

WideString a_st=L"땥"; // десятичный код этого иероглифа 46437
WideString b_st=L"펜"; // а этого 54172

int res=weight(*a_st) - weight(*b_st);
Насколько я знаю для иероглифов нет разделения по регистрам. Переменная res получится равной 0.

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

Re:

Сообщение GLaz » Ср ноя 26, 2008 11:51 pm

Max Diesel писал(а): Насколько я знаю для иероглифов нет разделения по регистрам. Переменная res получится равной 0.
Проверил. Этих иероглифов действительно нет в массиве. Читаю unicode стандарт и пытаюсь понять, почему.

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

Сообщение Max Diesel » Чт ноя 27, 2008 12:08 am

Ну вообще-то функция WStrLIComp вполне корректно обработала иероглифы и национальные символы других стран в именах каталогов при сортировке... так что похоже ей можно доверять.

GLaz
Сообщения: 17
Зарегистрирован: Вс окт 19, 2008 12:57 am

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

Сообщение GLaz » Чт ноя 27, 2008 12:42 am

Только что нарыл в документации по юникоду, что вся эта система с весами работает хорошо, пока не встречаются исключения. А именно "CJK Ideographs" и "Hangul Syllables". Первое - это что-то китайское, второе - корейский алфавит. Описано каким образом эти иероглифы раскладываются на составные части, чтобы их можно было тоже сортировать. Тут волосы дыбом и становятся.

Если WStrLIComp работала нормально, то твоя правда - лучше ее и использовать, т.к. я не рискнул бы все эти манипуляции с иероглифами делать :)

Интересно, как ты проверил, что иероглифы сортируются нормально?

Закрыто