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/Makefileindex 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.hindex 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.cindex 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.cindex 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.outindex 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.sqlnew file mode 100644index 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.controlindex 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.sqlindex 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
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