pg.ddx.io  pgsql-general@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Martin Kalcher <martin.kalcher@aboutsource.net>
To: Thomas Munro <thomas.munro@gmail.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Proposal to introduce a shuffle function to intarray extension
Date: Sun, 17 Jul 2022 04:25:27 +0200
Message-ID: <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net> (raw)
In-Reply-To: <CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com>
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net>
	<CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com>

Am 16.07.22 um 23:56 schrieb Thomas Munro:
> On Fri, Jul 15, 2022 at 8:36 PM Martin Kalcher
> <martin.kalcher@aboutsource.net> wrote:
>> I would like to see a function like this inside the intarray extension.
>> Is there any way to get to this point? How is the process to deal with
>> such proposals?
> 
> Hi Martin,
> 
> I'm redirecting this to the pgsql-hackers@ mailing list, where we talk
> about code.  For the archives, Martin's initial message to -general
> was:
> 
> https://www.postgresql.org/message-id/9d160a44-7675-51e8-60cf-6d64b76db831%40aboutsource.net
> 
> The first question is whether such a thing belongs in an external
> extension, or in the contrib/intarray module.  The latter seems like a
> reasonable thing to want to me.  The first step towards that will be
> to get your code into .patch format, as in git format-patch or git
> diff, that can be applied to the master branch.
> 
> https://wiki.postgresql.org/wiki/Submitting_a_Patch
> 
> Some initial feedback from me: I'd recommend adding a couple of
> comments to the code, like the algorithm name for someone who wants to
> read more about it  (I think it's a Fisher-Yates shuffle?). You'll
> need to have the contrib/intarrays/intarray--1.5--1.6.sql file that
> creates the function.  You might want to add something to
> control/intarray/sql/_int.sql that invokes the function when you run
> make check in there (but doesn't display the results, since that'd be
> unstable across machines?), just to have 'code coverage' (I mean, it'd
> prove it doesn't crash at least).  Once details are settled, you'd
> also want to add documentation in doc/src/sgml/intarray.sgml.  I
> understand that this is a specialised int[] shuffle, but I wonder if
> someone would ever want to have a general array shuffle, and how that
> would work, in terms of naming convention etc.

Hello Thomas,

Thank you for pointing me towards the correct list.

I do not feel qualified to answer the question wether this belongs in an 
external extension or in contrib/intarray. That reason i would like to 
see it in contrib/intarray is, that it is lot easier for me to get our 
operations team to upgrade our database system, because of new features 
we need, than to get them to install a self-maintained extension on our 
database servers.

Thank you for your feedback. I tried to address all your points and made 
a first patch. Some points are still open:

- Documentation is postponed until further feedback.

- I am not shure about the naming. intarray has generic names like
   sort() and uniq() and specialised names like icount(). I guess in case
   someone wants to have a general array shuffle it could be accomplished
   with function overloading. Or am i wrong here?

- I added a second function sample(), because it is a lot faster to take
   some elements from an array than to shuffle the whole array and
   slice it. This function can be removed if it is not wanted. The
   important one is shuffle().

Martin

Attachments:

0001-Introduce-shuffle-and-sample-to-intarray-extension.patch (text/x-patch, 7.8K) download From 2c6c28755416556597188c323604ec975faffa25 Mon Sep 17 00:00:00 2001 From: Martin Kalcher <martin.kalcher@aboutsource.net> Date: Sun, 17 Jul 2022 01:53:05 +0200 Subject: [PATCH] Introduce shuffle() and sample() to intarray extension * shuffle(arr) returns an array with the elements of the provided array in random order * sample(arr, n) returns an array with n randomly-chosen elements from the provided array --- contrib/intarray/Makefile | 4 +- contrib/intarray/_int.h | 2 + contrib/intarray/_int_op.c | 35 +++++++++++++++ contrib/intarray/_int_tool.c | 57 +++++++++++++++++++++++++ contrib/intarray/expected/_int.out | 36 ++++++++++++++++ contrib/intarray/intarray--1.5--1.6.sql | 16 +++++++ contrib/intarray/intarray.control | 2 +- contrib/intarray/sql/_int.sql | 6 +++ 8 files changed, 155 insertions(+), 3 deletions(-) create mode 100644 contrib/intarray/intarray--1.5--1.6.sql diff --git a/contrib/intarray/Makefile b/contrib/intarray/Makefile index 3817c1669a..1a79c359ed 100644 --- a/contrib/intarray/Makefile +++ b/contrib/intarray/Makefile @@ -12,8 +12,8 @@ OBJS = \ _intbig_gist.o EXTENSION = intarray -DATA = intarray--1.4--1.5.sql intarray--1.3--1.4.sql intarray--1.2--1.3.sql \ - intarray--1.2.sql intarray--1.1--1.2.sql \ +DATA = intarray--1.5--1.6.sql intarray--1.4--1.5.sql intarray--1.3--1.4.sql \ + intarray--1.2--1.3.sql intarray--1.2.sql intarray--1.1--1.2.sql \ intarray--1.0--1.1.sql PGFILEDESC = "intarray - functions and operators for arrays of integers" diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h index 304c29525c..eaa7a09ae8 100644 --- a/contrib/intarray/_int.h +++ b/contrib/intarray/_int.h @@ -123,6 +123,8 @@ bool inner_int_overlap(ArrayType *a, ArrayType *b); bool inner_int_contains(ArrayType *a, ArrayType *b); ArrayType *inner_int_union(ArrayType *a, ArrayType *b); ArrayType *inner_int_inter(ArrayType *a, ArrayType *b); +void inner_int_shuffle(ArrayType *a); +ArrayType *inner_int_sample(ArrayType *a, int n); void rt__int_size(ArrayType *a, float *size); void gensign(BITVECP sign, int *a, int len, int siglen); diff --git a/contrib/intarray/_int_op.c b/contrib/intarray/_int_op.c index 5b164f6788..8c4edf6ddf 100644 --- a/contrib/intarray/_int_op.c +++ b/contrib/intarray/_int_op.c @@ -167,6 +167,8 @@ PG_FUNCTION_INFO_V1(sort); PG_FUNCTION_INFO_V1(sort_asc); PG_FUNCTION_INFO_V1(sort_desc); PG_FUNCTION_INFO_V1(uniq); +PG_FUNCTION_INFO_V1(shuffle); +PG_FUNCTION_INFO_V1(sample); PG_FUNCTION_INFO_V1(idx); PG_FUNCTION_INFO_V1(subarray); PG_FUNCTION_INFO_V1(intarray_push_elem); @@ -255,6 +257,39 @@ uniq(PG_FUNCTION_ARGS) PG_RETURN_POINTER(a); } +Datum +shuffle(PG_FUNCTION_ARGS) +{ + ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0); + + CHECKARRVALID(a); + inner_int_shuffle(a); + PG_RETURN_POINTER(a); +} + +Datum +sample(PG_FUNCTION_ARGS) +{ + ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0); + ArrayType *r; + + int n = PG_GETARG_INT32(1); + + CHECKARRVALID(a); + + if (n >= ARRNELEMS(a)) + PG_RETURN_POINTER(a); + + if (n < 0) + ereport(ERROR, + (errcode(ERRCODE_INVALID_PARAMETER_VALUE), + errmsg("second parameter must not be negative"))); + + r = inner_int_sample(a, n); + PG_FREE_IF_COPY(a, 0); + PG_RETURN_POINTER(r); +} + Datum idx(PG_FUNCTION_ARGS) { diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c index 8ed4d63fc3..b26c910deb 100644 --- a/contrib/intarray/_int_tool.c +++ b/contrib/intarray/_int_tool.c @@ -179,6 +179,63 @@ inner_int_inter(ArrayType *a, ArrayType *b) return resize_intArrayType(r, k); } +void +inner_int_shuffle(ArrayType *a) +{ + int *d = ARRPTR(a); + int n = ARRNELEMS(a); + int i, tmp; + + /* + * Shuffling is done using the Fisher-Yates shuffle algorithm: + * Iterate through the array and swap the current head with a + * randomly-chosen element from behind the current head (possibly + * the head itself). + */ + while (n > 1) + { + i = random() % n; + tmp = d[i]; + d[i] = *d; + *d = tmp; + d++; + n--; + } +} + +ArrayType * +inner_int_sample(ArrayType *a, int n) +{ + ArrayType *r; + int *da, + *dr; + int na = ARRNELEMS(a); + + n = Min(na, n); + r = new_intArrayType(n); + da = ARRPTR(a), + dr = ARRPTR(r); + + /* + * Choosing samples is done using a variant of the "inside-out" + * Fisher-Yates shuffle algorithm: + * Iterate through the source array, move a randomly-chosen + * element from behind the current head (or the head itself) to + * the destination array and replace it with the current head. + */ + while (n > 0) + { + int i = random() % na; + *dr = da[i]; + da[i] = *da; + dr++; + n--; + da++; + na--; + } + return r; +} + void rt__int_size(ArrayType *a, float *size) { diff --git a/contrib/intarray/expected/_int.out b/contrib/intarray/expected/_int.out index a09d40efa1..cffa683ffe 100644 --- a/contrib/intarray/expected/_int.out +++ b/contrib/intarray/expected/_int.out @@ -85,6 +85,42 @@ SELECT subarray('{1234234,-30,-30,234234,-30}',0,-1); {1234234,-30,-30,234234} (1 row) +SELECT sort(shuffle('{1234234,-30,-30,234234,-30}')); + sort +------------------------------ + {-30,-30,-30,234234,1234234} +(1 row) + +SELECT shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}') != shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}'); + ?column? +---------- + t +(1 row) + +SELECT icount(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6)); + icount +-------- + 6 +(1 row) + +SELECT icount(uniq(sort(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6)))); + icount +-------- + 6 +(1 row) + +SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) <@ '{1,2,3,4,5,6,7,8,9,10,11,12}'; + ?column? +---------- + t +(1 row) + +SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) != sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6); + ?column? +---------- + t +(1 row) + SELECT #'{1234234,234234}'::int[]; ?column? ---------- diff --git a/contrib/intarray/intarray--1.5--1.6.sql b/contrib/intarray/intarray--1.5--1.6.sql new file mode 100644 index 0000000000..5d5ef8ee01 --- /dev/null +++ b/contrib/intarray/intarray--1.5--1.6.sql @@ -0,0 +1,16 @@ +/* contrib/intarray/intarray--1.5--1.6.sql */ + +-- complain if script is sourced in psql, rather than via ALTER EXTENSION +\echo Use "ALTER EXTENSION intarray UPDATE TO '1.6'" to load this file. \quit + +-- Add shuffle functions + +CREATE FUNCTION shuffle(_int4) +RETURNS _int4 +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; + +CREATE FUNCTION sample(_int4, int4) +RETURNS _int4 +AS 'MODULE_PATHNAME' +LANGUAGE C STRICT; diff --git a/contrib/intarray/intarray.control b/contrib/intarray/intarray.control index c3ff753e2c..6ae8881f15 100644 --- a/contrib/intarray/intarray.control +++ b/contrib/intarray/intarray.control @@ -1,6 +1,6 @@ # intarray extension comment = 'functions, operators, and index support for 1-D arrays of integers' -default_version = '1.5' +default_version = '1.6' module_pathname = '$libdir/_int' relocatable = true trusted = true diff --git a/contrib/intarray/sql/_int.sql b/contrib/intarray/sql/_int.sql index b26fc57e4d..3eb15d5c08 100644 --- a/contrib/intarray/sql/_int.sql +++ b/contrib/intarray/sql/_int.sql @@ -18,6 +18,12 @@ SELECT idx('{1234234,-30,-30,234234,-30}',-30); SELECT subarray('{1234234,-30,-30,234234,-30}',2,3); SELECT subarray('{1234234,-30,-30,234234,-30}',-1,1); SELECT subarray('{1234234,-30,-30,234234,-30}',0,-1); +SELECT sort(shuffle('{1234234,-30,-30,234234,-30}')); +SELECT shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}') != shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}'); +SELECT icount(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6)); +SELECT icount(uniq(sort(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6)))); +SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) <@ '{1,2,3,4,5,6,7,8,9,10,11,12}'; +SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) != sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6); SELECT #'{1234234,234234}'::int[]; SELECT '{123,623,445}'::int[] + 1245; -- 2.37.1

view thread (25+ messages)  latest in thread

Message-ID: <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net>
Permalink:  ../b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net/
Also on:    postgresql.org/message-id/b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net

 ·  · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients from your mail client; the link fills in
  the headers below: reply via email
  Some clients, webmail especially, drop In-Reply-To and References from
  a link, and the reply then starts a new thread: use the mbox below.

  To: pgsql-general@postgresql.org
  Cc: martin.kalcher@aboutsource.net, thomas.munro@gmail.com, pgsql-hackers@lists.postgresql.org
  Subject: Re: Proposal to introduce a shuffle function to intarray extension
  In-Reply-To: <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net>
  References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> <CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com> <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox