[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

View this message in context:
Sent from the Gnu - GLPK - Help mailing list archive at

reply via email to

[Prev in Thread] Current Thread [Next in Thread]