Обсуждение: How to delete few elements from array beginning?

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

How to delete few elements from array beginning?

От
Alexander Farber
Дата:
Hello fellow PostgreSQL users,

what is please the most efficient way to delete a slice from the start of a longer array (after I have copied it to another array)?

Do I really have to copy a large slice of the array to itself, like in the last line here:

        pile_array := pile_array || swap_array;

        /* here I copy away swap_len elements */
        new_hand := pile_array[1:swap_len];

        /* here I don't know how to efficiently remove already copied elements */
        pile_array := pile_array[(swap_len + 1):ARRAY_LENGTH(pile_array, 1)];

or is there a better way?

Thank you
Alex

P.S. The listing of the entire stored function in question:

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
        i           integer;
        j           integer;
        swap_len    integer;
        hand_len    integer;
        pile_len    integer;
        swap_array  varchar[];
        pile_array  varchar[];
        old_hand    varchar[];
        new_hand    varchar[];
        hand_ignore boolean[];
BEGIN
        swap_array := STRING_TO_ARRAY(in_swap, NULL);
        swap_len := ARRAY_LENGTH(swap_array, 1);

        SELECT hand1, pile, ARRAY_LENGTH(hand1, 1), ARRAY_LENGTH(pile, 1)
        INTO old_hand, pile_array, hand_len, pile_len
        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, ARRAY_LENGTH(hand2, 1), ARRAY_LENGTH(pile, 1)
                INTO old_hand, pile_array, hand_len, pile_len
                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;

        pile_array := pile_array || swap_array;
        -- pile_array := words_shuffle(pile_array);
        new_hand := pile_array[1:swap_len];
        pile_array := pile_array[(swap_len + 1):pile_len]; /* XXX is it good? */

        hand_ignore := ARRAY_FILL(FALSE, ARRAY[hand_len]);

        <<hand_loop>>
        FOR i IN 1..hand_len LOOP
                FOR j IN 1..swap_len LOOP
                        IF hand_ignore[j] = FALSE AND
                           old_hand[i] = swap_array[j] THEN
                                hand_ignore[j] := TRUE;
                                CONTINUE hand_loop;
                        END IF;
                END LOOP;

                new_hand := new_hand || old_hand[i];
        END LOOP;
/*
        UPDATE words_games
        SET hand1 = new_hand,
        pile = pile_array,
        played1 = CURRENT_TIMESTAMP
        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
                UPDATE words_games
                SET hand2 = new_hand,
                pile = pile_array,
                played2 = CURRENT_TIMESTAMP
                WHERE gid = in_gid
                AND player2 = in_uid
                -- and it is second player's turn
                AND (played2 IS NULL OR played2 < played1);
        END IF;
*/

END
$func$ LANGUAGE plpgsql;



Re: How to delete few elements from array beginning?

От
"Mike Sofen"
Дата:

>>Alexander Farber wrote on  Wednesday, March 09, 2016 4:11 AM

Hello fellow PostgreSQL users,

what is please the most efficient way to delete a slice from the start of a longer array (after I have copied it to another array)?

Do I really have to copy a large slice of the array to itself, like in the last line here:

        pile_array := pile_array || swap_array;

        /* here I copy away swap_len elements */
        new_hand := pile_array[1:swap_len];

        /* here I don't know how to efficiently remove already copied elements */
        pile_array := pile_array[(swap_len + 1):ARRAY_LENGTH(pile_array, 1)];

or is there a better way?

Thank you

Alex

<< 

Have you considered a normal (relational), non-array-based data model for this app (2 or 3 tables in a 1:M/M:M) instead of the single table model you’ve shown?  That would then allow you to use normal sql set-based operations that are readable, understandable, maintainable and very fast/scalable. 

When I see row by row operations (looping or cursors) in what should be a real time query…that’s my alarm bell that perhaps the code has wandered off a valid solution path.

Mike

Re: How to delete few elements from array beginning?

От
Alexander Farber
Дата:
Hello Mike,

On Wed, Mar 9, 2016 at 2:42 PM, Mike Sofen <msofen@runbox.com> wrote:
>
> Have you considered a normal (relational), non-array-based data model for this app (2 or 3 tables in a 1:M/M:M) instead of the single table model you’ve shown?  That would then allow you to use normal sql set-based operations that are readable, understandable, maintainable and very fast/scalable.
>
> When I see row by row operations (looping or cursors) in what should be a real time query…that’s my alarm bell that perhaps the code has wandered off a valid solution path.
>

thank you for your reply.

I have considered that for my Scrabble-like word game, but with rows I would not know how to -

1) swap several tiles with same letter values (like player hand is "AABBCCD" and she swaps "BBC"). With rows and DISTINCT I don't know how to do that

2) how to represent 15 x 15 game board.... ok I could store a varchar(225) string...

For the backend of my game I would like to implement as much as possible in PL/pgSQL and as little as possible in PHP.

A decade ago I implemented a card game as a "hobby programmer project" and I like how its data is still kept clean by PostgreSQL, despite 4000 active players.

Also while implementing the card game I was given a great advice on this mailing list (to use timestamptz instead of year-week strings) and later regretted ignoring it :-) So any advices are welcome

Regards
Alex

P.S. Here my current implementation of letter swapping, any comments are welcome:

CREATE TABLE words_games (
        gid SERIAL PRIMARY KEY,
        created timestamptz NOT NULL,

        player1 integer REFERENCES words_users(uid) ON DELETE CASCADE NOT NULL,
        player2 integer REFERENCES words_users(uid) ON DELETE CASCADE,

        played1 timestamptz,
        played2 timestamptz,

        hand1 varchar[7] NOT NULL,
        hand2 varchar[7] NOT NULL,
        pile  varchar[116] NOT NULL,

        board varchar[15][15] NOT NULL,
        style integer NOT NULL CHECK (1 <= style AND style <= 4)
);

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
        i           integer;
        j           integer;
        letter      varchar;
        swapped     integer;
        swap_len    integer;
        hand_len    integer;
        pile_len    integer;
        swap_array  varchar[];
        pile_array  varchar[];
        old_hand    varchar[];
        new_hand    varchar[];
BEGIN
        swap_array := STRING_TO_ARRAY(in_swap, NULL);
        swap_len := ARRAY_LENGTH(swap_array, 1);

        SELECT
                hand1,
                pile,
                ARRAY_LENGTH(hand1, 1),
                ARRAY_LENGTH(pile, 1)
        INTO
                old_hand,
                pile_array,
                hand_len,
                pile_len
        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,
                        ARRAY_LENGTH(hand2, 1),
                        ARRAY_LENGTH(pile, 1)
                INTO
                        old_hand,
                        pile_array,
                        hand_len,
                        pile_len
                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;

        IF NOT FOUND THEN
                RAISE EXCEPTION 'Game % not found for user %', in_gid, in_uid;
        END IF;

        swapped := 0;
        <<hand_loop>>
        FOR i IN 1..hand_len LOOP
                letter := old_hand[i];

                FOR j IN 1..swap_len LOOP
                        IF swap_array[j] IS NOT NULL AND
                           swap_array[j] = letter THEN
                                /* move letter from swap to pile */
                                pile_array := pile_array || letter;
                                swap_array[j] := NULL;
                                swapped := swapped + 1;
                                CONTINUE hand_loop;
                        END IF;
                END LOOP;

                /* letter was not found in swap, keep it in hand */
                new_hand := new_hand || letter;
        END LOOP;

        IF swapped = 0 OR swapped <> swap_len THEN
                RAISE EXCEPTION 'Invalid swap % for hand %', in_swap, old_hand;
        END IF;

        -- pile_array := words_shuffle(pile_array);
        new_hand   := new_hand || pile_array[1:swapped];
        pile_array := pile_array[(1 + swapped):(pile_len + swapped)];

        UPDATE words_games SET
                hand1   = new_hand,
                pile    = pile_array,
                played1 = CURRENT_TIMESTAMP
        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
                UPDATE words_games SET
                        hand2   = new_hand,
                        pile    = pile_array,
                        played2 = CURRENT_TIMESTAMP
                WHERE gid = in_gid
                AND player2 = in_uid
                /* and it is second player's turn */
                AND (played2 IS NULL OR played2 < played1);
        END IF;
END
$func$ LANGUAGE plpgsql;



Re: How to delete few elements from array beginning?

От
Chris Travers
Дата:


On Wed, Mar 9, 2016 at 1:10 PM, Alexander Farber <alexander.farber@gmail.com> wrote:
Hello fellow PostgreSQL users,

what is please the most efficient way to delete a slice from the start of a longer array (after I have copied it to another array)?

Do I really have to copy a large slice of the array to itself, like in the last line here:

        pile_array := pile_array || swap_array;

        /* here I copy away swap_len elements */
        new_hand := pile_array[1:swap_len];

        /* here I don't know how to efficiently remove already copied elements */
        pile_array := pile_array[(swap_len + 1):ARRAY_LENGTH(pile_array, 1)];

or is there a better way?

This looks like something for card hands?

What you are doing seems correct to me.

Thank you
Alex

P.S. The listing of the entire stored function in question:

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
        i           integer;
        j           integer;
        swap_len    integer;
        hand_len    integer;
        pile_len    integer;
        swap_array  varchar[];
        pile_array  varchar[];
        old_hand    varchar[];
        new_hand    varchar[];
        hand_ignore boolean[];
BEGIN
        swap_array := STRING_TO_ARRAY(in_swap, NULL);
        swap_len := ARRAY_LENGTH(swap_array, 1);

        SELECT hand1, pile, ARRAY_LENGTH(hand1, 1), ARRAY_LENGTH(pile, 1)
        INTO old_hand, pile_array, hand_len, pile_len
        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, ARRAY_LENGTH(hand2, 1), ARRAY_LENGTH(pile, 1)
                INTO old_hand, pile_array, hand_len, pile_len
                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;

        pile_array := pile_array || swap_array;
        -- pile_array := words_shuffle(pile_array);
        new_hand := pile_array[1:swap_len];
        pile_array := pile_array[(swap_len + 1):pile_len]; /* XXX is it good? */

        hand_ignore := ARRAY_FILL(FALSE, ARRAY[hand_len]);

        <<hand_loop>>
        FOR i IN 1..hand_len LOOP
                FOR j IN 1..swap_len LOOP
                        IF hand_ignore[j] = FALSE AND
                           old_hand[i] = swap_array[j] THEN
                                hand_ignore[j] := TRUE;
                                CONTINUE hand_loop;
                        END IF;
                END LOOP;

                new_hand := new_hand || old_hand[i];
        END LOOP;
/*
        UPDATE words_games
        SET hand1 = new_hand,
        pile = pile_array,
        played1 = CURRENT_TIMESTAMP
        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
                UPDATE words_games
                SET hand2 = new_hand,
                pile = pile_array,
                played2 = CURRENT_TIMESTAMP
                WHERE gid = in_gid
                AND player2 = in_uid
                -- and it is second player's turn
                AND (played2 IS NULL OR played2 < played1);
        END IF;
*/

END
$func$ LANGUAGE plpgsql;






--
Best Wishes,
Chris Travers

Efficito:  Hosted Accounting and ERP.  Robust and Flexible.  No vendor lock-in.

Re: How to delete few elements from array beginning?

От
Alexander Farber
Дата:
Hello Chris,

On Wed, Mar 9, 2016 at 4:42 PM, Chris Travers <chris.travers@gmail.com> wrote:


On Wed, Mar 9, 2016 at 1:10 PM, Alexander Farber <alexander.farber@gmail.com> wrote:

what is please the most efficient way to delete a slice from the start of a longer array (after I have copied it to another array)?

Do I really have to copy a large slice of the array to itself, like in the last line here:

        pile_array := pile_array || swap_array;

        /* here I copy away swap_len elements */
        new_hand := pile_array[1:swap_len];

        /* here I don't know how to efficiently remove already copied elements */
        pile_array := pile_array[(swap_len + 1):ARRAY_LENGTH(pile_array, 1)];

or is there a better way?

This looks like something for card hands?

What you are doing seems correct to me.


actually card hands would be easier - because cards are unique in the deck.

But here I have letter hands (like "AAABCDE") in a word game and they are not unique in the pile...

Regards
Alex

Re: How to delete few elements from array beginning?

От
Chris Travers
Дата:


On Wed, Mar 9, 2016 at 4:53 PM, Alexander Farber <alexander.farber@gmail.com> wrote:
Hello Chris,

On Wed, Mar 9, 2016 at 4:42 PM, Chris Travers <chris.travers@gmail.com> wrote:


On Wed, Mar 9, 2016 at 1:10 PM, Alexander Farber <alexander.farber@gmail.com> wrote:

what is please the most efficient way to delete a slice from the start of a longer array (after I have copied it to another array)?

Do I really have to copy a large slice of the array to itself, like in the last line here:

        pile_array := pile_array || swap_array;

        /* here I copy away swap_len elements */
        new_hand := pile_array[1:swap_len];

        /* here I don't know how to efficiently remove already copied elements */
        pile_array := pile_array[(swap_len + 1):ARRAY_LENGTH(pile_array, 1)];

or is there a better way?

This looks like something for card hands?

What you are doing seems correct to me.


actually card hands would be easier - because cards are unique in the deck.

But here I have letter hands (like "AAABCDE") in a word game and they are not unique in the pile...

But it seems like a similar problem.  Namely:

1.  You have an ordered list of cards (these may be lettered cards).  These start out as existing in a shuffled deck but once shuffled you have an order.  Whether or not the cards are unque

2.  When you draw a card, you have to remove it from the head of the list.

Now on to some basic points (though you can probably do this in a straight SQL query):

SQL arrays are more or less like math matrices.  For this reason it doesn't make sense to treat them as programming structures per se.  Instead you have a matrix and you create another matrix by slicing it. So this is how you have to think about the problem.

Also consider that PostgreSQL tuples are copy on write anyway.

Now, if you want something that uses an array more like a queue, it is best to write that portion in pl/perl.  However if you do that you have to think carefully about mutability.

Hope this helps
Chris Travers

Regards
Alex




--
Best Wishes,
Chris Travers

Efficito:  Hosted Accounting and ERP.  Robust and Flexible.  No vendor lock-in.