Wie kann ich Daten schneller lesen?

Question

Hmmm ... es ist schwierig, eine Methode zum Lesen/Schreiben von Daten schneller genug zu finden, um in diesem Problem akzeptiert zu werden ( https://www.spoj.pl/problems/intest/ ) Verwenden F#.

Mein Code ( http://paste.ubuntu.com/548748/ ) bekommt tle ...

Irgendwelche Ideen, wie man das Datenlesen beschleunigt?

Answer 1

Diese Version von mir übergibt das Zeitlimit (ist aber immer noch schrecklich langsam ~ 14 Sekunden):

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

Obwohl der Flaschenhals dieser Version eigentlich ist string -> uint32 Die Konvertierung (Standard -UINT32 -Cast von String ist noch langsamer) Der Messwert selbst dauert ungefähr 2 Sekunden (vs 6 Sek. Gesamtzeit) in meiner Stichprobeneingabe (~ 100 m Datei) - immer noch kein großartiges Ergebnis. Einmal s2i wird im imperativen Stil umgeschrieben, die Gesamtlaufzeit kann auf Spoj auf 10 Sekunden reduziert werden:

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

Answer 2

Ich weiß eigentlich nicht, aber ich würde vermuten, dass das Lesen eines seit dem Charakter nach dem anderen schlecht ist, und Sie sollten zB 4K nacheinander in einen Puffer lesen und dann den Puffer verarbeiten.

Answer 3

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