Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit53d3daa

Browse files
committed
Specialize intarray sorting
There is at least one report in the field of storing millions ofintegers in arrays, so it seems like a good time to specializeintarray's qsort function. In doing so, streamline the comparators:Previously there were three, two for each direction for sortingand one passed to qunique_arg. To preserve the early exit in thecase of descending input, pass the direction as an argument tothe comparator. This requires giving up duplicate detection, whichpreviously allowed skipping the qunique_arg() call. Testing showedno regressions this way.In passing, get rid of nearby checks that the input has at leasttwo elements, since preserving them would make some macros lessreadable. These are not necessary for correctness, and seem likepremature optimizations.Author: Andrey M. Borodin <x4mmm@yandex-team.ru>Discussion:https://postgr.es/m/098A3E67-E4A6-4086-9C66-B1EAEB1DFE1C@yandex-team.ru
1 parent164bac9 commit53d3daa

File tree

2 files changed

+34
-48
lines changed

2 files changed

+34
-48
lines changed

‎contrib/intarray/_int.h

Lines changed: 8 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -41,17 +41,17 @@ typedef struct
4141
#defineSORT(x) \
4242
do { \
4343
int_nelems_ = ARRNELEMS(x); \
44-
if (_nelems_ > 1) \
45-
isort(ARRPTR(x), _nelems_); \
44+
bool _ascending = true; \
45+
isort(ARRPTR(x), _nelems_, &_ascending); \
4646
} while(0)
4747

4848
/* sort the elements of the array and remove duplicates */
4949
#definePREPAREARR(x) \
5050
do { \
5151
int_nelems_ = ARRNELEMS(x); \
52-
if (_nelems_ > 1) \
53-
if (isort(ARRPTR(x), _nelems_)) \
54-
(x) = _int_unique(x); \
52+
bool _ascending = true; \
53+
isort(ARRPTR(x), _nelems_, &_ascending); \
54+
(x) = _int_unique(x); \
5555
} while(0)
5656

5757
/* "wish" function */
@@ -109,7 +109,7 @@ typedef struct
109109
/*
110110
* useful functions
111111
*/
112-
boolisort(int32*a,intlen);
112+
voidisort(int32*a,size_tlen,void*arg);
113113
ArrayType*new_intArrayType(intnum);
114114
ArrayType*copy_intArrayType(ArrayType*a);
115115
ArrayType*resize_intArrayType(ArrayType*a,intnum);
@@ -176,16 +176,12 @@ boolexecconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot);
176176
boolgin_bool_consistent(QUERYTYPE*query,bool*check);
177177
boolquery_has_required_values(QUERYTYPE*query);
178178

179-
intcompASC(constvoid*a,constvoid*b);
180-
intcompDESC(constvoid*a,constvoid*b);
181-
182179
/* sort, either ascending or descending */
183180
#defineQSORT(a,direction) \
184181
do { \
185182
int_nelems_ = ARRNELEMS(a); \
186-
if (_nelems_ > 1) \
187-
qsort((void*) ARRPTR(a), _nelems_, sizeof(int32), \
188-
(direction) ? compASC : compDESC ); \
183+
bool _ascending = (direction) ? true : false; \
184+
isort(ARRPTR(a), _nelems_, &_ascending); \
189185
} while(0)
190186

191187
#endif/* ___INT_H__ */

‎contrib/intarray/_int_tool.c

Lines changed: 26 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -186,36 +186,38 @@ rt__int_size(ArrayType *a, float *size)
186186
*size= (float)ARRNELEMS(a);
187187
}
188188

189-
/*qsort_argcomparison function for isort() */
190-
staticint
189+
/* comparison function for isort() and _int_unique() */
190+
staticinlineint
191191
isort_cmp(constvoid*a,constvoid*b,void*arg)
192192
{
193193
int32aval=*((constint32*)a);
194194
int32bval=*((constint32*)b);
195195

196-
if (aval<bval)
197-
return-1;
198-
if (aval>bval)
199-
return1;
200-
201-
/*
202-
* Report if we have any duplicates. If there are equal keys, qsort must
203-
* compare them at some point, else it wouldn't know whether one should go
204-
* before or after the other.
205-
*/
206-
*((bool*)arg)= true;
196+
if (*((bool*)arg))
197+
{
198+
/* compare for ascending order */
199+
if (aval<bval)
200+
return-1;
201+
if (aval>bval)
202+
return1;
203+
}
204+
else
205+
{
206+
if (aval>bval)
207+
return-1;
208+
if (aval<bval)
209+
return1;
210+
}
207211
return0;
208212
}
209213

210-
/* Sort the given data (len >= 2). Return true if any duplicates found */
211-
bool
212-
isort(int32*a,intlen)
213-
{
214-
boolr= false;
215-
216-
qsort_arg(a,len,sizeof(int32),isort_cmp,&r);
217-
returnr;
218-
}
214+
#defineST_SORT isort
215+
#defineST_ELEMENT_TYPE int32
216+
#defineST_COMPARE(a,b,ascending) isort_cmp(a, b, ascending)
217+
#defineST_COMPARE_ARG_TYPE void
218+
#defineST_SCOPE
219+
#defineST_DEFINE
220+
#include"lib/sort_template.h"
219221

220222
/* Create a new int array with room for "num" elements */
221223
ArrayType*
@@ -311,10 +313,10 @@ ArrayType *
311313
_int_unique(ArrayType*r)
312314
{
313315
intnum=ARRNELEMS(r);
314-
boolduplicates_found;/* not used */
316+
boolascending= true;
315317

316318
num=qunique_arg(ARRPTR(r),num,sizeof(int),isort_cmp,
317-
&duplicates_found);
319+
&ascending);
318320

319321
returnresize_intArrayType(r,num);
320322
}
@@ -393,15 +395,3 @@ int_to_intset(int32 elem)
393395
aa[0]=elem;
394396
returnresult;
395397
}
396-
397-
int
398-
compASC(constvoid*a,constvoid*b)
399-
{
400-
returnpg_cmp_s32(*(constint32*)a,*(constint32*)b);
401-
}
402-
403-
int
404-
compDESC(constvoid*a,constvoid*b)
405-
{
406-
returnpg_cmp_s32(*(constint32*)b,*(constint32*)a);
407-
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp