Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 29.10.2018
Сообщений: 35
1

Оптимизация log

16.03.2019, 15:12. Показов 586. Ответов 4
Метки нет (Все метки)

Доброго времени суток!!
Имеется код функции:
C++ (Qt)
1
2
3
4
5
6
7
int q(int i, int j) {
  int k = (int)(log(1.0*j - i + 1) / log(2.0));
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}
Помогите оптимизировать без log
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.03.2019, 15:12
Ответы с готовыми решениями:

оптимизация по скорости sin cos log e
Нужна помощь по курсачу. Задание состоит в следующем: написать sin cos log e работающие в 2 раза...

По заданым значениям х и у найти значение величины log x y (log с основанием х)
Подскажите,где ошибка в if-else.Потому-что,когда вводить вместо х или у 0,почему-то еррор не...

по заданым значениям х и у найти значение величины log x y (log с основанием х )
я в принципе понимаю как написать эту программу,но,хоть убейте,в хелпе visual studio 2008 не могу...

функция log
Ув.Форумчане, помогите мне необходимо написать эту формула в 3 функция получается. 1) стандартная...

4
Модератор
Эксперт С++
11128 / 9166 / 5506
Регистрация: 18.12.2011
Сообщений: 24,479
16.03.2019, 16:01 2
у меня получается
y=j-i+1
k=ln(y)/ln(2)
k=log2(y)
2k=y=j-i+1
Т.е. к имеет всего один единичный бит в представлении (остальные нули).
Т.о. для нахождения k надо вычислить j-i+1 и найти позицию старшего единичного бита.

Как это сделать сходу не соображу
если циклом, то так
C++
1
2
3
4
k=1;
int t=j+i-1;
while(t>>=1)
   k<<=1;
В любом случае - это гораздо эффективнее, чем считать 2 логарифма.
0
0 / 0 / 0
Регистрация: 29.10.2018
Сообщений: 35
16.03.2019, 20:01  [ТС] 3
zss, вот так?
C++ (Qt)
1
2
3
4
5
6
7
8
9
int q(int i, int j) {
    int k = 1;
    int t = j + i - 1;
    while(t >>= 1) k <<= 1;
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}
0
Модератор
Эксперт С++
11128 / 9166 / 5506
Регистрация: 18.12.2011
Сообщений: 24,479
16.03.2019, 20:35 4
Ну, наверное.
Вы, ведь, задачу не поставили.
Проверить не могу.
0
0 / 0 / 0
Регистрация: 29.10.2018
Сообщений: 35
17.03.2019, 14:03  [ТС] 5
zss, вот задача:
Дан массив из n чисел. Требуется написать программу, которая будет отвечать на запросы следующего вида: найти минимум на отрезке между u и v включительно.

Формат входных данных
В первой строке входного файла даны три натуральных числа n, m (1≤n≤105, 1≤m≤107) и a1 (0≤a1<16714589) — количество элементов в массиве, количество запросов и первый элемент массива соответственно. Вторая строка содержит два натуральных числа u1 и v1 (1≤u1,v1≤n) — первый запрос.
Элементы a2,a3,…,an задаются следующей формулой:

ai+1=(23⋅ai+21563)mod16714589.
Например, при n=10, a1=12345 получается следующий массив: a = (12345, 305498, 7048017, 11694653, 1565158, 2591019, 9471233, 570265, 13137658, 1325095).

Запросы генерируются следующим образом:

ui+1=((17⋅ui+751+ansi+2i)modn)+1,
vi+1=((13⋅vi+593+ansi+5i)modn)+1,

где ansi — ответ на запрос номер i.

Обратите внимание, что ui может быть больше, чем vi.

Формат выходных данных
В выходной файл выведите um, vm и ansm (последний запрос и ответ на него).

C++ (Qt)
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
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#define MAX 100001
#define LOGMAX 17
 
using namespace std;
int a[MAX];
int mas[MAX][LOGMAX];
 
void check(int &u, int &v) {
  int temp;
  if (u > v) temp = u, u = v, v = temp;
}
 
void RMQ_nlogn(int n) {
  int i, j;
  for (i = 1; i <= n; i++) mas[i][0] = i;
  for (j = 1; (1 << j) <= n; j++)
    for (i = 1; i + (1 << (j - 1)) <= n; i++)
      if (a[mas[i][j - 1]] < a[mas[i + (1 << (j - 1))][j - 1]])
         mas[i][j] = mas[i][j - 1];
      else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];
}
 
int q(int i, int j) {
  int k = (int)(log(1.0*j - i + 1) / log(2.0));
  int res = mas[i][k];
  if (a[mas[j - (1<<k) + 1][k]] < a[res])
      res = mas[j - (1<<k) + 1][k];
  return res;
}
 
int main()  {
    int n, m, u, v, u1, v1, ans;
    scanf("%d %d",&n,&m);
    scanf("%d %d %d",&a[1],&u,&v);
    for(int i = 2; i <= n; i++)
      a[i] = (23 * a[i-1] + 21563) % 16714589;
    RMQ_nlogn(n);
    for(int i = 1; i <= m; i++) {
        u1 = u; v1 = v; check(u1,v1);
        ans = a[q(u1,v1)];
          if (i < m) {
              u = ((17*u + 751 + ans + 2*i) % n) + 1;
                 v = ((13*v + 593 + ans + 5*i) % n) + 1;
               }
             }
 
    printf("%d %d %d\n",u,v,ans);
    return 0;
}
Вот фулл код, но у него TL из за log
Прив вашей оптимизации не работает

Ввод для проверки:
10 8 12345
3 9
Ответ:
5 3 1565158
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.03.2019, 14:03

Console log
Доброго времени суток всем. Подскажите, а как сделать перехват из консольной программы что бы всё...

Перегрузка Log(2)
u1 = sin(3.14*2/12)/(log(2)); Пишет, что перегруженная функция. Что сделать?

Функция log
Здравствуйте! Такой вопрос. Я использовала функцию log для нахождения логарифма по основанию 2 от...

Ошибка с Log(10)
Ругается &quot;error C2668: log: неоднозначный вызов перегруженной функции&quot; в этой строчке if (...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.