Обсуждение: Subtract one array from another, both with non-unique elements

Поиск
Список
Период
Сортировка

Subtract one array from another, both with non-unique elements

От
Alexander Farber
Дата:
Hello,

could someone please recommend the most efficient way subtracting elements of one array from the other in PostgreSQL 9.5?

Should I create a new array or can I work on the existing one (and if the latter - will FOREACH work well when elements are removed "from under its feet"?).

Both arrays contain non-unique letters and represent a hand of a player and a list of characters to be swapped.

Here is my stored procedure sofar (apologies for non-english chars):

words=> select words_swap_game(1,1,'ТЕ');
NOTICE:  swap_array = {Т,Е}
NOTICE:  hand_array = {Т,Ъ,Б,В,Е,О,Р}
NOTICE:  pile_array = {С,Н,Л,Л,Д,П,Г,Ц,И,К,Ж,М,У,А,Д,Е,В,Г,Ч,О,*,Я,И,О,И,П,С,Е,О,Е,А,О,У,Т,З,К,А,Ы,Н,М,Н,Ф,Е,Н,Ь,Р,Ы,С,В,М,Д,Б,Й,П,Ш,Н,К,К,*,Ж,И,А,Л,Я,Е,М,М,Э,В,Р,О,Н,А,С,Й,Т,Н,А,П,А,Н,Р,И,К,Ю,О,Й,Е,А,Е,Д,О,Й,К,И,Д,С,Л,О,С,З,Х,П,И,Б,Т,И,Я,В,Щ,П,У,А,А,Е,Х}
 words_swap_game 
-----------------
 
(1 row)

CREATE OR REPLACE FUNCTION words_swap_game(
        IN in_uid integer,
        IN in_gid integer,
        IN in_swap varchar(7))
        RETURNS void AS
$func$
DECLARE
        swap_array varchar[];
        hand_array varchar[];
        pile_array varchar[];
BEGIN
        swap_array := (SELECT STRING_TO_ARRAY(in_swap, NULL));
        RAISE NOTICE 'swap_array = %', swap_array;

        SELECT hand1, pile
        INTO hand_array, pile_array
        FROM words_games
        WHERE gid = in_gid 
        AND player1 = in_uid
        /* and it is first player's turn */
        AND (played1 IS NULL OR played1 < played2);

        IF NOT FOUND THEN
                SELECT hand2, pile
                INTO hand_array, pile_array 
                FROM words_games
                WHERE gid = in_gid 
                AND player2 = in_uid
                /* and it is second player's turn */
                AND (played2 IS NULL OR played2 < played1);
        END IF; 

        RAISE NOTICE 'hand_array = %', hand_array;
        RAISE NOTICE 'pile_array = %', pile_array;

        IF NOT hand_array @> swap_array THEN
                RAISE EXCEPTION 'Hand % does not contain swap %', hand_array, swap_array;
        END IF;

        FOREACH x IN ARRAY swap_array
        LOOP
                RAISE NOTICE 'x = %', x;
                IF x = ANY(hand_array) THEN
                        RAISE NOTICE 'Found';
                        -- How to remove x from hand_array?
                END IF;
        END LOOP;
END
$func$ LANGUAGE plpgsql;


Thanks
Alex

Re: Subtract one array from another, both with non-unique elements

От
bricklen
Дата:
On Sun, Mar 6, 2016 at 9:22 AM, Alexander Farber <alexander.farber@gmail.com> wrote:
could someone please recommend the most efficient way subtracting elements of one array from the other in PostgreSQL 9.5?

There are quite a few examples of array functions at http://postgres.cz/wiki/Array_based_functions, probably worth having a look.

Re: Subtract one array from another, both with non-unique elements

От
Alexander Farber
Дата:
Thank you, but shouldn't I better use FOREACH for my task?

On Sun, Mar 6, 2016 at 6:34 PM, bricklen <bricklen@gmail.com> wrote:
On Sun, Mar 6, 2016 at 9:22 AM, Alexander Farber <alexander.farber@gmail.com> wrote:
could someone please recommend the most efficient way subtracting elements of one array from the other in PostgreSQL 9.5?

There are quite a few examples of array functions at http://postgres.cz/wiki/Array_based_functions, probably worth having a look.

Re: Subtract one array from another, both with non-unique elements

От
Pavel Stehule
Дата:
Hi

2016-03-06 18:41 GMT+01:00 Alexander Farber <alexander.farber@gmail.com>:
Thank you, but shouldn't I better use FOREACH for my task?


SQL based solution (functional based) solution can be faster and shorter. PLpgSQL is nice language, but what you can do about arrays functionally, you should to do :). Usually it is significantly faster.

But, you can try - it is good example for learning, try to implement it different ways and compare speed.

Pavel
 

On Sun, Mar 6, 2016 at 6:34 PM, bricklen <bricklen@gmail.com> wrote:
On Sun, Mar 6, 2016 at 9:22 AM, Alexander Farber <alexander.farber@gmail.com> wrote:
could someone please recommend the most efficient way subtracting elements of one array from the other in PostgreSQL 9.5?

There are quite a few examples of array functions at http://postgres.cz/wiki/Array_based_functions, probably worth having a look.


Re: Subtract one array from another, both with non-unique elements

От
Alexander Farber
Дата:
So I have written my own stored function
to subtract one non-unique array from another
(like swapping tiles in a word game):

DROP FUNCTION IF EXISTS words_array_subtract(anyarray, anyarray);
CREATE OR REPLACE FUNCTION words_array_subtract(from_array anyarray, remove_array anyarray)
        RETURNS anyarray AS
$func$
        DECLARE
                i integer;
                j integer;
                from_ignore boolean[];
                remove_ignore boolean[];
                result_array from_array%TYPE := '{}';
        BEGIN
                IF NOT from_array @> remove_array THEN
                        RAISE EXCEPTION '% does not contain %', from_array, remove_array;
                END IF;

                from_ignore   := ARRAY_FILL(FALSE, ARRAY[ARRAY_LENGTH(from_array, 1)]);
                remove_ignore := ARRAY_FILL(FALSE, ARRAY[ARRAY_LENGTH(remove_array, 1)]);

                RAISE NOTICE 'from_ignore = %', from_ignore;
                RAISE NOTICE 'remove_ignore = %', remove_ignore;

                FOR i IN ARRAY_LOWER(from_array, 1)..ARRAY_UPPER(from_array, 1) LOOP
                        FOR j IN ARRAY_LOWER(remove_array, 1)..ARRAY_UPPER(remove_array, 1) LOOP
                                IF from_ignore[i] = FALSE AND
                                   remove_ignore[j] = FALSE AND
                                   from_array[i] = remove_array[j] THEN
                                        from_ignore[i] := TRUE;
                                        remove_ignore[j] := TRUE;
                                END IF;
                        END LOOP;
                END LOOP;

                FOR i IN ARRAY_LOWER(from_array, 1)..ARRAY_UPPER(from_array, 1) LOOP
                        IF from_ignore[i] = FALSE THEN
                                result_array := ARRAY_APPEND(result_array, from_array[i]);
                        END IF;
                END LOOP;

                RETURN result_array;
        END;
$func$ LANGUAGE plpgsql;

# select words_array_subtract(ARRAY['A','A','B','B','C'], ARRAY['A','B']);
NOTICE:  from_ignore = {f,f,f,f,f}
NOTICE:  remove_ignore = {f,f}
 words_array_subtract
----------------------
 {A,B,C}
(1 row)

# select words_array_subtract(ARRAY[1,2,2,3,4,4, 5], ARRAY[2,4,4]);
NOTICE:  from_ignore = {f,f,f,f,f,f,f}
NOTICE:  remove_ignore = {f,f,f}
 words_array_subtract
----------------------
 {1,2,3,5}
(1 row)


If you have any improvement proposals please tell me.

Regards
Alex

Re: Subtract one array from another, both with non-unique elements

От
Alexander Farber
Дата:
Here 1-pass version, if you have improvement suggestions, you are welcome -

DROP FUNCTION IF EXISTS words_array_subtract(anyarray, anyarray);
CREATE OR REPLACE FUNCTION words_array_subtract(from_array anyarray, remove_array anyarray)
        RETURNS anyarray AS
$func$
        DECLARE
                i integer;
                j integer;
                remove_ignore boolean[];
                result_array from_array%TYPE := '{}';
        BEGIN
                IF NOT from_array @> remove_array THEN
                        RAISE EXCEPTION '% does not contain %', from_array, remove_array;
                END IF;

                remove_ignore := ARRAY_FILL(FALSE, ARRAY[ARRAY_LENGTH(remove_array, 1)]);
                RAISE NOTICE 'remove_ignore = %', remove_ignore;

                <<from_loop>>
                FOR i IN ARRAY_LOWER(from_array, 1)..ARRAY_UPPER(from_array, 1) LOOP
                        FOR j IN ARRAY_LOWER(remove_array, 1)..ARRAY_UPPER(remove_array, 1) LOOP
                                IF remove_ignore[j] = FALSE AND
                                   from_array[i] = remove_array[j] THEN
                                        remove_ignore[j] := TRUE;
                                        CONTINUE from_loop;
                                END IF;
                        END LOOP;

                        result_array := ARRAY_APPEND(result_array, from_array[i]);
                END LOOP;

                RETURN result_array;
        END;
$func$ LANGUAGE plpgsql;

# select words_array_subtract(ARRAY[1,2,2,3,4,4, 5], ARRAY[2,4,4]);
NOTICE:  remove_ignore = {f,f,f}
 words_array_subtract
----------------------
 {1,2,3,5}
(1 row)

# select words_array_subtract(ARRAY['A','A','B','B','C'], ARRAY['A','B']);
NOTICE:  remove_ignore = {f,f}
 words_array_subtract
----------------------
 {A,B,C}
(1 row)



On Tue, Mar 8, 2016 at 2:28 PM, Alexander Farber <alexander.farber@gmail.com> wrote:
So I have written my own stored function
to subtract one non-unique array from another
(like swapping tiles in a word game):


Re: Subtract one array from another, both with non-unique elements

От
Victor Yegorov
Дата:
2016-03-08 15:59 GMT+02:00 Alexander Farber <alexander.farber@gmail.com>:
Here 1-pass version, if you have improvement suggestions, you are welcome -

My variant:

CREATE OR REPLACE FUNCTION arrexcept(anyarray, anyarray) RETURNS anyarray AS $arrexcept$
  SELECT array_agg(un) FROM (
    SELECT un, row_number() OVER (PARTITION BY un ORDER BY ord) id FROM unnest($1) with ordinality AS t(un, ord)
    EXCEPT
    SELECT un, row_number() OVER (PARTITION BY un ORDER BY ord) id FROM unnest($2) with ordinality AS t(un, ord)
  ) x;
$arrexcept$ LANGUAGE sql;

postgres=# select arrexcept(ARRAY['A','A','B','B','C'], ARRAY['A','B']);
 arrexcept
-----------
 {A,B,C}
(1 row)


But it doesn't preserves the order of the elements, not sure if this is important.



--
Victor Y. Yegorov