C # primer generador, gasto excesivo con la matriz de bits

Question

(C #, el primer generador) Aquí está algo de código a un amigo y yo estábamos hurgando en:

public List<int> GetListToTop(int top)
{            
    top++;
    List<int> result = new List<int>();
    BitArray primes = new BitArray(top / 2);
    int root = (int)Math.Sqrt(top);
    for (int i = 3, count = 3; i <= root; i += 2, count++)
    {
        int n = i - count;
        if (!primes[n])
            for (int j = n + i; j < top / 2; j += i)
            {
                primes[j] = true;
            }
    }
    if (top >= 2)
        result.Add(2);            
    for (int i = 0, count = 3; i < primes.Length; i++, count++)
    {
        if (!primes[i])
        {
            int n = i + count;
            result.Add(n);
        }
    }

    return result;
}

En mi dorky AMD x64 1800+ (de doble núcleo), para todos los números primos inferiores a 1 mil millones en 34546.875ms. El problema parece estar más en el almacenamiento de la matriz de bits. Tratando de hacer girar más de 2 mil millones ~ es más que la BitArray quiere almacenar. Cualquier ideas sobre cómo conseguir alrededor de eso?

Answer 1

Me partes de "intercambio" de la matriz fuera del disco. Por eso, quiero decir, dividir la matriz de bits en trozos de entramado de mil millones de bits y almacenarlos en el disco.

El tener sólo unos pocos trozos de la memoria en un momento dado. Con C # (o cualquier otro lenguaje orientado a objetos), que debe ser fácil para encapsular la gran cantidad dentro de esta clase de fragmentación.

Usted tendrá que pagar por ello con un tiempo de generación más lenta pero no ve ninguna forma de evitar eso hasta que tengamos mayores espacios de direcciones y compiladores de 128 bits.

Answer 2

O como un enfoque alternativo a la sugerida por Pax, hacer uso de las nuevas clases de archivo asignado en memoria en .NET 4.0 y dejar que el sistema operativo decidir qué trozos necesita estar en la memoria en cualquier momento dado.

Nota sin embargo que usted desea para tratar de optimizar el algoritmo para aumentar la localidad para que no terminen innecesariamente hasta el intercambio de páginas dentro y fuera de la memoria (más difícil que esta frase hace que suene).

Answer 3

El uso de múltiples BitArrays para aumentar el tamaño máximo. Si un número es de gran desplazamiento de bit y almacenar el resultado en un poco de matriz para almacenar los bits 33-64.

BitArray second = new BitArray(int.MaxValue);
long num = 23958923589;
if (num > int.MaxValue)
{
    int shifted = (int)num >> 32;
    second[shifted] = true;
}

long request = 0902305023;
if (request > int.MaxValue)
{
    int shifted = (int)request >> 32;
    return second[shifted];
}
else return first[request];

Por supuesto que sería bueno si BitArray apoyaría tamaño hasta System.Numerics.BigInteger.
Realizar intercambios con el disco hará que su código muy lento.
Tengo un sistema operativo de 64 bits, y mi BitArray también está limitado a 32 bits.

PS: sus cálculos con números primos parece extraño, la mía tiene el siguiente aspecto:

for (int i = 2; i <= number; i++)
    if (primes[i])
        for (int scalar = i + i; scalar <= number; scalar += i)
        {
            primes[scalar] = false;
            yield return scalar;
        }

Answer 4

El algoritmo Sieve sería mejor rendimiento. Pude determinar todos los primos de 32 bits (un total de aproximadamente 105 millones de dólares) para la gama int en menos de 4 minutos con eso. Por supuesto devolver la lista de los números primos es una cosa diferente como el requisito de memoria que habría un poco más de 400 MB (1 int = 4 bytes). Utilizando un bucle los números fueron impresos en un archivo y luego importados a una base de datos para más diversión :) Sin embargo, para el bit 64 prepara el programa necesitaría varias modificaciones y tal vez se requiera su ejecución distribuidos en varios nodos. También se refieren a los siguientes enlaces

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

http://en.wikipedia.org/wiki/Prime-counting_function