Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/21: Рейтинг темы: голосов - 21, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
1

Подскажите место с ошибкой в оптимизированном коде

15.09.2018, 00:35. Показов 3936. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Прохожу курс по c++, стоит задача оптимизировать код электронной книги, в которой выводится мотивационное сообщение с процентом от всех людей, которых обогнал читатель при ограничении в кол-во запросов 10^6, номера страниц меньше 1000, а номера пользователей не превосходят 10^5.

Изначальный код, правильный, но медленный:
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
class ReadingManager {
public:
  ReadingManager()
      : user_page_counts_(MAX_USER_COUNT_ + 1, 0),
        sorted_users_(),
        user_positions_(MAX_USER_COUNT_ + 1, -1) {}
 
  void Read(int user_id, int page_count) {
    if (user_page_counts_[user_id] == 0) {
      AddUser(user_id);
    }
    user_page_counts_[user_id] = page_count;
    int& position = user_positions_[user_id];
    while (position > 0 && page_count > user_page_counts_[sorted_users_[position - 1]]) {
      SwapUsers(position, position - 1);
    }
  }
 
  double Cheer(int user_id) const {
    if (user_page_counts_[user_id] == 0) {
      return 0;
    }
    const int user_count = GetUserCount();
    if (user_count == 1) {
      return 1;
    }
    const int page_count = user_page_counts_[user_id];
    int position = user_positions_[user_id];
    while (position < user_count &&
      user_page_counts_[sorted_users_[position]] == page_count) {
      ++position;
    }
    if (position == user_count) {
        return 0;
    }
 
    return (user_count - position) * 1.0 / (user_count - 1);
  }
 
private:
  static const int MAX_USER_COUNT_ = 100000;
 
  vector<int> user_page_counts_;
  vector<int> sorted_users_;
  vector<int> user_positions_;
 
  int GetUserCount() const {
    return sorted_users_.size();
  }
  void AddUser(int user_id) {
    sorted_users_.push_back(user_id);
    user_positions_[user_id] = sorted_users_.size() - 1;
  }
  void SwapUsers(int lhs_position, int rhs_position) {
    const int lhs_id = sorted_users_[lhs_position];
    const int rhs_id = sorted_users_[rhs_position];
    swap(sorted_users_[lhs_position], sorted_users_[rhs_position]);
    swap(user_positions_[lhs_id], user_positions_[rhs_id]);
  }
};
После оптимизации:
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
class ReadingManager {
public:
    ReadingManager()
        : user_page_counts_(),
        sorted_users_(),
        user_positions_() {}
 
    void Read(int user_id, int page_count) {
        if (user_page_counts_.count(user_id) != 1) {//Log(Q)
        }
        else {
        int prevP = user_page_counts_[user_id];//Log(Q)
        sorted_users_.erase(user_positions_[user_id]);// amortized O(1)
        }
        user_page_counts_[user_id] = page_count;//Log(Q)
        user_positions_[user_id] = sorted_users_.insert(make_pair(page_count, user_id)); //2Log(Q)
    }
 
    double Cheer(int user_id) {
        if (user_page_counts_.count(user_id) != 1) {//Log(Q)
            return 0;
        }
        multiset<pair<int, int>>::iterator position = user_positions_[user_id]; //Log(Q)
        const int user_count = sorted_users_.size(); // O(1)
        if (user_count == 1) {
            return 1;
        }
        if (position == sorted_users_.begin()) { //Log(N)
            return 0;
        }
        while (position != sorted_users_.begin() 
            && (*position).first == (*prev(position)).first 
            && (*position).second > (*prev(position)).second) {
 
            user_positions_[user_id] = prev(position);
            user_positions_[(*prev(position)).second] = position;
            position = prev(position);
        }
        
        if (position == prev(sorted_users_.end())) { //Log(N)
            return 1;       
        }
        position = next(position);
        const int page_count = user_page_counts_[user_id]; //Log(Q)
        int positionOnRange = distance(sorted_users_.begin(), user_positions_[user_id]) + 1;//Log(Q)
        user_positions_[user_id] = position;
        user_positions_[(*prev(position)).second] = prev(position);
        return 1 - ((user_count - positionOnRange) * 1.0 / (user_count - 1));
    }
 
private:
    map<int, int> user_page_counts_;
    multiset<pair<int, int>> sorted_users_;  
    map<int, multiset<pair<int, int>>::iterator> user_positions_;
};
Работает быстрее, все мои проверки на числа проходит, но оценочное задание в курсе не принимает его из-за неправильного ответа. Может у меня уже глаз замылился, и кто-нибудь сможет указать, где что-то идет не так? Переписывать код за меня не прошу, так вся задача потеряет смысл.
P.s:
Ф-ция main:
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
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  ReadingManager manager;
 
  int query_count;
  cin >> query_count;
 
  for (int query_id = 0; query_id < query_count; ++query_id) {
    string query_type;
    cin >> query_type;
    int user_id;
    cin >> user_id;
 
    if (query_type == "READ") {
      int page_count;
      cin >> page_count;
      manager.Read(user_id, page_count);
    } else if (query_type == "CHEER") {
      cout << setprecision(6) << manager.Cheer(user_id) << "\n";
    }
  }
 
  return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.09.2018, 00:35
Ответы с готовыми решениями:

Не могу разобратся с ошибкой в приведенном ниже коде!!!
//--------------------------------------------------------------------------- #include &lt;vcl.h&gt;...

Подскажите с ошибкой
Написал элементарный код на сложение, не идет что-то. Подскажите)

подскажите с ошибкой в программе
не могу понять, что не так ошибка в 66 строке :&quot; i dose not name a type&quot; #include &lt;stdio.h&gt;...

Помогите разобраться с ошибкой в коде удаления первого слов и первой буквы
не могу разобраться с ошибкой. Мне нужно удалить 1 слово и с каждого слова первую букву class...

5
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 1
25.09.2018, 13:28 2
ответа не знаю, но сразу спрошу, почему set?
Ведь делать map сам Бог велел.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
25.09.2018, 13:31  [ТС] 3
Kuzia domovenok, да с ним тоже делал, но не приняло, пришлось такие извращения вытворять
0
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 1
25.09.2018, 13:36 4
Vakarine, это неверный подход к решению проблем. Вы чего-то не поняли, получили ошибку и вместо её исправления делаете что-то ещё, исходя из неверного понимания. Например непонимания условия.

Сделай map
Лучше покажи полное условие.
0
0 / 0 / 0
Регистрация: 15.09.2018
Сообщений: 14
25.09.2018, 20:29  [ТС] 5
Kuzia domovenok, не, решение у меня работало нормально, но время работы было слишком большим. Условие смогу отправить только через ≈5 часов

Добавлено через 6 часов 26 минут
Kuzia domovenok,
Условие
Разработайте систему стимулирования чтения электронных книг. Для простоты будем считать, что книга всего одна, но её одновременно читают много людей. Необходимо следить за прогрессом чтения у всех пользователей и выводить мотивирующие уведомления. А именно, ваша программа должна обрабатывать следующие события:

READ user page — сохранить факт того, что пользователь под номером userдочитал книгу до страницы page. Если ранее такой пользователь не встречался, необходимо его добавить. Гарантируется, что в рамках одного пользователя номера страниц в соответствующих ему событиях возрастают.
CHEER user — сообщить пользователю user, какая доля существующих пользователей (не считая его самого) прочитала меньшую часть книги, чем он. Если этот пользователь на данный момент единственный, доля считается равной 1. Если для данного пользователя пока не было ни одного события READ, доля считается равной 0, а сам пользователь не учитывается при вычислении долей для других пользователей до тех пор, пока для него не случится событие READ.
Формат входных данных
В первой строке вводится количество запросов Q — натуральное число, не превосходящее 10^6. В следующих Q строках в соответствии с описанным выше форматом вводятся запросы. Гарантируется, что все вводимые числа целые и положительные, при этом номера пользователей не превосходят 10^5, а номера страниц не превосходят 1000.

Формат выходных данных
Для каждого запроса CHEER user выведите единственное вещественное число от 0 до 1 — долю пользователей, прочитавших меньше страниц, чем user. Формат вывода этого числа должен быть в точности таким же, как в опубликованном ниже медленном решении.

Ограничения
4 секунды на выполнение всех запросов. Все описанные в условии гарантии действительно справедливы для всех тестов, на которых будет запускаться ваша программа. Проверять корректность тестов не нужно.
0
Эксперт по математике/физике
3390 / 1913 / 571
Регистрация: 09.04.2015
Сообщений: 5,365
28.09.2018, 12:19 6
Эффективная организация данных обеспечивает до 90% быстродействия обработки.
Ваш подход по построению связных списков является очень существенным тормозом в быстродействии.
Мое мнение в классе для хранения данных надо создать два массива:
1. массив пользователей (допустим Users), тип данных unsigned int или unsigned short из 10^5 элементов (или на один больше если устранить пересчет номеров пользователя и допустить номера пользователей от 0 до 10^5 включительно).
В этом массиве храниться сколько страниц прочитал пользователь, определяемых по событию READ
Имя/номер пользователя нигде не хранится, а определяется номером элемента массива.
Исходное состояние инициализируется нулем в конструкторе, и обозначает что данный пользователь прочитал 0 страниц.
2. массив страниц книги (допустим Pages), тип данных unsigned long или long из 1000 элементов (по максимальному числу страниц в книге). В этом массиве хранится для каждой страницы в порядке очередности, сколько пользователей их уже прочитали.
Исходное состояние инициализируется нули в конструкторе, и обозначает что никто еще ничего не читал.

Сразу необходимо отметить одну особенность элемента Pages[0], из-за условия
Цитата Сообщение от Vakarine Посмотреть сообщение
Если для данного пользователя пока не было ни одного события READ, доля считается равной 0
то в этом элементе по сути будет хранится число пользователей, которые начали читать книгу.

Функции конструктора ясны по выше приведенным описаниям.

Обработка события READ сводится к увеличению на единицу числа прочитанных страниц
C
1
2
3
4
for(i=Users[user]; i<page; i++){
  Pages[i]++;
}
Users[user]=page;
Обработка события CHEER
C
1
2
3
4
5
6
7
8
9
10
11
double Rez;
if(Users[user]==0){
  Rez=0;
}
else{
  if( Pages[0]==1){
    Rez=1;
  }
else{
  Rez=double(Pages[0]-Pages[user])/(Pages[0]-1);
}
Формулы проверьте, а то писал по быстрому на коленке.

PS Часто по таким подходам в организации хранения данных (без динамических массивов) мне пытаются указать, что происходит избыточное занятие памяти, однако если сравнить например Вашу модель данных и сколько она занимает памяти при числе пользователей хотя бы половина от максимальной, то избыточности уже и незаметно. А по скорости обработки выигрыш должен быть большой.
0
28.09.2018, 12:19
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.09.2018, 12:19
Помогаю со студенческими работами здесь

Программа завершается с ошибкой, подскажите почему
Вводится координата шахматной доски где распологается конь, это координата при выводе обозначается...

Объясните пожалуйста одно место в коде
Смотрел я как-то видосик на ютубе и писал код. Потом долго разбирался, рисовал на листике и т.д....

Как отследить место ошибки в коде?
Проблема кратко: при записи в регистр RTC_CNT контроллер наглухо виснет. Отладчика нет,...

Как передать текст из textbox в определенное место в коде
Всем привет, помогите с кодом. Данный код загружает html код определенного сайта в lisbox. Мне...

Найти в коде место, где происходит обращение к function
Найти в коде место, где происходит обращение к function. program name8; uses crt; const n=5;...

Почему блок с fixed занимает место над блоком, который идёт в коде за ним?
Приветствую! Столкнулся с вопросом. Код ниже. Создан блок. По идее, блок, идущий в коде за ним,...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru