F# - Facebook黑客杯 - 双人广场

Question

我正在努力加强我的F#-fu并决定解决Facebook黑客杯双方问题.我在运行时遇到了一些问题,并且想知道是否有人可以帮我弄清楚它为什么比我的C#等效速度慢得多.

另一篇文章有​​很好的描述;

资料来源:2011年Facebook黑客杯资格赛

双平方数是整数X,可以表示为两个正方形的总和.例如,10是双平方,因为10 = 3 ^ 2 + 1 ^ 2.给定X,我们如何确定它可以写成两个方格之和的方式？例如,10只能写为3 ^ 2 + 1 ^ 2(我们不计算1 ^ 2 + 3 ^ 2不同).另一方面,25可以写成5 ^ 2 + 0 ^ 2或4 ^ 2 + 3 ^ 2.

你需要解决0≤X≤2,147,483,647这个问题.

例子:

10 => 1

25 => 2

3 => 0

0 => 1

1 => 1

竞争中的数字

1740798996
1257431873
2147483643
602519112
858320077
1048039120
415485223
874566596
1022907856
65
421330820
1041493518
5
1328649093
1941554117
4225
2082925
0
1
3

我的基本策略(我愿意批评)是;

1. 创建一个初始化为0的输入数字的字典(用于memoize)
2. 获取最大数字(LN)并将其传递给计数/备忘录功能
3. 将LN平方根作为int
4. 计算所有数字0到LN的平方并存储在dict中
5. 从0到LN的非重复数字组合的求和方
   
   • 如果sum在备忘录中,请在备忘录中添加1
6. 最后,输出原始数字的计数.

这是F#代码(见底部的代码更改)我写过我相信这个策略对应(运行时间:~8:10);

open System
open System.Collections.Generic
open System.IO

/// Get a sequence of values
let rec range min max = 
    seq { for num in [min .. max] do yield num }

/// Get a sequence starting from 0 and going to max
let rec zeroRange max = range 0 max    

/// Find the maximum number in a list with a starting accumulator (acc)
let rec maxNum acc = function
    | [] -> acc
    | p::tail when p > acc -> maxNum p tail
    | p::tail -> maxNum acc tail

/// A helper for finding max that sets the accumulator to 0
let rec findMax nums = maxNum 0 nums

/// Build a collection of combinations; ie [1,2,3] = (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)
let rec combos range =    
    seq { 
          let count = ref 0
          for inner in range do 
              for outer in Seq.skip !count range do 
                  yield (inner, outer)
              count := !count + 1          
        }

let rec squares nums = 
    let dict = new Dictionary<int, int>()
    for s in nums do
        dict.[s] <- (s * s)
    dict

/// Counts the number of possible double squares for a given number and keeps track of other counts that are provided in the memo dict.
let rec countDoubleSquares (num: int) (memo: Dictionary<int, int>) =
    // The highest relevent square is the square root because it squared plus 0 squared is the top most possibility
    let maxSquare = System.Math.Sqrt((float)num)

    // Our relevant squares are 0 to the highest possible square; note the cast to int which shouldn't hurt.
    let relSquares = range 0 ((int)maxSquare)

    // calculate the squares up front;
    let calcSquares = squares relSquares

    // Build up our square combinations; ie [1,2,3] = (1,1), (1,2), (1,3), (2,2), (2,3), (3,3)
    for (sq1, sq2) in combos relSquares do
        let v = calcSquares.[sq1] + calcSquares.[sq2]
        // Memoize our relevant results
        if memo.ContainsKey(v) then            
            memo.[v] <- memo.[v] + 1

    // return our count for the num passed in
    memo.[num]


// Read our numbers from file.
//let lines = File.ReadAllLines("test2.txt")
//let nums = [ for line in Seq.skip 1 lines -> Int32.Parse(line) ]

// Optionally, read them from straight array
let nums = [1740798996; 1257431873; 2147483643; 602519112; 858320077; 1048039120; 415485223; 874566596; 1022907856; 65; 421330820; 1041493518; 5; 1328649093; 1941554117; 4225; 2082925; 0; 1; 3]

// Initialize our memoize dictionary
let memo = new Dictionary<int, int>()
for num in nums do
    memo.[num] <- 0

// Get the largest number in our set, all other numbers will be memoized along the way
let maxN = findMax nums

// Do the memoize
let maxCount = countDoubleSquares maxN memo

// Output our results.
for num in nums do
    printfn "%i" memo.[num]

// Have a little pause for when we debug
let line = Console.Read()

这是我在C#中的版本(运行时间:~1:40:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

namespace FBHack_DoubleSquares
{
    public class TestInput
    {
        public int NumCases { get; set; }
        public List<int> Nums { get; set; }

        public TestInput()
        {
            Nums = new List<int>();
        }

        public int MaxNum()
        {
            return Nums.Max();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            // Read input from file.
            //TestInput input = ReadTestInput("live.txt");

            // As example, load straight.
            TestInput input = new TestInput
            {
                NumCases = 20,
                Nums = new List<int>
                {
                    1740798996,
                    1257431873,
                    2147483643,
                    602519112,
                    858320077,
                    1048039120,
                    415485223,
                    874566596,
                    1022907856,
                    65,
                    421330820,
                    1041493518,
                    5,
                    1328649093,
                    1941554117,
                    4225,
                    2082925,
                    0,
                    1,
                    3,
                }
            };

            var maxNum = input.MaxNum();

            Dictionary<int, int> memo = new Dictionary<int, int>();
            foreach (var num in input.Nums)
            {
                if (!memo.ContainsKey(num))
                    memo.Add(num, 0);
            }

            DoMemoize(maxNum, memo);

            StringBuilder sb = new StringBuilder();
            foreach (var num in input.Nums)
            {
                //Console.WriteLine(memo[num]);
                sb.AppendLine(memo[num].ToString());
            }

            Console.Write(sb.ToString());

            var blah = Console.Read();
            //File.WriteAllText("out.txt", sb.ToString());
        }

        private static int DoMemoize(int num, Dictionary<int, int> memo)
        {
            var highSquare = (int)Math.Floor(Math.Sqrt(num));

            var squares = CreateSquareLookup(highSquare);
            var relSquares = squares.Keys.ToList();

            Debug.WriteLine("Starting - " + num.ToString());
            Debug.WriteLine("RelSquares.Count = {0}", relSquares.Count);

            int sum = 0;
            var index = 0;            
            foreach (var square in relSquares)
            {
                foreach (var inner in relSquares.Skip(index))
                {
                    sum = squares[square] + squares[inner];
                    if (memo.ContainsKey(sum))
                        memo[sum]++;
                }
                index++;
            }

            if (memo.ContainsKey(num))
                return memo[num];

            return 0;            
        }

        private static TestInput ReadTestInput(string fileName)
        {
            var lines = File.ReadAllLines(fileName);
            var input = new TestInput();
            input.NumCases = int.Parse(lines[0]);
            foreach (var lin in lines.Skip(1))
            {
                input.Nums.Add(int.Parse(lin));
            }

            return input;
        }

        public static Dictionary<int, int> CreateSquareLookup(int maxNum)
        {
            var dict = new Dictionary<int, int>();
            int square;
            foreach (var num in Enumerable.Range(0, maxNum))
            {
                square = num * num;
                dict[num] = square;
            }

            return dict;
        }
    }   
}

谢谢参观.

UPDATE

稍微更改组合功能将导致相当大的性能提升(从8分钟到3:45):

/// Old and Busted...
let rec combosOld range =    
    seq { 
          let rangeCache = Seq.cache range
          let count = ref 0
          for inner in rangeCache do 
              for outer in Seq.skip !count rangeCache do 
                  yield (inner, outer)
              count := !count + 1          
        }

/// The New Hotness...
let rec combos maxNum =    
    seq {
        for i in 0..maxNum do
            for j in i..maxNum do
                yield i,j } 

Answer 1

同样,x ^ 2 + y ^ 2 = k的整数解的数量也是

• 零,如果有一个素数因子等于3 mod 4
• k的素数除数的四倍,等于1 mod 4.

请注意,在第二种选择中,您将^ 2 + b ^ 2计为(-a)^ 2 + b ^ 2(和其他符号)的不同解,并计算为b ^ 2 + a ^ 2.因此,如果您希望将解决方案设置为集合而不是有序对,那么您可能希望除以4并再次除以2(如@Wei Hu所指出的那样).

知道了这一点,编写一个提供解决方案数量的程序很容易:一次性计算最多46341的素数.

给定k,使用上面的列表计算k的素数除数(测试到sqrt(k)).计算等于1 mod 4的数,并求和.如果需要,将4乘以答案.

所有这些都是任何懒惰函数语言中的一个或两个线程(我不知道f#,在Haskell中它将是两行长),一旦你有一个primes无限的序列:计算除数= 1 mod 4(filterby |> count或者一些东西)这些线条是非常自然的.

我怀疑它比强制分解更快.

Answer 2

你的F#combos功能很糟糕.就像是

let rec combos range =
    let a = range |> Seq.toArray
    seq {
        for i in 0..a.Length-1 do
            for j in i..a.Length-1 do
                yield i,j } 

应该是一个很大的加速.