Расстояние одномерного землевладельца в BigQuery/SQL

Question

Пусть P и Q - два конечных распределения вероятностей по целым числам с поддержкой от 0 до некоторого большого целого числа N. Расстояние одномерного движителя земли между P и Q является минимальной стоимостью, которую вы должны заплатить, чтобы преобразовать P в Q, учитывая, что оно стоит г *| нм | "переместить" вероятность r, связанную с целым числом n, в другое целое число m.

Для этого есть простой алгоритм. В псевдокоде:

previous = 0
sum = 0
for i from 0 to N:
    previous = P(i) - Q(i) + previous
    sum = sum + abs(previous)         // abs = absolute value
return sum

Теперь предположим, что у вас есть две таблицы, каждая из которых содержит распределение вероятностей. колонка n содержит целые числа и столбец p содержит соответствующую вероятность. Таблицы верны (все вероятности находятся в диапазоне от 0 до 1, их сумма - я хочу вычислить расстояние движителя земли между этими двумя таблицами в BigQuery (Standard SQL).

1. Является ли это возможным? Я чувствую, что нужно использовать аналитические функции, но у меня нет большого опыта с ними, поэтому я не знаю, как туда добраться.
2. Что если N (максимальное целое число) очень большое, а мои таблицы - нет? Можем ли мы адаптировать решение, чтобы избежать вычисления для каждого целого числа i?

Answer 1

Я адаптировал ответ Майкла, чтобы исправить его, вот решение, которое я выбрал. Предположим, что целые числа хранятся в столбце i и вероятность в столбце p, Сначала я соединяю две таблицы, затем вычисляю EMD(i) для всех i используя окно, я суммирую все абсолютные значения.

WITH
joined_table AS (
  SELECT
    IFNULL(table1.i, table2.i) AS i,
    IFNULL(table1.p, 0) AS p,
    IFNULL(table2.p, 0) AS q,
  FROM table1
  OUTER JOIN table2
  ON table1.i = table2.i
),
aggr AS (
  SELECT
    (SUM(p-q) OVER win) * (i - (LAG(i,1) OVER win)) AS emd
  FROM joined_table
  WINDOW win AS (
    ORDER BY i
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  )
)
SELECT SUM(ABS(emd)) AS total_emd
FROM aggr

Answer 2

Надеюсь, я полностью понимаю вашу проблему. Похоже, это то, что вы ищете:

WITH Aggr AS (
  SELECT rp.n AS n, SUM(rp.p - rq.p)
  OVER(ORDER BY rp.n ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS emd
  FROM P rp
  LEFT JOIN Q rq
  ON rp.n = rq.n
) SELECT SUM(ABS(a.emd)) AS total_emd
FROM Aggr a;

WRT вопрос № 2, обратите внимание, что мы сканируем только то, что на самом деле в таблицах, независимо от N, предполагая однозначное соответствие для каждого n в P с n в Q.