Forums > Dev

Concept Lattice Galois ?

October 28, 2010 | 6:18 am

Hello maxers,

just in case :

i’m reading papers on "Treillis de Galois" and i’m thinking about doing an external with that for tidy up MIDI data stream ; is anybody have experiences to share with that kind of algorithm ?


November 25, 2010 | 7:15 am

Hello maxers,

that’s a general coding question …

in my external i’m building a concept lattice ; to store attributes (itemset) of each concept, i have implemented an array of char with the nomber of attributes as size (1/0 for yes/no). It works ; But as 90% of CPU cost of my external is spend comparing itemset (inclusion/intersection) : i’m thinking to improve it.

long concept_inclusion (t_romeo *x, char *ptr)
	{
		long i ;
		long k = 2 ;
		long t = 0 ;

		for (i = 0 ; i < TAILLE_DESCRIPTEURS ; i++)
			{
				if (x->intersection[i] = (ptr[i] && x->vecteur[i]))
					{
						 t ++ ;
					}
				else if (ptr[i])
					{
						k = 0 ;
					}
				else if (x->vecteur[i] && k == 2)
					{
						k = 1 ;
					}
			}

		x->cardinal_intersection = t ;

		return k ;
	}

the function return 0 if PTR itemset is not include in VECTEUR itemset, 1 if it is, and 2 if itemsets are exactly the same ; the function compute itemsets intersection in each case.

1. is there an easy way to improve this function ?

2. as i have 128 items, i thought about coding them as bits with 4 long ? and use bit operation ; but as i’m not experience enought with that :
– do you think it will be really more efficient.
– do i have to care with endianness (i think i don’t but … ) ?
– tips and tricks ?

Thanks anyway …


November 25, 2010 | 5:24 pm

Hello maxers,

finally speed up the process x4 using four ulong …

Maybe a 128 bits data type is best ?


November 30, 2010 | 1:51 pm

Just saw your posts…

if statements are relatively expensive. Use them when you need them, but be careful about using them when you don’t really need them. For instance, in your code above, you evaluate ptr[i] twice in the chain of if…else if statements. You might get slightly better performance with

if (ptr[i]) {
  if (x->vecteur[i]) t += 1;
  else               k = 0;
  }
  //etc.

You might also find that you can improve loop performance by breaking out of the main loop the first time k is set to 1, then following up with a second loop that skips the test of that flag. Something like this [WARNING--UNTESTED CODE]

for (i = 0; i < TAILLE_DESCRIPTEURS; i += 1) {
  // ASSERT: (k == 2)
  if (ptr[i]) {
    if (x->vecteur[i]) t += 1;
    else               {k = 0; break;}
    }
  else if (x->vecteur[i]) {
    k = 1;
    break;
    }
  }
// Complete tests for any remaining vector items
while (++i < TAILLE_DESCRIPTEURS) {
  // ASSERT: (k != 2)
  if (ptr[i]) {
    if (x->vecteur[i]) t += 1;
    else               k = 0;
    }
  }

The only way to know for sure which of these alternatives gives the best performance is to test them. But if your original loop really is an embouteillage, either alternative ought to improve performance.

But you’ll often get much better performance from a bit vector, if it’s appropriate for your data. This is what you seem to have done.


November 30, 2010 | 6:17 pm

Hello Peter Castine,

thanks for reply ; not so easy with my uncomplete code …

Yep, i finally did it using bit vectors as ALL the CPU cost of the algorithm was used in this compare function ; the problem was to know if a concept (f.e : {40, 50, 80}) is "include in" or "equal to" another concept (f.e : {40, 50, 60, 100, 120}) and get the intersection in case of not (f.e : {40, 50}) ; as my alphabet is known (midi 0-127) i use a 4 x 32 bit vector size for the operation (instead of arrays as in the code i send previously) …

I was afraid as i never used bit operator before ;-)

I post the resulted external somewhere in the forum …


Viewing 5 posts - 1 through 5 (of 5 total)