Haskell bu kod parçası çalışırçok-O ama -O ile daha yavaş olmalı non-dangerous. Birisi bana neler olduğunu anlatabilir mi? Eğer önemliyse, this problem, çözmek için bir girişim olduğunu ve ikili arama ve kalıcı ağaç kesimi kullanır:

import Control.Monad
import Data.Array

data Node =
      Leaf   Int           -- value
    | Branch Int Node Node -- sum, left child, right child
type NodeArray = Array Int Node

-- create an empty node with range [l, r)
create :: Int -> Int -> Node
create l r
    | l   1 == r = Leaf 0
    | otherwise  = Branch 0 (create l m) (create m r)
    where m = (l   r) `div` 2

-- Get the sum in range [0, r). The range of the node is [nl, nr)
sumof :: Node -> Int -> Int -> Int -> Int
sumof (Leaf val) r nl nr
    | nr <= r   = val
    | otherwise = 0
sumof (Branch sum lc rc) r nl nr
    | nr <= r   = sum
    | r  > nl   = (sumof lc r nl m)   (sumof rc r m nr)
    | otherwise = 0
    where m = (nl   nr) `div` 2

-- Increase the value at x by 1. The range of the node is [nl, nr)
increase :: Node -> Int -> Int -> Int -> Node
increase (Leaf val) x nl nr = Leaf (val   1)
increase (Branch sum lc rc) x nl nr
    | x < m     = Branch (sum   1) (increase lc x nl m) rc
    | otherwise = Branch (sum   1) lc (increase rc x m nr)
    where m = (nl   nr) `div` 2

-- signature said it all
tonodes :: Int -> [Int] -> [Node]
tonodes n = reverse . tonodes' . reverse
    where
        tonodes' :: [Int] -> [Node]
        tonodes' (h:t) = increase h' h 0 n : s' where s'@(h':_) = tonodes' t
        tonodes' _ = [create 0 n]

-- find the minimum m in [l, r] such that (predicate m) is True
binarysearch :: (Int -> Bool) -> Int -> Int -> Int
binarysearch predicate l r
    | l == r      = r
    | predicate m = binarysearch predicate l m
    | otherwise   = binarysearch predicate (m 1) r
    where m = (l   r) `div` 2

-- main, literally
main :: IO ()
main = do
    [n, m] <- fmap (map read . words) getLine
    nodes <- fmap (listArray (0, n) . tonodes n . map (subtract 1) . map read . words) getLine
    replicateM_ m $ query n nodes
    where
        query :: Int -> NodeArray -> IO ()
        query n nodes = do
            [p, k] <- fmap (map read . words) getLine
            print $ binarysearch (ok nodes n p k) 0 n
            where
                ok :: NodeArray -> Int -> Int -> Int -> Int -> Bool
                ok nodes n p k s = (sumof (nodes ! min (p   s   1) n) s 0 n) - (sumof (nodes ! max (p - s) 0) s 0 n) >= k

(Bu tam olarak code review ile aynı kod ama bu soru başka bir sorunu giderir.)

Bu C: benim giriş jeneratör

#include <cstdio>
#include <cstdlib>
using namespace std;
int main (int argc, char * argv[]) {
    srand(1827);
    int n = 100000;
    if(argc > 1)
        sscanf(argv[1], "%d", &n);
    printf("%d %d\n", n, n);
    for(int i = 0; i < n; i  )
        printf("%d%c", rand() % n   1, i == n - 1 ? '\n' : ' ');
    for(int i = 0; i < n; i  ) {
        int p = rand() % n;
        int k = rand() % n   1;
        printf("%d %d\n", p, k);
    }
}

Durumda C compiler kullanılabilir, this is the result of ./gen.exe 1000 yok.

Bu bilgisayarımda yürütme sonuç

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.3
$ ghc -fforce-recomp 1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ time ./gen.exe 1000 | ./1827.exe > /dev/null
real    0m0.088s
user    0m0.015s
sys     0m0.015s
$ ghc -fforce-recomp -O 1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ time ./gen.exe 1000 | ./1827.exe > /dev/null
real    0m2.969s
user    0m0.000s
sys     0m0.045s

Ve bu yığın profil Özet:

$ ghc -fforce-recomp -rtsopts ./1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ ./gen.exe 1000 | ./1827.exe  RTS -s > /dev/null
      70,207,096 bytes allocated in the heap
       2,112,416 bytes copied during GC
         613,368 bytes maximum residency (3 sample(s))
          28,816 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)
                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0       132 colls,     0 par    0.00s    0.00s     0.0000s    0.0004s
  Gen  1         3 colls,     0 par    0.00s    0.00s     0.0006s    0.0010s
  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    0.03s  (  0.03s elapsed)
  GC      time    0.00s  (  0.01s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    0.03s  (  0.04s elapsed)
  %GC     time       0.0%  (14.7% elapsed)
  Alloc rate    2,250,213,011 bytes per MUT second
  Productivity 100.0% of total user, 83.1% of total elapsed
$ ghc -fforce-recomp -O -rtsopts ./1827.hs
[1 of 1] Compiling Main             ( 1827.hs, 1827.o )
Linking 1827.exe ...
$ ./gen.exe 1000 | ./1827.exe  RTS -s > /dev/null
   6,009,233,608 bytes allocated in the heap
     622,682,200 bytes copied during GC
         443,240 bytes maximum residency (505 sample(s))
          48,256 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)
                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     10945 colls,     0 par    0.72s    0.63s     0.0001s    0.0004s
  Gen  1       505 colls,     0 par    0.16s    0.13s     0.0003s    0.0005s
  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    2.00s  (  2.13s elapsed)
  GC      time    0.87s  (  0.76s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    2.89s  (  2.90s elapsed)
  %GC     time      30.3%  (26.4% elapsed)
  Alloc rate    3,009,412,603 bytes per MUT second
  Productivity  69.7% of total user, 69.4% of total elapsed

Bu soruya düzgün bir cevap alır zamanı geldi sanırım.

Ne -O ile kodunuzu oldu

Bana ana işlevi yakınlaştırayım ve hafifçe yeniden yazmak:

main :: IO ()
main = do
    [n, m] <- fmap (map read . words) getLine
    line <- getLine
    let nodes = listArray (0, n) . tonodes n . map (subtract 1) . map read . words $ line
    replicateM_ m $ query n nodes

Açıkça, burada niyet NodeArray bir kez oluşturulan, ve sonra query m çağırmaları her kullanılır.

Ne yazık ki, DZD bu kod, etkili dönüşür

main = do
    [n, m] <- fmap (map read . words) getLine
    line <- getLine
    replicateM_ m $ do
        let nodes = listArray (0, n) . tonodes n . map (subtract 1) . map read . words $ line
        query n nodes

ve hemen sorun burada görebilirsiniz.

Devlet, neden programlar performansım yok . hack nedir

Neden devlet diyor hack, (kabaca): tip bir şey Olduğunda “IO a, yalnızca bir kez denir varsayalım”.. official documentation çok fazla ayrıntılı değil:

-fno-state-hack

Off "" mademki bir Devlet ile herhangi bir lambda# argüman tek giriş olduğu için token, dolayısıyla sorun iç işler için satır içi olarak kabul edilir. devlet hack açmak Bu IO ve ST monad kod performansını artırmak olabilir, ama paylaşım azaltılması riskini çalışır.

IO tipinde bir fonksiyon tanımlamak ve nerede maddesi, örn . kabaca, fikir şöyledir:

foo x = do
    putStrLn y
    putStrLn y
  where y = ...x...

Türü bir şey IO a türü bir şey RealWord -> (a, RealWorld) olarak görülebilir. Bu görüş, yukarıda olur (yaklaşık)

foo x = 
   let y = ...x... in 
   \world1 ->
     let (world2, ()) = putStrLn y world1
     let (world3, ()) = putStrLn y world2
     in  (world3, ())

29* *çağrı (genellikle) foo argument world Bu gibi görünecektir. Ama foo tanımı sadece bir argüman alır, diğeri de daha sonra yerel bir lambda ifadesi tarafından tüketilen! 32 ** çok yavaş bir telefon olacak. Eğer kod şöyle olsaydı çok daha hızlı olurdu

foo x world1 = 
   let y = ...x... in 
   let (world2, ()) = putStrLn y world1
   let (world3, ()) = putStrLn y world2
   in  (world3, ())

Bu eta-genişleme olarak adlandırılan ve çeşitli gerekçelerle (checking how it is being called, ve bu durumda tipi yönlendirilmiş keşif analyzing the function’s definition, örneğin) üzerinde yapılır.

Ne yazık ki eğer 34 ** çağrısı aslında let fooArgument = foo argument, yani bir tartışma formu, ama world (henüz) geçti hiç duyulmamış. Eğer fooArgument sonra birkaç kez kullanılan orijinal kodu, y hala sadece bir kez hesaplanır ve paylaştı. , y düzeltilmiş kodun içinde ne olduğunu yeniden hesaplanan her zaman hassas olacak nodes.

Bir şeyler tamir edilebilir mi?

Muhtemelen. Bunu yaparken de bir girişim için #9388 bkz. Tamir sorunu budönüşümü derleyici mümkün değildir, bundan emin olsa Tamam, olur bir çok durumda performans maliyeti. Ve muhtemelen teknik sorun olmadığı durumlarda, yani orada paylaşım kaybolur, ama daha hızlı arama gelen speedups seferden ekstra maliyet ağır bastığı için hala faydalıdır. Buradan nereye belli değil.