Как посчитать кол-во вхождений строк в файл?

Question

[mrgloom]

Допустим есть текстовый файл, где каждая строчка это слово, слова могут встречаться в файле по нескольку раз, необходимо посчитать кол-во вхождений каждого слова в файл.
Проблема в том, что слов может быть несколько сотен миллионов, т.е. текстовый файл размером >4ГБ.

1.Как лучше хранить данные вместо текстового файла?
2.По сути можно было бы использовать std::map для подсчёта, но что если всё не влезет в память? (т.е. по хорошему хотелось бы std::map который как бы лежит на диске)

По сути задача выглядит как {id,name,surname} что как бы намекает на SQL, но не очень то хочется с ним связываться(т.к. лишняя привязка и я с ним не работал почти), и сколько таких записей он сможет потянуть и насколько просто подсчитать кол-во вхождений используя SQL?

так же если кто-то может предложить решение на python может это будет даже лучше.

Answer 1

[mrstrictly]

"Несколько миллионов" для современных объемов оперативной памяти -- это не проблема. Имеет смысл уточнить ограничения, накладываемые на вашу программу. Вы пробовали решить ее "в лоб"? Не занимаетесь ли вы преждевременной оптимизацией? :)
Если объем входного текста действительно не ограничен сверху, тогда это задача выглядит, например, как один из класссических примеров map-reduce (я ни в коем случае не о фреймворках, хадупах и прочих зукиперах, а об идее), которая сводится к тому, чтобы разбить входной поток на N фрагментов фиксированного размера (например, по миллиону строк), посчитать количество слов в каждом фрагменте независимо (шаг map), получив на выходе N наборов ключ-значение (где, ключ -- слово, значение -- число вхождений), далее просуммировать эти наборы (шаг reduce). Если число ключей на выходе map опять же огромно (что я себе представляю с трудом для "натуральных" языков), можно шардить промежуточные результаты, когда шаг map на выходе выдает не один сплошной файл, а K фрагментов (например, первый -- слова на "a-c", второй -- на "d-f" и т.д.). Здесь немного подробнее об этом: michaelnielsen.org/blog/write-your-first-mapreduce...

Comments

[mrgloom]

Ага, как раз читал про map-reduce(ссылка в закладках), мне как раз показалось это сложным из-за того что надо пользоваться какими то фреймворками (но по ссылке то вроде чистый питон). В реальных условиях данные могут еще и прибывать всё время, т.е. верхней границы нет (это вроде называется streaming algorithm highscalability.com/blog/2012/4/5/big-data-countin... ).

Answer 2

[RPG]

С++11 + unordered_map. Не метеор, но map стабильно обгоняет и для решения задачи за глаза хватит.

А вообще вот так это решается в Bash:
sort file | uniq -c
Если структура сложная, то предварительно нужно выделить ключ из файла, например так:

$ cut -d: -f7 /etc/passwd | sort | uniq -c
      2 /bin/bash
      1 /bin/sync
      1 /sbin/halt
     34 /sbin/nologin
      1 /sbin/shutdown

Answer 3

[Евгений]

std::map вполне может подойти. Миллион записей для современного кол-ва оперативки не так уж и много :-)
С SQL будет очень просто посчитать кол-во вхождений, но имхо это оверхэд для данной задачи :-)

Answer 4

[tsarevfs]

Вы явно преждевременно оптимизируете. Решение на питоне, абсолютно в лоб, достаточно быстро работает на файле с 10M слов по 8 символов. К слову это всего 100 мегабайт. Даже если слов будет в 10 раз больше памяти хватит.

import random, string
from collections import defaultdict as ddict

def randomword(length):
   return ''.join(random.choice(string.lowercase) for i in range(length))

def main():
	f = open('a.txt', 'w')
	for i in range(10000000):
		f.write(randomword(8) + '\n')

	f.close()
	print('gen finished')

	d = ddict(int)
	stat = ddict(int)
	f = open('a.txt', 'r')
	for w in f.readlines():
		d[w] += 1
		stat[d[w]] += 1
		if d[w] > 1:
			stat[d[w] - 1] -= 1

	print stat




if __name__ == '__main__':
	main()

Answer 5

[Boniface]

Добрый день. Это тривиальная задача. Используйте регулярные выражения или готовые функции для нахождения числа вхождений подстроки в строку. Например php substr_count.

Answer 6

[DancingOnWater]

В случае миллионов вариантов map - плохое решение - слишком много коллизий будет.

Comments

[tsarevfs]

В плюсах map это красно-черное дерево. О каких коллизиях вы говорите?