ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)
25 сообщений из 93, страница 3 из 4
  3  все
Шарики(задача по программированию)
    #39195593
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Anatoly Moskovsky,

И эти люди не советуют рекурсию )))))

Я даже не поверил сначала, что это работает.

Работает. Но эффективность неочь
...
Рейтинг: 0 / 0
18.03.2016, 17:04
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195594
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonAnatoly Moskovsky, давай тыщу шариков. Посмотрим как летает твой "Запорожец".
Разрешаю ))
Сложность - O(n)
в 0.2 сек уложится, не бойтесь ))
...
Рейтинг: 0 / 0
18.03.2016, 17:05
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195600
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SiemarglAnatoly Moskovsky,

И эти люди не советуют рекурсию )))))

Я даже не поверил сначала, что это работает.

Работает. Но эффективность неочь
Во-первых, это алгоритм, а не оптимизированная программа. Цель была показать что там происходит.
Во-вторых, не верю что неочь, давайте пруфы в сравнении с другими реализациями )))
...
Рейтинг: 0 / 0
18.03.2016, 17:10
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195602
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Нормально все, где вы тормоза увидели? Разве что state.push_back(v), несколько раз перевыделение памяти сделает, но это не большой тормоз на 500 элементах, и можно полечить выделив место заранее.
...
Рейтинг: 0 / 0
18.03.2016, 17:11
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195607
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Коллеги а вы тестили вариант с двумя локальными минимумами?

(У меня к сож нет компиллятора под рукой щас)
...
Рейтинг: 0 / 0
18.03.2016, 17:16
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195610
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
Dima T,

Сложность O(n), но на каждый элемент 2 вызова функции.
И отдельно возня с динамическим массивом (хотя его тут можно заменить обычным фиксированным стеком).

Для сравнения в рекурсии - один вызов функции.
Причем хотя я написал для каждого элемента - можно вызывать ее только один раз для пары если два соседних шарика отличаются.
Т.е работы примерно вчетверо меньше.
...
Рейтинг: 0 / 0
18.03.2016, 17:19
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195614
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonКоллеги а вы тестили вариант с двумя локальными минимумами?

(У меня к сож нет компиллятора под рукой щас)
По идее для кода выше без разницы сколько минимумов. Может чуть допилить надо (сходу не могу сказать), а сложность так и останется: два прохода.
...
Рейтинг: 0 / 0
18.03.2016, 17:21
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195616
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
У меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть
рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что
какой-то кейс недотестирован.
...
Рейтинг: 0 / 0
18.03.2016, 17:22
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195619
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Siemargl,

Ну вот пусть ТС и оптимизирует, там есть куда и все прямо в глаза бросается. Я еле удержался когда писал ))
...
Рейтинг: 0 / 0
18.03.2016, 17:24
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195622
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonУ меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть
рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что
какой-то кейс недотестирован.
Тут неявная рекурсия. state - это стек
...
Рейтинг: 0 / 0
18.03.2016, 17:24
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195623
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Anatoly MoskovskyТут неявная рекурсия
Но при этом это один из тех немногих случаев, когда алгоритм проще реализовать именно с неявной рекурсией.
...
Рейтинг: 0 / 0
18.03.2016, 17:26
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195625
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Anatoly MoskovskymaytonУ меня по перформансу нет вопросов. Просто я (теоретически) там ожидал увидеть
рекурсию но не увидел. И один проход.... Вобщем возникло подорзрение что
какой-то кейс недотестирован.
Тут неявная рекурсия. state - это стек
Я понял. А если использовать std::stack ?
...
Рейтинг: 0 / 0
18.03.2016, 17:27
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195631
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonЯ понял. А если использовать std::stack ?
А оно внутри все равно так же устроено ))
...
Рейтинг: 0 / 0
18.03.2016, 17:29
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195632
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А ну ОК. Остался пустяк. Растолковать автору.
...
Рейтинг: 0 / 0
18.03.2016, 17:31
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195633
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SiemarglТ.е работы примерно вчетверо меньше.
Не согласен. Рекурсия - однозначно вызов функции (что не быстро), а тут все функции оптимизатор заинлайнит.

vector это по сути обычный массив, который довыделяет память при необходимости, причем не по одному элементу, а сразу кратно текущему размеру (в 1,5 раза где-то читал). В принципе тут это решаемо на берегу:
Код: plaintext
1.
2.
std::vector<int> state;
state.reserve(1000);


и перевыделения памяти вообще не будет во время работы.
...
Рейтинг: 0 / 0
18.03.2016, 17:31
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195641
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Почему "вызов функции" == "не быстро" ?
...
Рейтинг: 0 / 0
18.03.2016, 17:43
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195649
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Leonid KudryavtsevПочему "вызов функции" == "не быстро" ?
Все регистры в стэк, код функции, восстановление обратно. Или современные компиляторы как-то по другому вызов делают?

Под "не быстро" имел ввиду по сравнению с инлайном, где не надо регистры сохранять/восстанавливать.
...
Рейтинг: 0 / 0
18.03.2016, 17:50
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195657
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
Dima TВсе регистры в стэк...
Нет такого AFAIK
...
Рейтинг: 0 / 0
18.03.2016, 18:04
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195665
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, есть такой трюк. Называется хвостовая рекурсия. Механию ее работы я до конца не
понимаю. Но гуры от Функциональщины говорят-де она с помощью этого "хвоста"
способна сворачивать рекурсии в обычные циклы.

Haskell, Scala теоретически ее поддерживают.
...
Рейтинг: 0 / 0
18.03.2016, 18:13
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195673
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
maytonНазывается хвостовая рекурсия. Механию ее работы я до конца не
понимаю.
Думаю к этой теме это не имеет отношения.

А механика проста. При хвостовой рекурсии, после рекурсивного вызова локальные переменные вызывающей функции уже не используются, поэтому сам вызов можно не проводить, а сымитировать прямо в текущем фрейме, путем установки новых значений аргументов и перехода в начало функции.
...
Рейтинг: 0 / 0
18.03.2016, 18:22
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195676
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Leonid KudryavtsevDima TВсе регистры в стэк...
Нет такого AFAIK
Не силен в асме, кодом доказывать не буду. Пример рефакторинга собственного кода. Схематично.
Было
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
int f(value) {
  static vector<> cache;
  if(нет в кэше) {
     дозаполнение кэша с рекурсивным вызовом f()
  }
   return из кэша;
}


переписал в класс
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
class {
  static vector<> cache;

  void cache_fill() {
     дозаполнение кэша с вызовом f()
  }

  int f(value) {
   return из кэша;
  }
}


Именно так, без каких-либо доп оптимизаций. Просто скопипастил куски кода. Ну и в клиентском коде создание объекта добавил. Стало работать на 15-20% быстрее, т.к. компилятор смог инлайнить f()
...
Рейтинг: 0 / 0
18.03.2016, 18:27
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195679
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
поторопился, такой класс
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
class {
  static vector<> cache;

  void cache_fill() {
     дозаполнение кэша с вызовом f()
  }

  int f(value) {
   if(нет в кэше) cache_fill();
   return из кэша;
  }
}
...
Рейтинг: 0 / 0
18.03.2016, 18:29
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195691
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Опять поторопился :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
class {
  static vector<> cache;

  void cache_fill() {
     дозаполнение кэша с рекурсивным вызовом cache_fill()
  }

  int f(value) {
   if(нет в кэше) cache_fill();
   return из кэша;
  }
}



Вобщем не знаю точно за счет чего, но как написал стало работать быстрее на 15-20%. Я считаю из-за инлайна.
...
Рейтинг: 0 / 0
18.03.2016, 18:39
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195706
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Вообще-то в данном случае под виндовсом главный тормоз будет в
Код: plaintext
1.
while (is >> v) {


Недавно тестили. 18908145
...
Рейтинг: 0 / 0
18.03.2016, 18:50
| Ответить | Цитировать | Написать  
Шарики(задача по программированию)
    #39195750
Siemargl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Siemargl
Участник
SiemarglDima T,

Сложность O(n), но на каждый элемент 2 вызова функции.
И отдельно возня с динамическим массивом (хотя его тут можно заменить обычным фиксированным стеком).

Для сравнения в рекурсии - один вызов функции.
Причем хотя я написал для каждого элемента - можно вызывать ее только один раз для пары если два соседних шарика отличаются.
Т.е работы примерно вчетверо меньше.
Приврал. Проверил. Вдвое.
На данных 10 3 3 2 2 1 1 1 2 2 3 3
у АМ 13 вызовов функций (не включая работу с вектором)
у меня - 6

Чуть позже выложу ассемблер
...
Рейтинг: 0 / 0
18.03.2016, 19:28
| Ответить | Цитировать | Написать  
25 сообщений из 93, страница 3 из 4
  3  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]