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

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

Модератор: motyara

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

Re:

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

Max Diesel писал(а):(во время обучения в учебном заведении преподаватель информатики была очень недовольна тем, что в отличие от остальной группы я писал код программы в одну строку вместо привычных ей 5-10 строк).
Отчасти она была права. Код должен быть хорошо читаем. Во всяком случае, это важнее чем количество строк.
Max Diesel писал(а):Числа бывают разные... число "8774531" вполне можно сравнить с числом "6785375" через int, а если у чисел длина 800 знаков?
Да, об этом я не подумал. Но честно говоря, если в именах файлов по 800 цифр, то абсолютно безразлично, как они отсортированы. Без слез на такой каталог все равно смотреть будет нельзя и воспользоваться результатом умной сортировки - тоже. Надо решать конкретную задачу, а не некий общий случай. По-моему, интом (ну, или long long для перфекционистов) вполне можно ограничиться. И предусмотреть заглушку (т.е. традиционную сортировку) для чисел которые не лезут в диапазон.
Не надо впадать в крайности - если теория вероятности говорит, что случай менее вероятен, чем прямое попадание в компьютер метеорита, то реализовывать его не надо :). Попадания метеорита комп все равно не переживет.
Max Diesel писал(а):Хм... без компилятора и соответственно без тестирования - это какой-то вероятно новый уровень программирования (Unreal Commander зачастую содержит ошибки, которые могут навести на мысль что программа сформирована в голове

Ни в коем разе. В голове был сформулирован мой отрывок. Это не новый уровень и даже не совсем программирование. Скорее размышления на тему, оформленные в код.

Max Diesel писал(а): Для начала хотелось бы отметить что функция "wsscanf" в стандартной сборке отсутствует (либо я просто не нашел что именно надо заинклудить).

Гугль утверждает, что есть - #include <widec.h> или swscanf - #include <stdio.h>. Чем они различаются - не знаю, прототип один и тот же. Впрочем, у строчных функций часто случается такое дублирование.

Max Diesel писал(а):Рекурсия для функции сравнения - жесткий подход... сразу скажу результат - заменив wchar на wchar_t (насколько я знаю, он так называется для Wide), поставив sscanf(String(string1).c_str(),"%d", &nNum1); вместо wsscanf(string1, "%d", &nNum1); запуском функции сортировки я отправил компьютер в такие глубокие размышления, что если бы через 10-15 секунд не произошло переполнение буфера, то вероятно пришлось бы отключать приложение принудительно. Было бы неплохо если бы Вы сначала протестировали код... хотя спасибо за старания.

Можно было бы и без рекурсии - но так элегантнее и не нужно дважды писать одно и то же. С точки зрения производительности и расхода памяти не блеск, но вряд ли затормозит сильно. Наверняка, именно она и отправила приложение в ступор. Значит, чего-то я недоглядел :). Если будет время - поставлю компилятор и проверю.

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

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

Сообщение panter_dsd » Ср фев 20, 2008 12:48 pm

Размышления на счет больших чисел:
1. Можно ввести ограничение на длину числа, т.е. если предел превышается, то сортировка отрабатывает с погрешностью.
2. Можно не переводить в инт, а работать со строками, т.е. вытягивать подстроки с цифрами и их уже сравнивать
Пример:
fi123le.txt
fi32le.txt
str1=123
str2=32
str1>str2
Если по длине не равны, то можно сразу сказать какое из них больше, думаю это решит проблему с большими числами.
С уважением.
Пантер.

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

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

Сообщение maXmo » Ср фев 20, 2008 2:03 pm

Согласен, учёт 800-символьных чисел – это оверкилл, не говоря уже о том, что длина имени файла ограничена 260 символами. Специальная функция для преобразования строки в число: int _wtoi(const wchar_t*). С другой стороны, сравнение чисел в строковом представлении может при определённой аккуратности дать большую производительность. Я поначалу именно так и подумал, что такой приём был выбран именно из соображений производительности. :) Подумал: «Ну он и хакер!» :lol:
Diff писал(а):

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

   // пока строки равны, идем до первого различия.
   while (*p1 && *p2 && *p1 != *p2){
проворонил начало числа, и в swscanf передавал nNum вместо &nNum. Странно, как AV не вылетело. Плюс символы надо сравнивать case-insensitive.

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

Сообщение Max Diesel » Ср фев 20, 2008 10:59 pm

Diff писал(а):Отчасти она была права. Код должен быть хорошо читаем. Во всяком случае, это важнее чем количество строк.
Для opensource-проектов возможно... а вообще сам-то я свой код воспринимаю вполне корректно, бывают конечно ситуации когда какой-нибудь if длиной в три-четыре экрана заставляет меня самого призадуматься о том, чего же я там имел в виду, но такое бывает редко, чаще мои названия переменных имеют длину по 10-20 символов и из названия можно узнать не только то, для чего переменная используется, но и отдельные принимаемые ею значения. Соответственно по названиям ориентируюсь.
Diff писал(а):Не надо впадать в крайности - если теория вероятности говорит, что случай менее вероятен, чем прямое попадание в компьютер метеорита, то реализовывать его не надо :). Попадания метеорита комп все равно не переживет.
На мой взгляд именно факт учета крайних значений функций отличает программиста от всех остальных категорий людей...
Diff писал(а):Гугль утверждает, что есть - #include <widec.h> или swscanf - #include <stdio.h>.
Возможно, но похоже он не проверял входит ли этот файл в стандартную сборку Builder'а. Сам Builder считает что не входит.
maXmo писал(а):Согласен, учёт 800-символьных чисел – это оверкилл, не говоря уже о том, что длина имени файла ограничена 260 символами.
Сказав про 800-значное число я MAX_PATH не учитывал лишь чтобы с первого взгляда было понятно про что речь.

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

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

Сообщение Diff » Чт фев 21, 2008 6:57 pm

С другой стороны, сравнение чисел в строковом представлении может при определённой аккуратности дать большую производительность.
Да, здравое зерно тут есть. Но именно что при аккуратности.
Для opensource-проектов возможно... а вообще сам-то я свой код воспринимаю вполне корректно
И для любого коммерческого проекта. И вообще для любого проекта, если есть вероятность, что твой код придется править кому-то еще. Да и собственный по прошествии полугода может в тупик поставить не по-детски.
Я когда вижу в коде подобные конструкции - бью программистов по голове, выкатываю баги и требую переписать. И переписывают не споря - code quality specification такие штуки прямо запрещает.
На мой взгляд именно факт учета крайних значений функций отличает программиста от всех остальных категорий людей...
Учет крайних значений - это одно, а необоснованные обобщения - совсем другое. Стремление реализовать гипотетический "общий случай" вместо решения конкретной задачи - очень нездоровая тенденция, ведущая к растрате ресурсов и ненужному усложнению кода. Через это все проходят, я могу наблюдать разрушительные последствия собственного стремления к глобальности :). Если получается сделать без дополнительных затрат - прекрасно. Если нет - нафиг.

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

Сообщение Max Diesel » Пт фев 22, 2008 1:24 am

Diff писал(а):Я когда вижу в коде подобные конструкции - бью программистов по голове, выкатываю баги и требую переписать. И переписывают не споря - code quality specification такие штуки прямо запрещает.
Вот мы и выяснили главную причину происхождения вирусов... но вроде бы не в этом состоит смысл темы.

shraibikus
Сообщения: 18
Зарегистрирован: Чт ноя 08, 2007 4:25 pm

Re:

Сообщение shraibikus » Пн апр 07, 2008 8:00 am

Max Diesel писал(а):...во время обучения в учебном заведении преподаватель информатики была очень недовольна тем, что в отличие от остальной группы я писал код программы в одну строку вместо привычных ей 5-10 строк...
тут не только в удобочитаемости дело, но и оптимизация в том числе :wink:

Ведь примитивно
код:

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

...
i:=1;
while i>0 do
begin
  i:=pos('.',s);
  delete(s,i,1);
end;
считается более оптимизирован, чем:

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

while pos('.',s)>0 do delete(s,pos('.',s),1);
так-что стоит задуматься, однако :mrgreen:
работает - не лезь, а-то перестанет (ц) rom.by

oco
Сообщения: 13
Зарегистрирован: Чт янв 31, 2008 4:03 pm
Откуда: Хмельницкий, Украина
Контактная информация:

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

Сообщение oco » Ср июл 16, 2008 6:04 pm

А что мешает написать:

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

while (i=pos('.',s))>0 do delete(s,i,1);
:)

Аватара пользователя
kostik-aaron
Охотник за багами
Сообщения: 211
Зарегистрирован: Пт фев 15, 2008 12:34 pm
Откуда: Зеленоград
Контактная информация:

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

Сообщение kostik-aaron » Чт июл 17, 2008 8:38 am

Бред. самый лучший код - это тот, который выполняется всех быстрее. для уроков информатики может и лучше писать более "удобочитаемо", но в деле системы реального времени важна любая задержка. А хороший программист разберётся в коде, если тот рабочий. Говорю тоже не просто так, а по опыту.
Настоящий инженер учится всю жизнь!

tl431
Охотник за багами
Сообщения: 104
Зарегистрирован: Сб окт 20, 2007 1:29 am

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

Сообщение tl431 » Чт сен 04, 2008 9:17 pm

Прошу прощения за оффтоп, но MAX_PATH на NT>5.0 системах давно уже не 260. И выбор его равным 260 уже привел к потоку багрепортов на форуме тоталкоммандера. Не стоит повторять чужие ошибки и повторно наступать на уже испробованные грабли.

shraibikus
Сообщения: 18
Зарегистрирован: Чт ноя 08, 2007 4:25 pm

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

Сообщение shraibikus » Чт сен 04, 2008 11:17 pm

oco писал(а):А что мешает написать:

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

while (i=pos('.',s))>0 do delete(s,i,1);
:)
Всё это, конечно, красиво и имеет место быть смысл.
Только - не работает (в Delphi 7 в частности), не стоит ждать от интерпритатора/компилятора абсолютной гибкости.
Хотя, возможно, в каком-нибудь СиППе это легко-реализуемо, простите не фкурсах :mrgreen:
Но примари-СУБЖ всей тусовки форума делфовый таки все-же :wink:
работает - не лезь, а-то перестанет (ц) rom.by

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

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

Сообщение maXmo » Пт сен 05, 2008 7:30 pm

tl431 писал(а):Прошу прощения за оффтоп, но MAX_PATH на NT>5.0 системах давно уже не 260. И выбор его равным 260 уже привел к потоку багрепортов на форуме тоталкоммандера. Не стоит повторять чужие ошибки и повторно наступать на уже испробованные грабли.
странно, погрепал по заголовочным файлам PlatformSDK, везде #define MAX_PATH 260, иных значений нет.

tl431
Охотник за багами
Сообщения: 104
Зарегистрирован: Сб окт 20, 2007 1:29 am

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

Сообщение tl431 » Сб сен 06, 2008 2:15 am

Согласен. Вношу уточнение. UNC-имена могут быть длиннее 260 символов (до 65536/2) емнип. Так могут пошутить например WinRar при распаковке или IE при сохраненении файлов в кэш. Оба они давно уличены в том, что кладут на винт файлы с именем длиннее 260 символов, и потом на этих именах спотыкается большинство ФМ.
Вот для примера список багрепортов с форумов ТС
http://forum.wincmd.ru/viewtopic.php?t= ... ht=maxpath
http://forum.wincmd.ru/viewtopic.php?t= ... ht=maxpath
http://ghisler.ch/board/viewtopic.php?t ... ath+length
http://ghisler.ch/board/viewtopic.php?t ... dbef98f334
http://forum.wincmd.ru/viewtopic.php?t=6090&start=15
http://forum.wincmd.ru/viewtopic.php?t= ... ht=maxpath
Причем список, вероятно, неполный. Я поленился копать дальше.

Между прочим, на следующую версию ТС уже запланировано увеличение максимальной длины пути до 1024.

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

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

Сообщение maXmo » Пн сен 08, 2008 2:19 pm

tl431 писал(а):Согласен. Вношу уточнение. UNC-имена могут быть длиннее 260 символов (до 65536/2) емнип.
хмм… Вроде чтобы достичь ограничения 32кб, надо использовать непарсеные пути, а использовать их достаточно геморно, так что в УК это появится весьма нескоро.
и что, что багрепорты? ТЦ-то в них не виноват, это works by design.

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

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

Сообщение GLaz » Ср ноя 05, 2008 8:58 pm

Вот вариант, когда числа сравниваются только целые. По этому же принципу можно было бы сделать и для дробных, используя _wtof, только вот разделителем бы была точка, а не запятая. Ищу как изменить стандартный разделитель в плюсах.

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

bool is_digit(wchar_t c)
{
  return c >= L'0' && c <= L'9';
}

// result is the same as strcmp() has
int compare_str_with_int(const wchar_t* str1, const wchar_t* str2)
{
  while (*str1 && *str2)
  {
    int chr1;
    bool chr1int;
    if (is_digit(*str1))
    {
      chr1 = _wtoi(str1);
      chr1int = true;
      do 
      { 
        ++str1; 
      } 
      while (is_digit(*str1));
    }
    else
    {
      chr1 = *str1;
      chr1int = false;
      ++str1;
    }

    int chr2;
    bool chr2int;
    if (is_digit(*str2))
    {
      chr2 = _wtoi(str2);
      chr2int = true;
      do 
      { 
        ++str2; 
      } 
      while (is_digit(*str2));
    }
    else
    {
      chr2 = *str2;
      chr2int = false;
      ++str2;
    }

    if (chr1int != chr2int)
      return chr1int ? -1 : 1;
    else
      if (chr1 != chr2)
        return chr1 - chr2;
  }

  return 0;
}

Закрыто