[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: |
xypron |
Subject: |
Re: [Help-glpk] Building set of sets from plain set - efficient implementation |
Date: |
Wed, 10 Dec 2008 10:00:29 -0800 (PST) |
Hello Andrew,
>> 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.
Best regards
Xypron
--
View this message in context:
http://www.nabble.com/Building-set-of-sets-from-plain-set-tp20927524p20940602.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.
Re: [Help-glpk] Building set of sets from plain set - efficient implementation,
xypron <=
- 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, 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