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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
IvanPryamoy_2
0 / 0 / 0
Регистрация: 21.01.2013
Сообщений: 23
#1

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

22.02.2013, 10:18. Просмотров 389. Ответов 4
Метки нет (Все метки)

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)
Можно как-то от него избавиться? Или оно не замедляет работу программы? Функция сравнения библиотечная, поэтому использовать какие-то глобальные переменные типа временного буфера вряд ли получится.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.02.2013, 10:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как оптимизировать функцию сотрировки строк? (C++):

Как оптимизировать функцию рисования отрезка - C++
Привет. От нечего делать решил написать функцию рисования отрезка по алгоритму Брезенхема. Использовал dev-cpp + MinGW и библиотеку...

Оптимизировать функцию - C++
Помогите оптимизировать функцию она работает правильно только очень медленно :cry: уже несколько дней над ней сижу и ничего не выходит ...

Нужно оптимизировать функцию - C++
Немножко не шарю но она должна сортировать пузырьком: #include &lt;iostream&gt; #include &lt;time.h&gt; using namespace std; int pokerface...

Как передать в функцию массив символьных строк? - C++
Допустим имею char* T={&quot;aaaa&quot;, &quot;bbbb&quot;, &quot;ccc&quot;}; как передать например по указателю.

Avx, как написать эффективную функцию сравнения строк фиксированной длины? - C++
Начал изучать AVX, и никак не могу понять в чем преимущество функции _mm256_cmpeq_epi8, если потом все равно нужно делать 32 сравнения?...

Реализовать функцию перемещения строк, принимающую в качестве параметров два вектора строк - C++
Подскажите насколько правильно решена задача. условие: Напишите функцию MoveStrings, которая принимает два вектора строк, source и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
22.02.2013, 12:15 #2
qsort - сишная функция. Используйте плюсовую std::sort, которая быстрее, удобнее и безопаснее.
1
IvanPryamoy_2
0 / 0 / 0
Регистрация: 21.01.2013
Сообщений: 23
22.02.2013, 12:26  [ТС] #3
Цитата Сообщение от diagon Посмотреть сообщение
qsort - сишная функция. Используйте плюсовую std::sort, которая быстрее, удобнее и безопаснее.
За наводку спасибо. Но основной вопрос все- таки в оптимизации функции сравнения двух строк.
0
diagon
Higher
1929 / 1195 / 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 позволяет заинлайнить вызов функции сравнения(т.е. вызовов функции не будет).
1
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; //!!! добавлена проверка конца строки
    }
 
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.02.2013, 14:40
Привет! Вот еще темы с ответами:

Используя функцию копирования строк, организуйте конкатенацію и копирование строк в четвертый массив, содержащий полные имена - C++
Пожалуйста с этим заданием. Написать программу, которая описывает четыре массива. Три первых массива должны содержать имена, фамилии и...

Написать программу, использующую стандартную функцию сравнения строк для определения среди трех строк, вводимых пользователем, одинаковых. - C++
Написать программу, использующую стандартную функцию сравнения строк для определения среди трех строк, вводимых пользователем, одинаковых.

Строка: Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк. - C++
Добавить в строковый класс функцию, которая создает строку, содержащую пересечение двух строк, то есть общие символы для двух строк....

Как оптимизировать код? - C++
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;iomanip&gt; using namespace...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.02.2013, 14:40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru