Использование пользовательских функций JavaScript внутри BigQuery для вычисления Фибоначчи
BigQuery имеет удобную функциональность для поддержки пользовательских функций, написанных на SQL и JavaScript, поэтому я подумал, что было бы интересно решить небольшую проблему с числами Фибоначчи.
Я почти уверен, что видел эту задачу в Project Euler или в чем-то подобном, поэтому, пожалуйста, не используйте это как способ обмана. Задача заключается в следующем:
Найдите сумму последних 6 шести цифр для первых 1000 чисел Фибоначчи. Это может показаться немного сложным, поэтому мы начнем медленно с вычисления полных чисел Фибоначчи, а затем продолжим.
Что такое последовательность Фибоначчи?
Последовательность определяется как:
- a(0) = 0
- a(1) = 1
- a(n) = a(n-2) + a(n-1)
Итак, каждый элемент является суммой двух предыдущих. Вот он в действии:
0, 1, 1, 2, 3, 5, 8, 13, 21…
Как вы понимаете, эти числа могут довольно быстро стать довольно большими. Например, 50-е число - 12,586,269,025, что больше 12 миллиардов, с буквой b! (100-е число: 354,224,848,179,261,915,075 😬)
Как, черт возьми, мы это делаем в BigQuery?
Теперь, когда мы знаем, что такое ряд Фибоначчи, возникает очевидный вопрос, как создать цикл в BigQuery. Что ж, есть способы сделать это с помощью сценариев BigQuery, но здесь я буду использовать вместо этого пользовательские функции JavaScript.
Вот функция JavaScript для вычисления n-го числа Фибоначчи:
Я знаю JavaScript от нуля до нуля, поэтому, пожалуйста, напишите мне в комментариях, если я делаю здесь что-то глупое!
Вот оно в действии, если вы хотите поиграть с ним.
Время использовать функцию
Чтобы создать эту функцию в BigQuery, нам нужно использовать объявление CREATE TEMP FUNCTION:
Мы можем использовать то же тело функции JavaScript, что и выше. Все, что нам нужно сделать, это удалить бит function fib(n) из бита JavaScript и добавить типы ввода и вывода в бит SQL. Обратите внимание, как мы говорим fibonacci(n INT64), чтобы объявить, что ввод должен быть целым числом, и RETURNS INT64, чтобы указать тип вывода.
Давайте возьмем цифры в BigQuery:
Если вы не знаете, что происходит с генератором массивов и отменой вложенности в withstatement, ознакомьтесь с моей статьей FizzBuzz с BigQuery 🍾 - там все объясняется.
Вот результаты:
╔═════╦═════╦═════════════╗ ║ Row ║ num ║ fib_n ║ ╠═════╬═════╬═════════════╣ ║ 1 ║ 0 ║ 0 ║ ║ 2 ║ 1 ║ 1 ║ ║ 3 ║ 2 ║ 1 ║ ║ 4 ║ 3 ║ 2 ║ ║ 5 ║ 4 ║ 3 ║ ║ 6 ║ 5 ║ 5 ║ ║ 7 ║ 6 ║ 8 ║ ║ 8 ║ 7 ║ 13 ║ ║ 9 ║ 8 ║ 21 ║ ║ 10 ║ 9 ║ 34 ║ ║ 11 ║ 10 ║ 55 ║ ║ 12 ║ 20 ║ 6765 ║ ║ 13 ║ 30 ║ 832040 ║ ║ 14 ║ 40 ║ 102334155 ║ ║ 15 ║ 50 ║ 12586269025 ║ ╚═════╩═════╩═════════════╝
Это заняло 0,5 секунды. Не так уж и плохо, и похоже, что он работает нормально, так как у нас есть тот же 50-й элемент, что и выше.
Теперь настоящий вызов
Если вы вернетесь к началу, то увидите, что первоначальной задачей было вычислить сумму последних 6 цифр для первых 1000 чисел Фибоначчи. Теперь это будет легко. Хитрость здесь в том, чтобы понять, что для точного вычисления последних 6 цифр вам нужны только последние 6 цифр, поэтому мы можем выбросить остальные, используя оператор по модулю. Нам нужен этот трюк, иначе наш INT64 станет слишком большим и переполнится.
Нам просто нужно добавить: var new_num = (numbers[0] + numbers[1]) % 1000000; в нашу функцию JavaScript, а затем просуммировать все результаты. Вот для этого SQL:
Это работало за 0,9 секунды, так что BigQuery сейчас действительно потеет ... И результат:
╔═════╦═══════════╗ ║ Row ║ result ║ ╠═════╬═══════════╣ ║ 1 ║ 477632375 ║ ╚═════╩═══════════╝
Я бы порекомендовал вам изменить приведенный выше SQL и посмотреть на последние 6 цифр сотого числа Фибоначчи, чтобы убедиться, что это правильно!
Подведение итогов
Подводя итог, можно сказать, что функции JavaScript действительно легко добавить в BigQuery, и вы можете вместе провести несколько интересных вычислений. Более того, вы даже можете использовать библиотеки JavaScript, если включите файл .js в корзину Google Cloud Storage. Как это круто?
