С Новым годом! Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
57 / 43 / 12
Регистрация: 27.10.2018
Сообщений: 454

Оптимизировать алгоритм

10.07.2019, 04:11. Показов 2713. Ответов 37
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Не углубляясь в детали , суть задачи - добавлять в конец вектора два элемента с значением первого и удалять первый элемент из вектора .
Я реализировал так :
C++
1
2
3
4
5
6
#include <string>
#include <vector>
std::string who_is_next(std::vector<std::string> &names, long long r) {
for (int i = r;; --i) {
if (i == 1)  { return names[0]; }
else{ names.vector::push_back(names[0]); names.vector::push_back(names[0]);names.erase(names.begin());}}}
Данный код проходит 10063 итераций цикла в тесте за 4875-6285 мс (почему разное время - незнаю )при таком инпуте :
C++
1
2
3
4
std::vector<std::string> names = {"Sheldon", "Leonard", "Penny", "Rajesh", "Howard"};  
        Assert::That(who_is_next(names, 1), Equals("Sheldon"));
        Assert::That(who_is_next(names, 52), Equals("Penny"));
        Assert::That(who_is_next(names, 10010), Equals("Howard"));
Ограничение на прохождение теста - 12000 мс.
Как уложиться в это время при таких значениях на входе не представляю :
C++
1
2
3
4
string[] names = new string[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
Line.WhoIsNext(names, 1) == "Sheldon"
Line.WhoIsNext(names, 52) == "Penny"
Line.WhoIsNext(names, 7230702951) == "Leonard"
Помогите пожалуста оптимизировать данное решение \подсказать иную реализацию,заранее спасибо.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.07.2019, 04:11
Ответы с готовыми решениями:

Оптимизировать алгоритм
Приятель подкинул задачку: Получить новую матрицу В, элемент b которой равен наименьшему из элементов a исходной матрицы, где k меняется...

Помогите оптимизировать алгоритм
Помогите, пожалуйста, оптимизировать алгоритм. Задача следующая. Есть 5 форм, например, с 10 текстбоксами в каждой форме. Необходимо...

Как оптимизировать этот алгоритм до O(n)?
У меня есть список m и число n. Нужно найти два элемента из этого списка, сумма которых будет ближе всего к n. Как это можно сделать за...

37
 Аватар для LegionK
393 / 263 / 193
Регистрация: 02.05.2017
Сообщений: 1,003
10.07.2019, 05:53
Цитата Сообщение от plzvtl Посмотреть сообщение
оптимизировать данное решение
точно нельзя на deque заменить твой вектор?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.07.2019, 08:58
Цитата Сообщение от plzvtl Посмотреть сообщение
Не углубляясь в детали , суть задачи - добавлять в конец вектора два элемента с значением первого и удалять первый элемент из вектора .
Может всё-таки углубишься в детали. А то звучит слегка бредово.

Цитата Сообщение от plzvtl Посмотреть сообщение
Помогите пожалуста оптимизировать данное решение \подсказать иную реализацию,заранее спасибо.
Основная оптимизация здесь, как было сказано выше - использовать std::deque вместо std::vector
Но, если уж приспичило именно вектор - сначала лучше удалять элемент, а потом добавлять
C++
1
2
3
4
auto item = std::move(names[0]);
names.erase(names.begin());
names.push_back(item);
names.push_back(std::move(item));
0
 Аватар для Krokodil9798
330 / 145 / 56
Регистрация: 17.10.2015
Сообщений: 580
10.07.2019, 09:41
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
сначала лучше удалять элемент, а потом добавлять
oleg-m1973, а почему?
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.07.2019, 09:43
Цитата Сообщение от Krokodil9798 Посмотреть сообщение
oleg-m1973, а почему?
Потому что удаление из начала вектора приводит к перемещению всех остальных элементов. Лучше перемещать на два элемента меньше.
0
 Аватар для Krokodil9798
330 / 145 / 56
Регистрация: 17.10.2015
Сообщений: 580
10.07.2019, 09:46
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Лучше перемещать на два элемента меньше
oleg-m1973, На один. Но вообще да, согласен с Вами. Хотя, в случае с обычными числами, такие детали несущественны.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.07.2019, 09:57
Цитата Сообщение от Krokodil9798 Посмотреть сообщение
oleg-m1973, На один. Но вообще да, согласен с Вами. Хотя, в случае с обычными числами, такие детали несущественны.
Ну да, на один.
Там std::string.
0
 Аватар для Krokodil9798
330 / 145 / 56
Регистрация: 17.10.2015
Сообщений: 580
10.07.2019, 10:01
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Там std::string.
oleg-m1973, Не обратил внимание, прошу прощения Тогда Ваше замечание относительно порядка операций действительно очень важно.
plzvtl, я бы ещё использовал резервирование памяти (раз Вы используете вектор).
0
57 / 43 / 12
Регистрация: 27.10.2018
Сообщений: 454
10.07.2019, 15:30  [ТС]
Цитата Сообщение от LegionK Посмотреть сообщение
точно нельзя на deque заменить твой вектор?
Да , можно заменить на deque, я об этом не подумал.Хотя , я на входе всегда имею вектор , надо будет его еще переписывать в deque, опять же "хотя" это может дать свой прирост из-за того что итерации будут быстрее.
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Может всё-таки углубишься в детали. А то звучит слегка бредово.
Вот как звучит условие
"Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on."
никаких технических деталей нет, так что по моему оно мало полезно.
0
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
10.07.2019, 15:38
Это ж как от колы наклюкаться, что двоиться начинают. И почему на входе всегда вектор, а не сразу deque ?
0
57 / 43 / 12
Регистрация: 27.10.2018
Сообщений: 454
10.07.2019, 15:40  [ТС]
Цитата Сообщение от Manowar Посмотреть сообщение
И почему на входе всегда вектор, а не сразу deque ?
Эти 2 вызова - это фиксированные тесты , их условия видны тем кто проходит , условий , других тестов не видно , но я сомневаюсь что там не вектор.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.07.2019, 15:45
Цитата Сообщение от plzvtl Посмотреть сообщение
Эти 2 вызова - это фиксированные тесты , их условия видны тем кто проходит , условий , других тестов не видно , но я сомневаюсь что там не вектор.
Так что решил - оставить vector или использовать deque?
0
57 / 43 / 12
Регистрация: 27.10.2018
Сообщений: 454
10.07.2019, 15:48  [ТС]
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
Так что решил - оставить vector или использовать deque?
Ничто не мешает мне реализировать и так и так и просто посмотреть где результат будет лучше.
Нет такого , что я сильно ограничен выбором.
0
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
10.07.2019, 15:54
Цитата Сообщение от plzvtl Посмотреть сообщение
Ничто не мешает мне реализировать и так и так и просто посмотреть где результат будет лучше.
Нет такого , что я сильно ограничен выбором.
Для вектора предлагаю сделать так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::string who_is_next(std::vector<std::string> &names, long long r) 
{
    names.reserve(names.size() + r * 2);
    
    size_t i = 0;
    for (; i < r; ++i)
    {
        auto item = std::move(names[i]);
        names.emplace_back(item);
        names.emplace_back(std::move(item));
    }
 
    names.erase(names.begin(), names.begin() + i);
    return names[0];
}
0
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
10.07.2019, 15:59
А когда они там у аппарата бухать эту "колу" перестанут, есть какое нить условие, какой критерий остановки программы?
1
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
10.07.2019, 16:14
plzvtl, проверяется только возвращаемое значение функции? Или содержимое вектора тоже?
Просто вижу, что при очередном вызове функции используется вектор, измененный при предыдущем вызове. Так задумано?
0
57 / 43 / 12
Регистрация: 27.10.2018
Сообщений: 454
10.07.2019, 16:32  [ТС]
Цитата Сообщение от 0x10 Посмотреть сообщение
plzvtl, проверяется только возвращаемое значение функции? Или содержимое вектора тоже?
В задании сказано "кто купит колу n-ый раз ", поэтому я считаю что проверяется только возвращаемое значение.
Цитата Сообщение от Manowar Посмотреть сообщение
А когда они там у аппарата бухать эту "колу" перестанут, есть какое нить условие, какой критерий остановки программы?
Как я понимаю , нету.

Добавлено через 15 минут
Цитата Сообщение от 0x10 Посмотреть сообщение
Так задумано?
Да, так должно быть.
0
1719 / 568 / 187
Регистрация: 12.03.2016
Сообщений: 2,169
10.07.2019, 16:33
Цитата Сообщение от plzvtl Посмотреть сообщение
Как я понимаю , нету
как нету ?
Цитата Сообщение от plzvtl Посмотреть сообщение
кто купит колу n-ый раз
лучше над алгоритмом подумать.
0
3258 / 2060 / 351
Регистрация: 24.11.2012
Сообщений: 4,909
10.07.2019, 16:36
Цитата Сообщение от plzvtl Посмотреть сообщение
В задании сказано "кто купит колу n-ый раз ", поэтому я считаю что проверяется только возвращаемое значение.
Цитата Сообщение от plzvtl Посмотреть сообщение
Да, так должно быть.
Так первое или второе?
Спрошу конкретнее: у вас функция who_is_next принимает вектор по ссылке и модифицирует его. Это обязательное условие?
0
57 / 43 / 12
Регистрация: 27.10.2018
Сообщений: 454
10.07.2019, 16:41  [ТС]
Цитата Сообщение от Manowar Посмотреть сообщение
как нету ?
Не понимаю вопроса , количество итераций это " r "как указано в цикле , других "особых" вариантов для завершения цикла нету.

Добавлено через 3 минуты
Цитата Сообщение от 0x10 Посмотреть сообщение
Спрошу конкретнее: у вас функция who_is_next принимает вектор по ссылке и модифицирует его. Это обязательное условие?
Если я буду принимать по значению ,например , все будет так же по моему , точных указаний как принимать параметры нету.
Можно по ссылке , можно по значению .
Сейчас меня начали брать сомнения должен ли измененный вектор попадать например в
C++
1
Assert::That(who_is_next(names, 10010), Equals("Howard"));
вместо начального.Но поскольку данный тест проходит , я считаю что так надо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
10.07.2019, 16:41
Помогаю со студенческими работами здесь

Преобразование строки в байты: оптимизировать алгоритм
Часть программы .... которая строку(довольно большую) содержащую 0 и 1 преобразует в байты( читает по 8 символов получаем байт удаляем...

Оптимизировать алгоритм проверки ударения слов
Здравствуйте, уважаемые участники форума. На образовательном сайте решал задание, система решение приняла. Так как я неопытный в...

оптимизировать алгоритм поиска вхождений строки в текстовый файл (1 Мб)
Здравствуйте. По заданию требовалось составить программу для подсчета вхождений разных сочетаний букв с алфавита от 1 буквы до 4 в...

Исправить алгоритм расчета ЕИ и максимально оптимизировать с целью повышения быстродействия
Всем доброго времени суток. Помогите выполнить тестовое задание. Условия: Запрос от Министерства энергетики Нской области: ...

Оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления
Всего один вопрос. Как оптимизировать алгоритм, чтобы уменьшить количество операций для проверок деления? #include &lt;iostream&gt; ...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru