Сколько врмени должно занимать получение частоты слов из большого файла?

Question

[12rbah]

Есть файл объемом 5 гигабайт, нужно найти частоту встречаемости слов. Моя реализация занимает по времени тратит около 6 минут на проверку вхождения одного слова и мне кажется, что это слишком много. Поэтому решил уточнить является ли такое время проверки нормальным для такого объема данных.

Comments

[iBird Rose]

ты хоть код выложи, раз ты у тебя уже есть реализация.
p.s. чисто гипотетически большая часть времени в данной операции может занимать чтение из файла. и нужно смотреть на оптимизацию в этом направлении.

[Vi Vola]

Как минимум можешь наверное сравнить свой алгоритм с gnu grep дав ему на вход такой же большой файл.

[12rbah]

iBird Rose, вот моя реализация

package main

import (
	"fmt"
	"io"
	"os"
	"strings"
)

func main() {
	words := []string{"def", "class", "push"}
	wordFreq := make(map[string]int)
	readFromBigFile("/home/alex/Desktop/1.txt", words, wordFreq)
	fmt.Println(wordFreq)
}

func getFreq(MainText string, words []string, wf map[string]int) {
	for _, word := range words {
		word = strings.ToUpper(word)
		var TextForSearch string = MainText
		end := true

		for end {
			index := strings.Index(TextForSearch, word)
			if index >= 0 {
				wf[word]++
				TextForSearch = TextForSearch[index+len(word):]
			} else {
				end = false
			}
		}

	}
}

func readFromBigFile(path string, words []string, wf map[string]int) {
	initMap(words, wf)
	f, err := os.Open(path)
	if err != nil {
		return
	}
	defer f.Close()
	var offset int64
	for {
		b := make([]byte, 1024*1024*30)
		n, err := f.ReadAt(b, offset)
		getFreq(strings.ToUpper(string(b)), words, wf)

		offset += int64(n)
		if err == io.EOF {
			break
		}
	}
}

func initMap(words []string, wf map[string]int) {
	for _, word := range words {
		wf[word] = 0
	}
}

[WinPooh32]

12rbah, можно гораздо проще же:

спойлер

package main

import (
	"bufio"
	"fmt"
	"os"
	"strings"
)

func main(){
	table := map[string]uint{"def": 0, "class": 0, "push": 0}

	f, err := os.Open("file.txt")
	if err != nil {
		return
	}
	defer f.Close()

	scanner := bufio.NewScanner(f)
	scanner.Split(bufio.ScanWords)

	for scanner.Scan(){
		word := strings.ToLower(scanner.Text())
		if count, ok := table[word]; ok {
			table[word] = count + 1
		}
	}

	fmt.Println(table)
}

Не факт, что быстрее отработает, но читать код хотябы приятнее будет :)

Answer 1

[Vitaly]

Невозможно ответить однозначно. Время в данном контексте зависит от многих факторов: алгоритма, вашего железа, компилятора, флагов сборки и т.п. То есть, время не говорит читателю вашего вопроса вообще ничего.

В конце концов, если ресурсы позволяют, можно прочитать весь файл в какой-нибудь структуру типа словаря и получать частоту вхождения слова за O(1) или O(log n) в зависимости от того, какую струтуру вы выбрали. Тут время будет тратится на чтения файла и создание структуры данных, но один раз.

Answer 2

[xmoonlight]

6 минут (или меньше) - для получения полной частотной статы по всем словам за один проход.
Ещё быстрее: можно читать файл в несколько потоков, а разрывы - склеить по ориентиру байт-смещения.

Comments

[WinPooh32]

Ещё быстрее: можно читать файл в несколько потоков...

Будет медленнее, если файл разбить на части, т.к. боттлнек происходит при чтении с диска. Даже если у вас будет ssd.
Смысл есть только в распараллеливании над последовательно считанным с диска буфером.

[xmoonlight]

WinPooh32, если обрабатывать сразу - то можно сэкономить на чтении в момент обработки другим потоком.

[WinPooh32]

xmoonlight, предлагаете асинхронную обработку? Да это поможет, но только нужно асинхронность делать на уровене ОС, в приложении нет смысла плодить потоки, если CPU простаивает.

Можно ОС заранее просить оптимизировать запросы к диску с помощью posix_fadvise, а потом уже заполнять свой буфер через read.

[xmoonlight]

WinPooh32, или так, да.
Лучше - один раз пробежаться и составить частоту слова по каждому предложению.
Кмк, толку потом, будет куда больше...