In this case, since the argument can have only 1000 different values, you
can use the technique in Section 16 of *Index-Of, a 30-Year Quest
<https://www.jsoftware.com/papers/indexof/indexof.htm>* or Section 3.3 of *APL
Since 1978 <http://doi.org/10.1145/3386319>.* That is, use *key* f/.
On Sun, Sep 13, 2020 at 2:21 PM Julian Fondren <jfond...@minimaltype.com>
wrote:
> Suppose we have a file with 10 million lines, with a lot of
> repeats (realistic example: a huge log with a lot of emails or
> IPs to consider).
>
> This sentence can create such a file:
>
> 'names.list' fwrites~ a. {~ (a.i.'a') + 10 #.inv 1e7 ?@$ 1000
>
> And here are some ways to get the top 5 occurrences in this
> list, with their rough costs:
>
> (5s, 1.3 GB) Bash oneliner:
>
> sort names.list| uniq -c|sort -n|tail -5
>
> (2s, 6 MB) Perl, using a hash to count words:
>
> #! /usr/bin/env perl
> use strict;
> use warnings;
>
> my %words;
> open my $ws, '<', 'names.list' or die $!;
> while (defined (my $w = <$ws>)) {
> chomp $w;
> $words{$w}++;
> }
> printf "%7d %s\n", $words{$_}, $_ for
> (sort { $words{$b} <=> $words{$a} } keys %words)[0..5];
>
> (12s, 11 GB) J, avoiding immutable i. hash tables:
>
> words =: s:<;._2 fread 'names.list'
> uniq =: ~. words
> count =: +/"1 uniq ="0 1 words
> top =: ((#count) - >:i.5) ({ /:) count
> echo (5 s: top { uniq) ,: <"0 top { count
>
> (9s, 1.5 GB) J, trying to use immutable i. hash tables:
>
> words =: 0$<''
> count =: 0$0
> search =: words&i.
> 3 : 0''
> for_w. 'b' fread 'names.list' do.
> i =. search w
> if. i = #words do.
> words =: words , w
> search =: words&i.
> count =: count , 1
> else.
> count =: (>:i{count) i } count
> end.
> end.
> )
> top =: ((#count) - >:i.5) ({ /:) count
> echo (top { words) ,: <"0 top { count
>
> This only has to rebuild the hash table 1e3 times despite
> processing 1e7 lines, so 'search' does very well.
>
> On less friendly data (by taking the names.list generator above
> changing 1000 to 1e7) this solution didn't finish in 22 minutes.
> Perl's also hit by the rebuilds, going from 2s to 19s.
>
> (42s, 1.5 GB) J, trying a mutable hash table from RosettaCode:
>
> coclass 'dictionary'
> okchar=:~. (,toupper) '0123456789abcdefghijklmnopqrstuz'
> ok=: ] [ [: assert [: *./ e.&okchar
> intern=: [: ('z' , ok)&.> boxxopen
> has=: _1 < nc@intern
> set=: 4 :'(intern x)=: y'
> get=: ".@>@intern
>
> words=: conew 'dictionary'
> keys=:0$<''
> 3 : 0''
> for_w. 'b' fread 'names.list' do.
> if. has__words >w do.
> (>w) set__words 1+get__words (>w)
> else.
> (>w) set__words 1
> keys =: keys , w
> end.
> end.
> )
> values=:get__words each keys
> echo echo (5 {. keys \: values) ,: (5 {. \:~ values)
>
> (1.5s, 450 MB) a jd solution:
>
> require 'data/jd'
> words=:'m' fread 'names.list'
> jdadminnew'tmp'
> jd'createtable t1 word byte ',":1{$words
> jd'insert';'t1';'word';words
> 'ws cn' =: 5&{. each 1{"1 jd'read count:count word by word from t1
> order by count desc'
> echo (<"1 ws) ,: ;/cn
>
>
> This is a problem where, in a language with mutable hash
> tables, I'd use them and this would mostly work out well. In
> J, I feel like I'm missing some useful primitive or some APL
> technique. Is that the case?
>
> Cheers,
> Julian
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
