Как я могу читать данные быстрее? - PullRequest
4 голосов
/ 30 декабря 2010

Хммм ... довольно сложно найти метод для чтения / записи данных достаточно быстро, чтобы ПРИНЯТЬ эту проблему (https://www.spoj.pl/problems/INTEST/), используя F # .

Мой код (http://paste.ubuntu.com/548748/) получает TLE ...

Есть идеи, как ускорить чтение данных?

Ответы [ 3 ]

4 голосов
/ 01 января 2011

Эта моя версия проходит ограничение по времени (но все еще ужасно медленная ~ 14 секунд):

open System
open System.IO

// need to change standard buffer, not to add an additional one
let stream = new StreamReader(Console.OpenStandardInput(4096))

let stdin = Seq.unfold (fun s -> if s = null then None else Some (s,stream.ReadLine())) <| stream.ReadLine()

let inline s2i (s : string) = Array.fold (fun a d -> a*10u + (uint32 d - uint32 '0') ) 0u <| s.ToCharArray()

let calc = 
    let fl = Seq.head stdin
    let [|_;ks|] = fl.Split(' ')
    let k = uint32 ks
    Seq.fold (fun a s -> if (s2i s) % k = 0u then a+1 else a) 0 <| Seq.skip 1 stdin

printf "%A" calc

Хотя узким местом этой версии на самом деле является string -> uint32 преобразование (стандартный каст uint32 изСтрока еще медленнее) само чтение занимает около 2 секунд (против 6 секунд общего времени) на моем вводе сэмпла (файл ~ 100M) - все еще не очень хороший результат.Как только s2i будет переписан в императивном стиле, общее время выполнения может быть уменьшено до 10 секунд на spoj:

let inline s2i (s : string) =
    let mutable a = 0u
    for i in 0..s.Length-1 do a <- a*10u + uint32 (s.Chars(i)) - uint32 '0'
    a
2 голосов
/ 30 декабря 2010

На самом деле я не знаю, но я бы предположил, что чтение символа «так» за раз является плохим, и вы должны прочитать, например, 4k в буфер за один раз, а затем обработать буфер.

1 голос
/ 30 декабря 2010
let buf =
    let raw = System.Console.OpenStandardInput()
    let bytebuf = new System.IO.BufferedStream(raw)
    new System.IO.StreamReader(bytebuf)

buf.Read()     // retrieves a single character as an int from the buffer
buf.ReadLine() // retrieves a whole line from the buffer
...