Brojanje reči

[Prizma]

Оћу ђавола… Сад ме чачка ђе је запело . Грешка откопана, ал решење мора да се мења комплетно. Значи неки hashset…

 

[Prizma]

Програмче преправљено и тестирано на оба ситема. Једино не проваљујем како ми реч lord остаје великим словима, ал мрзи ме да се бакћем сад.

 

[Branimir_Maksimovic]

Samo si zaboravio da prikacis programce

 

[Prizma]

Качим кад се вратим. Баш да видим резултат и на другим дистроима. Требаће ти одавде око 200mb
.NET Downloads for Linux, macOS, and Windows
и libicu52_1. Има ваљда за арч

 

[Branimir_Maksimovic]

Imam vec instalirano:

~ >>> pacman -Qs dotnet   
local/dotnet-host 2.2.0+100-1
  A generic driver for the .NET Core Command Line Interface
local/dotnet-runtime 2.2.0+100-1
  The .NET Core runtime
local/dotnet-sdk 2.2.0+100-1
  The .NET Core SDK

 

[Prizma]

Ок. Твој тест ће бити мало меродавнији, будући да ја користим легалну верзију W10 ко и сваки просечан србин, с тим што је ова додатно огољена од разноразних глупости, па ради много брже.

 

[Prizma]

Ево га. Само измени путању фајла у Program.cs, то сам одрадио сељачки.

Мала занимљивост:
Мислим да никада више нећу урадити тако ефикасну оптимизацију xD

 

[Branimir_Maksimovic]

“it took me 2848 miliseconds to do this”

Pojavljuje se i And i and kao dve razlicite reci, znaci nisi uradio pretvaranje u mala slova pre brojanja.

greska je cini mi se ovde:

  string[] separatedWords = SeparateWords(text);
  string[] filteredWords = IsString(separatedWords);
  GetUniqueWords(UniqueWords,separatedWords, out int totalSum);
  CalculateReps(UniqueWords, separatedWords, totalSum, stoperica);

Znaci racunas filteredWords ali dalje nigde ne koristis u izracunavanju.

 

[Prizma]

Ту је, ал не сме да се замени тек тако, морам малчице да преправим IsString() ф-ју. Користио сам оне најпримитивније листе које су брже, ал имају крајње нефлексибилну употребу.
Edit:
Ако није проблем, који процесор имате? Гледам резултате, ~2 секунде је фина разлика.
Код ћу да преправим, али сада већ морам да будем добро дете и идем на спавање.

 

[Branimir_Maksimovic]

Heh, kad ne mozes da dodajes na niz u csharp
Koristi listu umesto toga i resen problem.

 

[Prizma]

Преправљено, ал не могу да измерим разлику у брзини, јер ми тренутно нешто ради у позадини. Позабавићу се multithreading-ом, то нисам користио никад. Можда успем да смакнем још коју милисекунду.

 

[Branimir_Maksimovic]

Napravio sam multi threading Haskell verziju al je drasticno sporije zato sto jedino sto moze da se paralelizuje je
brojanje reci. Znaci operacija filterisanja i razdvajanja reci najvise uzima a to ne moze da se paralelizuje.
Elem, evo konkurentne verzije Haskell programa kad sam je vec uradio

{-# Language BangPatterns #-}
import qualified Data.HashTable.IO as H
import qualified Data.ByteString as B
import qualified Data.ByteString.Char8 as B8
import Data.List
import Data.List.Split
import Text.Printf
import Data.Char
import Data.IORef
import Data.Hashable
import Control.Concurrent
import qualified Control.Monad as CM
import GHC.Conc (numCapabilities)
type HashTable k v = H.BasicHashTable k v
newtype MyString = MyString B.ByteString
deriving (Eq)

instance Hashable MyString where
hash (MyString s) = B.foldl (\x y -> x*33 + fromIntegral y) 5381 s
hashWithSalt salt s = hash s
wordFreqConc:: [B.ByteString] -> IO [(B.ByteString, Int)]
wordFreqConc xs = do
let actions = map (\xs -> wordFreq xs) $ chunksOf numCapabilities xs
vars <- mapM (\action -> do
var <- newEmptyMVar
forkIO $ do
!answer <- action
putMVar var answer
return var) actions
result <- H.new :: IO (HashTable B.ByteString (IORef Int))
results <- mapM takeMVar vars
out <- CM.foldM (\hres ht -> CM.foldM (\lst (k,v) -> do
res <- H.lookup lst k
case res of
Nothing -> do
x <- newIORef v
H.insert lst k x
Just x -> do
modifyIORef’ x (+v)
return lst) hres ht)
result results
lst <- H.toList out
mapM ((x,y)-> do
v <- readIORef y
return (x,v)) lst

wordFreq :: [B.ByteString] -> IO [(B.ByteString, Int)]
wordFreq xs = do
ht <- H.new :: IO (HashTable MyString (IORef Int))
mapM_ (updatefreq ht) xs
lst <- H.toList ht
mapM ((MyString x,y)-> do
v <- readIORef y
return (x,v)) lst
where updatefreq ht word = do
!lu <- H.lookup ht (MyString word)
case lu of
Nothing -> do
ref <- newIORef 1
H.insert ht (MyString word) ref
Just x -> modifyIORef’ x (+1)
return ()

main = do
contents <- B.readFile “bible.txt”
result <- wordFreqConc.B8.words $
B8.map toLower $ B8.filter (not.isPunct) contents
let sorted = reverse.sort $ map ((x,y) -> (y,x)) $ result
mapM_ ((x,y) -> printf “%8d %s\n” x (B8.unpack y)) $ take 20 sorted

isPunct c =
c == ‘’’ || c == ‘.’ || c == ‘;’ || c == ‘(’ || c == ‘)’
|| c == ‘"’ || c == ‘?’ || c == ‘-’ || c == ‘_’ || c == ‘!’
|| c == ‘,’ || c == ‘:’ || c == ‘|’

kompajlira se sa:
ghc -O2 bbl4.hs -threaded -rtsopts
a startuje sa:
time ./bbl4 +RTS -N
ovo +RTS je pocetak za Haskell runtime parametre, a -N kaze da koristi jezgara koliko ima, znaci recimo -N2 je da se ogranici na
2 jezgra.

 

[Prizma]

Ја нисам стигао да се занимам до краја. Једино што сам открио, је да је убацивање елемената у листу на тај начин шкакљив (тј. не ради) и да постоји цео скуп класа који се бави том тематиком (све имају управо concurrent префикс). О томе како се све врши контрола над извршавањем појединих thread-ова… има доста. Дођох, видех, сватих да немадох појма. Но најосновнији начин мислим да сам сконтао, а дал ће имати ефекта, видећу. Изиграх се сит са овим

 

[Branimir_Maksimovic]

Pogledaj samo moj primer. Ne treba ti nikakvo lokovanje, samo podelis u chunkove listu reci, onoliko koliko ima
procesora recimo, i onda to paralelno, pa kumuliras. btw sad videh da chunksOf deli u chunkove po parametru ne
u parametar chunkova. Kad stignem kuci popravicu
Inace sumnjam da ce i tad biti brze od single threaded verzije.

 

[Branimir_Maksimovic]

Evo je chunks f-ja, pozvati umesto chunksOf:

chunks :: Int -> [a] -> [[a]] chunks n xs = let clen = length xs `div` n in chunks' clen xs where chunks' _ [] = [] chunks' clen xs = take clen xs : chunks' clen (drop clen xs)

 

[Branimir_Maksimovic]

Elem idemo dalje, bolji rezultat za Haskell se dobija sa -A50m, tj 50 mega za start arenu.

~/…/d/bible >>> time ./bbl4 +RTS -N -A50m -s
63924 the
51696 and
34734 of
13561 to
12913 that
12667 in
10420 he
9838 shall
8997 unto
8971 for
8854 i
8473 his
8177 a
7830 lord
7376 they
7013 be
6989 is
6659 him
6596 not
6430 them
327,384,584 bytes allocated in the heap
164,768 bytes copied during GC
242,856 bytes maximum residency (1 sample(s))
158,552 bytes maximum slop
0 MB total memory in use (0 MB lost due to fragmentation)
[CODE]                                 Tot time (elapsed)  Avg pause  Max pause

Gen 0 0 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.002s 0.002s 0.0015s 0.0015s

TASKS: 34 (1 bound, 33 peak workers (33 total), using -N16)

SPARKS: 0(0 converted, 0 overflowed, 0 dud, 0 GC’d, 0 fizzled)

INIT time 0.014s ( 0.036s elapsed)
MUT time 0.508s ( 0.310s elapsed)
GC time 0.002s ( 0.002s elapsed)
EXIT time 0.002s ( 0.004s elapsed)
Total time 0.526s ( 0.352s elapsed)

Alloc rate 644,731,727 bytes per MUT second

Productivity 96.6% of total user, 88.2% of total elapsed

./bbl4 +RTS -N -A50m -s 0.39s user 0.15s system 146% cpu 0.370 total
[/CODE]

A sad i Rust. Moj omiljeni jezik, koji isto pratim od pocetka
MT resenje podestite CONC na kolko imate logickih procesora:

use std::fs::File;
use std::io;
use std::io::prelude::;
use std::collections::;
use std::sync::mpsc;
use std::thread;
static CONC:usize = 16;

fn main()->Result<(),std::io::Error> {
let mut buf : String = String::new();
let mut file = File::open(“bible.txt”)?;
let n = file.read_to_string(&mut buf)?;
let filtered =
buf.chars().filter(|c| !is_punct(*c)).collect::()
.to_lowercase();
let filtered:Vec = filtered.split_whitespace().map(|x| x.to_string()).collect();
let mut hm : HashMap<String,u32> = HashMap::new();
let chunks = chunks(CONC,&filtered);
let clen = chunks.len();
[CODE]let (tx, rx) = mpsc::channel();

for i in chunks {
    let tx = tx.clone();
    thread::spawn(move || {
        let mut hm: HashMap<String,u32> = HashMap::new();
        for j in i {
            let v = hm.entry(j).or_insert(0);
            *v += 1;
        }
        tx.send(hm).unwrap();
    });
}
for _ in 0..clen {
    let lst = rx.recv().unwrap();
    for (k,v) in lst {
        let vv = hm.entry(k).or_insert(0);
        *vv += v;
    }
}
let mut bm:Vec<(u32,String)> = Vec::new();
for (i,j) in hm {
    bm.push((j,i));
}
bm.sort();
let mut k = 1;
for (i,j) in bm.iter().rev().take(20) {
    println!("{:2} {:8} {}",k,i,j);
    k+=1;
}
Ok(())

}
fn chunks<T:Clone>(n: usize,mut buf : &[T])->Vec<Vec> {
let mut res = Vec::new();
let clen = buf.len() / n;
while buf.len() > clen {
let chunk:Vec = buf[…clen].to_vec();
buf = &buf[clen…];
res.push(chunk)
}
if buf.len() > 0 {
let chunk:Vec = buf.to_vec();
res.push(chunk);
}
res
}

fn is_punct(c: char)->bool{
c == ‘’’ || c == ‘.’ || c == ‘;’ || c == ‘(’ || c == ‘)’
|| c == ‘"’ || c == ‘?’ || c == ‘-’ || c == ‘_’ || c == ‘!’
|| c == ‘,’ || c == ‘:’ || c == ‘|’
}
[/CODE]

Iskompajlirajte sa:
rustc -O -C target-cpu=native bbl.rs
rezultat:

~/.../d/bible >>> time ./bbl 1 63924 the 2 51696 and 3 34734 of 4 13561 to 5 12913 that 6 12667 in 7 10420 he 8 9838 shall 9 8997 unto 10 8971 for 11 8854 i 12 8473 his 13 8177 a 14 7830 lord 15 7376 they 16 7013 be 17 6989 is 18 6659 him 19 6596 not 20 6430 them ./bbl 0.46s user 0.05s system 157% cpu 0.326 total

 

[100]

Bane, još u Brainfuck-u da uradiš i to bi bilo to.

 

[Dragan]

Hm? mislim da bi asembler dao najbrže rešenje…

 

[Branimir_Maksimovic]

Zavisi kako gledas, najvise vremena da se uradi svakako ;p

 

[Prizma]

Касно стижем на Косово, ал ајде… Мучна недеља. Multithreading ( илити вишенитновање, његујмо Србљански језик) има једну гадну ману, а то је да ако радим с једном листом, оба треда ( пардон, нити ) могу да врше промену вредности над истим индексом… па који превагне… не знам како ми није то пало на памет раније. Резултат је наравно погрешан. Бактаћу се још, ако буде било прилике.