Determinare se un array di bit è in una raccolta di array di bit

Question

Dati gli array di bit NxN bidimensionali, sto cercando di valutare il modo migliore per determinare se un array di bit è già in una vasta raccolta di array di bit visti in precedenza.

Un approccio diretto metterebbe gli array di bit in una tabella hash. Ma per confrontare gli array è necessaria una funzione # 'equalp: test, che potrebbe non essere molto efficiente. (Ma forse SBCL ottimizza automaticamente per diversi tipi di chiavi?)

Un altro piano è convertire tutti gli array di bit in numeri interi e inserire gli interi in una tabella hash. Quindi il test potrebbe essere # 'eql:

(defun bit-arr-to-int (bit-array)
  (reduce (lambda (bit1 bit2)
            (+ (* bit1 2) bit2))
          (make-array (array-total-size bit-array)
                      :displaced-to bit-array)))

Non sono sicuro, tuttavia, se ciò finirà per essere più efficiente del lasciare che SBCL gestisca le cose, dal momento che elabora ancora individualmente ogni elemento. Forse una tabella hash personalizzata offrirebbe un vantaggio in termini di efficienza?

Una terza opzione potrebbe comportare la modifica della rappresentazione di base da matrice di bit a vettore di bit semplice (noto anche come numero intero), poiché le dimensioni della matrice di bit originale sono note. Per consentire riferimenti a elementi equivalenti a un array, ciò richiederebbe una funzione che traduca una riga di array implicita, la coordinata col in un indice vettoriale di bit semplice esplicito. Potrebbe essere più efficiente calcolare gli indici secondo necessità, piuttosto che convertire un intero array di bit in un intero per ogni ricerca nella tabella hash, come sopra.

Apprezza alcune intuizioni esperte.

Answer 1

Penso che l'unico modo per saperlo sia provare e vedere cosa è più veloce.

Un orribile trucco che puoi provare è rappresentare i bit-vettori come uno svantaggio (row-length . integer-of-bits). È necessaria la lunghezza della riga in modo da poter calcolare l'offset nel numero intero di bit. Quindi puoi fare qualcosa del genere (questi potrebbero essere sbagliati perché sono sempre confuso da dpbe ldb):

(deftype index ()
  `(integer 0 ,most-positive-fixnum))

(defun make-bv (columns)
  (declare (type index columns))
  (cons columns 0))

(defun bv-ref (bv row column)
  (declare (type (cons index integer) bv)
           (type index row column))
  (let ((columns (car bv)))
    (assert (< column columns) (column) "column out of range")
    (ldb (byte 1 (+ (* row columns) column)) (cdr bv))))

(defun (setf bv-ref) (bit bv row column)
  (declare (type bit bit)
           (type (cons index integer) bv)
           (type index row column))
  (let ((columns (car bv)))
    (assert (< column columns) (column) "column out of range")
    (setf (cdr bv) (dpb bit (byte 1 (+ (* row columns) column)) (cdr bv)))
    bit))

Nella vita reale, ovviamente, vuoi integrare queste cose.

Una rappresentazione come questa è forse buona per l'hashing (puoi semplicemente eseguire l'hashing equal, o anche avere tabelle eqlhash annidate per i due elementi nei contro) con il notevole problema che non importa quante righe ha l'oggetto: essenzialmente hanno tutte un numero illimitato di righe.

È orribile se gli "array" sono significativamente grandi e si cambiano molto i bit in essi perché si consuma un nuovo bignum ogni volta che si cambia un po '.

Ma penso che l'unico modo per saperlo sia misurare.