[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Building set of sets from plain set - efficient implemen
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Building set of sets from plain set - efficient implementation |
Date: |
Wed, 10 Dec 2008 21:35:59 +0300 |
>>> set T{k in K, i in I} := setof{(i,j,k,l,m) in S} (j,m,l);
>>> This is implemented in Mathprog as follows:
>>> for all k in K do
>>> { for all i in I do
>>> { T[k,i] := empty;
>>> for all (i',j,k',l,m) in S do
>>> { if i' = i and k' = k then
>>> T[k,i] := T[k,i] union {(j,m,l)}
>>> }
>>> }
>>>}
> as you remarked this implementation is not efficient. I suggest the
> following implementation that will work in O(n log(n)) time:
> 1.) Enumerate the superset {k in K, i in I} domain and collect it into a
> list ( O(n) )
> 2.) Sort the list ( O(n log(n)) )
> 3.) Iterate through the subset domain {(i,j,k,l,m) in S} ( O(n) )
> 3a.) Find the corresponding entry in the list ( O( n log(n)) )
> 3b.) Append the subset entry to the list entry ( O(n)) )
> 4.) Insert the collected sets from the list into the superset ( O(n)) )
> Hence no special syntax is needed.
This would be easy in a programming language. However, in Mathprog
the statement:
set T{k in K, i in I} := setof{(i,j,k,l,m) in S} (j,m,l);
is translated in something like the following procedure:
procedure T(k in K, i in I)
{ find T[k,i] in T array;
if T[k,i] is not found then
{ T[k,i] := setof{(i,j,k,l,m) in S} (j,m,l);
add T[k,i] to T array;
}
return T[k,i];
}
which is called every time on evaluating set expressions containing
references to members of T. Note that initially the T array is empty.
To evaluate all members of T efficiently it is necessary to carry
out the loop 'setof{(i,j,k,l,m) in S}' from the procedure, that is
impossible.
My idea is to use S to create fake data, i.e. as if there were the
following block in the data section:
T[...,...] = ... ... ... ;
T[...,...] = ... ... ... ... ... ;
T[...,...] = ... ... ;
and then to "read" these data into T. Of course, no actual i/o will
be performed.
Do you know if there is a similar operation in the sql language?
Re: [Help-glpk] Building set of sets from plain set - efficient implementation, xypron, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation,
Andrew Makhorin <=
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, xypron, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/10
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/13
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, glpk xypron, 2008/12/13
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/13
- Re: [Help-glpk] Building set of sets from plain set - efficient implementation, Andrew Makhorin, 2008/12/13