Я работаю над усилением своего F # -фу и решил заняться проблемой двойных квадратов на Facebook Hacker Cup. У меня возникли некоторые проблемы со временем выполнения, и мне было интересно, может ли кто-нибудь помочь мне понять, почему он намного медленнее, чем мой эквивалент C #.
Есть хорошее описание из другого поста;
Источник: Facebook Hacker Cup
Отборочный раунд 2011
Двойное квадратное число - целое число 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
Моя основная стратегия (которую я открыт для критики) заключается в том, чтобы:
- Создать словарь (для запоминания) введенных чисел, инициализированных 0
- Получить наибольшее число (LN) и передать его функции подсчета / напоминания
- Получите квадратный корень LN как int
- Рассчитать квадраты для всех чисел от 0 до LN и сохранить в dict
- Сумма квадратов для неповторяющихся комбинаций чисел от 0 до LN
- Если сумма указана в записке, добавьте 1 к записке
- Наконец, выведите количество исходных чисел.
Вот код 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 }