Le meilleur que je pourrais utiliser est d'utiliser une sortie rapide sur la logique de bouclage. Combiné avec la possibilité d'utiliser l'approche non-zéro comme décrit par themis, vous pouvez répondre à votre question en inspectant moins de 2% du problème N^2. Vous trouverez ci-dessous un code qui donne le minutage pour les nombres compris entre 80% et 99% de 0%. Lorsque les nombres obtiennent environ 88% de zéro, l'approche de leur approche passe à être meilleure (mais elle n'a pas été codée dans l'exemple ci-dessous).
Cette solution n'est pas très théorique, mais elle est pratique.
OK, voici quelques « théorie » de l'espace de problème:
Fondamentalement, chaque bit de X (la sortie) est le OU sommation des bits sur la diagonale d'un réseau construit en ayant les bits de A le long du haut (MSB à LSB de gauche à droite) et les bits de B sur le côté (MSB à LSB de haut en bas). Puisque le bit de X est 1, s'il y en a un sur la diagonale, vous pouvez effectuer une sortie rapide sur la traversée de la cellule.
Le code ci-dessous fait cela et montre que même pour les nombres qui sont ~ 87% de zéro, il suffit de vérifier ~ 2% des cellules. Pour les nombres plus denses (plus de 1), ce pourcentage diminue encore plus.En d'autres termes, je ne m'inquiéterais pas des algorithmes complexes et je ferais juste une vérification logique efficace. Je pense que l'astuce consiste à regarder les bits de votre sortie comme les diagonales de la grille par opposition aux bits de A shift-OU avec les bits de B. La chose la plus délicate est de garder une trace des bits que vous pouvez regarder en A et B et comment indexer les bits correctement.
Espérons que cela a du sens. Faites-moi savoir si j'ai besoin d'expliquer un peu plus loin (ou si vous trouvez des problèmes avec cette approche). REMARQUE: Si nous connaissions un peu mieux l'espace de votre problème, nous pourrions optimiser l'algorithme en conséquence. Si vos nombres sont pour la plupart non-nuls, alors cette approche est meilleure que celle-ci, car il en résulterait plus de calculs et plus d'espace de stockage nécessaire (sizeof (int) * NNZ).
NOTE 2: Cela suppose que les données sont essentiellement des bits, et j'utilise BitArray de .NET pour stocker et accéder aux données. Je ne pense pas que cela causerait des maux de tête importants lorsqu'ils sont traduits dans d'autres langues. L'idée de base s'applique toujours.
using System;
using System.Collections;
namespace BigIntegerOr
{
class Program
{
private static Random r = new Random();
private static BitArray WeightedToZeroes(int size, double pctZero, out int nnz)
{
nnz = 0;
BitArray ba = new BitArray(size);
for (int i = 0; i < size; i++)
{
ba[i] = (r.NextDouble() < pctZero) ? false : true;
if (ba[i]) nnz++;
}
return ba;
}
static void Main(string[] args)
{
// make sure there are enough bytes to hold the 6000 bits
int size = (6000 + 7)/8;
int bits = size * 8;
Console.WriteLine("PCT ZERO\tSECONDS\t\tPCT CELLS\tTOTAL CELLS\tNNZ APPROACH");
for (double pctZero = 0.8; pctZero < 1.0; pctZero += 0.01)
{
// fill the "BigInts"
int nnzA, nnzB;
BitArray a = WeightedToZeroes(bits, pctZero, out nnzA);
BitArray b = WeightedToZeroes(bits, pctZero, out nnzB);
// this is the answer "BigInt" that is at most twice the size minus 1
int xSize = bits * 2 - 1;
BitArray x = new BitArray(xSize);
int LSB, MSB;
LSB = MSB = bits - 1;
// stats
long cells = 0;
DateTime start = DateTime.Now;
for (int i = 0; i < xSize; i++)
{
// compare using the diagonals
for (int bit = LSB; bit < MSB; bit++)
{
cells++;
x[i] |= (b[MSB - bit] && a[bit]);
if (x[i]) break;
}
// update the window over the bits
if (LSB == 0)
{
MSB--;
}
else
{
LSB--;
}
//Console.Write(".");
}
// stats
TimeSpan elapsed = DateTime.Now.Subtract(start);
double pctCells = (cells * 100.0)/(bits * bits);
Console.WriteLine(pctZero.ToString("p") + "\t\t" +elapsed.TotalSeconds.ToString("00.000") + "\t\t" +
pctCells.ToString("00.00") + "\t\t" + cells.ToString("00000000") + "\t" + (nnzA * nnzB).ToString("00000000"));
}
Console.ReadLine();
}
}
}
Pouvez-vous remplacer plus avec ou? Cela ne donne pas de résultats incorrects, si vous avez le même bit dans n'importe quelle position sur deux des chaînes, vous obtiendrez 1 et non 0. – JSchlather
Il ne dit pas que vous obtiendrez les mêmes résultats. Il se demande s'il existe des algorithmes d'accélération pour la multiplication "OU" de la même manière qu'il existe des algorithmes d'accélération pour une multiplication régulière. –
Quelle est la taille de vos numéros biginteger? (combien de bits) –