Форум программистов, компьютерный форум CyberForum.ru

Как оптимизировать функцию сотрировки строк? - C++

Восстановить пароль Регистрация
 
IvanPryamoy_2
0 / 0 / 0
Регистрация: 21.01.2013
Сообщений: 23
22.02.2013, 10:18     Как оптимизировать функцию сотрировки строк? #1
VisualStudio2012, Win7x64Prof

Итак, есть массив строк типа wchar_t, которые надо отсортировать (пусть это список ФИО сотрудников). Вызов функции qsort:
C++
1
qsort((void*) ArrayFIO, QuantityFIO, sizeof(wchar_t*), cmp_wchar_t);
А вот как выглядит функция сравнения строк:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int cmp_wchar_t(void const *const str1, void const *const str2)
{
    //так как сравниваются строки wchar_t, то передаются указатели на строки, значит указатели на указатели
    cint Lenght1 = wcslen(*(wchar_t**) str1);
    cint Lenght2 = wcslen(*(wchar_t**) str2);
    cint Lenght = min(Lenght1, Lenght2);
 
    for(int Index = 0; Index < Lenght; ++Index)
    {
        if((*(wchar_t**)str1)[Index] < (*(wchar_t**)str2) [Index]) return -1;
        else if((*(wchar_t**)str1)[Index] > (*(wchar_t**)str2) [Index]) return 1;
    }
 
    if(Lenght1 == Lenght2) return 0;
    else if(Lenght1 < Lenght2) return -1;
    else return 1;
}
Меня напрягает постоянное преобразование указателей:
C++
1
2
(*(wchar_t**)str1)
(*(wchar_t**)str2)
Можно как-то от него избавиться? Или оно не замедляет работу программы? Функция сравнения библиотечная, поэтому использовать какие-то глобальные переменные типа временного буфера вряд ли получится.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2013, 10:18     Как оптимизировать функцию сотрировки строк?
Посмотрите здесь:

C++ Как оптимизировать эту фцию:
Написать программу, использующую стандартную функцию сравнения строк для определения среди трех строк, вводимых пользователем, одинаковых. C++
Используя функцию копирования строк, организуйте конкатенацію и копирование строк в четвертый массив, содержащий полные имена C++
Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк. C++
C++ Как оптимизировать код?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.02.2013, 12:15     Как оптимизировать функцию сотрировки строк? #2
qsort - сишная функция. Используйте плюсовую std::sort, которая быстрее, удобнее и безопаснее.
IvanPryamoy_2
0 / 0 / 0
Регистрация: 21.01.2013
Сообщений: 23
22.02.2013, 12:26  [ТС]     Как оптимизировать функцию сотрировки строк? #3
Цитата Сообщение от diagon Посмотреть сообщение
qsort - сишная функция. Используйте плюсовую std::sort, которая быстрее, удобнее и безопаснее.
За наводку спасибо. Но основной вопрос все- таки в оптимизации функции сравнения двух строк.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.02.2013, 13:22     Как оптимизировать функцию сотрировки строк? #4
Цитата Сообщение от IvanPryamoy_2 Посмотреть сообщение
Но основной вопрос все- таки в оптимизации функции сравнения двух строк.
Касты не должны влиять на быстродействие.
У вас есть две проблемы:
1) При каждом сравнении вы пробегаете по обеим строкам, чтобы узнать их длину (wcslen - обычный цикл до '\0', если вы не знали)
2) При каждом сравнении вызывается функция сравнения
Обе проблемы решаются с использованием STL, а конкретно с использованием std::wstring и std::sort.
std::wstring всегда знает свой размер, а std::sort позволяет заинлайнить вызов функции сравнения(т.е. вызовов функции не будет).
IvanPryamoy_2
0 / 0 / 0
Регистрация: 21.01.2013
Сообщений: 23
22.02.2013, 14:40  [ТС]     Как оптимизировать функцию сотрировки строк? #5
Оптимизировал функцию сравнения строк, чтобы не было расчета длины:

C++
1
2
3
4
5
6
7
8
9
10
11
12
int  cmp_wchar_t(void const *const str1, void const *const str2)
{
    //так как сравниваются строки wchar_t, то передаются указатели на строки, значит указатели на указатели
    for(int Index = 0; ; ++Index)
    {
        if((*(wchar_t**)str1)[Index] < (*(wchar_t**)str2) [Index]) return -1;       
        else if((*(wchar_t**)str1)[Index] > (*(wchar_t**)str2) [Index]) return 1;
        
        if((*(wchar_t**)str1)[Index] == '\0') return 0; //!!! добавлена проверка конца строки
    }
 
}
Yandex
Объявления
22.02.2013, 14:40     Как оптимизировать функцию сотрировки строк?
Ответ Создать тему
Опции темы

Текущее время: 02:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru