6

次の形式の PostgreSQL テーブルがあります。

base_id int | mods smallint[]
     3      |   {7,15,48}

次の形式のテーブルにデータを入力する必要があります。

combo_id int | base_id int | mods smallint[]
     1       |     3       |      
     2       |     3       |      {7}
     3       |     3       |      {7,15}   
     4       |     3       |      {7,48}   
     5       |     3       |      {7,15,48}
     6       |     3       |      {15}
     7       |     3       |      {15,48}
     8       |     3       |      {48}

最初のテーブルを反復処理し、組み合わせを 2 番目のテーブルに書き込む関数を使用して、これをほぼ正確に行うことができると思います: SQL ですべての組み合わせを生成する

しかし、私はPostgresの初心者であり、plpgsqlを使用してこれを行う方法を一生理解できません。特に高速である必要はありません。バックエンドで定期的にのみ実行されます。最初のテーブルには約 80 のレコードがあり、大まかな計算では、2 番目のテーブルには約 2600 のレコードが期待できることを示唆しています。

誰かが少なくとも私を正しい方向に向けることができますか?

編集: Craig: PostgreSQL 9.0 を持っています。UNNEST() を正常に使用できました。

FOR messvar IN SELECT * FROM UNNEST(mods) AS mod WHERE mod BETWEEN 0 AND POWER(2, @n) - 1
LOOP
    RAISE NOTICE '%', messvar;
END LOOP;

しかし、次にどこに行くべきかわかりませんでした。

編集:参考までに、私は最終的にErwinのソリューションを使用し、各セットにnull結果(「{}」)を追加するために1行追加し、Erwinが参照する特別なケースを削除しました:

CREATE OR REPLACE FUNCTION f_combos(_arr integer[], _a integer[] DEFAULT '{}'::integer[], _z integer[] DEFAULT '{}'::integer[])
RETURNS SETOF integer[] LANGUAGE plpgsql AS
$BODY$
DECLARE
 i int;
 j int;
 _up int;
BEGIN
 IF array_length(_arr,1) > 0 THEN 
    _up := array_upper(_arr, 1);

    IF _a = '{}' AND _z = '{}' THEN RETURN QUERY SELECT '{}'::int[]; END IF;
    FOR i IN array_lower(_arr, 1) .. _up LOOP
       FOR j IN i .. _up  LOOP
          CASE j-i
          WHEN 0,1 THEN
             RETURN NEXT _a || _arr[i:j] || _z;
          ELSE
             RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
             RETURN QUERY SELECT *
             FROM f_combos(_arr[i+1:j-1], _a || _arr[i], _arr[j] || _z);
          END CASE;
       END LOOP;
    END LOOP;
 ELSE
    RETURN NEXT _arr;
 END IF;
END;
$BODY$

次に、その関数を使用してテーブルにデータを入力しました。

INSERT INTO e_ecosystem_modified (ide_ecosystem, modifiers) 
(SELECT ide_ecosystem, f_combos(modifiers) AS modifiers FROM e_ecosystem WHERE ecosystemgroup <> 'modifier' ORDER BY ide_ecosystem, modifiers);

ソース テーブルの 79 行と修飾子配列の最大 7 項目から、クエリは出力テーブルに 2630 行を入力するのに 250 ミリ秒かかりました。素晴らしい。

4

2 に答える 2

5

私がそれを眠った後、私は完全に新しく、より単純で、より速い考えを持っていました:

CREATE OR REPLACE FUNCTION f_combos(_arr anyarray)
  RETURNS TABLE (combo anyarray) LANGUAGE plpgsql AS
$BODY$
BEGIN
    IF array_upper(_arr, 1) IS NULL THEN
        combo := _arr; RETURN NEXT; RETURN;
    END IF;

    CASE array_upper(_arr, 1)
--  WHEN 0 THEN -- does not exist
    WHEN 1 THEN
        RETURN QUERY VALUES ('{}'), (_arr);
    WHEN 2 THEN
        RETURN QUERY VALUES ('{}'), (_arr[1:1]), (_arr), (_arr[2:2]);
    ELSE
        RETURN QUERY
        WITH x AS (
            SELECT f.combo FROM f_combos(_arr[1:array_upper(_arr, 1)-1]) f
            )
        SELECT x.combo FROM x
        UNION ALL
        SELECT x.combo || _arr[array_upper(_arr, 1)] FROM x;
    END CASE;
END
$BODY$;

電話:

SELECT * FROM f_combos('{1,2,3,4,5,6,7,8,9}'::int[]) ORDER BY 1;

512行、合計実行時間:2.899ミリ秒

説明

  • NULL空の配列で特殊なケースを処理します。
  • 2つのプリミティブ配列の組み合わせを作成します。
  • これ以上の配列は次のように分類されます。
    • 長さn-1の同じ配列の組み合わせ
    • 加えて、要素nと組み合わされたものすべて..再帰的に..

あなたがそれを手に入れたら、本当に簡単です。

  • 下付き文字1で始まる1次元整数配列で機能します(以下を参照)。
  • 古いソリューションの2〜3倍の速度で、拡張性が向上します。
  • すべての要素タイプで再び機能します(ポリモーフィックタイプを使用)。
  • 質問に表示されているように(そして@Craigがコメントで私に指摘したように)、結果に空の配列を含めます。
  • より短く、よりエレガント。

これは、 1(デフォルト)で始まる配列添え字を想定しています。値がわからない場合は、次のような関数を呼び出して正規化します。

SELECT * FROM  f_combos(_arr[array_lower(_arr, 1):array_upper(_arr, 1)]);

配列の添え字を正規化するためのより洗練された方法があるかどうかはわかりません。私はそれについて質問を投稿しました:
1次元配列の配列添え字を正規化して1で始まるようにします

古い解決策(遅い)

CREATE OR REPLACE FUNCTION f_combos2(_arr int[], _a int[] = '{}', _z int[] = '{}')
 RETURNS SETOF int[] LANGUAGE plpgsql AS
$BODY$
DECLARE
   i int;
   j int;
   _up int;
BEGIN
   IF array_length(_arr,1) > 0 THEN 
      _up := array_upper(_arr, 1);

      FOR i IN array_lower(_arr, 1) .. _up LOOP
         FOR j IN i .. _up  LOOP
            CASE j-i
            WHEN 0,1 THEN
               RETURN NEXT _a || _arr[i:j] || _z;
            WHEN 2 THEN
               RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
               RETURN NEXT _a || _arr[i:j] || _z;
            ELSE
               RETURN NEXT _a || _arr[i:i] || _arr[j:j] || _z;
               RETURN QUERY SELECT *
               FROM f_combos2(_arr[i+1:j-1], _a || _arr[i], _arr[j] || _z);
            END CASE;
         END LOOP;
      END LOOP;
   ELSE
      RETURN NEXT _arr;
   END IF;
END;
$BODY$;

電話:

SELECT * FROM f_combos2('{7,15,48}'::int[]) ORDER BY 1;

1次元整数配列で機能します。これはさらに最適化することができますが、この質問の範囲では確かに必要ありません。
ORDER BY質問に表示された順序を課します。

NULLコメントに記載されているように、NULLまたは空の配列を指定します。

PostgreSQL 9.1でテストされていますが、中途半端な最新バージョンで動作するはずです。 少なくともPostgreSQL7.4以降は存在していますarray_lower()array_upper()バージョン8.4では、パラメーターのデフォルトのみが新しくなっています。簡単に交換できます。

パフォーマンスはまともです。

SELECT DISTINCT * FROM f_combos('{1,2,3,4,5,6,7,8,9}'::int[]) ORDER BY 1;

511行、合計実行時間:7.729ミリ秒

説明

これは、隣接する要素のすべての組み合わせのみを作成するこの単純なフォームに基づいています。

CREATE FUNCTION f_combos(_arr int[])
  RETURNS SETOF int[] LANGUAGE plpgsql AS
$BODY$
DECLARE
   i  int;
   j  int;
  _up int;
BEGIN
   _up := array_upper(_arr, 1);

   FOR i in array_lower(_arr, 1) .. _up LOOP
      FOR j in i .. _up LOOP
         RETURN NEXT _arr[i:j];
      END LOOP;
   END LOOP;
END;
$BODY$;

ただし、これは3つ以上の要素を持つサブ配列では失敗します。それで:

  • 3つの要素を持つサブ配列の場合、外側の2つの要素だけを持つ1つの配列が追加されます。これは、パフォーマンスを向上させるこの特殊なケースのショートカットであり、厳密には必要ありません

  • 3つを超える要素を持つサブ配列の場合、外側の2つの要素を取得し、同じ関数によって再帰的に作成された内側の要素のすべての組み合わせを入力します。

于 2012-08-17T01:16:59.190 に答える
3

1 つのアプローチは、再帰的な CTE を使用することです。ただし、Erwin の更新された再帰関数は大幅に高速であり、スケーリングも優れているため、これは興味深い別のアプローチとして非常に役立ちます。Erwin の更新版はより実用的です。

少しカウントする方法を試してみましたが (最後を参照)、配列から任意の要素をすばやく取り出す方法がなければ、どちらの再帰的方法よりも遅いことがわかりました。

再帰的 CTE 組み合わせ関数

CREATE OR REPLACE FUNCTION combinations(anyarray) RETURNS SETOF anyarray AS $$
WITH RECURSIVE
    items AS (
            SELECT row_number() OVER (ORDER BY item) AS rownum, item
            FROM (SELECT unnest($1) AS item) unnested
    ),
    q AS (
            SELECT 1 AS i, $1[1:0] arr
            UNION ALL
            SELECT (i+1), CASE x
                    WHEN 1 THEN array_append(q.arr,(SELECT item FROM items WHERE rownum = i))
                    ELSE q.arr END
            FROM generate_series(0,1) x CROSS JOIN q WHERE i <= array_upper($1,1)
    )
SELECT q.arr AS mods
FROM q WHERE i = array_upper($1,1)+1;
$$ LANGUAGE 'sql';

これはポリモーフィック関数であるため、あらゆるタイプの配列で機能します。

ロジックは、作業テーブルを使用して、ネストされていない入力セットの各項目を反復処理することです。世代番号が 1 の作業テーブルの空の配列から始めます。入力セットの各エントリに対して、世代番号が増分された 2 つの新しい配列を作業テーブルに挿入します。2 つのうちの 1 つは、前の世代からの入力配列のコピーであり、もう 1 つは、入力セットの (世代番号) 番目の項目が追加された入力配列です。世代番号が入力集合の項目数を超える場合は、最後の世代を返します。

使用法

この関数をウィンドウ関数combinations(smallint[])と組み合わせて集合を返す関数として使用することで、目的の結果を得ることができます。row_number

-- assuming table structure
regress=# \d comb
       Table "public.comb"
 Column  |    Type    | Modifiers 
---------+------------+-----------
 base_id | integer    | 
 mods    | smallint[] | 


SELECT base_id, row_number() OVER (ORDER BY mod) AS mod_id, mod 
FROM (SELECT base_id, combinations(mods) AS mod FROM comb WHERE base_id = 3) x
ORDER BY mod;

結果

regress=# SELECT base_id, row_number() OVER (ORDER BY mod) AS mod_id, mod 
regress-# FROM (SELECT base_id, combinations(mods) AS mod FROM comb WHERE base_id = 3) x
regress-# ORDER BY mod;
 base_id | mod_id |    mod    
---------+--------+-----------
       3 |      1 | {}
       3 |      2 | {7}
       3 |      3 | {7,15}
       3 |      4 | {7,15,48}
       3 |      5 | {7,48}
       3 |      6 | {15}
       3 |      7 | {15,48}
       3 |      8 | {48}
(8 rows)

Time: 2.121 ms

要素配列がゼロの場合、null の結果が生成されます。combinations({})1行を返したい場合{}は、UNION ALLwith{}が機能します。

仮説

単純な組み合わせではなく、 k-multicombination 内のすべての k に対して k-combinations が必要なようです。繰り返しとの組み合わせの数を参照してください。

つまり、0 から n までのすべての k について、セットの要素のすべての k の組み合わせが必要です。ここで、n はセットのサイズです。

関連する SO の質問: SQL - 考えられるすべての組み合わせを検索します。これには、ビット カウントに関する非常に興味深い回答があります。

Pgにはビット操作が存在するため、ビットカウントアプローチが可能になるはずです。より効率的であると期待するかもしれませんが、配列から散らばった要素のサブセットを選択するのは非常に遅いため、実際には遅くなります

CREATE OR REPLACE FUNCTION bitwise_subarray(arr anyarray, elements integer)
RETURNS anyarray AS $$
SELECT array_agg($1[n+1]) 
FROM generate_series(0,array_upper($1,1)-1) n WHERE ($2>>n) & 1 = 1;
$$ LANGUAGE sql;

COMMENT ON FUNCTION bitwise_subarray(anyarray,integer) IS 'Return the elements from $1 where the corresponding bit in $2 is set';

CREATE OR REPLACE FUNCTION comb_bits(anyarray) RETURNS SETOF anyarray AS $$ 
SELECT bitwise_subarray($1, x) 
FROM generate_series(0,pow(2,array_upper($1,1))::integer-1) x;
$$ LANGUAGE 'sql';

bitwise_subarrayより高速な書き込み方法を見つけることができれば、comb_bits非常に高速になります。たとえば、小さな C 拡張関数のように、私は SO answer のためにそれらの 1 つを書くのに十分なだけ狂っています

于 2012-08-17T02:14:05.137 に答える