Задачка на самый быстрый подсчет встречаемости слов

$ sed -i 's/make_unique_for_overwrite/make_unique/' 1.cpp

$ wc -l huge.txt
6455997 huge.txt

$ wc -l words.txt
58801281 words.txt

lve@gw3: ~/src/wc$ /usr/bin/time -f "%E %U %S %M"  ./a 
3342166 the
1851942 and
1715610 of
1559709 to
1323954 a
 956950 in
 932225 i

0:02.06 1.99 0.06 462832

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <string.h>

char *in_file="huge.txt";

static uint8_t aho_lc[256] = {
  0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
 16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,
 32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,
 48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,
 64, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',  91,  92,  93,  94,  95,
 96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127,
};

struct node {
    struct node *next[32];
    int count;
} root = { .next = {NULL,}, .count = 0};

struct word {
    int count;
    char *t;
};
typedef struct word word_t;

word_t *all_words = NULL;
int all_words_count = 0;
word_t *words_last;

char d_buf[1024];

void dump(struct node *n,int pos,char *buf,size_t l) {
    int i;
    if(pos >= l) return;
    for(i=0;i < 32; i++) {
       char c = 'a'+i;
       if(n->next[i]) {
        buf[pos] = c;
        dump(n->next[i],pos+1,buf,l);
       }
    }
    buf[pos] = 0;
    if(n->count) {
        words_last->count = n->count;
        words_last->t = strdup(buf);
        words_last++;
    }
    return;
}
int cmp_cnt(const void *a, const void *b) {
    return ((word_t *)b)->count - ((word_t *)a)->count;
}

int main(int argc,char **argv) {

char *buf,*i,*end,c;
int fd,na,ci;
struct stat st;
struct node *n;

    if(argv[1]) in_file = argv[1];
    if(stat(in_file,&st)) abort();
    fd=open(in_file,O_RDONLY);
    if(fd < 0) abort();

    buf = mmap(NULL,st.st_size,PROT_READ,MAP_SHARED,fd,0);
    if(buf == MAP_FAILED) abort();

    end = buf + st.st_size;
    for(i=buf,n = &root; i < end; i++) {
        c = *i;
        na = 1;
        if((c & 0xC0) != 0x80) {
            c = (char)aho_lc[(uint8_t)c];
            if(c >= 'a' && c <= 'z')
                na = 0;
        } else
            i++;
        if(na) {
            if(n != &root) {
                if(!n->count) all_words_count++;
                n->count++; n = &root;
            }
            continue;
        }
        ci = c - 'a';
        if(ci >= 32) abort();
        if(!n->next[ci]) {
            n->next[ci] = (struct node*)calloc(1,sizeof(struct node));
            if(!n->next[ci]) abort();
        }
        n = n->next[ci];
    }
    munmap(buf,st.st_size);
    close(fd);
    all_words = (struct word *)calloc(all_words_count,sizeof(struct word));
    words_last = all_words;
    dump(&root,0,d_buf,sizeof(d_buf)-1);

    qsort(all_words,all_words_count,sizeof(word_t),cmp_cnt);
    for(ci = 0; ci < all_words_count; ci++) {
        printf("%7d %s\n",all_words[ci].count,all_words[ci].t);
        if(ci >= 6) break;
    }
    return 0;
}

@@ -80 +80 @@
-        c = *i;
+        c = *i | 0x20;
@@ -82,2 +82,2 @@
-        if((c & 0xC0) != 0x80) {
-            c = (char)aho_lc[(uint8_t)c];
+        /* if((c & 0xC0) != 0x80) {
+            c = (char)aho_lc[(uint8_t)c]; */
@@ -86,2 +86,2 @@
-        } else
-            i++;
+        /* } else
+            i++;*/

$ ls -sh random.txt 
50M random.txt

$ /bin/time -f "%E %U %S %M" ./vel random.txt                
  92364 p
  92318 u
  ...
0:03.53 2.91 0.60 2716716

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"sort"
	"strings"
	"unicode"
	"unicode/utf8"
)

type word struct {
	s string
	n int
}

type byCount []word

func (w byCount) Len() int               { return len(w) }
func (w byCount) Less(i int, j int) bool { return w[i].n < w[j].n }
func (w byCount) Swap(i int, j int)      { w[i], w[j] = w[j], w[i] }

func main() {
	f, err := os.Open("huge.txt")
	if err != nil {
		log.Fatal(err)
	}
	defer f.Close()
	s := bufio.NewScanner(f)
	s.Split(func(data []byte, atEOF bool) (advance int, token []byte, err error) {
		start := 0
		for width := 0; start < len(data); start += width {
			var r rune
			r, width = utf8.DecodeRune(data[start:])
			if unicode.IsLetter(r) {
				break
			}
		}
		for width, i := 0, start; i < len(data); i += width {
			var r rune
			r, width = utf8.DecodeRune(data[i:])
			if !unicode.IsLetter(r) {
				return i + width, data[start:i], nil
			}
		}
		if atEOF && len(data) > start {
			return len(data), data[start:], nil
		}
		return start, nil, nil
	})
	m := make(map[string]int)
	for s.Scan() {
		m[strings.ToLower(s.Text())]++
	}
	var w []word
	for k, v := range m {
		w = append(w, word{s: k, n: v})
	}
	sort.Sort(sort.Reverse(byCount(w)))
	o, err := os.Create("out.txt")
	if err != nil {
		log.Fatal(err)
	}
	defer o.Close()
	for _, v := range w {
		fmt.Fprintln(o, v.n, v.s)
	}
}

3343163 the
1852685 and
1715662 of
1559874 to
1320986 a
956891 in
933115 i
781270 he
713514 that
690876 was

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"os"
	"sort"
)

type StringIntStruct struct {
	k string
	v int
}

type ArrayOfStringIntStruct []StringIntStruct

func (a ArrayOfStringIntStruct) Len() int           { return len(a) }
func (a ArrayOfStringIntStruct) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ArrayOfStringIntStruct) Less(i, j int) bool { return a[i].v > a[j].v }

func main() {
	content, err := ioutil.ReadFile("huge.txt")
	if err != nil {
		log.Fatal(err)
	}
	map_words := make(map[string]int)
	var word [1024]byte
	w := 0
	for _, c := range content {
		c = c | 32
		if c >= 'a' && c <= 'z' {
			word[w] = c
			w += 1
			continue
		}
		if w > 0 {
			map_words[string(word[0:w])] += 1
			w = 0
		}
	}
	count_words := len(map_words)
	array_words := make(ArrayOfStringIntStruct, count_words)
	w = 0
	for k, v := range map_words {
		array_words[w] = StringIntStruct{k, v}
		w++
	}
	sort.Sort(array_words)
	o, err := os.Create("out.txt")
	if err != nil {
		log.Fatal(err)
	}
	defer o.Close()
	for _, v := range array_words {
		fmt.Fprintln(o, v.v, v.k)
	}
}

package main

import (
	"fmt"
	"io/ioutil"
	"log"
	"runtime"
	"sort"
	"sync"
)

type StringIntStruct struct {
	k string
	v int
}

type ArrayOfStringIntStruct []StringIntStruct

func (a ArrayOfStringIntStruct) Len() int           { return len(a) }
func (a ArrayOfStringIntStruct) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ArrayOfStringIntStruct) Less(i, j int) bool { return a[i].v > a[j].v }

func fill_data(wg *sync.WaitGroup, data []byte, start int, stop int, m map[string]int) {
	defer wg.Done()
	var word [1024]byte
	w := 0
	for i := start; i <= stop; i++ {
		c := data[i] | 32
		if c >= 'a' && c <= 'z' {
			word[w] = c
			w += 1
			continue
		}
		if w > 0 {
			m[string(word[0:w])]++
			w = 0
		}
	}

}

func main() {
	var wg sync.WaitGroup
	content, err := ioutil.ReadFile("huge.txt")
	if err != nil {
		log.Fatal(err)
	}
	len_content := len(content)
	num_of_cores := runtime.NumCPU()
	arr_map_words := make([]map[string]int, num_of_cores)
	part_content := len_content / num_of_cores
	var part_start, part_stop int
	part_start = 0
	for core := 1; core <= num_of_cores; core++ {
		part_stop = part_content * core
		var bound_sym byte
		for {
			if part_stop >= len_content-1 {
				part_stop = len_content - 1
				break
			}
			bound_sym = content[part_stop] | 32
			if bound_sym < 'a' || bound_sym > 'z' {
				break
			}
			part_stop++
		}
		arr_map_words[core-1] = make(map[string]int)
		wg.Add(1)
		go fill_data(&wg, content, part_start, part_stop, arr_map_words[core-1])
		part_start = part_stop + 1
	}
	wg.Wait()
	map_words := arr_map_words[0]
	for core := 1; core < num_of_cores; core++ {
		for k, v := range arr_map_words[core] {
			map_words[k] += v
		}
	}
	count_words := len(map_words)
	array_words := make(ArrayOfStringIntStruct, count_words)
	w := 0
	for k, v := range map_words {
		array_words[w] = StringIntStruct{k, v}
		w++
	}
	sort.Sort(array_words)

	for i, word := range array_words {
		if i >= 20 {
			break
		}
		fmt.Printf("%v   %v\n", word.v, word.k)
	}
	fmt.Printf("------------\nCount words: %d\n", count_words)
}

$ /bin/time -f "Time: %e s; Mem: %M kB" ./count_words
3343241 the
1852717 and
1715705 of
1560152 to
1324244 a
Time: 1.35 s; Mem: 677996 kB

$ /bin/time -f "Time: %e s; Mem: %M kB" ./vel        
...
Time: 1.67 s; Mem: 439876 kB

package test;

import java.io.*;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.channels.SeekableByteChannel;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;

public class WordsCounter {
    public static void main(String[] args) throws IOException {
        var startTime = System.nanoTime();

        var wordStats = new HashMap<String, WordStat>();

        var inputPath = Path.of("C:\\Users\\Vladimir\\Downloads\\huge.txt");
        try (var fileChannel = FileChannel.open(inputPath)) {
            MappedByteBuffer mappedBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size());
            var wordBuilder = new StringBuilder();
            while (mappedBuffer.hasRemaining()) {
                byte b = mappedBuffer.get();
                if (('A' <= b) && (b <= 'Z')) {
                    wordBuilder.append((char) (b + ('a' - 'A')));
                } else if (('a' <= b) && (b <= 'z')) {
                    wordBuilder.append((char) b);
                } else {
                    if (!wordBuilder.isEmpty()) {
                        var word = wordBuilder.toString();
                        var wordStat = wordStats.get(word);
                        if (wordStat == null) {
                            wordStat = new WordStat(word);
                            wordStats.put(word, wordStat);
                        } else {
                            wordStat.incCount();
                        }
                        wordBuilder.delete(0, wordBuilder.length());
                    }
                }
            }
        }

        var part1Time = System.nanoTime();
        System.out.println("Part 1: " + (part1Time - startTime));

        var wordStatList = new ArrayList<>(wordStats.values());
        wordStatList.sort(Comparator.comparing(WordStat::count).reversed());

        var part2Time = System.nanoTime();
        System.out.println("Part 2: " + (part2Time - part1Time));

        var resultPath = Path.of("tmp\\result.txt");
        try (var writer = Files.newBufferedWriter(resultPath)) {
            for (WordStat wordStat : wordStatList) {
                writer.write(Integer.toString(wordStat.count()));
                writer.write(' ');
                writer.write(wordStat.word());
                writer.newLine();
            }
        }
        var part3Time = System.nanoTime();
        System.out.println("Part 3: " + (part3Time - part2Time));
        System.out.println("Total: " + (part3Time - startTime));
    }

    static class WordStat {
        private final String word;
        private int count;

        WordStat(String word) {
            this.word = word;
            count = 1;
        }

        String word() {
            return word;
        }

        int count() {
            return count;
        }

        void incCount() {
            count++;
        }
    }
}

Part 1: 4861061700
Part 2: 62542400
Part 3: 59626800
Total: 4983230900

package test;

import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class WordsCounter {
    public static void main(String[] args) throws IOException, ExecutionException, InterruptedException {
        var startTime = System.nanoTime();
        System.out.println("start");

        List<HashMap<String, WordStat>> wordStatsList = new ArrayList<>();

        var inputPath = Path.of("C:\\Users\\Vladimir\\Downloads\\huge.txt");
        try (var fileChannel = FileChannel.open(inputPath)) {
            MappedByteBuffer mappedBuffer = fileChannel.map(FileChannel.MapMode.READ_ONLY, 0, fileChannel.size());
            int limit = mappedBuffer.limit();
            var nThreads = Runtime.getRuntime().availableProcessors();
            var executorService = Executors.newFixedThreadPool(nThreads);
            List<Future<HashMap<String, WordStat>>> futures = new ArrayList<>();
            int start = 0;
            for (int i = 1; i < nThreads; i++) {
                int end = i * limit / nThreads;
                while (true) {
                    int b1 = mappedBuffer.get(end - 1);
                    int b2 = mappedBuffer.get(end);
                    boolean l1 = (('A' <= b1) && (b1 <= 'Z')) || (('a' <= b1) && (b1 <= 'z'));
                    boolean l2 = (('A' <= b2) && (b2 <= 'Z')) || (('a' <= b2) && (b2 <= 'z'));
                    if (!l1 || !l2) {
                        break;
                    }
                    end++;
                }
                futures.add(executorService.submit(new CounterTask(mappedBuffer, start, end)));
                start = end;
            }
            futures.add(executorService.submit(new CounterTask(mappedBuffer, start, limit)));

            for (Future<HashMap<String, WordStat>> future : futures) {
                var wordStats = future.get();
                wordStatsList.add(wordStats);
            }
            executorService.shutdown();
        }

        HashMap<String, WordStat> wordStats = wordStatsList.get(0);
        for (int i = 1; i < wordStatsList.size(); i++) {
            var wordStats2 = wordStatsList.get(i);
            for (Map.Entry<String, WordStat> wordStat2Entry : wordStats2.entrySet()) {
                String word = wordStat2Entry.getKey();
                WordStat wordStat2 = wordStat2Entry.getValue();
                WordStat wordStat = wordStats.get(word);
                if (wordStat == null) {
                    wordStats.put(word, wordStat2);
                } else {
                    wordStat.incCount(wordStat2.count());
                }
            }
        }

        var wordStatList = new ArrayList<>(wordStats.values());
        wordStatList.sort(Comparator.comparing(WordStat::count).reversed());

        var resultPath = Path.of("tmp\\result.txt");
        try (var writer = Files.newBufferedWriter(resultPath)) {
            for (WordStat wordStat : wordStatList) {
                writer.write(Integer.toString(wordStat.count()));
                writer.write(' ');
                writer.write(wordStat.word());
                writer.newLine();
            }
        }
        var part4Time = System.nanoTime();
        System.out.println("Total: " + (part4Time - startTime));
    }

    static class WordStat {
        private final String word;
        private int count;

        WordStat(String word) {
            this.word = word;
            count = 1;
        }

        String word() {
            return word;
        }

        int count() {
            return count;
        }

        void incCount() {
            count++;
        }

        void incCount(int amount) {
            count += amount;
        }
    }

    private static class CounterTask implements Callable<HashMap<String, WordStat>> {
        private final ByteBuffer byteBuffer;
        private final int start;
        private final int end;

        CounterTask(ByteBuffer byteBuffer, int start, int end) {
            this.byteBuffer = byteBuffer;
            this.start = start;
            this.end = end;
        }

        @Override
        public HashMap<String, WordStat> call() {
            var wordStats = new HashMap<String, WordStat>();
            var wordBuilder = new StringBuilder(70);
            for (int i = start; i < end; i++) {
                byte b = byteBuffer.get(i);
                if (('A' <= b) && (b <= 'Z')) {
                    wordBuilder.append((char) (b + ('a' - 'A')));
                } else if (('a' <= b) && (b <= 'z')) {
                    wordBuilder.append((char) b);
                } else if (!wordBuilder.isEmpty()) {
                    var word = wordBuilder.toString();
                    var wordStat = wordStats.get(word);
                    if (wordStat == null) {
                        wordStat = new WordStat(word);
                        wordStats.put(word, wordStat);
                    } else {
                        wordStat.incCount();
                    }
                    wordBuilder.delete(0, wordBuilder.length());
                }
            }
            if (!wordBuilder.isEmpty()) {
                var word = wordBuilder.toString();
                var wordStat = wordStats.get(word);
                if (wordStat == null) {
                    wordStat = new WordStat(word);
                    wordStats.put(word, wordStat);
                } else {
                    wordStat.incCount();
                }
            }
            return wordStats;
        }
    }
}

start
Total: 2182135900

int b1 = mappedBuffer.get(end - 1);
int b2 = mappedBuffer.get(end);
boolean l1 = (('A' <= b1) && (b1 <= 'Z')) || (('a' <= b1) && (b1 <= 'z'));
boolean l2 = (('A' <= b2) && (b2 <= 'Z')) || (('a' <= b2) && (b2 <= 'z'));

while (true) {
    int b = mappedBuffer.get(end) | 0x20;
    if (b < 'a' || b > 'z')
        break;
    end++;
}