Issue 276200044: 4 - Andrew Popov - 3
|
Created:
8 years, 5 months ago by andrewpov Modified:
8 years, 3 months ago Reviewers:
ys.algorithms Visibility:
Public. |
Description4 - Andrew Popov - 3
Patch Set 1 #
Total comments: 5
Patch Set 2 : Next iteration #
Total comments: 5
Patch Set 3 : Next iteration #
Total comments: 12
Patch Set 4 : next iteration #
Total comments: 1
MessagesTotal messages: 9
Родион https://codereview.appspot.com/276200044/diff/1/main.cpp File main.cpp (right): https://codereview.appspot.com/276200044/diff/1/main.cpp#newcode12 main.cpp:12: long long coefficient; публичные поля запрещены https://codereview.appspot.com/276200044/diff/1/main.cpp#newcode14 main.cpp:14: long long base; Коэффициенты линейной функции имеют нормальные названия. Можно посмотреть их в http://en.wikipedia.org/wiki/Linear_equation#Linear_equations_in_two_variables https://codereview.appspot.com/276200044/diff/1/main.cpp#newcode35 main.cpp:35: vector<vector<long long>> hash_table; Для внутренних (второго уровня) хеш-таблиц лучше сделать отдельный класс, и общаться с ним через интерфейс как у FixedSet'а (внутри init подбирать хеш-фукнцию и т.п.). https://codereview.appspot.com/276200044/diff/1/main.cpp#newcode45 main.cpp:45: void InputNumbers (vector<int>& numbers, vector<int>& requests); думаю, что понадобится функция для чтения одного вектора https://codereview.appspot.com/276200044/diff/1/main.cpp#newcode51 main.cpp:51: RequestsProcessing (numbers, requests); а кто печатает?
Sign in to reply to this message.
Исправляй и присылай полный код, прям как следующую ревизию этого файла. Родион https://codereview.appspot.com/276200044/diff/20001/main.cpp File main.cpp (right): https://codereview.appspot.com/276200044/diff/20001/main.cpp#newcode13 main.cpp:13: long long number_of_bins; Брать по модулю размера таблицы -- это не дело хеш-функции, это обязанность хеш-таблицы. хеш-функция может существовать и без таблицы. https://codereview.appspot.com/276200044/diff/20001/main.cpp#newcode20 main.cpp:20: long long operator () (long long number) const; правда функция может быть вычислена в точке тип long long https://codereview.appspot.com/276200044/diff/20001/main.cpp#newcode22 main.cpp:22: void Randomize (long long input_number_of_bins); https://wiki.school.yandex.ru/shad/groups/2015/semester1/Algorithms1/Stylegui... пункт 19 а) стоит принять generator по ссылке и использовать его внутри функции б) лучше сделать функцию static и создать внутри новый объект (и вернуть его по значению) https://codereview.appspot.com/276200044/diff/20001/main.cpp#newcode30 main.cpp:30: private: дважды private https://codereview.appspot.com/276200044/diff/20001/main.cpp#newcode34 main.cpp:34: SecondLevelHashTable() ; там что-то нетривиальное происходит? если нет, то компилятор сам определит такой конструктор
Sign in to reply to this message.
Не очень понял, что как с рандомом нужно поступить. Создал какой-то класс, чтобы передавать можно было, но кажется это не совсем то, что хотелось. А еще не понял, зачем делать статическую функцию Randomize, возвращающую объект класса. Единственное логичное применение такого действия я видел при засовывании конструкторов в private, чтобы объектов класса больше одного нельзя было создавать. А тут целый вектор их.
Sign in to reply to this message.
Не уверен, что с первого раза все хорошо отправилось, повторю. Андрей.
Sign in to reply to this message.
Извиняюсь за долгий ответ. Исправляй замечания, которые я сделал, и наверно можно будет засчитывать. Родион https://codereview.appspot.com/276200044/diff/40001/main.cpp File main.cpp (right): https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode37 main.cpp:37: static UniverseHashFunction Randomize (RandomIntGenerator& slope_generator, так как ограничения на slope задаются только PRIME. 1 <= slope < PRIME 0 <= const term < PRIME то можно просто принять std::mt19937 generator здесь, а внутри (этого метода) создать два std::uniform_int_distribution<> distribution'a и вызвать их https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode53 main.cpp:53: size_t number_of_bins = 2 * numbers.size() * numbers.size(); странно, что есть зависимость между двумя разными переменными в разных методах. лучше сделать внешнюю функцию, которая принимает (numbers, hash_function, number_of_bins) и проверяет есть ли коллиции. https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode60 main.cpp:60: check[hash] = true; название слишком общее https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode77 main.cpp:77: hash_table[i] = 1000*1000*1000 + 1; Как пользователю узнать, что число 1000*1000*1000 + 1 нельзя вставлять в set? Лучше сделать простой аналог boost::optional (в нашем случае это может быть просто класс, содержащий T value, bool is_initialized и удобные методы для работы) http://www.boost.org/doc/libs/1_60_0/libs/optional/doc/html/index.html https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode90 main.cpp:90: if (hash_value >= hash_table.size()) { просто сперва можно написать if (table.empty()) { return false; } https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode106 main.cpp:106: for (int i = 0; i < numbers.size(); ++i) { для подсчета суммы квадратов стоит сделать отдельную функцию https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode107 main.cpp:107: sum += check[i] * check[i]; + стоит обратить внимание на возможное переполнение https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode109 main.cpp:109: if (sum <= 2 * numbers.size()) { эту 2 стоит сделать публичной константой класса (так пользователю сразу будут видны гарантии) https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode110 main.cpp:110: return true; return sum <= 2 * size() https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode122 main.cpp:122: RandomIntGenerator slope_generator(1, 1000*1000*1000); slope должен быть [1, prime number ) https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode155 main.cpp:155: results_of_queries[iteration] = true; res..[i] = set.countains(...) https://codereview.appspot.com/276200044/diff/40001/main.cpp#newcode175 main.cpp:175: scanf("%d", &number_elements); https://wiki.school.yandex.ru/shad/groups/2015/semester1/Algorithms1/Stylegui... пункт 4
Sign in to reply to this message.
Добрый вечер! Спасибо, что проверили. У меня 1 вопрос: что подразумевается под комментарием "стоит обратить внимание на возможное переполнение" в 107 строке прошлой посылки. Я постарался заметить ненужные long long на int и теперь хотя бы глупых переполнений от произведения двух чисел точно не будет. Но нужно ли вписать проверку в цикл на случай переполнения в суммировании? При ограничениях задачи вообще ничего не должно случиться. С уважением, Андрей.
Sign in to reply to this message.
Засчитано (действительно, переполнения там не может быть, ведь там все в long long) Родион https://codereview.appspot.com/276200044/diff/60001/main.cpp File main.cpp (right): https://codereview.appspot.com/276200044/diff/60001/main.cpp#newcode64 main.cpp:64: private: https://google.github.io/styleguide/cppguide.html#Declaration_Order
Sign in to reply to this message.
|
