как иметь дело с большим текстовым файлом (около 300M)

Существует текстовый файл (около 300M), и мне нужно посчитать десять самых обитаемых слов (некоторые слова остановки исключены). Тест-машина имеет 8 ядер и систему Linux, любой язык программирования приветствуется и может использовать только фреймворк с открытым исходным кодом (hasoop - не вариант), у меня нет никакого опыта программирования mutithread, где я могу начать и как дать стоимость решения как можно меньше времени?как иметь дело с большим текстовым файлом (около 300M)

источник

2013-08-12 novice

300M - это не большое дело, это вопрос секунд для вашей задачи, даже для одноядерной обработки на высокоуровневом интерпретируемом языке, таком как python, если вы сделаете это правильно. У Python есть преимущество в том, что он сделает ваше программирование для подсчета слов очень простым для кодирования и отладки по сравнению со многими языками более низкого уровня. Если вы все еще хотите распараллеливать (хотя для запуска одноядерного ядра в python потребуется всего несколько секунд), я уверен, что кто-то может опубликовать быстрый и простой способ сделать это.

источник

2013-08-12 14:07:41 user2566092

Для некоторых задач за считанные секунды может представлять собой крупную сделку. – vegatripy

Если предположить, что у вас есть 1 слово в каждой строке, вы можете сделать следующее в питона

from collections import Counter 

FILE = 'test.txt' 
count = Counter() 

with open(FILE) as f: 
    for w in f.readlines(): 
     count[w.rstrip()] += 1 

print count.most_common()[0:10]

источник

2013-08-12 14:17:58 dopplesoldner

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

Вышеприведенный код работает в ** O (n) ** времени. Вы не можете улучшить время O (n), так как вы ** ДОЛЖНЫ ** видеть каждое слово по крайней мере один раз. Единственное, что вы можете улучшить, это требования к пространству - это использует пространство O (n). Вы можете сделать дальнейшую оптимизацию, чтобы уменьшить это. – dopplesoldner

@dopplesoldner Хотя это O (n), в зависимости от аппаратного обеспечения и FS, вы можете * * читать файл параллельно, что значительно ускорит выполнение программы и сделает ее более масштабируемой. Иногда O (n) недостаточно, особенно когда OP явно задает вопрос об оптимизации для многоядерной системы. – amit

Прочитайте файл и создать карту [Слово, число] всех происходящих слова как и значение - количество вхождений слов во время их чтения.

Любой язык должен выполнять эту работу.

После прочтения файла один раз у вас есть карта.

Затем перебирает карту и запомнить десять слов с наибольшим кола значение

источник

2013-08-12 14:19:06 MrSmith42

спасибо, но это слишком медленно, и причина, по которой я отправляю этот вопрос, - это найти более быстрое решение. – novice

Вы не найдете более быстрое решение, чем * O (n) *. Вам нужно прочитать файл один раз. – MrSmith42

@ MrSmith42 Зависит от FS и аппаратного обеспечения, вы можете прочитать его параллельно в некоторых случаях. – amit

Как решить эту проблему с хорошей масштабируемостью:

Проблема может быть решена с помощью 2 map-reduce шагов :

Шаг 1:

map(word): 
    emit(word,1) 
Combine + Reduce(word,list<k>): 
    emit(word,sum(list))

После этого шага у вас есть список (word,#occurances)

Шаг 2:

map(word,k): 
    emit(word,k): 
Combine + Reduce(word,k): //not a list, because each word has only 1 entry. 
    find top 10 and yield (word,k) for the top 10. //see appendix1 for details

На шаге 2 вы должны использовать один редуктор, проблема все еще масштабируемой, так как он (единственный редуктор) имеет только 10*#mappers записей в качестве входных данных.

Solution для 300 Мб файла:

Практически 300MB не такой большой файл, так что вы можете просто создать histogram (на память, с деревом/карты на основе хэш), и затем выведите из него верхние значения k.

Используя карту, поддерживающую параллелизм, вы можете разделить файл на части и позволить каждому потоку изменять, когда это необходимо. Обратите внимание, что если он действительно эффективно расщепляется, зависит от FS, и иногда линейное сканирование одним потоком является обязательным.

Приложение 1:
Как получить Top K:

Используйте мин кучу и перебирать элементы, минимальная куча будет содержать самые высокие K элементы во все времена.

Fill the heap with first k elements. 
For each element e: 
    If e > min.heap(): 
     remove the smallest element from the heap, and add e instead.

Кроме того, more details in this thread

источник

2013-08-12 14:21:31 amit

как иметь дело с большим текстовым файлом (около 300M)

ответ

Смежные вопросы