6
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

BigQueryで簡単にbit全探索

Posted at

福岡でデータ基盤エンジニアしている荒木です!
日々の業務の中でクエリを書いていると、SQLでbit全探索 が書きたいなーと思うことってありますよね?僕は一度もないです。
BigQueryの関数とWith句を使うとbit全探索が意外と簡単に書けたのでご紹介したいと思います。
例題として、価値と重さが設定された20個品物を一定の重さ以下で価値を最大化する問題(いわゆる ナップザック問題)を考えてみたいと思います。
(前提知識として通常のプログラミング言語でbit全探索を理解している方を対象としています = bit全探索についての説明はしません。)

bit.sql
WITH nimotu AS (
  -- テストケース
  SELECT 0  AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 1  AS id,   5 AS value,  5 AS weight UNION ALL
  SELECT 2  AS id,   4 AS value,  1 AS weight UNION ALL
  SELECT 3  AS id,   1 AS value,  5 AS weight UNION ALL
  SELECT 4  AS id,   3 AS value,  5 AS weight UNION ALL
  SELECT 5  AS id, 100 AS value, 20 AS weight UNION ALL
  SELECT 6  AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 7  AS id,   5 AS value,  5 AS weight UNION ALL
  SELECT 8  AS id,   4 AS value,  1 AS weight UNION ALL
  SELECT 9  AS id,   1 AS value,  2 AS weight UNION ALL
  SELECT 10 AS id,   3 AS value,  5 AS weight UNION ALL
  SELECT 11 AS id, 100 AS value, 20 AS weight UNION ALL
  SELECT 12 AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 13 AS id,   5 AS value,  5 AS weight UNION ALL
  SELECT 14 AS id,   4 AS value,  1 AS weight UNION ALL
  SELECT 15 AS id,   1 AS value,  2 AS weight UNION ALL
  SELECT 16 AS id,   3 AS value,  5 AS weight UNION ALL
  SELECT 17 AS id, 100 AS value, 20 AS weight UNION ALL
  SELECT 18 AS id,   2 AS value,  9 AS weight UNION ALL
  SELECT 19 AS id,   5 AS value,  5 AS weight 
), solve AS(
  SELECT
    SUM(
      -- bitが0の商品は加算
      CASE WHEN bit & (1 << id) = 0 
        THEN nimotu.value 
        ELSE 0 
      END
    ) AS value,
    SUM(
      -- bitが0の商品は加算
      CASE WHEN bit & (1 << id) = 0 
        THEN nimotu.weight 
        ELSE 0 
      END 
    ) AS weight
  -- 商品idと選び方をcross joinして1レコードがある選び方のときのある商品の状態を示すテーブルを作成
  FROM
    -- 商品idの列挙
    UNNEST(GENERATE_ARRAY(0, 19)) AS id
  CROSS JOIN
    -- bitで選び方を列挙
    UNNEST(GENERATE_ARRAY(0, 1<<19)) AS bit
  LEFT JOIN
    nimotu
  ON
    id = nimotu.id
  GROUP BY
    -- 選び方でグループ分けして1レコードがある選び方を示すテーブルに変換
    bit
)
SELECT
  MAX(value)
FROM
  solve
WHERE
  -- 重量は50以下の設定にする
  weight <= 50

GENERATE_ARRAYで商品idの連番テーブルと選び方のbit列の連番テーブル作ってCROSS JOINします。するとある商品がある選び方のときにの状態を示すテーブルができます。なのでbitでグループ分けして、bit & ( 1 << id )が0の商品を合計すると全ての選び方を全列挙することができました。

6
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
6
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?