Skip to content

Instantly share code, notes, and snippets.

@xflr6

xflr6/fca_variants.py

Last active June 4, 2022 14:16
Show Gist options
  • Save xflr6/0b48339860abcdbee21ef38239bf36f5 to your computer and use it in GitHub Desktop.
Save xflr6/0b48339860abcdbee21ef38239bf36f5 to your computer and use it in GitHub Desktop.
Download ZIP
Compare different methods to brute-force FCA concept generation (sets, longs, gmpy2, NumPy bools, Numpy uint64)
Raw
fca_variants.py
"""Compare different brute-force FCA concept generation methods."""
from collections.abc import Iterator, Sequence
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:]
#PROPERTIES = PROPERTIES * 100
#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)
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: 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)
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(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()
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: 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)
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: 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()
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,
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')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment