c# - 重构乐趣 - 素数

Question

从 Uncle Bob 的书 Clean Code(示例是用 Java 编写的，所以这是我的第一个 Java 翻译)，我一直在研究素数的重构示例。

问题是:您将如何重构以下代码？

这里有 4 个版本:UglyVersion :-)、BobVersion、PeteVersion、PeteVersionClassMember。我这样做是为了好玩，希望你也喜欢 :-)

class ProgramBad
{
    static void Main()
    {
        int[] result = GeneratePrimes.generatePrimes(30);
        foreach (var i in result)
            Console.Write(i.ToString() + ", ");
    }
}

/// <summary>
/// Given an array of integers starting at 2, cross out the multiples of 2.  Fine the next
/// uncrossed integer, and cross out all of its multiples.
/// Repeat until you have passed the square root of the maximum value
/// </summary>
public class GeneratePrimes
{
    public static int[] generatePrimes(int maxValue)
    {
        if (maxValue >= 2) // the only valid case
        {
            // declarations
            int s = maxValue + 1; // size of the array
            bool[] f = new bool[s];
            int i;

            // initialize array to be true
            for (i = 0; i < s; i++)
            {
                f[i] = true;
            }

            // get rid of non-primes
            f[0] = f[1] = false;

            //sieve
            int j;
            for (i = 2; i < Math.Sqrt(s) + 1; i++)
            {
                if (f[i]) // if i is uncrossed, cross its multiples
                {
                    for (j = 2 * i; j < s; j += i)
                        f[j] = false; // multiple is not a prime
                }
            }

            // how many primes are there?
            int count = 0;
            for (i = 0; i < s; i++)
            {
                if (f[i])
                    count++; // bump count
            }

            int[] primes = new int[count];

            //move the primes into the result
            for (i = 0, j=0;i<s ; i++)
            {
                if (f[i])
                    primes[j++] = i;
            }

            return primes; // return the primes
        } else // maxvalue < 2
            return new int[0]; // return null array if bad input
    }
}

Bob 的重构版本:

class ProgramBob
    {
        static void Main()
        {
            int[] result = PrimeGeneratorBob.generatePrimes(30);
            foreach (var i in result)
                Console.Write(i + ", ");
        }
    }

    /// <summary>
    /// Generates prime number up to a user specified maximum
    /// The algorithm used is the Sieve of Eratosthenes.
    /// Given an array of integers starting at 2:
    /// Find the first uncrossed (eg 3 ) integer, and cross out all its multiples (eg 6,9,12,14)
    /// Repeat until there are no more multipes in the array
    /// </summary>
    class PrimeGeneratorBob
    {
        static bool[] crossedOut;
        static int[] result;

        static public int[] generatePrimes(int maxValue)
        {
            if (maxValue < 2)
                return new int[0];
            else
            {
                uncrossIntegersUpTo(maxValue);
                crossOutMultiples();
                putUncrossedIntegersIntoResult();
                return result;
            }
        }

        static void uncrossIntegersUpTo(int maxValue)
        {
            crossedOut = new bool[maxValue + 1]; // as bool array starts at 0, and if maxvalue = 10, we need an array of length 11
            for (int i = 2; i < crossedOut.Length; i++) // less than as we don't want to reference crossedOut[4] which doesn't exist
                crossedOut[i] = false;
        }

        static void crossOutMultiples()
        {
            int limit = determineIterationLimit();
            for (int i = 2; i <= limit; i++)
                if (notCrossed(i))
                    crossOutMultiplesOf(i);
        }

        static int determineIterationLimit()
        {
            // Every multiple in the array has a prime factor that
            // is less than or equal to the square root of the array size, 
            // which is the largest number we are trying to find primes in.
            // So we don't have to cross out numbers
            // larger than that square root of the maxnumber, as they will have been crossed out already
            double iterationLimit = Math.Sqrt(crossedOut.Length);
            return (int) iterationLimit;
        }

        static void crossOutMultiplesOf(int i)
        {
            for (int multiple = 2*i; multiple < crossedOut.Length; multiple += i)
                crossedOut[multiple] = true;
        }

        static bool notCrossed(int i)
        {
            return crossedOut[i] == false;
        }

        static void putUncrossedIntegersIntoResult()
        {
            result = new int[numberOfUncrossedIntegers()];
            for (int j = 0, i = 2; i < crossedOut.Length; i++)
                if (notCrossed(i))
                    result[j++] = i;
        }

        static int numberOfUncrossedIntegers()
        {
            int count = 0;
            for (int i = 2; i < crossedOut.Length; i++)
                if (notCrossed(i))
                    count++;
            return count;
        }
    }

我喜欢的是:

• 全面了解程序的工作原理有多容易，例如uncrossIntegersUpTo(最大值);crossOutMultiples();putUncrossedIntegersIntoResult();

周末我和一个 friend 结对，我们想出了这个版本:

class PetesRefactored
{
    static void MainPete()
    {
        PrimeGeneratorPete pg = new PrimeGeneratorPete();
        int[] arrayOfPrimes = pg.generatePrimes(30);
        foreach (int prime in arrayOfPrimes)
            Console.Write(prime + ", ");
    }
}

/// <summary>
/// Generates prime number up to a user specified maximum
/// The algorithm used is the Sieve of Eratosthenes.
/// Given an array of integers starting at 2:
/// Find the first uncrossed (eg 3 ) integer, and cross out all its multiples (eg 6,9,12,14)
/// Repeat until there are no more multipes in the array
/// </summary>
class PrimeGeneratorPete
{
    public int[] generatePrimes(int maxValue)
    {
        bool[] crossedOut;

        if (maxValue < 2)
            return new int[0];
        else
        {
            crossedOut = new bool[maxValue + 1];
            uncrossIntegersUpTo(crossedOut);
            crossOutMultiples(crossedOut);
            return putUncrossedIntegersIntoResult(crossedOut);
        }
    }

    void uncrossIntegersUpTo(bool[] crossedOut)
    {
        for (int i = 2; i < crossedOut.Length; i++) 
            crossedOut[i] = false;
    }

    void crossOutMultiples(bool[] crossedOut)
    {
        int limit = determineIterationLimit(crossedOut);
        for (int i = 2; i <= limit; i++)
            if (!crossedOut[i])
                crossOutMultiplesOf(crossedOut, i);
    }

    int determineIterationLimit(bool[] crossedOut)
    {
        // Every multiple in the array has a prime factor that
        // is less than or equal to the square root of the array size, 
        // which is the largest number we are trying to find primes in.
        // So we don't have to cross out numbers
        // larger than that square root of the maxnumber, as they will have been crossed out already
        double iterationLimit = Math.Sqrt(crossedOut.Length);
        return (int) iterationLimit;
    }

    void crossOutMultiplesOf(bool[] crossedOut, int i)
    {
        for (int multiple = 2*i; multiple < crossedOut.Length; multiple += i)
            crossedOut[multiple] = true;
    }

    int[] putUncrossedIntegersIntoResult(bool[] crossedOut)
    {
        int[] result = new int[numberOfUncrossedIntegers(crossedOut)];
        for (int j = 0, i = 2; i < crossedOut.Length; i++)
            if (!crossedOut[i])
                result[j++] = i;
        return result;
    }

    int numberOfUncrossedIntegers(bool[] crossedOut)
    {
        int count = 0;
        for (int i = 2; i < crossedOut.Length; i++)
            if (!crossedOut[i])
                count++;
        return count;
    }
}

我们:

• 在 generatePrimes 方法中初始化 crossedOut 而不是“child”方法
• 将 crossedOut 作为参数而不是类作用域变量传入
• 取出(分解)notCrossed(i) 方法作为 !crossedOut[i] 是非常可读的内联。
• 让一切都非静态

感谢 Casey 和匿名。

这是将 crossedOut 作为类级别变量的代码。我喜欢这样，因为它在将参数传递给方法时减少了一些噪音。

class PrimeGeneratorPeteClassMember
{
    bool[] crossedOut;

    public int[] generatePrimes(int maxValue)
    {
        if (maxValue < 2)
            return new int[0];
        else
        {
            crossedOut = new bool[maxValue + 1];
            uncrossIntegersUpTo();
            crossOutMultiples();
            return putUncrossedIntegersIntoResult();
        }
    }

    void uncrossIntegersUpTo()
    {
        for (int i = 2; i < crossedOut.Length; i++)
            crossedOut[i] = false;
    }

    void crossOutMultiples()
    {
        int limit = determineIterationLimit();
        for (int i = 2; i <= limit; i++)
            if (!crossedOut[i])
                crossOutMultiplesOf(i);
    }

    int determineIterationLimit()
    {
        double iterationLimit = Math.Sqrt(crossedOut.Length);
        return (int)iterationLimit;
    }

    void crossOutMultiplesOf(int i)
    {
        for (int multiple = 2 * i; multiple < crossedOut.Length; multiple += i)
            crossedOut[multiple] = true;
    }

    int[] putUncrossedIntegersIntoResult()
    {
        int[] result = new int[numberOfUncrossedIntegers()];
        for (int j = 0, i = 2; i < crossedOut.Length; i++)
            if (!crossedOut[i])
                result[j++] = i;
        return result;
    }

    int numberOfUncrossedIntegers()
    {
        int count = 0;
        for (int i = 2; i < crossedOut.Length; i++)
            if (!crossedOut[i])
                count++;
        return count;
    }
}

Answer 1

老实说？我根本不会重构。也许只是因为我曾经是个数学迷，但我发现第一个版本更容易阅读。

重构算法通常没有多大意义。当您重构代码时，这意味着您希望重用或更改它的一部分。在这种情况下，整个代码块是静态且不可变的 - 您唯一可以更改的是用不同的算法替换整个函数。单行函数，如 notCrossed显得特别无用；它们只是使代码更加冗长，而没有帮助解释任何尚不明显的内容。

实际上，我可能会进行两种重构:

• 更改类名GeneratePrimes进入PrimeGenerator ，就像你已经做过的那样。动词类名总是让我陷入困境 - 它是类还是方法？

• 将其更改为返回 IList<int>或 IEnumerable<int> .返回的数组类型是 Considered Harmful .

• 编辑 - 还有三分之一的重构是删除一些无用的注释并使用有意义的变量名(在适当的地方)。

除此之外 - 坚持使用原始版本!

---

编辑 - 实际上，我越看原作就越不喜欢它。不是因为它的组织方式，而是因为它的编写方式。这是我的重写:

public class PrimeGenerator
{
    public static IEnumerable<int> GeneratePrimes(int maxValue)
    {
        if (maxValue < 2)
            return Enumerable.Empty<int>();

        bool[] primes = new bool[maxValue + 1];
        for (int i = 2; i <= maxValue; i++)
            primes[i] = true;

        for (int i = 2; i < Math.Sqrt(maxValue + 1) + 1; i++)
        {
            if (primes[i])
            {
                for (int j = 2 * i; j <= maxValue; j += i)
                    primes[j] = false;
            }
        }

        return Enumerable.Range(2, maxValue - 1).Where(i => primes[i]);
    }
}

好了，好多了!