Pertanyaan F # - Cup Hacker Facebook - Kuadrat Ganda


Saya sedang berusaha memperkuat F # -fu dan memutuskan untuk menangani masalah Facebook Squeeze Cup Double Squares. Saya mengalami beberapa masalah dengan run-time dan bertanya-tanya apakah ada yang bisa membantu saya mencari tahu mengapa itu jauh lebih lambat daripada C # setara saya.

Ada deskripsi yang bagus dari pos lain;

Sumber: Cup Hacker Facebook   Babak Kualifikasi 2011

Sebuah bilangan kuadrat-ganda adalah bilangan bulat X   yang dapat diekspresikan sebagai jumlah dari   dua kotak sempurna. Misalnya, 10   adalah double-square karena 10 = 3 ^ 2 +   1 ^ 2. Diberikan X, bagaimana kita dapat menentukan berapa banyak cara yang dapat dilakukan   ditulis sebagai jumlah dari dua kotak? Untuk   Misalnya, 10 hanya dapat ditulis sebagai 3 ^ 2   + 1 ^ 2 (kami tidak menghitung 1 ^ 2 + 3 ^ 2 sebagai berbeda). Di sisi lain, 25 kaleng   dituliskan sebagai 5 ^ 2 + 0 ^ 2 atau sebagai 4 ^ 2 + 3 ^ 2.

Anda harus menyelesaikan masalah ini untuk 0 ≤   X ≤ 2,147,483,647.

Contoh:

10 => 1

25 => 2

3 => 0

0 => 1

1 => 1

Angka Dari Kompetisi

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

Strategi dasar saya (yang saya terbuka untuk kritik) adalah untuk;

  1. Buat kamus (untuk memoize) dari nomor input yang diinisialisasi ke 0
  2. Dapatkan nomor terbesar (LN) dan teruskan ke fungsi hitung / memo
  3. Dapatkan LN square root sebagai int
  4. Hitung kuadrat untuk semua angka 0 ke LN dan simpan dalam dict
  5. Jumlah kuadrat untuk kombinasi angka yang tidak berulang dari 0 ke LN
    • Jika jumlah dalam memo, tambahkan 1 untuk memo
  6. Akhirnya, output jumlah angka asli.

Berikut adalah kode F # (Lihat perubahan kode di bagian bawah) Saya telah menulis bahwa saya percaya sesuai dengan strategi ini (Runtime: ~ 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()

Dan inilah versi saya di C # (Runtime: ~ 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;
        }
    }   
}

Terima kasih telah memeriksanya.

MEMPERBARUI

Mengubah fungsi kombo sedikit akan menghasilkan peningkatan kinerja yang cukup besar (dari 8 menit hingga 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 } 

4
2018-01-13 14:59


asal


Jawaban:


Saya suka urutan, tetapi dalam kasus ini, mereka mungkin alat yang salah untuk pekerjaan itu. Masalah ini adalah kesempatan untuk mencoba solusi rekursif non-trivial. Dengan menggunakan mutasi, akan mudah untuk melakukan algoritma seperti ini (dengan Python, pilihan pseudo-code saya ..)

def f(n):
    i = 0
    j = int(1 + sqrt(n))
    count = 0
    # 'i' will always be increased, and j will always be decreased.  We
    # will stop if i > j, so we can avoid duplicate pairs.
    while i <= j:
        s = i * i + j * j
        if s < n:
            # if any answers exist for this i, they were with higher
            # j values.  So, increment i.
            i +=  1
        elif s > n:
            # likewise, if there was an answer with this j, it was
            # found with a smaller i.  so, decrement it.
            j -= 1
        else:
            # found a solution.  Count it, and then move both i and 
            # j, because they will be found in at most one solution pair.
            count += 1
            i += 1
            j -= 1
    return count    

Sekarang, ini sepertinya berhasil. Mungkin itu tidak benar, atau bukan yang terbaik, tapi saya suka bagaimana kode rekursif terlihat di F #. (Peringatan .. Saya tidak punya F # di komputer ini ... tapi saya harap saya bisa melakukannya dengan benar.)

let f n = 
    let rec go i j count =
        if i > j then count
        else
            let s = i * i + j * j
            if s < n then 
                go (i + 1) j count
            else if s > n then
                go i (j - 1) count
            else
                go (i + 1) (j - 1) (count + 1)
    go 0 (1 + (n |> float |> sqrt |> int)) 0

Solusi ini berjalan dalam O (sqrt (N)) waktu untuk setiap panggilan, dan membutuhkan memori konstan. Solusi memoizing membutuhkan waktu O (N) untuk mengatur kamus dan ukuran kamus setidaknya O (sqrt (N)). Untuk N besar, ini sangat berbeda.


2
2018-01-17 16:23



Sekali lagi, jumlah solusi bilangan bulat dari x ^ 2 + y ^ 2 = k adalah salah satunya

  • nol, jika ada faktor utama yang sama dengan 3 mod 4
  • empat kali jumlah pembagi utama k yang sama dengan 1 mod 4.

Perhatikan bahwa pada alternatif kedua, Anda menghitung ^ 2 + b ^ 2 sebagai solusi berbeda untuk (-a) ^ 2 + b ^ 2 (dan tanda lainnya), dan b ^ 2 + a ^ 2. Jadi, Anda mungkin ingin membagi dengan empat, dan bagi lagi dengan 2 (mengambil lantai, seperti yang ditunjukkan @Wei Hu) jika Anda menginginkan solusi sebagai set alih-alih pasangan yang dipesan.

Mengetahui hal ini, menulis program yang memberikan sejumlah solusi mudah: menghitung bilangan prima hingga 46341 sekali dan untuk semua.

Diberikan k, hitung pembagi utama k dengan menggunakan daftar di atas (uji hingga sqrt (k)). Hitung yang sama dengan 1 mod 4, dan jumlah. Gandakan jawaban dengan 4 jika diperlukan.

Semua ini adalah satu atau dua liner dalam bahasa fungsional yang malas (saya tidak cukup tahu f #, di Haskell panjangnya dua baris), setelah Anda memiliki primes Urutan tak terbatas: menghitung pembagi = 1 mod 4 (filterby |> count atau sesuatu di sepanjang garis ini) adalah sesuatu yang sangat alami.

Saya menduga itu lebih cepat daripada brute memaksa dekomposisi.


7
2018-01-13 15:30



F kamu# combos fungsi memiliki perf yang mengerikan. Sesuatu seperti

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 } 

harus menjadi percepatan besar.


5
2018-01-13 18:09



EDIT

Mengingat kode C #, perbedaan terbesar adalah bahwa kode C # mengulang daftar, sedangkan kode F # iterasi atas urutan. The Seq.cache hanya benar-benar membantu ketika Anda benar-benar melakukan perhitungan atas seq, dalam hal ini, tidak menghindari berjalan di atas urutan berulang kali.

Fungsi ini akan lebih seperti kode C #, tetapi membutuhkan input untuk menjadi array, bukan sembarang urutan.

Tapi, seperti yang Anda katakan di tempat lain, diperlukan algoritma yang lebih baik secara keseluruhan.

let combos (ss: int []) =
    let rec helper idx =
    seq {
        if idx < ss.Length then
            for jdx in idx + 1 .. ss.Length - 1 do
                 yield (ss.[idx], ss.[jdx])
            yield! helper (idx + 1)
        }
    helper 0

END EDIT

Ini mungkin menjadi bagian dari mengapa ini lebih lambat daripada kode C # yang setara, meskipun saya pikir IEnumerable akan memiliki masalah yang sama.

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          
    }

Rentang loop ganda di atas menyebabkannya dievaluasi berulang kali. Seq.cache dapat digunakan untuk menghindari ini, jika urutan harus dilihat berulang kali.


1
2018-01-13 15:25



Ini akan membantu beberapa.

// Build up our square combinations;
for (sq1, sq2) in combos maxSquare do
    let v = calcSquares.[sq1] + calcSquares.[sq2]

    // Memoize our relevant results
    match memo.TryGetValue v with
    | true, value -> memo.[v] <- value + 1
    | _ -> ()

1
2018-01-13 23:49



Saya telah menggunakan F # untuk piala peretas Facebook. Inilah solusi saya yang selesai dalam waktu kurang dari 0,5 detik. Sementara saya setuju bahwa Anda harus melakukan fungsional yang Anda bisa, tetapi kadang-kadang menjadi penting adalah pendekatan yang lebih baik, terutama dalam kompetisi coding yang dibatasi waktu.

let int_sqrt (n:int) :int =
    int (sqrt (float n))

let double_square (x: int) :int =
    let mutable count = 0
    let square_x = int_sqrt x
    for i in 0..square_x do
        let y = int_sqrt (x - i*i)
        if y*y + i*i = x && i<=y then count <- count + 1
    count

1
2018-01-27 03:14



Tanpa memeriksa kode, algoritme Anda kurang optimal. Saya memecahkan ini dengan yang berikut:

Let N be the number we're testing.
Let X,Y such that X^2 + Y^2 = N
For all 0 <= X < sqrt(N)
   Let Ysquared = N - X^2
   if( Ysquared > Xsquared ) break; //prevent duplicate solutions
   if( isInteger( sqrt(ySquared) ) )
      //count unique solution

0
2018-01-13 15:09