Last active
June 4, 2022 14:16
-
-
Save xflr6/0b48339860abcdbee21ef38239bf36f5 to your computer and use it in GitHub Desktop.
Revisions
-
xflr6 revised this gist
Jun 4, 2022 . 1 changed file with 53 additions and 9 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,5 +1,6 @@ """Compare different brute-force FCA concept generation methods.""" from collections.abc import Iterator, Sequence from itertools import combinations, compress import time @@ -41,10 +42,14 @@ #BOOLS = [b * 100 for b in BOOLS] def concepts_set(objects: Sequence[str], properties: Sequence[str], bools: Sequence[Sequence[int]] ) -> Iterator[tuple[Sequence[str], Sequence[str]]]: """Yield all (extent, intent) pairs in shortlex order.""" P = range(len(properties)) O = range(len(objects)) X = [frozenset(compress(P, b)) for b in bools] Y = [frozenset(compress(O, b)) for b in zip(*bools)] P = frozenset(P) @@ -53,43 +58,57 @@ def concepts_set(objects, properties, bools): for r in range(len(objects) + 1): for cmb in combinations(X, r): prime = P.intersection(*cmb) double = O for i in prime: double &= Y[i] if len(double) == r: intent = tuple(properties[i] for i in sorted(prime)) extent = tuple(objects[i] for i in sorted(double)) yield (extent, intent) def concepts_long(objects: Sequence[str], properties: Sequence[str], bools: Sequence[Sequence[int]] ) -> Iterator[tuple[Sequence[str], Sequence[str]]]: """Yield all (extent, intent) pairs in shortlex order.""" X = [int(''.join(str(x) for x in boo)[::-1], 2) for boo in bools] Y = [int(''.join(str(x) for x in boo)[::-1], 2) for boo in zip(*bools)] P = (1 << len(properties)) - 1 O = (1 << len(objects)) - 1 I = [(i, 1 << i) for i in range(len(properties))] E = [(i, 1 << i) for i in range(len(objects))] for r in range(len(objects) + 1): for cmb in combinations(X, r): prime = P for c in cmb: prime &= c b = prime double = O for y in Y: if b & 1: double &= y b >>= 1 if not b: break if bin(double).count('1') == r: intent = tuple(properties[i] for i, n in I if prime & n) extent = tuple(objects[i] for i, n in E if double & n) yield (extent, intent) def concepts_gmpy2(objects: Sequence[str], properties: Sequence[str], bools: Sequence[Sequence[int]] ) -> Iterator[tuple[Sequence[str], Sequence[str]]]: """Yield all (extent, intent) pairs in shortlex order.""" X = [gmpy2.xmpz(''.join(str(x) for x in boo)[::-1], 2) for boo in bools] Y = [gmpy2.xmpz(''.join(str(x) for x in boo)[::-1], 2) for boo in zip(*bools)] P = gmpy2.xmpz((1 << len(properties)) - 1) @@ -100,16 +119,22 @@ def concepts_gmpy2(objects, properties, bools): prime = P.copy() for c in cmb: prime &= c double = O.copy() for i in prime.iter_set(): double &= Y[i] if double.digits(2).count('1') == r: intent = tuple(properties[i] for i in prime.iter_set()) extent = tuple(objects[i] for i in double.iter_set()) yield (extent, intent) def concepts_numpy(objects: Sequence[str], properties: Sequence[str], bools: Sequence[Sequence[int]] ) -> Iterator[tuple[Sequence[str], Sequence[str]]]: """Yield all (extent, intent) pairs in shortlex order.""" X = np.array(bools, dtype=bool) Y = X.transpose().copy() @@ -119,16 +144,22 @@ def concepts_numpy_bool(objects, properties, bools): for idx in combinations(indexes, r): P = X.take(idx, axis=0) prime = np.logical_and.reduce(P) O = Y.compress(prime, axis=0) double = np.logical_and.reduce(O) if np.count_nonzero(double) == r: intent = tuple(np.compress(prime, properties)) extent = tuple(np.compress(double, objects)) yield (extent, intent) # FIXME: missing infimum and supremum def concepts_numpy_uint64(objects: Sequence[str], properties: Sequence[str], bools: Sequence[Sequence[int]] ) -> Iterator[tuple[Sequence[str], Sequence[str]]]: X = np.packbits(bools, axis=1) X = np.pad(X, ((0, 0), (0, 8 - X.shape[1] % 8)), 'constant').view('uint64') Y = np.packbits(list(zip(*bools)), axis=1) @@ -140,18 +171,24 @@ def concepts_numpy_uint64(objects, properties, bools): P = X.take(idx, axis=0) prime = np.bitwise_and.reduce(P) pbools = np.unpackbits(prime.view('uint8')) O = Y.compress(pbools, axis=0) if not O.size: continue double = np.bitwise_and.reduce(O) dbools = np.unpackbits(double.view('uint8')) if np.count_nonzero(dbools) == r: intent = tuple(np.compress(pbools, properties)) extent = tuple(np.compress(dbools, objects)) yield (extent, intent) def concepts_numpy_bam(objects: Sequence[str], properties: Sequence[str], bools: Sequence[Sequence[int]] ) -> Iterator[tuple[Sequence[str], Sequence[str]]]: X = np.array(bools) X[X == 0] = -max([len(objects), len(properties)]) Y = X.transpose().copy() @@ -163,25 +200,32 @@ def concepts_numpy_bam(objects, properties, bools): o = O.copy() o[list(idx)] = 1 prime = o.dot(X) >= 0 double = prime.dot(Y) >= 0 if np.count_nonzero(double) == r: intent = tuple(np.compress(prime, properties)) extent = tuple(np.compress(double, objects)) yield (extent, intent) concept_funcs = [concepts_set, concepts_long, concepts_gmpy2, concepts_numpy, concepts_numpy_uint64, concepts_numpy_bam] for concepts in concept_funcs: n = 0 start = time.perf_counter_ns() for extent, intent in concepts(OBJECTS, PROPERTIES, BOOLS): print('{%s} <-> [%s]' % (', '.join(extent), ' '.join(intent))) n += 1 concepts.duration = (time.perf_counter_ns() - start) / 1_000_000_000 concepts.n = n print() -
Dec 18, 2021 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,4 +1,4 @@ """Compare different brute-force FCA concept generation methods.""" from itertools import combinations, compress import time -
Aug 1, 2021 . 1 changed file with 9 additions and 6 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -170,18 +170,21 @@ def concepts_numpy_bam(objects, properties, bools): yield (extent, intent) concept_funcs = [concepts_set, concepts_long, concepts_gmpy2, concepts_numpy_bool, concepts_numpy_uint64, concepts_numpy_bam] for concepts in concept_funcs: n = 0 start = time.perf_counter_ns() for extent, intent in concepts(OBJECTS, PROPERTIES, BOOLS): print('{%s} <-> [%s]' % (', '.join(extent), ' '.join(intent))) n += 1 concepts.duration = (time.perf_counter_ns() - start) / 1_000_000_000 concepts.n = n print() for concepts in concept_funcs: print(f'{concepts!r}: {concepts.n:d}, {concepts.duration:.3f} seconds') -
Jan 1, 2021 . 1 changed file with 30 additions and 40 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,46 +1,38 @@ # fca_variants.py - compare different brute-force concept generation methods from itertools import combinations, compress import time import gmpy2 import numpy as np OBJECTS = ('1s', '1de', '1pe', '1di', '1pi', '2s', '2d', '2p', '3s.m', '3s.f', '3s.n', '3d.m', '3d.f', '3d.n', '3p.m', '3p.f', '3p.n') PROPERTIES = ('+1', '-1', '+2', '-2', '+3', '-3', '+sg', '+du', '+pl', '-sg', '-du', '-pl', '+masc', '+fem', '+neut', '-masc', '-fem', '-neut') BOOLS = [(1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), (0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0), (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0), (0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0)] #OBJECTS += OBJECTS[-9:] #BOOLS += BOOLS[-9:] @@ -178,10 +170,8 @@ def concepts_numpy_bam(objects, properties, bools): yield (extent, intent) concept_funcs = [concepts_set, concepts_long, concepts_gmpy2, concepts_numpy_bool, concepts_numpy_uint64, concepts_numpy_bam] for concepts in concept_funcs: n = 0 -
Dec 8, 2019 . 1 changed file with 10 additions and 5 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,7 +1,12 @@ # fca_variants.py - compare different brute-force concept generation methods import sys import time if sys.version_info.major == 2: from itertools import izip as zip from itertools import combinations, compress import gmpy2 import numpy as np @@ -49,7 +54,7 @@ def concepts_set(objects, properties, bools): P = range(len(properties)) O = range(len(objects)) X = [frozenset(compress(P, b)) for b in bools] Y = [frozenset(compress(O, b)) for b in zip(*bools)] P = frozenset(P) O = frozenset(O) @@ -67,7 +72,7 @@ def concepts_set(objects, properties, bools): def concepts_long(objects, properties, bools): X = [int(''.join(str(x) for x in boo)[::-1], 2) for boo in bools] Y = [int(''.join(str(x) for x in boo)[::-1], 2) for boo in zip(*bools)] P = (1 << len(properties)) - 1 O = (1 << len(objects)) - 1 I = [(i, 1 << i) for i in range(len(properties))] @@ -94,7 +99,7 @@ def concepts_long(objects, properties, bools): def concepts_gmpy2(objects, properties, bools): X = [gmpy2.xmpz(''.join(str(x) for x in boo)[::-1], 2) for boo in bools] Y = [gmpy2.xmpz(''.join(str(x) for x in boo)[::-1], 2) for boo in zip(*bools)] P = gmpy2.xmpz((1 << len(properties)) - 1) O = gmpy2.xmpz((1 << len(objects)) - 1) @@ -134,7 +139,7 @@ def concepts_numpy_bool(objects, properties, bools): def concepts_numpy_uint64(objects, properties, bools): X = np.packbits(bools, axis=1) X = np.pad(X, ((0, 0), (0, 8 - X.shape[1] % 8)), 'constant').view('uint64') Y = np.packbits(list(zip(*bools)), axis=1) Y = np.pad(Y, ((0, 0), (0, 8 - Y.shape[1] % 8)), 'constant').view('uint64') indexes = range(len(objects)) -
Sep 4, 2018 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,192 @@ # fca_variants.py - compare different brute-force concept generation methods import time from itertools import combinations, compress, izip import gmpy2 import numpy as np OBJECTS = ( '1s', '1de', '1pe', '1di', '1pi', '2s', '2d', '2p', '3s.m', '3s.f', '3s.n', '3d.m', '3d.f', '3d.n', '3p.m', '3p.f', '3p.n' ) PROPERTIES = ( '+1', '-1', '+2', '-2', '+3', '-3', '+sg', '+du', '+pl', '-sg', '-du', '-pl', '+masc', '+fem', '+neut', '-masc', '-fem', '-neut' ) BOOLS = [ (1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0), (1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0), (0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0), (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0), (0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1), (0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1), (0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0) ] #OBJECTS += OBJECTS[-9:] #BOOLS += BOOLS[-9:] #PROPERTIES = PROPERTIES * 100 #BOOLS = [b * 100 for b in BOOLS] def concepts_set(objects, properties, bools): """Yield all (extent, intent) pairs in shortlex order.""" P = range(len(properties)) O = range(len(objects)) X = [frozenset(compress(P, b)) for b in bools] Y = [frozenset(compress(O, b)) for b in izip(*bools)] P = frozenset(P) O = frozenset(O) for r in range(len(objects) + 1): for cmb in combinations(X, r): prime = P.intersection(*cmb) double = O for i in prime: double &= Y[i] if len(double) == r: intent = tuple(properties[i] for i in sorted(prime)) extent = tuple(objects[i] for i in sorted(double)) yield (extent, intent) def concepts_long(objects, properties, bools): X = [int(''.join(str(x) for x in boo)[::-1], 2) for boo in bools] Y = [int(''.join(str(x) for x in boo)[::-1], 2) for boo in izip(*bools)] P = (1 << len(properties)) - 1 O = (1 << len(objects)) - 1 I = [(i, 1 << i) for i in range(len(properties))] E = [(i, 1 << i) for i in range(len(objects))] for r in range(len(objects) + 1): for cmb in combinations(X, r): prime = P for c in cmb: prime &= c b = prime double = O for y in Y: if b & 1: double &= y b >>= 1 if not b: break if bin(double).count('1') == r: intent = tuple(properties[i] for i, n in I if prime & n) extent = tuple(objects[i] for i, n in E if double & n) yield (extent, intent) def concepts_gmpy2(objects, properties, bools): X = [gmpy2.xmpz(''.join(str(x) for x in boo)[::-1], 2) for boo in bools] Y = [gmpy2.xmpz(''.join(str(x) for x in boo)[::-1], 2) for boo in izip(*bools)] P = gmpy2.xmpz((1 << len(properties)) - 1) O = gmpy2.xmpz((1 << len(objects)) - 1) for r in range(len(objects) + 1): for cmb in combinations(X, r): prime = P.copy() for c in cmb: prime &= c double = O.copy() for i in prime.iter_set(): double &= Y[i] if double.digits(2).count('1') == r: intent = tuple(properties[i] for i in prime.iter_set()) extent = tuple(objects[i] for i in double.iter_set()) yield (extent, intent) def concepts_numpy_bool(objects, properties, bools): """Yield all (extent, intent) pairs in shortlex order.""" X = np.array(bools, dtype=bool) Y = X.transpose().copy() indexes = range(len(objects)) for r in range(len(indexes) + 1): for idx in combinations(indexes, r): P = X.take(idx, axis=0) prime = np.logical_and.reduce(P) O = Y.compress(prime, axis=0) double = np.logical_and.reduce(O) if np.count_nonzero(double) == r: intent = tuple(np.compress(prime, properties)) extent = tuple(np.compress(double, objects)) yield (extent, intent) # FIXME: missing infimum and supremum def concepts_numpy_uint64(objects, properties, bools): X = np.packbits(bools, axis=1) X = np.pad(X, ((0, 0), (0, 8 - X.shape[1] % 8)), 'constant').view('uint64') Y = np.packbits(zip(*bools), axis=1) Y = np.pad(Y, ((0, 0), (0, 8 - Y.shape[1] % 8)), 'constant').view('uint64') indexes = range(len(objects)) for r in range(1, len(indexes) + 1): for idx in combinations(indexes, r): P = X.take(idx, axis=0) prime = np.bitwise_and.reduce(P) pbools = np.unpackbits(prime.view('uint8')) O = Y.compress(pbools, axis=0) if not O.size: continue double = np.bitwise_and.reduce(O) dbools = np.unpackbits(double.view('uint8')) if np.count_nonzero(dbools) == r: intent = tuple(np.compress(pbools, properties)) extent = tuple(np.compress(dbools, objects)) yield (extent, intent) def concepts_numpy_bam(objects, properties, bools): X = np.array(bools) X[X == 0] = -max([len(objects), len(properties)]) Y = X.transpose().copy() O = np.zeros(len(objects), int) indexes = range(len(objects)) for r in range(len(indexes) + 1): for idx in combinations(indexes, r): o = O.copy() o[list(idx)] = 1 prime = o.dot(X) >= 0 double = prime.dot(Y) >= 0 if np.count_nonzero(double) == r: intent = tuple(np.compress(prime, properties)) extent = tuple(np.compress(double, objects)) yield (extent, intent) concept_funcs = [ concepts_set, concepts_long, concepts_gmpy2, concepts_numpy_bool, concepts_numpy_uint64, concepts_numpy_bam, ] for concepts in concept_funcs: n = 0 start = time.time() for extent, intent in concepts(OBJECTS, PROPERTIES, BOOLS): print('{%s} <-> [%s]' % (', '.join(extent), ' '.join(intent))) n += 1 concepts.duration = time.time() - start concepts.n = n print for concepts in concept_funcs: print('%r: %d, %.3f seconds' % (concepts, concepts.n, concepts.duration))