Nice! It's worth pointing out, though, that by limiting yourself to
alpha chars, you're processing about 8% less data and the results don't
pass the tests. :P
$ wc kjvbible_x10.txt
998170 8211330 43325060
$ sed 's/[a-zA-Z ]//g' < kjvbible_x10.txt | wc
998170 739310 3600800
I think your version would still be faster, but I'm curious what the
numbers would look like if only whitespace chars were considered word
separators.
Dominik Pantůček writes:
> Another attack of [1]. But yeah, why not do some [2].
>
> Trees to the rescue [3].
>
> $ racket --version
> Welcome to Racket v8.0 [cs].
>
> $ racket countwords-bogdan2.rkt <kjvbible.txt |tail -1
> cpu time: 135 real time: 135 gc time: 8
>
> $ racket countwords-dzoe2.rkt <kjvbible.txt | tail -1
> cpu time: 69 real time: 69 gc time: 3
>
> I just changed (countwords) to (time (countwords)) in Bogdan's code to
> measure the running time.
>
> The difference is that I am positively defining which letters form words
> (a-z, A-Z) and that all others are treated as word separators. The
> buffer size is the same - and honestly, the speedup between 1024 and
> 1024^2 bytes buffer is barely measurable.
>
> The only option for further speedup I can immediately think of is to
> allocate a huge vector of wtnodes and change chld field to be a starting
> index into this big vector (should reduce allocations).
>
> Btw, making it unsafe does not speed it up at all (probably CS
> recognizes the vectors and all those refs are inlined anyway).
>
>
> Cheers,
> Dominik
>
> [1] https://xkcd.com/386/
> [2] http://phdcomics.com/comics/archive.php?comicid=1735
> [3] https://gist.github.com/dzoep/0e081d0544afac539a4829179c601e0e
>
> On 19. 03. 21 11:18, Bogdan Popa wrote:
>> I updated the gist with some cleanups and additional improvements that
>> get the runtime down to a little over 1s (vs ~350ms for the optimized C
>> and Rust code) on my maxed-out 2019 MBP and ~600ms on my M1 Mac Mini.
>>
>> Pawel Mosakowski writes:
>>
>>> Hi Bogdan,
>>>
>>> This is a brilliant solution and also completely over my head. It finishes
>>> in ~3.75s on my PC and is faster than the Python version which basically
>>> delegates all the work to C. I will need to spend some time on
>>> understanding it but I am looking forward to learning something new.
>>>
>>> Many thanks,
>>> Pawel
>>>
>>> On Thursday, March 18, 2021 at 7:22:10 PM UTC bogdan wrote:
>>>
>>>> I managed to get it about as fast as Python by making it really
>>>> imperative and rolling my own hash:
>>>>
>>>> https://gist.github.com/Bogdanp/fb39d202037cdaadd55dae3d45737571
>>>>
>>>> Sam Tobin-Hochstadt writes:
>>>>
>>>>> Here are several variants of the code:
>>>>> https://gist.github.com/d6fbe3757c462d5b4d1d9393b72f9ab9
>>>>>
>>>>> The enabled version is about the fastest I can get without using
>>>>> `unsafe` (which the rules said not to do). It's possible to optimize a
>>>>> tiny bit more by avoiding sorting, but only a few milliseconds -- it
>>>>> would be more significant if there were more different words.
>>>>>
>>>>> Switching to bytes works correctly for the given task, but wouldn't
>>>>> always work in the case of general UTF8 input. But those versions
>>>>> appeared not be faster for me. Also, writing my own string-downcase
>>>>> didn't help. And using a big buffer and doing my own newline splitting
>>>>> didn't help either.
>>>>>
>>>>> The version using just a regexp matching on a port (suggested by
>>>>> Robby) turned out not to be faster either, so my suspicion is that the
>>>>> original slowness is just using regexps for splitting words.
>>>>>
>>>>> Sam
>>>>>
>>>>> On Thu, Mar 18, 2021 at 11:28 AM Sam Tobin-Hochstadt
>>>>> <[email protected]> wrote:
>>>>>>
>>>>>> Here's a somewhat-optimized version of the code:
>>>>>>
>>>>>> #lang racket/base
>>>>>> (require racket/string racket/vector racket/port)
>>>>>>
>>>>>> (define h (make-hash))
>>>>>>
>>>>>> (time
>>>>>> (for* ([l (in-lines)]
>>>>>> [w (in-list (string-split l))]
>>>>>> [w* (in-value (string-downcase w))])
>>>>>> (hash-update! h w* add1 0)))
>>>>>>
>>>>>> (define v
>>>>>> (time
>>>>>> (for/vector #:length (hash-count h)
>>>>>> ([(k v) (in-hash h)])
>>>>>> (cons k v))))
>>>>>> (time (vector-sort! v > #:key cdr))
>>>>>> (define p (current-output-port) #;(open-output-nowhere))
>>>>>> (time
>>>>>> (for ([pair (in-vector v)])
>>>>>> (write-string (car pair) p)
>>>>>> (write-string (number->string (cdr pair)) p)
>>>>>> (newline p)))
>>>>>>
>>>>>> It's much more imperative, but also pretty nice and compact. The
>>>>>> `printf` optimization is significant for that portion of the program,
>>>>>> but that isn't much of the running time. The overall running time for
>>>>>> 10 copies of the KJV is about 9 seconds on my laptop.
>>>>>>
>>>>>> I think the remaining difference between Racket and other languages is
>>>>>> likely the `string-split` and `string-downcase` functions, plus the
>>>>>> relatively-inefficient string representation that Racket uses.
>>>>>>
>>>>>> Sam
>>>>>>
>>>>>>
>>>>>> On Thu, Mar 18, 2021 at 10:28 AM Pawel Mosakowski <[email protected]>
>>>> wrote:
>>>>>>>
>>>>>>> Hi David,
>>>>>>>
>>>>>>> Yes, the 21 seconds includes the interpreter startup time. I have
>>>> done a simple test to see how long it takes:
>>>>>>>
>>>>>>> $ time racket -e '(displayln "Hello, world")'
>>>>>>> Hello, world
>>>>>>>
>>>>>>> real 0m0.479s
>>>>>>> user 0m0.449s
>>>>>>> sys 0m0.030s
>>>>>>>
>>>>>>> I have also put my code inside a main function and profiled it:
>>>>>>>
>>>>>>> Profiling results
>>>>>>> -----------------
>>>>>>> Total cpu time observed: 20910ms (out of 20970ms)
>>>>>>> Number of samples taken: 382 (once every 55ms)
>>>>>>> (Hiding functions with self<1.0% and local<2.0%: 1 of 12 hidden)
>>>>>>>
>>>>>>> ==============================================================
>>>>>>> Caller
>>>>>>> Idx Total Self Name+src Local%
>>>>>>> ms(pct) ms(pct) Callee
>>>>>>> ==============================================================
>>>>>>> [1] 20910(100.0%) 0(0.0%) [running body]
>>>> ...word-occurences-profile.rkt":##f
>>>>>>> profile-thunk [2] 100.0%
>>>>>>> --------------------------------------------------------------
>>>>>>> [running body] [1] 100.0%
>>>>>>> [2] 20910(100.0%) 0(0.0%) profile-thunk
>>>> ...ket/pkgs/profile-lib/main.rkt:9:0
>>>>>>> run [3] 100.0%
>>>>>>> --------------------------------------------------------------
>>>>>>> profile-thunk [2] 100.0%
>>>>>>> [3] 20910(100.0%) 0(0.0%) run
>>>> ...share/racket/pkgs/profile-lib/main.rkt:39:2
>>>>>>> main [4] 100.0%
>>>>>>> --------------------------------------------------------------
>>>>>>> run [3] 100.0%
>>>>>>> [4] 20910(100.0%) 50(0.2%) main
>>>> ...cket/count-word-occurences-profile.rkt:5:0
>>>>>>> read-from-stdin-it [5] 98.5%
>>>>>>> ??? [6] 0.2%
>>>>>>> --------------------------------------------------------------
>>>>>>> main [4] 100.0%
>>>>>>> [5] 20606(98.5%) 11796(56.4%) read-from-stdin-it
>>>> ...-occurences-profile.rkt:19:6
>>>>>>> internal-split [7] 42.8%
>>>>>>> --------------------------------------------------------------
>>>>>>> main [4] 100.0%
>>>>>>> [6] 51(0.2%) 0(0.0%) ???
>>>> ...cket/collects/racket/private/sort.rkt:369:3
>>>>>>> generic-sort/key [8] 100.0%
>>>>>>> --------------------------------------------------------------
>>>>>>> read-from-stdin-it [5]100.0%
>>>>>>> [7] 8810(42.1%) 3528(16.9%) internal-split
>>>> ...collects/racket/string.rkt:117:0
>>>>>>> regexp-split [9] 59.9%
>>>>>>> --------------------------------------------------------------
>>>>>>> ??? [6] 100.0%
>>>>>>> [8] 51(0.2%) 0(0.0%) generic-sort/key
>>>> .../racket/private/sort.rkt:156:2
>>>>>>> copying-mergesort [10]100.0%
>>>>>>> --------------------------------------------------------------
>>>>>>> internal-split [7] 100.0%
>>>>>>> [9] 5282(25.3%) 2810(13.4%) regexp-split
>>>> ...ts/racket/private/string.rkt:338:2
>>>>>>> loop [11] 46.8%
>>>>>>> --------------------------------------------------------------
>>>>>>> generic-sort/key [8] 10.0%
>>>>>>> copying-mergesort [10] 90.0%
>>>>>>> [10] 51(0.2%) 51(0.2%) copying-mergesort
>>>> ...racket/private/sort.rkt:129:8
>>>>>>> copying-mergesort [10] 90.0%
>>>>>>> --------------------------------------------------------------
>>>>>>> regexp-split [9] 100.0%
>>>>>>> [11] 2471(11.8%) 2471(11.8%) loop
>>>> ...t/collects/racket/private/string.rkt:169:7
>>>>>>> --------------------------------------------------------------
>>>>>>>
>>>>>>> Kind regards,
>>>>>>> Pawel
>>>>>>>
>>>>>>>
>>>>>>> On Thursday, March 18, 2021 at 2:09:35 PM UTC [email protected]
>>>> wrote:
>>>>>>>>
>>>>>>>> Hi Pawel,
>>>>>>>>
>>>>>>>> I'll take a look at the code later, but did that 21 seconds include
>>>> startup time for the interpreter?
>>>>>>>>
>>>>>>>> On Thu, Mar 18, 2021, 9:24 AM Pawel Mosakowski <[email protected]>
>>>> wrote:
>>>>>>>>>
>>>>>>>>> Hello,
>>>>>>>>>
>>>>>>>>> I am a Racket beginner and I have come across this article:
>>>>>>>>>
>>>>>>>>> https://benhoyt.com/writings/count-words/
>>>>>>>>>
>>>>>>>>> This is my attempt at solving the challenge:
>>>>>>>>>
>>>>>>>>> https://pastebin.com/kL16w5Hc
>>>>>>>>>
>>>>>>>>> However when I have benchmarked it, it takes ~21 seconds to run
>>>> compared to the Python and Ruby versions which take around 3-4 seconds.
>>>>>>>>>
>>>>>>>>> I understand that both Ruby and Python probably have the string
>>>> operations and hash tables implemented in optimized C but is there anything
>>>> I can do to improve performance of my program?
>>>>>>>>>
>>>>>>>>> Many thanks for all help and suggestions.
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> You received this message because you are subscribed to the Google
>>>> Groups "Racket Users" group.
>>>>>>>>> To unsubscribe from this group and stop receiving emails from it,
>>>> send an email to [email protected].
>>>>>>>>> To view this discussion on the web visit
>>>> https://groups.google.com/d/msgid/racket-users/118c1340-66d1-421d-92a4-6b66c56cb88fn%40googlegroups.com
>>>> .
>>>>>>>
>>>>>>> --
>>>>>>> You received this message because you are subscribed to the Google
>>>> Groups "Racket Users" group.
>>>>>>> To unsubscribe from this group and stop receiving emails from it,
>>>> send an email to [email protected].
>>>>>>> To view this discussion on the web visit
>>>> https://groups.google.com/d/msgid/racket-users/09c58a34-bd2d-49e7-bfbd-d3253c1e6dd1n%40googlegroups.com
>>>> .
>>>>
>>
--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/racket-users/m2o8ff2vnt.fsf%40192.168.0.142.
