а ось складніша SQL задачка

[malyj_gorgan]

Спряжена до попередньої задачi.

Дано: таблиця з повідомленнями, які юзери шлють комусь там. Нас хвилюють три колонки: юзер айді uid, номер контакта num, час t (ну і ще всякі, неважливо)
Написати такий запит в цю таблицю (SELECT *...) щоби порахувало, скільком різним номерам підряд пішло повідомлення від нашого юзера
Тобто, уявіть собі, що ви дивитися на повідомлення лише від одного юзера, уже відсортовані за часом. Повідомлення ідуть на такі номери:
10, 11, 12, 10, 13, 14, 15, 11, 16, 17, 16
Потрібні мені цифри будуть такі:
3, 6, 8, 8, 8, 8, 8, 8, 8, 8, 2
Фактично, задача: для кожного елементу впорядкованої послідовності порахувати ширину максимального вікна, в яке входить цей елемент, і в якому всі елементи різні.

Я поки що не знаю. В якійсь стандартній мові програмування -- хай неелеґантно і складно в плані computational complexity, але таке написати я зможу, а в сіквелі якось завис.

Comments

[fenikso]

(не рішення) В сіквелі скоріш за все буде ще складніше сomputational complexity-wise, бо там навіть хешмап немає. Один з напрямків який приходить на думку, це перетворити 10, 11, 12 на послідовність пар з індексами (0, 10), (1, 11), (2, 12) сказавши що кожна пара це рядок нової таблиці а потім на цій таблиці зробити join до самої себе по значенню елемента та щоб другий індекс був більше. Щоб отримати щось на кшалт
(0, 10, nextIndexOf10), (1, 11, nextIndexOf11), (2, 12, nextIndexOf12)

Але цей напрямок може бути тупіковий, особливо якщо SQL взагалі без циклів.

[sassa_nf]

Ну й правильно, що завис. Проситься цикл із running max, але цього на SQL не напишеш.

[kondybas]

В SQL нема засобів для таких речей, бо в задачі всьо крутиться навколо впорядкованих списків, а SQL - то про множини. Які не є ані впорядкованими, ані списками. Це якщо в загальних рисах.

Питання: це абстрактна задача, чи прикладна?

[malyj_gorgan]

Це абстрактна задача збудована з реального прикладу. В реальному прикладі мені треба оцінити скільком різним людям підряд наш юзер шле ті месиджі. Але для реальних розвʼязків я на загальне рішення плюнув і дивлюся на DISTINCT num в обмеженому за часом вікні. Наче, працює

[kondybas]

Якщо це для боротьби із спамерами, що масово розсилають всяке, то цілком придатна метрика - відношення числа унікальних адресатів у часовому вікні до числа всіх меседжів у вікні. Чим більше це відношення, тим більше схоже на розсилку. А чим менше - тим більше схоже на активну переписку малого числа осіб.

[malyj_gorgan]

Зараз завелося дофіга і більше розумних спамерів, які не з одного номера розсилають свій спам, а заводять ферму девайсів (або щось таке, як я недавно постив) і потім кожен номер може слати одного листа на кілька хвилин, а то і на годину. Тому і хочеться таких рішень.
Можна, звичайно, вікно за кількістю рядків, воно, звичайно, теж варіант.

[sassa_nf]

Я б теж так робив. Дешева евристика ліпша за дороге точне рішення. Тим більше, що й постановка задачі не власне про різні номери підряд, а про активність, що виглядає як спам. Тут навіть не "різні номери підряд" має значення, а у якому часовому проміжку це відбулося. Якщо 1000 за годину - це одне, а 1000 за рік - це інше.

[malyj_gorgan]

1000 за рік -- теж спам, я тут пояснив: https://malyj-gorgan.dreamwidth.org/238528.html?thread=2828480#cmt2828480
Плюс, у нас важливий челендж -- не лише ловити, а мати конкретну метрику, яка виправдовує це діло: "чувак, ти послав 42 повідомлення різним людям, може, ти спамер?" -- воно закриває деякі бізнесові і юридичні потреби.

[sassa_nf]

Ха, так а якщо хтось користується отим девайсом, то якому з чуваків писати, що він спамер?

[aklepatc]

Something like this?
UPD: without join
UPD 2: not quite there but hopefully in the right direction.

WITH numbered AS (
  SELECT
    sender,
    receiver,
    _time,
    ROW_NUMBER() OVER (PARTITION BY sender ORDER BY _time) AS pos
  FROM tbl
),
next_duplicate AS (
  SELECT
    *,
    LEAD(pos) OVER (PARTITION BY sender, receiver ORDER BY pos) AS next_same_receiver
  FROM numbered
)
SELECT
  sender,
  receiver,
  _time,
  COALESCE(
    MIN(next_same_receiver) OVER (
      PARTITION BY sender
      ORDER BY pos
      ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
    ),
    MAX(pos) OVER (PARTITION BY sender) + 1
  ) - pos AS range_width
FROM next_duplicate

[malyj_gorgan]

Це ще не воно, але в ту сторону, точно.
Але якось надто складно виходить, навіть коли вийде

[aklepatc]

I believe it covers the case where the range starts at the current record.

If we want "at the current record or before it" semantics instead then add one more column to the middle step.

Where it calls LEAD() for the next dupe it should also call LAG() for the previous dupe. Then adjust range_width calculation accordingly.

[aklepatc]

Does the range start at the current record? Or does it possibly start before the current record?

I suspect the example is not quite right: 6 implies "starts at the current record" and the last 2 implies "starts before".

[malyj_gorgan]

Точно, це я наплутав з прикладом, а не з умовою задачі :)

[aklepatc]

All right then. My solution above is for the case where the range starts at the current record.

If we want "at the current or before" semantics then the required change is relatively easy. Where it calls LEAD() (for the next dupe) it should also call LAG() for the previous dupe.

[aklepatc]

This version should cover the case where the range possibly starts before the current record:

WITH numbered AS (
  SELECT
    sender,
    receiver,
    _time,
    ROW_NUMBER() OVER (
      PARTITION BY sender
      ORDER BY _time
    ) AS pos
  FROM tbl
),
duplicates AS (
  SELECT
    *,
    LAG(pos) OVER (
      PARTITION BY sender, receiver
      ORDER BY pos
    ) AS prev_same_receiver,
    LEAD(pos) OVER (
      PARTITION BY sender, receiver
      ORDER BY pos
    ) AS next_same_receiver
  FROM numbered
)
SELECT
  sender,
  receiver,
  _time,
  COALESCE(
    MIN(next_same_receiver) OVER (
      PARTITION BY sender
      ORDER BY pos
      ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
    ),
    MAX(pos) OVER (PARTITION BY sender) + 1
  ) - COALESCE(
    MAX(prev_same_receiver) OVER (
      PARTITION BY sender
      ORDER BY pos
      ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) + 1,
    pos
  ) AS range_width
FROM duplicates

[jonathan_simba]

*щось говорять по-погромістськи*

[malyj_gorgan]

Суміщаємо погромізм з зароблянням коштів на ЗСУ

[jonathan_simba]

За що ми щиро вдячні, друже!

[malyj_gorgan]

Це наша вам безмежна подяка і пошана!

[jonathan_simba]

Завжди ваші! ;)

Як казав один дідо, "The most noble fate a man can endure is to place his own mortal body between his loved home and the war's desolation".

Hier stehe ich. Ich kann nicht anders.