ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / Как правильно реализовать рекурсивную функцию в Postgres ?
22 сообщений из 22, страница 1 из 1
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39276593
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
Функция такая:
Код: plsql
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.
CREATE OR REPLACE FUNCTION peak1d
(A _int8, i int4, j int4) 
RETURNS int8
AS 
$$
DECLARE
  m      int4;
  t_var0 text;
  t_var1 text;
  t_var2 text;
  t_var3 text;
BEGIN
  m := floor((i+j)/2::numeric);
  IF A[m-1] <= A[m] AND A[m] >= A[m+1] THEN
    RAISE INFO '1. A[m] = "%"', A[m];
    RETURN m;
  ELSIF A[m - 1] > A[m] THEN
    m := ml_peak1d(A, i, m - 1);
    RETURN m;
  ELSIF A[m] < A[m + 1] THEN
    m := ml_peak1d(A, m + 1, j);
    RETURN m;
  ELSE
    RETURN 0::int4;
  END IF;
END 
$$
LANGUAGE plpgsql 
SECURITY DEFINER;

Функция должна рекурсивно реализовать алгоритм Peak Finding
Вызов такой:
Код: plsql
1.
2.
3.
SELECT public.peak1d 
(ARRAY[1,2,6,5,3,7,4], 
1::int4, 7::int4)

где 1-й параметр - массив чисел, 2-й параметер - нижний индекс массива, 3-й параметер - верхний индекс этого массива

Результат выполнения:
Код: plaintext
peak1d = 3
автор[SQL]SELECT public.peak1d
(ARRAY[1,2,6,5,3,7,4],
1::int4, 7::int4)

INFO: 1. A[m] = "6"
CONTEXT: PL/pgSQL function ml_peak1d(bigint[],integer,integer) line 19 at assignment
PL/pgSQL function peak1d(bigint[],integer,integer) line 14 at assignment

Time: 0.004s

Affected rows: 1
Т.е. рекурсия не получилась . Ожидаемые пики д.б. два:
- 3-й элемент массива (значение "6");
- 6-й элемент массива (значение "7").

Как это алгоритм реализовать рекурсивно в Pl/pgsql ?
...
Рейтинг: 0 / 0
19.07.2016, 18:56
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39276618
p2.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
p2.
Участник
Бока,

рекурсия-то тут зачем, если обычный проход по порядку. Да и функцию ради этого городить стоит ли, если данные наверняка из таблиц.
Определись только, могут ли являться пиками граничные элементы.
...
Рейтинг: 0 / 0
19.07.2016, 19:24
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39276629
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
p2.,

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

Алгоритма реализации Peak Finding, который вроде бы должен быть быстрым, я взял отсюда https://courses.csail.mit.edu/6.006/spring11/lectures/lec02.pdf , страница 10/23
...
Рейтинг: 0 / 0
19.07.2016, 19:44
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39276652
p2.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
p2.
Участник
Бока,

Поиск экстремум А проходят на первом курсе и "быстрым" считается золотое сечение, а не половинковое. Только вот подходит оно для действительных функций, да еще и непрерывных, дифференцируемых, выпуклых и прочая лабудень.
Если уберешь выход из рекурсии на первом найденном, то получишь усугубленный полный перебор.
Какова большизна данных у вас, если передаешь массив... всяк кулик хвалит свои сантиметры.
...
Рейтинг: 0 / 0
19.07.2016, 20:21
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39277095
bochkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
bochkov
Участник
А разве сплошным запросом нельзя вычислить пики
с помощью оконных функций?
...
Рейтинг: 0 / 0
20.07.2016, 14:00
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39277108
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
p2.Бока,

Поиск экстремум А проходят на первом курсе и "быстрым" считается золотое сечение, а не половинковое. Только вот подходит оно для действительных функций, да еще и непрерывных, дифференцируемых, выпуклых и прочая лабудень.
Если уберешь выход из рекурсии на первом найденном, то получишь усугубленный полный перебор.
Какова большизна данных у вас, если передаешь массив... всяк кулик хвалит свои сантиметры.
...
Рейтинг: 0 / 0
20.07.2016, 14:15
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278083
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
bochkov,

Я в итоге так и сделал, но алгоритм, про который я задал вопрос, который вроде бы должен быстрее работать (его наш алгоритмист предложил) я не смог имплементировать внутрь конструкции WITH RECURSIVE c использованиема внутри оконных функций lag и lead.
Попробоваал сделать функцию, вызывающую саму себя, но не получилось (как показано в корневом посте).
...
Рейтинг: 0 / 0
21.07.2016, 16:54
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278117
Фотография vyegorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
vyegorov
Участник
Бока,

Ваша функция получает просто int8 как первый аргумент, а не массив. Возвращает тоже int8, как она может вернуть несколько пиков?
В теле вы вызываете функцию `ml_peak1d`, она не приведена, но как есть -- это не рекурсивная функция.
...
Рейтинг: 0 / 0
21.07.2016, 17:34
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278118
p2.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
p2.
Участник
БокаОжидаемые пики д.б. дваБокано не получилось (как показано в корневом посте).ты документ по приведенной тобой ссылке прочитал? или, если не умеешь читать, головой подумать пробовал, сколько оно находит и за счет чего и в каких случаях это становится "быстрее".
Если же тебе нужны все пики, так или иначе, получать все данные в упорядоченном виде. Наложить lag/lead в данном случае, считай, ничего не стоит. Ты же собрался все эти данные засовывать в массив, массив в дом, который построил джек , в нем обращаться к элементам массива (пг - тот еще тормоз), а потом результат высуёвывать обратно.
...
Рейтинг: 0 / 0
21.07.2016, 17:34
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278132
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
vyegorov,

Я это поправил, но не помогло. Сейчас вот так:
Код: plsql
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.
CREATE OR REPLACE FUNCTION peak1d
(A _int8, i int4, j int4) 
RETURNS _int8
AS 
$$
DECLARE
  m      int4;
  ar_m   _int4;
  t_var0 text;
  t_var1 text;
  t_var2 text;
  t_var3 text;
BEGIN
  m := floor((i+j)/2::numeric);
  IF A[m-1] <= A[m] AND A[m] >= A[m+1] THEN
    ar_m := array_append(ar_m, m);
    RAISE INFO '1. ar_m = "%"', ar_m ;
--    RETURN ar_m;
  ELSIF A[m - 1] > A[m] THEN
     SELECT INTO ar_m peak1d(A, i, m - 1);
--    RETURN ar_m;
  ELSIF A[m] < A[m + 1] THEN
    SELECT INTO ar_m peak1d(A, m + 1, j);
--    RETURN ar_m;
  ELSE
    RETURN 0::_int4;
  END IF;
  RETURN ar_m;
END 
$$
LANGUAGE plpgsql 
SECURITY DEFINER;


Вызов:
Код: plsql
1.
2.
3.
SELECT public.peak1d 
(ARRAY[1,2,6,5,3,7,4], 
1::int4, 7::int4)


Результат:
peak1d
{3}
Messages:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
[SQL]SELECT public.peak1d 
(ARRAY[1,2,6,5,3,7,4], 
1::int4, 7::int4) 
-- ==================

INFO:  1. ar_m = "{3}"
CONTEXT:  SQL statement "SELECT           peak1d(A, m + 1, j)"
PL/pgSQL function peak1d(bigint[],integer,integer) line 19 at SQL statement
SQL statement "SELECT           peak1d(A, i, m - 1)"
PL/pgSQL function peak1d(bigint[],integer,integer) line 16 at SQL statement

Time: 0.004s

Affected rows: 1
...
Рейтинг: 0 / 0
21.07.2016, 17:41
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278157
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
p2.БокаОжидаемые пики д.б. дваБокано не получилось (как показано в корневом посте).ты документ по приведенной тобой ссылке прочитал? или, если не умеешь читать, головой подумать пробовал, сколько оно находит и за счет чего и в каких случаях это становится "быстрее".
Если же тебе нужны все пики, так или иначе, получать все данные в упорядоченном виде. Наложить lag/lead в данном случае, считай, ничего не стоит. Ты же собрался все эти данные засовывать в массив, массив в дом, который построил джек , в нем обращаться к элементам массива (пг - тот еще тормоз), а потом результат высуёвывать обратно.
lag/lead c CASE внутри запроса внутри конструкции WITH RECURSIVE я слелал, и это работает достаточно быстро.
Но поскольку мы не знаем, какие алгоритмы за этим стоят, то наш алгоритмист предполагает, что предлоденный им алгоритм будет работать быстрее. Хотелось бы прооверить.
По моему опыту, прочитать нужные даннык массив, а потом рабюотать с массивом, получается , зачастую быстрее , чем читать все записи с диска и для каждой записи делать lag, lead и CASE со срвынением lag и lead с текущим значением поля.
...
Рейтинг: 0 / 0
21.07.2016, 17:52
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278162
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
p2.БокаОжидаемые пики д.б. дватак это просто пример. Для этого примера ожидаемых пиков 2.
...
Рейтинг: 0 / 0
21.07.2016, 17:57
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278164
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
p2.ты документ по приведенной тобой ссылке прочитал? или, если не умеешь читать, головой подумать пробовал, сколько оно находит и за счет чего и в каких случаях это становится "быстрее".Это документа читал наш алгоритмест, который наши данные очень хорошор знает, и он и предположил, что этот алгоритма для нашего случая подходит. Я полагаюсь на его мнение.
Я уже реализовал с помощью WITH RECURSIVE, lag, lead и CASE, но хотелось бы и предложеннай алгоритмистом алгоритм реализовать, чтобы сравнить на наших данных.
...
Рейтинг: 0 / 0
21.07.2016, 18:02
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278165
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
Прошу прощения за описки, спешил, не проверил
...
Рейтинг: 0 / 0
21.07.2016, 18:03
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278412
Ролг Хупин
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ролг Хупин
Участник
Бокаp2.ты документ по приведенной тобой ссылке прочитал? или, если не умеешь читать, головой подумать пробовал, сколько оно находит и за счет чего и в каких случаях это становится "быстрее".Это документа читал наш алгоритмест, который наши данные очень хорошор знает, и он и предположил, что этот алгоритма для нашего случая подходит. Я полагаюсь на его мнение.
Я уже реализовал с помощью WITH RECURSIVE, lag, lead и CASE, но хотелось бы и предложеннай алгоритмистом алгоритм реализовать, чтобы сравнить на наших данных.

Похоже в этой схеме или "алгоритмест", или ТС лишний, было бы проще без кого-то
...
Рейтинг: 0 / 0
22.07.2016, 10:38
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39278631
qwwq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
qwwq
Участник
Ролг ХупинБокапропущено...
Это документа читал наш алгоритмест, который наши данные очень хорошор знает, и он и предположил, что этот алгоритма для нашего случая подходит. Я полагаюсь на его мнение.
Я уже реализовал с помощью WITH RECURSIVE, lag, lead и CASE, но хотелось бы и предложеннай алгоритмистом алгоритм реализовать, чтобы сравнить на наших данных.

Похоже в этой схеме или "алгоритмест", или ТС лишний, было бы проще без кого-то

а вот скажем, могабыть у вас такой ряд
0,1,0,1,0,1,....,0,1
или такой:
-1,1,-2,2,-3,3...-n,n

и скока в нем "пиков" надо вывести ?
и как оно запишется в виде О(f(n)) ?

т.е. повторяю вопрос

авторсколько оно находит и за счет чего и в каких случаях это становится "быстрее".

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


или у вас какая--то другая задача ?
...
Рейтинг: 0 / 0
22.07.2016, 13:34
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39279252
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
qwwqРолг Хупинпропущено...


Похоже в этой схеме или "алгоритмест", или ТС лишний, было бы проще без кого-то

а вот скажем, могабыть у вас такой ряд
0,1,0,1,0,1,....,0,1
или такой:
-1,1,-2,2,-3,3...-n,n

и скока в нем "пиков" надо вывести ?
и как оно запишется в виде О(f(n)) ?

т.е. повторяю вопрос

авторсколько оно находит и за счет чего и в каких случаях это становится "быстрее".

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


или у вас какая--то другая задача ?У меня лично задача простая:
- есть реализовынный алгоритм, который на оснорвании некоторых данных , храняшихся в таблицах порядка десятков миллионов записей , выводит данные для построения графиков статистического анализа;
- в алгоритм входят болки, реализующие binning, smoothing and peak finding;
- я пытаюсь найти способы уменьшения времени выполнения по каждому из этих блоков;
- в, частности , по блоку peak finding может быть поможет реализация метода "половинного деления" и "золотого сечения", но у меня не получилось реализовать, например, метод половинного деления на Pl/pgsql. Пока я деклаю WITH RECURSIVE запрос с CASE сравнением текущего значения поля с значениями по lag и lead;
- может быть метод "половинного деления" или "золотого сечения" можно реализовать в Pl/pythonu ?
...
Рейтинг: 0 / 0
24.07.2016, 11:35
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39279255
bochkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
bochkov
Участник
Когда много данных,
для быстрого представления
можно разбить весь массив на части
и получившуюся сетку заполнить
с помощью агрегатных функций
например надо за год диаграмму
вылова рыбы нарисовать
разбиваешь весь год на периоды по несколько
дней и сумму объёмов за период наносишь
на диаграмму
вот так можно индексы использовать
и быстро выводить
...
Рейтинг: 0 / 0
24.07.2016, 12:13
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39279306
qwwq
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
qwwq
Участник
bochkov,

это всё -- если агрегаты аддитивны


но мы отвлеклись -- ТС абсолютно не всасывает задачу
задача -- понять что ему надо, без словесов, которые ему пока не ясны

-- его спрашивают, может ли задача состоять в том, чтобы вывести аж N/k пиков
при заданном заранее k (в частности k=2). т.е. вывод ~O(N) .

и как он решил сделать это быстрее (т.е. за ~O(ln(N)) , чем сам объём вывода

а он -- "смусинг, ля , чятинг, ля, чмокинг, ля"
тьфу
и работодатель его -- туда же
...
Рейтинг: 0 / 0
24.07.2016, 17:29
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39281770
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
qwwq,

1. Абсолютно все пики надо вывести

2. "k" я не понял что такое. Согласно обьяснениям нашего алгоритмиста, нужно перебрать каждые три рядом стоящие значения и из них выбрать то, которое выше , чем то что слева и то, что справа одновременно. Те тройки, в которых это условие не выполняется, не имеют пика.

3. Обычная рекурсия, которую предоставляет Pgsql (WITH RECURSIVE и внутри сраввнение CASE значения из текущей записи со значениями, получаемыми с помощью windows functions "lag" и "lead"), это делает перебирая все записи внутри конструкции WITH RECURSIVE.

4. Алгоритм "половинное деление", описанный по ссылке выше с помощью условного языка, похожего на Python, не перебирает все значения подряд из массива (как утверждает наш алгоритмист).

5. Взять все значения для нахождения пиков в массив занимает времени существенно меньше, чем найти пики из записей в таблице с помощью метода "WITH RECURSIIVE -> CASE -> lag -> lead". Я попытался реализовать рекурсию как показано для метода "половинного сечения", но у меня не получилось и я задал вопрос.
...
Рейтинг: 0 / 0
28.07.2016, 12:03
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39281774
Бока
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Бока
Участник
Напоминаяю, как не получилось:
Код: plsql
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.
CREATE OR REPLACE FUNCTION peak1d
(A _int8, i int4, j int4) 
RETURNS _int8
AS 
$$
DECLARE
  m      int4;
  ar_m   _int4;
  t_var0 text;
  t_var1 text;
  t_var2 text;
  t_var3 text;
BEGIN
  m := floor((i+j)/2::numeric);
  IF A[m-1] <= A[m] AND A[m] >= A[m+1] THEN
    ar_m := array_append(ar_m, m);
    RAISE INFO '1. ar_m = "%"', ar_m ;
--    RETURN ar_m;
  ELSIF A[m - 1] > A[m] THEN
     SELECT INTO ar_m peak1d(A, i, m - 1);
--    RETURN ar_m;
  ELSIF A[m] < A[m + 1] THEN
    SELECT INTO ar_m peak1d(A, m + 1, j);
--    RETURN ar_m;
  ELSE
    RETURN 0::_int4;
  END IF;
  RETURN ar_m;
END 
$$
LANGUAGE plpgsql 
SECURITY DEFINER;


Вызов:
Код: plsql
1.
2.
3.
SELECT public.peak1d 
(ARRAY[1,2,6,5,3,7,4], 
1::int4, 7::int4)


Результат:
Код: plaintext
1.
2.
peak1d
{3}
Messages:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
[SQL]SELECT public.peak1d 
(ARRAY[1,2,6,5,3,7,4], 
1::int4, 7::int4) 
-- ==================

INFO:  1. ar_m = "{3}"
CONTEXT:  SQL statement "SELECT           peak1d(A, m + 1, j)"
PL/pgSQL function peak1d(bigint[],integer,integer) line 19 at SQL statement
SQL statement "SELECT           peak1d(A, i, m - 1)"
PL/pgSQL function peak1d(bigint[],integer,integer) line 16 at SQL statement

Time: 0.004s

Affected rows: 1
...
Рейтинг: 0 / 0
28.07.2016, 12:05
| Ответить | Цитировать | Написать  
Как правильно реализовать рекурсивную функцию в Postgres ?
    #39282520
Hawkmoon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Hawkmoon
Участник
Каждый погроммист считает себя алгоритмистом...

и видимо, каждый по 100 раз на дню перечитывает Кайта Самарского.
...
Рейтинг: 0 / 0
29.07.2016, 11:00
| Ответить | Цитировать | Написать  
22 сообщений из 22, страница 1 из 1
Форумы / PostgreSQL [игнор отключен] [закрыт для гостей] / Как правильно реализовать рекурсивную функцию в Postgres ?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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