|
|
Created:
8 years, 10 months ago by ChesnokovDS Modified:
8 years, 10 months ago Reviewers:
algorithms.shad.nsk Visibility:
Public. |
Patch Set 1 #
Total comments: 57
Patch Set 2 : second iter #
Total comments: 40
Patch Set 3 : third iteration #
Total comments: 2
MessagesTotal messages: 8
Первая посылка.
Sign in to reply to this message.
https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp File minimal_string.cpp (right): https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode27 minimal_string.cpp:27: Rule() {} Лучше NT проинициализировать на всякий случай какой-нибудь бессмыслицей, типа -1. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode29 minimal_string.cpp:29: explicit Rule(const string &str_rule) { Сделайте это методом типа importRule. Просто как-то не радует, что конструктор правила привязан к идиотскому формату ввода данной задачи (это в некотором смысла часть ввода). https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode35 minimal_string.cpp:35: std::copy(str_rule.begin() + 3, Проще: production = str_rule.substring(3); https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode44 minimal_string.cpp:44: size_t max_lenght; Не понимаю, каким образом это число является частью грамматики. Наверное, не надо хранить его внутри. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode48 minimal_string.cpp:48: Grammar(const vector<string> &str_rules, size_t max_l) { Если учесть, что max_length здесь не место, а конструктор грамматики лучше сделать НЕ привязанным к формату ввода-вывода, может быть лучше просто заменить класс на: typedef vector<Rule> Grammar; Ведь он никакого дополнительного поведения не даёт. Да и на мой взгляд можно не вкладывать Rule в Grammar. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode59 minimal_string.cpp:59: string production; Зачем вы храните копию правой части в состоянии? От этого время работы алгоритма становится больше (скорее всего, даже асимптотически). Насколько я знаю алгоритм Ёрли, в нём всегда в состоянии берётся какое-то правило грамматики. И более того, почему вы храните отдельно левую и правую часть, если можно сохранить сразу правило (Rule)? Незачем закрывать тип Rule от парсера, это лишь вызвало дополнительные неудобства. Есть два варианта решения проблемы: 1. Хранить индекс правила в грамматике парсера. Среди потенциальных проблем: Get_current_symbol не заработает. Хотя можно сохранить указатель на парсер, который оперирует этим состоянием, тогда заработает. Или можно в конструктор хотя бы передавать указатель на парсер, а след. символ посчитать прямо в конструкторе и просто запомнить. 2. Хранить ссылку на правило: const Rule &rule; Конечно, здесь понадобится немного аккуратности с инициализацией ссылок, но это несложно. Или использовать указатель. Правда под вопросом будет сравнение состояний (по адресу сравнивать нехорошо). https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode60 minimal_string.cpp:60: size_t index; index и ptr - одинаково не говорящие имена. Назовите одно start (типа где начинался разбор правила) или ruleStartInText, или startInText. А второй например rulePrefix или matchedPrefix или ещё как-то. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode85 minimal_string.cpp:85: return (96 < symbol && symbol < 123) || (symbol == '$'); Магические константы. Во-первых, 'a' вместо 97 и 'z' вместо 122. Во-вторых, тут правда нужно обрабатывать доллары? вроде же они удаляются из грамматики прямо при чтении? https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode90 minimal_string.cpp:90: void Insert_state(bool &changes, queue<State> &q, set<State> &s, const State state) { В таких случаях обычно bool возвращают (код возврата), а остальные данные передают по неконстантной ссылке: так удобнее. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode98 minimal_string.cpp:98: void Predict(bool &changes, const State &next_item, queue<State> ¤t_states, Определённо, очередь и множества состояний надо хранить как поле в классе парсинга, а не таскать их во всех методах руками. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode102 minimal_string.cpp:102: if (grammar.rules[index].NT == new_NT) { Вообще говоря, стоит предподсчитать списки правил для каждого символа, а то это неэффективно перебирать все правила для каждого состояния. Достаточно в момент инициализации посчитать map<char, vector<Rule*>> или map<char, vector<int>> и пользоваться здесь. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode111 minimal_string.cpp:111: if (next_item.Get_current_symbol() == pattern[step] || pattern[step] == '*') { Надо ввести константы для особых символов: WILDCARD = '*'; https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode122 minimal_string.cpp:122: for (set<State>::iterator iter = states[next_item.index].begin(); Заведите псевдоним для states[next_item].index. И уже поставьте компилятор поновее, пользуйтесь auto, особенно для итераторов. Или range-based for. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode138 minimal_string.cpp:138: string Find_minimal_string() { Этот метод не является часть алгоритма парсинга. Лучше поиск минимальной строки оформить ВНЕ парсера. Либо как отдельную функцию, либо как отдельный класс. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode142 minimal_string.cpp:142: if (!Contein(fuzzy)) { Это слово пишется не так. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode143 minimal_string.cpp:143: return "IMPOSSIBLE"; Определённо "IMPOSSIBLE" не стоит возвращать. Если на то пошло, "$" подходит лучше =) В любом случае, это должна быть константа класса. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode153 minimal_string.cpp:153: for (counter symbol = 1; symbol <= 26; ++symbol) { Зачем вам тип counter? Это просто эквивалент size_t? Здесь явно надо избавиться от магический констант. Может быть от 1 до 'z'-'a'? https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode160 minimal_string.cpp:160: fuzzy[len] = static_cast<char>(static_cast<int>('a') + symbol); Как насчёт единых функций перевода буквы в номер и обратно? =) https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode168 minimal_string.cpp:168: string pattern = old_attern + '$'; Опечатки исправьте, пожалуйста, их сильно много. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode169 minimal_string.cpp:169: State starting_state = State('\'', "S$", 0, 0); С учётом того, что лучше не хранить в состояниях копии правил, вам возможно придётся добавить это фиктивное правило в грамматику парсера. И сделайте константы немагическими: глобально или в Grammar: static const char START_NONTERMINAL = 'S'; в EarleyParsing: static const char HELP_NONTERMINAL = '\''; https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode170 minimal_string.cpp:170: State final_state = State('\'', "S$", 0, 2); Я может что не понимаю, но вам зачем доллар добавлять в этом правиле? Это действительно нужно? https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode175 minimal_string.cpp:175: { Вроде этот блок ничего не даёт, никаких локальных переменных не сокрывает. Тогда зачем он? И вообще, не лучше ли воспользоваться Insert_state, у вас ведь он есть? https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode181 minimal_string.cpp:181: while (changes) { Что ж, вы исправляете баг в оригинальном парсере Earley фактическим устранением BFS-а с ухудшением асимптотики в худшем случае. Вполне себе вариант =) В принципе, можно сделать правильно работающий BFS, если отдельно обработать зануляющиеся нетерминалы... но это сложнее, конечно. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode183 minimal_string.cpp:183: queue<State> buff; Зачем buff, почему нельзя сразу заполнять current_states? Зачем цикл, если можно написать просто: current_states.assign(states[step].begin(), states[step].end()); https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode184 minimal_string.cpp:184: for (set<State>::const_iterator it = states[step].begin(); Где ваш auto?... https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode191 minimal_string.cpp:191: State &next = current_states.front(); Вы сначала запоминаете ССЫЛКУ на первый элемент, потом его удаляете, а потом его используете -> undefined behavior. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode207 minimal_string.cpp:207: queue<State> buff = current_states; Да за такое отчислить мало! Есть же std::swap! https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode211 minimal_string.cpp:211: for (vector<set<State> >::const_iterator it = states.begin(); it != states.end(); ++it) { auto вам поможет... https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode212 minimal_string.cpp:212: if (it->find(final_state) != it->end()) { if (it->count(final_state)) return true; https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode222 minimal_string.cpp:222: size_t max_lenght; Это слово пишется по-другому.
Sign in to reply to this message.
Замечания исправил, за исключением пожалуй https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode143 честно говоря не понял что требуется. В данном участке кода у парсера спрашивается, содержится ли в грамматике какая либо строка длины не более чем "к" и если парсер выдает false то, по условиям задачи, нам нужно вывести "IMPOSSIBLE". https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp File minimal_string.cpp (right): https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode27 minimal_string.cpp:27: Rule() {} On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Лучше NT проинициализировать на всякий случай какой-нибудь бессмыслицей, типа > -1. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode29 minimal_string.cpp:29: explicit Rule(const string &str_rule) { On 2015/05/23 11:22:49, algorithms.shad.nsk wrote: > Сделайте это методом типа importRule. > Просто как-то не радует, что конструктор правила привязан к идиотскому формату > ввода данной задачи (это в некотором смысла часть ввода). Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode35 minimal_string.cpp:35: std::copy(str_rule.begin() + 3, On 2015/05/23 11:22:49, algorithms.shad.nsk wrote: > Проще: production = str_rule.substring(3); Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode44 minimal_string.cpp:44: size_t max_lenght; On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Не понимаю, каким образом это число является частью грамматики. > Наверное, не надо хранить его внутри. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode48 minimal_string.cpp:48: Grammar(const vector<string> &str_rules, size_t max_l) { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Если учесть, что max_length здесь не место, а конструктор грамматики лучше > сделать НЕ привязанным к формату ввода-вывода, может быть лучше просто заменить > класс на: > typedef vector<Rule> Grammar; > Ведь он никакого дополнительного поведения не даёт. > > Да и на мой взгляд можно не вкладывать Rule в Grammar. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode59 minimal_string.cpp:59: string production; On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Зачем вы храните копию правой части в состоянии? > От этого время работы алгоритма становится больше (скорее всего, даже > асимптотически). > Насколько я знаю алгоритм Ёрли, в нём всегда в состоянии берётся какое-то > правило грамматики. > И более того, почему вы храните отдельно левую и правую часть, если можно > сохранить сразу правило (Rule)? Незачем закрывать тип Rule от парсера, это лишь > вызвало дополнительные неудобства. > > Есть два варианта решения проблемы: > 1. Хранить индекс правила в грамматике парсера. Среди потенциальных проблем: > Get_current_symbol не заработает. Хотя можно сохранить указатель на парсер, > который оперирует этим состоянием, тогда заработает. Или можно в конструктор > хотя бы передавать указатель на парсер, а след. символ посчитать прямо в > конструкторе и просто запомнить. > 2. Хранить ссылку на правило: > const Rule &rule; > Конечно, здесь понадобится немного аккуратности с инициализацией ссылок, но это > несложно. Или использовать указатель. Правда под вопросом будет сравнение > состояний (по адресу сравнивать нехорошо). Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode60 minimal_string.cpp:60: size_t index; On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > index и ptr - одинаково не говорящие имена. > > Назовите одно start (типа где начинался разбор правила) или ruleStartInText, или > startInText. > А второй например rulePrefix или matchedPrefix или ещё как-то. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode85 minimal_string.cpp:85: return (96 < symbol && symbol < 123) || (symbol == '$'); On 2015/05/23 11:22:49, algorithms.shad.nsk wrote: > Магические константы. > Во-первых, 'a' вместо 97 и 'z' вместо 122. > Во-вторых, тут правда нужно обрабатывать доллары? вроде же они удаляются из > грамматики прямо при чтении? Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode98 minimal_string.cpp:98: void Predict(bool &changes, const State &next_item, queue<State> ¤t_states, On 2015/05/23 11:22:47, algorithms.shad.nsk wrote: > Определённо, очередь и множества состояний надо хранить как поле в классе > парсинга, а не таскать их во всех методах руками. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode102 minimal_string.cpp:102: if (grammar.rules[index].NT == new_NT) { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Вообще говоря, стоит предподсчитать списки правил для каждого символа, а то это > неэффективно перебирать все правила для каждого состояния. > Достаточно в момент инициализации посчитать map<char, vector<Rule*>> или > map<char, vector<int>> и пользоваться здесь. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode111 minimal_string.cpp:111: if (next_item.Get_current_symbol() == pattern[step] || pattern[step] == '*') { On 2015/05/23 11:22:49, algorithms.shad.nsk wrote: > Надо ввести константы для особых символов: WILDCARD = '*'; Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode122 minimal_string.cpp:122: for (set<State>::iterator iter = states[next_item.index].begin(); On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Заведите псевдоним для states[next_item].index. > И уже поставьте компилятор поновее, пользуйтесь auto, особенно для итераторов. > Или range-based for. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode138 minimal_string.cpp:138: string Find_minimal_string() { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Этот метод не является часть алгоритма парсинга. > Лучше поиск минимальной строки оформить ВНЕ парсера. Либо как отдельную функцию, > либо как отдельный класс. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode142 minimal_string.cpp:142: if (!Contein(fuzzy)) { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Это слово пишется не так. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode143 minimal_string.cpp:143: return "IMPOSSIBLE"; On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Определённо "IMPOSSIBLE" не стоит возвращать. > Если на то пошло, "$" подходит лучше =) > В любом случае, это должна быть константа класса. Acknowledged. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode153 minimal_string.cpp:153: for (counter symbol = 1; symbol <= 26; ++symbol) { On 2015/05/23 11:22:47, algorithms.shad.nsk wrote: > Зачем вам тип counter? Это просто эквивалент size_t? > > Здесь явно надо избавиться от магический констант. Может быть от 1 до 'z'-'a'? Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode160 minimal_string.cpp:160: fuzzy[len] = static_cast<char>(static_cast<int>('a') + symbol); On 2015/05/23 11:22:47, algorithms.shad.nsk wrote: > Как насчёт единых функций перевода буквы в номер и обратно? =) Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode168 minimal_string.cpp:168: string pattern = old_attern + '$'; On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Опечатки исправьте, пожалуйста, их сильно много. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode175 minimal_string.cpp:175: { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Вроде этот блок ничего не даёт, никаких локальных переменных не сокрывает. Тогда > зачем он? > И вообще, не лучше ли воспользоваться Insert_state, у вас ведь он есть? Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode184 minimal_string.cpp:184: for (set<State>::const_iterator it = states[step].begin(); On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Где ваш auto?... Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode191 minimal_string.cpp:191: State &next = current_states.front(); On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Вы сначала запоминаете ССЫЛКУ на первый элемент, потом его удаляете, а потом его > используете -> undefined behavior. Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode207 minimal_string.cpp:207: queue<State> buff = current_states; On 2015/05/23 11:22:47, algorithms.shad.nsk wrote: > Да за такое отчислить мало! Есть же std::swap! Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode211 minimal_string.cpp:211: for (vector<set<State> >::const_iterator it = states.begin(); it != states.end(); ++it) { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > auto вам поможет... Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode211 minimal_string.cpp:211: for (vector<set<State> >::const_iterator it = states.begin(); it != states.end(); ++it) { On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > auto вам поможет... Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode212 minimal_string.cpp:212: if (it->find(final_state) != it->end()) { On 2015/05/23 11:22:47, algorithms.shad.nsk wrote: > if (it->count(final_state)) > return true; Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode212 minimal_string.cpp:212: if (it->find(final_state) != it->end()) { On 2015/05/23 11:22:47, algorithms.shad.nsk wrote: > if (it->count(final_state)) > return true; Done. https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode222 minimal_string.cpp:222: size_t max_lenght; On 2015/05/23 11:22:48, algorithms.shad.nsk wrote: > Это слово пишется по-другому. Done.
Sign in to reply to this message.
Замечания исправил, за исключением пожалуй https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode143 честно говоря не понял что требуется. В данном участке кода у парсера спрашивается, содержится ли в грамматике какая либо строка длины не более чем "к" и если парсер выдает false то, по условиям задачи, нам нужно вывести "IMPOSSIBLE".
Sign in to reply to this message.
Кстати, это неоткалиброваность тестов или парсер Ирли так хорош, что проходит тесты, не более чем за 5ms каждый? 27 мая 2015 г., 0:56 пользователь <ChesnokovDS@gmail.com> написал: > Замечания исправил, за исключением пожалуй > > https://codereview.appspot.com/239180043/diff/1/minimal_string.cpp#newcode143 > честно говоря не понял что требуется. В данном участке кода у парсера > спрашивается, содержится ли в грамматике какая либо строка длины не > более чем "к" и если парсер выдает false то, по условиям задачи, нам > нужно вывести "IMPOSSIBLE". > > https://codereview.appspot.com/239180043/ >
Sign in to reply to this message.
https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp File minimal_string.cpp (right): https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode20 minimal_string.cpp:20: typedef size_t counter; Зачем этот typedef? https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode38 minimal_string.cpp:38: explicit Rule(const string &str_rule) { Хмм... Что насчёт переименования в Import?... https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode68 minimal_string.cpp:68: bool operator <(const State &rht) const { Странно конечно видеть, что это работает не за O(1)... Видимо у вас запас по времени большой. В принципе, если надеяться на неизменность вектора правил, можно было бы сравнивать по указателям. Но в таком случае надо убедиться, что все set-ы с состояниями очищены после завершения работы парсера, или чтобы правила нельзя было добавлять. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode81 minimal_string.cpp:81: queue<State> current_states; Лучше эти два поля объявить как-то ниже, отделить их от остальных: ведь они являются временными данными, в отличие от rules, например. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode92 minimal_string.cpp:92: bool Insert_state(bool &changes, set<State> &s, const State state, bool forward_insert) { Вообще-то если уж вы переделываете, чтобы bool возвращался как значение, то очевидно параметр changes надо убрать, так как он теперь дублирует возвращаемое значение. И очевидно в Predict, Scanner, Completer следует поступить в этим флагом так же. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode92 minimal_string.cpp:92: bool Insert_state(bool &changes, set<State> &s, const State state, bool forward_insert) { Возможно, "const State &" ?... https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode95 minimal_string.cpp:95: if (forward_insert) { Теперь вижу, что может быть не стоило критиковать передачу очередей через параметры. Напишите хотя бы: auto &q = (forward_insert ? forward_state : current_states); q.push(state); https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:108: vector<set<State> > &states, size_t step) { Уж коли выносите очереди в поле класса, почему вы не вынесли массив множеств состояний заодно? https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:111: if ((*(*it)).NT == new_NT) { const auto &rule = *it; if (rule->NT == new_NT) { ... А то получается мир звёздочек и скобочек. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:130: set<State> *current_set_of_states = &states[next_item.start_in_text]; Почему не ссылка? https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:132: iter != (states[next_item.start_in_text]).end(); Здесь почему не используете псевдоним? https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:136: State((*(*iter).rule), iter->start_in_text, Опять же, лучше завести псевдоним для *it, а потом пользоваться стрелочкой, чем разводить скобки и звёздочки. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:148: void Import_rules(const vector<string> &str_rules) { Вижу, вы как-то не так поняли моё предложение касательно функции Import. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:151: rules[index] = Rule(str_rules[index]); Мне кажется, будет разумнее в rules правило класть также внутри Insert_rule, а не снаружи его. А то сейчас Insert_rule есть, но оно почему-то делает половину работы по добавлению правила. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:156: EarleyParsing() {} Мне кажется, можно удалить либо этот конструктор, либо конструктор по вектору правил. А то вроде дублируется функционал методов. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:158: explicit EarleyParsing(vector<string> &str_rules) { Почему правила без const?... https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:166: states[0].insert(starting_state); Почему нельзя использовать Insert_state вместо этих двух строк? https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:173: queue<State> buff; Зачем buff, почему нельзя сразу заполнять current_states? Зачем цикл, если можно написать просто: current_states.assign(states[step].begin(), states[step].end()); https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:211: string Find_minimal_string(EarleyParsing &eps, size_t max_lenght) { lenght не так пишется. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:216: return "IMPOSSIBLE"; Речь идёт о том, что с точки зрения программиста получать ответ в виде "IMPOSSIBLE" или "ERROR" неудобно. Даже долбанный "$" неудобен. Можно сделать так: возвращать std::string + bool, причём булев флаг делать ложным, если никакое слово не нашлось (или при ошибке). Можно сделать ещё проще: возвращать std::unique_ptr<std::string> (В C# для этого есть Nullable). Если строка нашлась, возвращаем её (если пустая, возвращаем пустую). Если строка не нашлась, возвращаем нулевой указатель. При ошибке лучше бросать исключение или писать assert. Ведь ошибка по идее не должна произойти никогда, верно?
Sign in to reply to this message.
https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp File minimal_string.cpp (right): https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode20 minimal_string.cpp:20: typedef size_t counter; On 2015/05/27 05:34:41, algorithms.shad.nsk wrote: > Зачем этот typedef? Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode68 minimal_string.cpp:68: bool operator <(const State &rht) const { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Странно конечно видеть, что это работает не за O(1)... > Видимо у вас запас по времени большой. > > В принципе, если надеяться на неизменность вектора правил, можно было бы > сравнивать по указателям. Но в таком случае надо убедиться, что все set-ы с > состояниями очищены после завершения работы парсера, или чтобы правила нельзя > было добавлять. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode81 minimal_string.cpp:81: queue<State> current_states; On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Лучше эти два поля объявить как-то ниже, отделить их от остальных: ведь они > являются временными данными, в отличие от rules, например. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode92 minimal_string.cpp:92: bool Insert_state(bool &changes, set<State> &s, const State state, bool forward_insert) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Возможно, "const State &" ?... Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode92 minimal_string.cpp:92: bool Insert_state(bool &changes, set<State> &s, const State state, bool forward_insert) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Возможно, "const State &" ?... Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode92 minimal_string.cpp:92: bool Insert_state(bool &changes, set<State> &s, const State state, bool forward_insert) { On 2015/05/27 05:34:41, algorithms.shad.nsk wrote: > Вообще-то если уж вы переделываете, чтобы bool возвращался как значение, то > очевидно параметр changes надо убрать, так как он теперь дублирует возвращаемое > значение. > И очевидно в Predict, Scanner, Completer следует поступить в этим флагом так же. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode92 minimal_string.cpp:92: bool Insert_state(bool &changes, set<State> &s, const State state, bool forward_insert) { On 2015/05/27 05:34:41, algorithms.shad.nsk wrote: > Вообще-то если уж вы переделываете, чтобы bool возвращался как значение, то > очевидно параметр changes надо убрать, так как он теперь дублирует возвращаемое > значение. > И очевидно в Predict, Scanner, Completer следует поступить в этим флагом так же. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcode95 minimal_string.cpp:95: if (forward_insert) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Теперь вижу, что может быть не стоило критиковать передачу очередей через > параметры. > Напишите хотя бы: > auto &q = (forward_insert ? forward_state : current_states); > q.push(state); Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:108: vector<set<State> > &states, size_t step) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Уж коли выносите очереди в поле класса, почему вы не вынесли массив множеств > состояний заодно? Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:111: if ((*(*it)).NT == new_NT) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > const auto &rule = *it; > if (rule->NT == new_NT) { > ... > А то получается мир звёздочек и скобочек. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:130: set<State> *current_set_of_states = &states[next_item.start_in_text]; On 2015/05/27 05:34:41, algorithms.shad.nsk wrote: > Почему не ссылка? Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:132: iter != (states[next_item.start_in_text]).end(); On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Здесь почему не используете псевдоним? Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:136: State((*(*iter).rule), iter->start_in_text, On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Опять же, лучше завести псевдоним для *it, а потом пользоваться стрелочкой, чем > разводить скобки и звёздочки. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:151: rules[index] = Rule(str_rules[index]); On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Мне кажется, будет разумнее в rules правило класть также внутри Insert_rule, а > не снаружи его. А то сейчас Insert_rule есть, но оно почему-то делает половину > работы по добавлению правила. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:156: EarleyParsing() {} On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Мне кажется, можно удалить либо этот конструктор, либо конструктор по вектору > правил. А то вроде дублируется функционал методов. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:158: explicit EarleyParsing(vector<string> &str_rules) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Почему правила без const?... Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:166: states[0].insert(starting_state); On 2015/05/27 05:34:41, algorithms.shad.nsk wrote: > Почему нельзя использовать Insert_state вместо этих двух строк? Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:173: queue<State> buff; On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Зачем buff, почему нельзя сразу заполнять current_states? > Зачем цикл, если можно написать просто: > current_states.assign(states[step].begin(), states[step].end()); Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:211: string Find_minimal_string(EarleyParsing &eps, size_t max_lenght) { On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > lenght не так пишется. Done. https://codereview.appspot.com/239180043/diff/20001/minimal_string.cpp#newcod... minimal_string.cpp:216: return "IMPOSSIBLE"; On 2015/05/27 05:34:42, algorithms.shad.nsk wrote: > Речь идёт о том, что с точки зрения программиста получать ответ в виде > "IMPOSSIBLE" или "ERROR" неудобно. Даже долбанный "$" неудобен. > Можно сделать так: возвращать std::string + bool, причём булев флаг делать > ложным, если никакое слово не нашлось (или при ошибке). > Можно сделать ещё проще: возвращать std::unique_ptr<std::string> (В C# для этого > есть Nullable). Если строка нашлась, возвращаем её (если пустая, возвращаем > пустую). Если строка не нашлась, возвращаем нулевой указатель. > При ошибке лучше бросать исключение или писать assert. Ведь ошибка по идее не > должна произойти никогда, верно? Done.
Sign in to reply to this message.
Ладно, засчитываю. https://codereview.appspot.com/239180043/diff/40001/minimal_string.cpp File minimal_string.cpp (right): https://codereview.appspot.com/239180043/diff/40001/minimal_string.cpp#newcode48 minimal_string.cpp:48: struct ImportRule : Rule { Ну что за уродство? =) Почему нельзя сделать просто метод Rule::Import(string)? Откуда вообще взялась идея про наследование структур? =) https://codereview.appspot.com/239180043/diff/40001/minimal_string.cpp#newcod... minimal_string.cpp:119: if ((*it)->NT == new_NT) { Вы вроде завели псевдоним, а всё равно его не используете: почему-то здесь мир скобочек и звёздочек остался.
Sign in to reply to this message.
|