1:58 p.m.
As far as I know, we don't have a function for sorting string arrays, so I
implemented quicksort in hansl as shown below.
As you can see, the function sorts the array and returns a vector of
integers so that you can map the old positions to the new ones if needed.
Performance is not at all bad, I'd say.
I'm thinking: would it be worthwhile to add this to the "extra" package?
Or should we have a native C implementation? Also: is this imaginable for
other array types? I can't think of an obvious way to sort bundles or
matrices, but perhaps someone has a clever idea.
<hansl>
set verbose off
function void swap(strings *a, matrix *ndx, scalar i, scalar j)
string s = a[j]
scalar x = ndx[j]
string a[j] = a[i]
scalar ndx[j] = ndx[i]
string a[i] = s
scalar ndx[i] = x
end function
function scalar part(strings *a, matrix *ndx, scalar lo, scalar hi, bool reverse)
string pivot = a[hi]
scalar i = lo
loop j = lo .. (hi-1) --quiet
cmp = strncmp(a[j], pivot)
if (reverse ? cmp > 0 : cmp < 0)
swap(&a, &ndx, i++, j)
endif
endloop
swap(&a, &ndx, i, hi)
return i
end function
function void real_sqsort(strings *a, matrix *ndx, scalar lo, scalar hi, bool reverse)
if lo < hi
p = part(&a, &ndx, lo, hi, reverse)
real_sqsort(&a, &ndx, lo, p-1, reverse)
real_sqsort(&a, &ndx, p+1, hi, reverse)
endif
end function
function matrix strings_sort(strings *A, bool reverse[0])
scalar n = nelem(A)
if n == 1
return {1}
endif
matrix s = seq(1, n)
real_sqsort(&A, &s, 1, n, reverse)
return s
end function
###
### example
###
clear
x = defarray("alpha", "foo", "X", "bar",
"baz", "")
print x
ord = strings_sort(&x)
print x ord
</hansl>
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
3:39 p.m.
Am 11.04.2019 um 12:58 schrieb Riccardo (Jack) Lucchetti:
As far as I know, we don't have a function for sorting string
arrays,
so I implemented quicksort in hansl as shown below.
As you can see, the function sorts the array and returns a vector of
integers so that you can map the old positions to the new ones if
needed. Performance is not at all bad, I'd say.
What about an approach that represents the strings in a numeric fashion
and then leverages the native msortby() function to get the ordering?
I'm thinking: would it be worthwhile to add this to the "extra" package?
What's the use case, by the way?
Speaking about arrays and the extra package: I don't want to hijack your
thread, but I've thought that a function would be useful that takes an
array argument and applies some operation (another function)
automatically to all elements of the array.
cheers
sven
4:07 p.m.
On Thu, 11 Apr 2019, Sven Schreiber wrote:
> I'm thinking: would it be worthwhile to add this to the
"extra" package?
What's the use case, by the way?
I'm using aggregate() on a string-valued variable and I'd like to be able
to sort the results alphabetically.
Speaking about arrays and the extra package: I don't want to
hijack your
thread, but I've thought that a function would be useful that takes an
array argument and applies some operation (another function)
automatically to all elements of the array.
Something like this, you mean?
<hansl>
function matrices apply(const matrices A, string op)
n = nelem(A)
matrices ret = array(n)
loop i = 1 .. n --quiet
ret[i] = feval(op, A[i])
endloop
return ret
end function
matrices A = defarray(I(3), {2,1;1,2})
eval A[1]
eval A[2]
B = apply(A, "inv")
eval B[1]
eval B[2]
C = apply(A, "det")
eval C[1]
eval C[2]
<hansl>
That'd be nice to have as a native funciton, so that we don't have to
write a separate function for every array type we have (unless we find a
mechanism for having "array" as a function argument type).
-------------------------------------------------------
Riccardo (Jack) Lucchetti
Dipartimento di Scienze Economiche e Sociali (DiSES)
Università Politecnica delle Marche
(formerly known as Università di Ancona)
r.lucchetti(a)univpm.it
http://www2.econ.univpm.it/servizi/hpp/lucchetti
-------------------------------------------------------
6:51 p.m.
On Thu, 11 Apr 2019, Riccardo (Jack) Lucchetti wrote:
On Thu, 11 Apr 2019, Sven Schreiber wrote:
> Speaking about arrays and the extra package: I don't want to hijack your
> thread, but I've thought that a function would be useful that takes an
> array argument and applies some operation (another function)
> automatically to all elements of the array.
Something like this, you mean?
<hansl>
function matrices apply(const matrices A, string op)
n = nelem(A)
matrices ret = array(n)
loop i = 1 .. n --quiet
ret[i] = feval(op, A[i])
endloop
return ret
end function
[...]
Ah yes, feval(). I guess that should be documented!
Allin
6:55 p.m.
Am 11.04.19 um 17:51 schrieb Allin Cottrell:
On Thu, 11 Apr 2019, Riccardo (Jack) Lucchetti wrote:
> On Thu, 11 Apr 2019, Sven Schreiber wrote:
>
>> Speaking about arrays and the extra package: I don't want to hijack
>> your
>> thread, but I've thought that a function would be useful that takes an
>> array argument and applies some operation (another function)
>> automatically to all elements of the array.
>
> Something like this, you mean?
>
> <hansl>
> function matrices apply(const matrices A, string op)
> n = nelem(A)
> matrices ret = array(n)
> loop i = 1 .. n --quiet
> ret[i] = feval(op, A[i])
> endloop
> return ret
> end function
Just out of curiosity: Gretl wouldn't compute stuff in parallel
out-of-box, right?
Ah yes, feval(). I guess that should be documented!
feval() is indeed a very nice
function!
Best,
Artur
7:12 p.m.
Am 11.04.2019 um 17:55 schrieb Artur Tarassow:
Just out of curiosity: Gretl wouldn't compute stuff in parallel
out-of-box, right?
Hehe, well if "somebody" implemented the cross-array operation natively
and used OpenMP or stuff like that then perhaps it would... otherwise:
not, I guess.
>
> Ah yes, feval(). I guess that should be documented!
Yeah, I keep forgetting it (I'm a heavy user of gretl's built-in
documentation because I always forget things).
thanks
sven
9:03 p.m.
Am 11.04.19 um 18:12 schrieb Sven Schreiber:
Am 11.04.2019 um 17:55 schrieb Artur Tarassow:
> Just out of curiosity: Gretl wouldn't compute stuff in parallel
> out-of-box, right?
Hehe, well if "somebody" implemented the cross-array operation natively
and used OpenMP or stuff like that then perhaps it would... otherwise:
not, I guess.
Of course, I rather meant (without saying it explicitly) whether there
is some way to exploit C in a simple way to do this. But I guess this is
rather a non-trivial issue...
>
>>
>> Ah yes, feval(). I guess that should be documented!
Yeah, I keep forgetting it (I'm a heavy user of gretl's built-in
documentation because I always forget things).
The same applies to me :-)
Artur
11:20 p.m.
On Thu, 11 Apr 2019, Artur Tarassow wrote:
Am 11.04.19 um 18:12 schrieb Sven Schreiber:
> Am 11.04.2019 um 17:55 schrieb Artur Tarassow:
>> Just out of curiosity: Gretl wouldn't compute stuff in parallel
>> out-of-box, right?
>
> Hehe, well if "somebody" implemented the cross-array operation natively
> and used OpenMP or stuff like that then perhaps it would... otherwise:
> not, I guess.
Of course, I rather meant (without saying it explicitly) whether there is
some way to exploit C in a simple way to do this. But I guess this is rather
a non-trivial issue...
Yes, non-trivial. The thing is, with feval() "anything could happen"
(that is, any part of the libgretl code could be visited as a result
of the function call). Getting this right with OpenMP would require
that libgretl as a whole is thread-safe.
That's a worthy ambition but it's not the case at present. When we
employ OpenMP internally we're careful only to call functions that
we know to be thread-safe.
Also there's the thread-contention issue: if multiple threads called
simultaneously (say) a matrix inversion routine that's itself
multi-threaded (hello, openblas!) the results would probably not be
pretty. (Again, in internal use of OpenMP we take pains to avoid a
cascade of multiple threads each calling multiple threads, but it
wouldn't be easy to extend this to the case of simultaneous calls to
arbitrary libgretl functions.)
Nonetheless, non-trivial \neq impossible, so maybe some day!
Allin
10:07 a.m.
Am 11.04.2019 um 22:20 schrieb Allin Cottrell:
On Thu, 11 Apr 2019, Artur Tarassow wrote:
> Am 11.04.19 um 18:12 schrieb Sven Schreiber:
>> Am 11.04.2019 um 17:55 schrieb Artur Tarassow:
>>> Just out of curiosity: Gretl wouldn't compute stuff in parallel
>>> out-of-box, right?
>>
>> Hehe, well if "somebody" implemented the cross-array operation
natively
>> and used OpenMP or stuff like that then perhaps it would... otherwise:
>> not, I guess.
>
> Of course, I rather meant (without saying it explicitly) whether there
> is some way to exploit C in a simple way to do this. But I guess this
> is rather a non-trivial issue...
Yes, non-trivial. The thing is, with feval() "anything could happen"
(that is, any part of the libgretl code could be visited as a result of
the function call). Getting this right with OpenMP would require that
libgretl as a whole is thread-safe.
Hm, not sure I understand this point in the given context. What I
thought Artur meant is that for a given array of matrices the same
operation should be applied to every array member. That sounds to me
like a natural parallelization task without race conditions and so on.
OK, I guess one has to rule out that the operation itself accesses
sister elements in the same array, and I admit that ensuring this may
not be trivial.
But say you want to apply cdemean() to every matrix in an N-element
matrices array. In principle it wouldn't be too difficult to distribute
that task to different threads/cores, no?
Of course for small arrays the overhead may kill the performance gain.
thanks
sven
1:42 p.m.
Am 12.04.19 um 09:07 schrieb Sven Schreiber:
Am 11.04.2019 um 22:20 schrieb Allin Cottrell:
> On Thu, 11 Apr 2019, Artur Tarassow wrote:
>
>> Am 11.04.19 um 18:12 schrieb Sven Schreiber:
>>> Am 11.04.2019 um 17:55 schrieb Artur Tarassow:
>>>> Just out of curiosity: Gretl wouldn't compute stuff in parallel
>>>> out-of-box, right?
>>>
>>> Hehe, well if "somebody" implemented the cross-array operation
natively
>>> and used OpenMP or stuff like that then perhaps it would... otherwise:
>>> not, I guess.
>>
>> Of course, I rather meant (without saying it explicitly) whether there
>> is some way to exploit C in a simple way to do this. But I guess this
>> is rather a non-trivial issue...
>
> Yes, non-trivial. The thing is, with feval() "anything could happen"
> (that is, any part of the libgretl code could be visited as a result of
> the function call). Getting this right with OpenMP would require that
> libgretl as a whole is thread-safe.
Thanks for the explanation, Allin.
Hm, not sure I understand this point in the given context. What I
thought Artur meant is that for a given array of matrices the same
operation should be applied to every array member. That sounds to me
like a natural parallelization task without race conditions and so on.
OK, I guess one has to rule out that the operation itself accesses
sister elements in the same array, and I admit that ensuring this may
not be trivial.
But say you want to apply cdemean() to every matrix in an N-element
matrices array. In principle it wouldn't be too difficult to distribute
that task to different threads/cores, no?
Yes, that's an example I had in mind. But given that some functions
already natively seem to support multi-threading [at least for big
matrices and certain linear algebra operations I frequently enjoy
watching all cores fully demanded ;-)], there would be no real
value-added in parallelizing stuff. For more complex task, one can
(fortunately) always rely on your 'parallel_specs' package ;-)
Best,
Artur
2:26 p.m.
Am 12.04.2019 um 12:42 schrieb Artur Tarassow:
Yes, that's an example I had in mind. But given that some functions
already natively seem to support multi-threading [at least for big
matrices and certain linear algebra operations I frequently enjoy
watching all cores fully demanded ;-)], there would be no real
value-added in parallelizing stuff. For more complex task, one can
(fortunately) always rely on your 'parallel_specs' package ;-)
So I guess one would have to identify those functions which do get
native multi-threading via BLAS or whatever. But with respect to
parallel_specs, are you actually using it in practice?
thanks
sven
9:02 p.m.
Am 12.04.19 um 13:26 schrieb Sven Schreiber:
Am 12.04.2019 um 12:42 schrieb Artur Tarassow:
>
> Yes, that's an example I had in mind. But given that some functions
> already natively seem to support multi-threading [at least for big
> matrices and certain linear algebra operations I frequently enjoy
> watching all cores fully demanded ;-)], there would be no real
> value-added in parallelizing stuff. For more complex task, one can
> (fortunately) always rely on your 'parallel_specs' package ;-)
>
So I guess one would have to identify those functions which do get
native multi-threading via BLAS or whatever. But with respect to
parallel_specs, are you actually using it in practice?
I use parallel_specs for running model estimation in parallel which can
be distinguished by different sets of regressors or so . To be more
concrete, I ran logit/probit as well ARDL type of models in the past. Of
course parallel_specs could be very useful for cross-validation purpose
as well.
Best,
Artur
4:25 p.m.
Am 12.04.2019 um 20:02 schrieb Artur Tarassow:
Am 12.04.19 um 13:26 schrieb Sven Schreiber:
> So I guess one would have to identify those functions which do
get
> native multi-threading via BLAS or whatever. But with respect to
> parallel_specs, are you actually using it in practice?
>
I use parallel_specs for running model estimation in parallel which can
be distinguished by different sets of regressors or so . To be more
concrete, I ran logit/probit as well ARDL type of models in the past. Of
course parallel_specs could be very useful for cross-validation purpose
as well.
Thanks, that's interesting to hear. I wasn't quite sure whether the
thing is actually robust to use.
-sven
9:18 p.m.
On Fri, 12 Apr 2019, Sven Schreiber wrote:
Am 11.04.2019 um 22:20 schrieb Allin Cottrell:
> On Thu, 11 Apr 2019, Artur Tarassow wrote:
>
>> Am 11.04.19 um 18:12 schrieb Sven Schreiber:
>>> Am 11.04.2019 um 17:55 schrieb Artur Tarassow:
>>>> Just out of curiosity: Gretl wouldn't compute stuff in parallel
>>>> out-of-box, right?
>>>
>>> Hehe, well if "somebody" implemented the cross-array operation
natively
>>> and used OpenMP or stuff like that then perhaps it would... otherwise:
>>> not, I guess.
>>
>> Of course, I rather meant (without saying it explicitly) whether there
>> is some way to exploit C in a simple way to do this. But I guess this
>> is rather a non-trivial issue...
>
> Yes, non-trivial. The thing is, with feval() "anything could happen"
> (that is, any part of the libgretl code could be visited as a result of
> the function call). Getting this right with OpenMP would require that
> libgretl as a whole is thread-safe.
Hm, not sure I understand this point in the given context. What I
thought Artur meant is that for a given array of matrices the same
operation should be applied to every array member.
That was my understanding too.
That sounds to me like a natural parallelization task without race
conditions and so on.
The point is that "the same operation", executed by each of the
threads on its matrix, could involve calls to any gretl function,
built-in or user-defined, that accepts a matrix argument. And we know
that not every such function is currently thread-safe. Libgretl uses
static variables in quite a few places; thread-safe functions cannot
employ such variables without converting them to so-called
thread-local storage (TLS).
This is not an issue with MPI, since when multiple instances of gretl
are running -- as opposed to multiple threads under a single instance
-- each one automatically gets its own memory segment and its own
copies of any static variables.
Allin
10:50 a.m.
Am 11.04.2019 um 15:07 schrieb Riccardo (Jack) Lucchetti:
On Thu, 11 Apr 2019, Sven Schreiber wrote:
>> I'm thinking: would it be worthwhile to add this to the "extra"
package?
>
> What's the use case, by the way?
I'm using aggregate() on a string-valued variable and I'd like to be
able to sort the results alphabetically.
OK sorry, the thread then took a different direction. To be honest there
have been a bunch of ideas about "extra" over the last months (some by
myself) and I haven't really kept track. Probably I need to search the
archives to construct a list of potential additions.
In this particular case, is this still on the table? The alternative was
a C function I think.
> Speaking about arrays and the extra package: I don't want to
hijack your
> thread, but I've thought that a function would be useful that takes an
> array argument and applies some operation (another function)
> automatically to all elements of the array.
Something like this, you mean
...
ret[i] = feval(op, A[i])
...
That'd be nice to have as a native funciton, so that we don't
have to
write a separate function for every array type we have (unless we find a
mechanism for having "array" as a function argument type).
Yes, what about this idea?
BTW, I think there are at least two other theoretical possibilities to
enable the same hansl function for various input types:
1) If each object type only occurs once in the function signature,
loosen the requirement of positional arguments.
Such that for the signature:
function void myfunc(matrices mm[null], strings ss[null])
both these calls would be allowed: myfunc(mymatarr) and myfunc(mystrarr).
2) Named arguments -- this would of course be a substantial undertaking
to implement I guess. So given the likely fallout I'm not sure I like
the idea.
cheers
sven
2204
days inactive
2225
days old
14 comments
4 participants
participants (4)
-
Allin Cottrell -
Artur Tarassow -
Riccardo (Jack) Lucchetti -
Sven Schreiber