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

Поиск популярного триплета. Конструктивная критика - C++

Восстановить пароль Регистрация
 
Aloir
 Аватар для Aloir
216 / 216 / 13
Регистрация: 17.12.2010
Сообщений: 688
25.07.2014, 13:46     Поиск популярного триплета. Конструктивная критика #1
Добрый день. Недавно помогал решать задачу про триплеты, и захотелось услышать критики по своему коду . все-таки только учусь, и она я считаю будет полезной.

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

принципи тут все простое.. но .. вот что-то захотелось)))

ремарка:
Кликните здесь для просмотра всего текста

среда разработки MSVC 2010, к тому что, новый стандарт немного не проканает.
опустим спор про namespace std, просто было лень писать каждый раз
Кодировка: Multi-Byte


задача:
Кликните здесь для просмотра всего текста
найти самый популярный триплет (сочетание трех соседних букв в слове) и количество его повторений в строке.


код:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <tchar.h>
#include <string>
#include <Windows.h>
#include <iostream>
 
#include <vector>
#include <map>
#include <algorithm>
 
using namespace std;
 
const size_t g_triplet_lenght = 3; //длина триплета
 
//замена всех символов "не букв", на пробел
void replace_sym_to_space(string __inout &str)
{
    auto iRepl = str.begin();
    while(iRepl!= str.end())
    {
        if(IsCharAlpha(*iRepl) == 0)
            *iRepl = ' ';
        ++iRepl;
    }
}
 
//разбить строку по разделителю
void split(const string& __in text, vector<string>& __inout words, const char __in delim = ' ')
{ 
    words.clear();
    string lower_text(text);
 
    transform(lower_text.begin(), lower_text.end(), lower_text.begin(),tolower);
 
    TCHAR* pTempStr = strdup(lower_text.c_str()); 
    TCHAR* pWord = _tcstok(pTempStr,&delim); 
    
    while(pWord != NULL)
    {
        if(_tcsclen(pWord) >= g_triplet_lenght)
            words.push_back(pWord);
        pWord = _tcstok(NULL, &delim);     
        
    }
    free(pTempStr); 
}
 
//создает словарь триплетов с подсчетом количества повторений
void CreateTriplets(const string __in text, map<string,size_t> __out &triplets) 
 {
     triplets.clear();
     string tempStr(text);
     replace_sym_to_space(tempStr);
 
     //создаем список слов с длинной больше 2 символов
     vector<string> words;
     split(tempStr,words);
     auto iter = words.begin();
     while(iter!= words.end())
     {
         string temp(*iter);
         size_t len = temp.length();
        
         //разбиение слова на триплеты;
         //помещение и подсчет в словарь триплетов
         while(len >= g_triplet_lenght)
         {
             string trpl = temp.substr(0,3);
 
             auto iterF = triplets.find(trpl);
             if(iterF != triplets.end())
                (*iterF).second =++(*iterF).second;
             else
                 triplets.insert(make_pair(trpl,1));
             
             temp = temp.substr(1);
             len = temp.length();
         }
         ++iter;
     }
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(0,"RUS");
 
    const string input_string = "Карл у Клары украл кораллы, а Клара у Карла украла кларнет";
    cout <<"Входная строка: "<<endl << input_string<<endl<<endl;
    map<string,size_t> dictionary;
    CreateTriplets(input_string,dictionary);
 
    //поиск максимально повторяющихся триплетов
    size_t max_value = max_element(dictionary.begin(),dictionary.end(),
            [](const pair<string,size_t> &left,const pair<string,size_t> &right){return left.second < right.second;}
        )->second;
    
    for(auto iOutPut = dictionary.begin(); iOutPut != dictionary.end();++iOutPut)
    {
        if((*iOutPut).second == max_value)
            cout << "Триплет: " << (*iOutPut).first<< "; Количество повторений: "<<(*iOutPut).second<<endl;
    }
    
    cout <<endl;
    system("pause");
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
25.07.2014, 14:08     Поиск популярного триплета. Конструктивная критика #2
Цитата Сообщение от Aloir Посмотреть сообщение
код:
Особо не смотрел, но что бросилось в глаза:

1) TCHAR
2) #include <Windows.h>
3) __in, __inout, хм, ну-у-у-у, если только ты пользуешься соответствующим анализатором кода
4) Слишком много кода и ручной работы
Aloir
 Аватар для Aloir
216 / 216 / 13
Регистрация: 17.12.2010
Сообщений: 688
25.07.2014, 14:17  [ТС]     Поиск популярного триплета. Конструктивная критика #3
Voivoid,
1. по превычке леплю..
2. для функцииIsCharAlpha
3. приходится отголоски работы.. можно просто на коменты заменить /* IN */ и в том же духе или перед функцие описание параметров..
4. не понял. поясните что вы имеете ввиду.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
25.07.2014, 14:42     Поиск популярного триплета. Конструктивная критика #4
Как-то так, чуть покороче. Но еще я бы нашел алгоритм для разбора слова на триплеты... Но пока не удалось.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <string>
#include <vector>
#include <map>
#include <iostream>
 
#include <boost/algorithm/string.hpp>
 
const int triplet_length = 3;
 
std::map<std::string, int> create_triplets(const std::string& string)
{
   std::string str = string;
   std::replace_if(str.begin(), str.end(), [](const char value) { return !isalpha(value); }, ' ');
   std::vector<std::string> words;
   boost::split(words, str, boost::is_any_of(" "), boost::token_compress_on);
   words.erase(std::remove_if(words.begin(), words.end(), [](const std::string& w) { return w.length() < triplet_length; }),
   words.end());
   std::copy(words.begin(), words.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
 
   std::map<std::string, int> result;
   for (const std::string& w : words)
   {
      for (std::string::const_iterator pos = w.begin(); pos != w.end(); ++pos)
      {
         std::string::const_iterator next = pos + 3;
         if (next >= w.end())
         {
            break;
         }
         std::string triplet(pos, next);
         std::transform(triplet.begin(), triplet.end(), triplet.begin(), tolower);
         std::map<std::string, int>::iterator tpos = result.find(triplet);
         if (tpos == result.end())
         {
            result.insert(std::make_pair(triplet, 1));
         }
         else
         {
            ++tpos->second;
         }
      }
   }
   return result;
}
 
int main()
{
   const std::string str = "Karl y Klari ykral koralli, a Klara y Karla ykrala klarnet";
   //"Карл у Клары украл кораллы, а Клара у Карла украла кларнет";
   const std::map<std::string, int> triplets = create_triplets(str);
   const int max = std::max_element(triplets.begin(), triplets.end(),
         [](const std::pair<std::string, int>& p1, const std::pair<std::string, int>& p2)
         {
            return std::max(p1.second, p2.second);
         }
   )->second;
   for (const auto& p : triplets)
   {
      if (p.second == max)
      {
         std::cout << "triplet: " << p.first << " " << p.second << std::endl;
      }
   }
}
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
25.07.2014, 14:49     Поиск популярного триплета. Конструктивная критика #5
Цитата Сообщение от ForEveR Посмотреть сообщение
Как-то так, чуть покороче
Уже лучше, мой вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <fcntl.h>
#include <io.h>
#include <stdio.h>
 
#include <windows.h>
 
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <vector>
 
namespace {
  const int g_triplet_size = 3;
}
 
std::vector<std::wstring> break_word_to_triplets( const std::wstring& a_str ) {
  if( a_str.size() < g_triplet_size ) {
    return std::vector<std::wstring>();
  }
 
  std::vector<std::wstring> triplets;
  for( std::size_t i = 0; i <= a_str.size() - g_triplet_size; ++i ) {
    triplets.push_back( a_str.substr( i, g_triplet_size ) );
  }
 
  return triplets;
}
 
std::vector<std::wstring> break_sentence_to_triplets( std::wstring a_str ) {
  std::transform( a_str.cbegin(), a_str.cend(), a_str.begin(), &tolower );
  std::vector < std::wstring > triplets;
 
  std::wistringstream ss( a_str );
  std::wstring str;
  while( ss >> str ) {
    auto word_triplets = break_word_to_triplets( str );
    triplets.insert( triplets.end(), std::make_move_iterator( word_triplets.begin() ), std::make_move_iterator( word_triplets.end() ) );
  }
 
  return triplets;
}
 
int main() {
 
  _setmode( _fileno( stdout ), _O_U8TEXT );
  ::SetConsoleOutputCP( CP_UTF8 );
 
  std::wstring input = L"Карл у Клары украл кораллы, а Клара у Карла украла кларнет";
  auto triplets = break_sentence_to_triplets( input );
  typedef std::map<const std::wstring, int> TripletMap;
  TripletMap map;
  for( const auto& triplet : triplets ) {
    map[ triplet ] += 1;
  }
 
  auto iter = std::max_element( map.cbegin(), map.cend(), std::bind( std::less<int>(), std::bind( &TripletMap::value_type::second, std::placeholders::_1 ), std::bind( &TripletMap::value_type::second, std::placeholders::_2 ) ) );
  std::wcout << iter->first << L" : " << iter->second << L"\n";
 
  return 0;
}
Цитата Сообщение от Aloir Посмотреть сообщение
2. для функцииIsCharAlpha
Если же isalpha
Aloir
 Аватар для Aloir
216 / 216 / 13
Регистрация: 17.12.2010
Сообщений: 688
25.07.2014, 15:10  [ТС]     Поиск популярного триплета. Конструктивная критика #6
Voivoid, isalpha - хм, что-то вообще из головы вылетело.

спасибо за примеры, буду изучать..
правда тут кое где стандарт 11.. , msvc2010 не поддерживает все никак не доберусь до 13 студии

к сожалению мало практики по работе с всякими функциями std,а с boostом практический нету..
на работе MFC..

вот пытаюсь наработать навык, но пока идет медленно..
Psilon
Master of Orion
 Аватар для Psilon
5742 / 4690 / 619
Регистрация: 10.07.2011
Сообщений: 14,162
Записей в блоге: 5
Завершенные тесты: 4
25.07.2014, 18:36     Поиск популярного триплета. Конструктивная критика #7
Voivoid, а чем 1) и 2) плохи? Типа Win only?
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
25.07.2014, 19:25     Поиск популярного триплета. Конструктивная критика #8
Цитата Сообщение от Psilon Посмотреть сообщение
Voivoid, а чем 1) и 2) плохи? Типа Win only?
1) На дворе 2014 год как-никак. TCHAR был нужен во времена переходного периода, когда unicode только-только просачивался в пользовательские приложения. Сейчас имеет смысл сразу выбирать unicode ( или utf8 или utf16 ). Ну или ansi если пишется что-нибудь уровня laba3.

2) windows.h ради одной фукнции IsCharAlpha это странновато.
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,673
26.07.2014, 09:16     Поиск популярного триплета. Конструктивная критика #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/////////////////////////////////////////////////////////////////////////////////////////
//найти самый популярный триплет (сочетание трех соседних букв в слове) и количество его повторений в строке.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <functional>
#include <iostream>
#include <iterator>
#include <locale>
#include <map>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef std::map    < T_str,    int >   T_count_of_substr;
/////////////////////////////////////////////////////////////////////////////////////////
void    get_from_str_and_substr_len_count_of_substr_and_max_count
    (
        T_str   const       &   s,
        int                     substr_len,
        T_count_of_substr   &   count_of_substr,
        int                 &   substr_count_max
    )
{
    int     substr_count_cur    =   0;
    auto    start_it            =   s.begin();
 
    for(;;)
    {
        auto    substr_it   =   std::search_n
                                    (
                                        start_it,
                                        s.end(),
                                        substr_len,
                                        'a',
                                        []  (
                                                char    L,
                                                char    R
                                            )
                                        {
                                            return  isalpha
                                                        (
                                                            L,
                                                            std::locale("")
                                                        );
                                        }
                                    );
 
        if  (
                substr_it  ==  s.end()
            )
        {
            break;
        }
 
        start_it    =   substr_it;
        ++start_it;
 
        substr_count_cur   =   ++count_of_substr
                                    [
                                        s.substr
                                            (
                                                std::distance( s.begin(), substr_it ),
                                                substr_len
                                            )
                                    ];
 
        if( substr_count_cur > substr_count_max )
        {
            substr_count_max   =   substr_count_cur;
        }
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
namespace std
{
    std::ostream& operator<<
        (
            std::ostream                            &   out,
            T_count_of_substr::value_type   const   &   substr_and_count
        )
    {
        out     <<  '\t'
                <<  '\"'
                <<  substr_and_count.first
                <<  '\"'
                <<  '\t'
                <<  "число повторений: "
                <<  substr_and_count.second
                <<  std::endl;
 
        return out;
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void    print_most_frequent_substr_with_len_of_str_for_count_max
    (
        T_str               const   &   s,
        int                             substr_len,
        T_count_of_substr   const   &   count_of_substr,
        int                             substr_count_max
    )
{
    std::cout   <<  s
                <<  std::endl
                <<  std::endl
                <<  "В данной строке из подстрок длины "
                <<  substr_len
                <<  " чаще всего встречаются следующие:"
                <<  std::endl;
 
    if  (
            count_of_substr.empty()
        )
    {
        std::cout   <<  "ни одной нет."
                    <<  std::endl;
    }
 
    std::remove_copy_if
        (
            count_of_substr.begin                                   (),
            count_of_substr.end                                     (),
            std::ostream_iterator<T_count_of_substr::value_type>    ( std::cout ),
 
            [ substr_count_max ]( T_count_of_substr::value_type  substr_and_count )
            {
                return  substr_and_count.second    <   substr_count_max;
            }
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
void    str_tolower( T_str  &   s )
{
    std::transform
        (
            s.begin     (),
            s.end       (),
            s.begin     (),
 
            []( char symb )
            {
                return  tolower
                            (
                                symb,
                                std::locale("")
                            );
            }
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    srand(unsigned(time(0)));
 
    T_str   s   =   "Карл у Клары украл кораллы, а Клара у Карла украла кларнет";
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  "Введите длину буквенной подстроки: ";
 
        int     substr_len  =   0;
        std::cin    >>  substr_len;
 
        if( substr_len < 1 )
        {
            break;
        }
 
        T_str   lower_s     =   s;
        str_tolower( lower_s );
 
        T_count_of_substr   count_of_substr;
        int                 substr_count_max    =   0;
 
        get_from_str_and_substr_len_count_of_substr_and_max_count
            (
                lower_s,
                substr_len,
                count_of_substr,
                substr_count_max
            );
 
        print_most_frequent_substr_with_len_of_str_for_count_max
            (
                s,
                substr_len,
                count_of_substr,
                substr_count_max
            );
    }//for
}
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
26.07.2014, 12:45     Поиск популярного триплета. Конструктивная критика #10
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
26.07.2014, 13:02     Поиск популярного триплета. Конструктивная критика #11
Voivoid, Ну. Если убрать форматирование, получится ненамного больше строк, нежели у тебя, насколько я вижу.
Voivoid
 Аватар для Voivoid
580 / 256 / 12
Регистрация: 31.03.2013
Сообщений: 1,284
26.07.2014, 13:08     Поиск популярного триплета. Конструктивная критика #12
Собственно от форматирования-то у меня глаза и полезли на лоб. До кода уже дело не дошло, что-нибудь там прочитать мне не представляется возможным
ForEveR
26.07.2014, 13:18
  #13

Не по теме:

Voivoid, Да, у Mr.X довольно необычный стиль форматирования, но язык знает хорошо. Поэтому как он пишет на форуме - его дело, главное что задача решается, ИМХО.

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.07.2014, 13:26     Поиск популярного триплета. Конструктивная критика
Еще ссылки по теме:

Поиск пикселя и поиск изображения на экране C++
Пишем рогалик: пояснения по коду и его критика C++
Поиск числа в двумерном массиве (бинарный поиск) C++

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

Или воспользуйтесь поиском по форуму:
Psilon
26.07.2014, 13:26     Поиск популярного триплета. Конструктивная критика
  #14

Не по теме:

ForEveR, имхо необычный == плохой. Потому как по статистике программист больше читает код, чем пишет. А когда код может прочитать десяток "избранных", то какой бы он ни был распрекрасный по другим параметрам - глобально он не очень.

Yandex
Объявления
26.07.2014, 13:26     Поиск популярного триплета. Конструктивная критика
Ответ Создать тему
Опции темы

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