Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Подсчет частоты слов в тексте

Автор: 14SatanA88 25.10.2012, 00:36

Доброго времени суток, уважаемые программеры.

Предыстория:
Не так давно, исходя из утверждений одного знакомого мне человека, решил выяснить, где же быстрее всего считается частота слов в тексте. Просто интересно стало. Но так как программист я хреновый, подумал, что не лишним будет создать тему на форуме.

Входные данные:
У нас есть файл с текстом, содержаший только латиницу (чтобы не заморачиваться с кодировками).

Выходные данные
Опять же текстовый файл, содержащий пары "слово = частота" в алфавитном порядке, разделенные переводом строки.

Некоторые замечания:
Будем считать словом последовательность символов из диапазона [a-zA-Z] (только буквы латинского алфавита, никаких апострофов и дефисов). Регистр символов не важен. Я взял для примера оригинал "Противостояния" Стивена Кинга (~2.5 Mb). Он лежит в аттаче. Время считается только на стадии подсчетов. То есть получение текста из файла / запись результатов / сортировка хеша по ключам не важны.

Смысл создания темы:
Далее я приведу исходный код сабжа на нескольких ЯП и результаты тестирования на моей машине. Я прошу Вас взглянуть на код, сказать, где можно что-либо исправить, дабы ускорить его. Ну и было бы превосходно сопроводить замечания подробными комментариями. Некоторым может быть не интересно, и поэтому прошу не оставлять бессмысленных постов. Критика же приветствуется.

С++ (среднее время = 646 ms)

Код


#include <stdio>
#include <conio>
#include <fstream>
#include <string>
#include <map>
#include <iostream>
#include <dos>
#include <time>

using namespace std;

unsigned char toLower(unsigned char c)
{
  if ( c == 168 ) return (unsigned char)184;
  else if ( (c >= 192) && (c <= 223) ) return (unsigned char)(c + 32);
  else if ( (c >= 65 ) && (c <= 90) ) return (unsigned char)(c + 32);
  else return (unsigned char)c;
}

int main()
{
  char *text;
  ifstream fin;
  map < string, unsigned int, less<string> > words;
  map < string, unsigned int, less<string> >::iterator cur;

  fin.open("stand.txt");
  fin.seekg(0, ios::end);
  int size = fin.tellg();
  fin.seekg(0, ios::beg);
  text = new char[size];
  fin.read(text, size);
  fin.close();

  string word("");
  int c;

  int wCount = 0;

  clock_t t1, t2;   
  t1 = clock();

  for (int i = 0; i < size; i++)
  {
    c = (unsigned char)text[i];
    if ( ((c >= 65) && (c <= 90)) || ((c >= 97) && (c <= 122))
        || ((c >= 192) && (c <= 255))
        || (c == 168) || (c == 184) )
    {
      word += toLower(c);
    }
    else
    {
      if ( word.length() != 0 )
      {
        wCount++;
        words[word]++;
      }
      word = "";
    }
  }

  t2 = clock();

  float diff = (((float)t2 - (float)t1) / 1000000.0F ) * 1000;
  printf("elapsed time = %f s\n", diff);

  FILE *f = fopen("output.txt", "w");

  printf("total words count = %d\n", wCount);
  printf("unique words count = %d\n", words.size());
  for (cur = words.begin(); cur != words.end(); cur++)
  {
    fprintf(f, "%s = ", (*cur).first);
    fprintf(f, "%d\n", (*cur).second);
  }

  fclose(f);

  getch();

  return 0;
}

Java (среднее время = 605 ms)

Код


package words;

import java.io.*;
import java.nio.charset.Charset;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class Words {

  public static boolean isLetter(char c) {    
    if ( (c >= 97) && (c <= 122) ) return true; // a - z
    if ( (c >= 65) && (c <= 90) )  return true; // A - Z
    return false;
  }
  
  public static char toLower(char c) {
    if ( (c >= 65) && (c <= 90) )  return (char)((char)c+32); // A-Z to a-z
    return c;
  }
  
  public static void main(String[] args) {
    
    StringBuffer sb = new StringBuffer("");
    
    try {      
      InputStreamReader isr = new InputStreamReader(new FileInputStream("stand.txt"), Charset.forName("CP1251"));
      BufferedReader br = new BufferedReader(isr);
      String line;
      String NL = System.getProperty("line.separator");
      while ( (line = br.readLine()) != null) {
        sb.append(line + NL);
      }
      br.close();
    } catch (FileNotFoundException ex) {
      System.out.println("Файл не найден");
    } catch (IOException ex) {
      System.out.println("Ошибка ввода-вывода");
    }
    
    String text = sb.toString();
    Map<String, Integer> words = new TreeMap<String, Integer>();
    
    long startTime = System.currentTimeMillis();
        
    int tWords = 0;   
            
    StringBuffer word = new StringBuffer();
    for (int i = 0; i < text.length(); i++) {
      char c = text.charAt(i);
      if ( isLetter(c) ) {
        word.append(toLower(c));
      }
      else {
        if ( word.length() != 0 ) {
          tWords++;
          if (words.containsKey(word.toString())) {
            words.put(word.toString(), words.get(word.toString()) + 1);
          }
          else {
             words.put(word.toString(), 1);
          }
        }
        word.delete(0, word.length());
      }     
    }
    
    long endTime = System.currentTimeMillis();
    long time = endTime - startTime;
    System.out.println("На подсчеты затрачено " + time + " мс");    
    
    System.out.println("Всего слов = " + tWords);
    int uWords = words.size();
    System.out.println("Уникальных слов = " + uWords);   
    
    try {
      BufferedWriter bw = new BufferedWriter(new FileWriter("output.txt"));
      for (Map.Entry<String, Integer> entry: words.entrySet()) {
        bw.write(entry.getKey() + " = " + entry.getValue());
        bw.newLine();
      }
      bw.close();
    } catch (IOException ex) {
      System.out.println("Ошибка ввода-вывода");
    }
    
  }
}

Perl (среднее время = 224 ms)

Код


use Cwd qw(abs_path);
use File::Basename qw(dirname);
$ipath = dirname(abs_path($0)) . "/stand.txt";
$opath = dirname(abs_path($0)) . "/output.txt";

open INPUT, "<", $ipath or die;
open OUTPUT, ">", $opath or die;

use Time::HiRes;
$start = [ Time::HiRes::gettimeofday( ) ];

$twords = 0;

while(<INPUT>) {
    tr/A-Za-z/ /cs; 
    foreach $word (split(' ', lc $_)) {
        $words{$word}++;
        $twords++;
    }
}
close INPUT;

$uwords = keys %words;

$elapsed = Time::HiRes::tv_interval( $start );

foreach $word (sort keys %words) {
    print OUTPUT "$word = $words{$word}\n"; 
}
close OUTPUT;

print "elapsed time: $elapsed seconds\n";
print "total words count = $twords\n";
print "unique words count = $uwords\n";

PHP (среднее время = 307 ms)

Код


<?php

$ifile = "stand.txt";
$ofile = "output.txt";

$fi = fopen($ifile, 'r');
$text = strtolower(fread($fi, filesize($ifile)));

$time_start = microtime(true);

$text = preg_replace("/-/", " ", $text);
$words = array_count_values(str_word_count($text, 1));

$time_end = microtime(true);
$time_elapsed = $time_end - $time_start;

ksort($words);
$out = "";
foreach($words as $word => $count) {
    $out .= "$word = $count".PHP_EOL;
}
$fo = fopen($ofile, 'w');
fwrite($fo, $out);

$tWords = str_word_count($text);
$uWords = sizeof($words);

print "elapsed time = " . round($time_elapsed * 1000) . " ms<br>";
print "total words = " . $tWords . "<br>";
print "unique words = " . $uWords . "<br>";

?>

Python (среднее время = 1448 ms)

Код


import time

with open('stand.txt') as fi: 
    text = fi.read()

word = ''
words = {}
tWords = 0
uWords = 0

start = time.time()

for i in text:
    if 'a' <= i <= 'z' or 'A' <= i <= 'Z':
        word += i.lower()
    else: 
        if word:
            tWords += 1
            if word in words:
                words[word] = words[word] + 1
            else:
                words[word] = 1
        word = ''
        
finish = time.time()
        
with open('output.txt', 'w') as fo:
    for i in sorted(words):
        s = str(i) + ' = ' + str(words[i]) + '\n'
        fo.write(s)
        
uWords = len(words)
elapsed = finish - start
print 'elapsed time = {0:.3f} s'.format(elapsed)
print 'total words = {0}'.format(tWords)
print 'unique words = {0}'.format(uWords)

Файлы с исходными кодами, а так же пример входного и выходного файла в аттаче.

P.S. Судите строго.

Автор: Akina 25.10.2012, 07:35

Аттача-то и не подвезли... небось не заархивировал, прежде чем аттачить?

Автор: disputant 25.10.2012, 08:45

Не силен в остальных языках, на код C++ оставил впечатление "зачем просто, если можно сложно?!"

Автор: Silent 25.10.2012, 15:45

Сильно возмутился я представленным цифрам, и решил проверить на деле - "за державу обидно" (за С++ то есть). Каким компилятором получен результат? учитывая присутствующий заголовочный файл <dos> и тег C++ Builder - предполагаю, что в сильно бородатом borland c++ 3.1, так? Ужас =)

Вот мои результаты (среднее время по пяти замерам):

Код


С++        249,6    g++ 4.4.5
Perl        255,2    perl v5.10.1
C#        269,6    visual C# 2008 compiler v3.5.21022.8
Go        353,4    go 1.0.1
PHP        558,2    php 5.3.3
Python    1708,4    python 2.6.6
Java        -        -

Размер тестового файла был 2,5Мб.
Платформа i3, 2Gb, debian 6 (WinXP для C#)

на Java решение не тестил, но мое мнение - она не должна выйти за 300-350мс, все решения тестировались "как есть"

Прилагаю исходники на C# и Golang:

Код


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ACMSharp
{
    class vingrad2
    {
        static void Main(string[] args)
        {
            int start = Environment.TickCount;
            System.IO.StreamReader r = new System.IO.StreamReader("stand.txt");
            string s = r.ReadToEnd();
            string word = "";
            int count = 0;
            Dictionary<string, int> words = new Dictionary<string, int>();
            for (int i = 0; i < s.Length; i++)
                if (s[i] >= 'A' && s[i] <= 'Z' || s[i] >= 'a' && s[i] <= 'z') word += s[i];
                else 
                {
                    if (words.ContainsKey(word)) words[word]++;
                    else words.Add(word, 1);
                    word = "";
                    count++;
                }
            Console.Write("Time: {2}\nAlls words: {0}\nUnique words: {1}\n", count, words.Count, Environment.TickCount - start);
        }
    }
}

Golang:

Код


package main

import "os"

var words map[string]int = make(map[string]int)

func main() {
    var reqFile *os.File
    var err error
    if reqFile, err = os.OpenFile("stand.txt", os.O_RDONLY, 0); err != nil {
        println("Error file open")
    }
    fi, err := reqFile.Stat()
    var bytes = make([]uint8, fi.Size())
    reqFile.Read(bytes)
    word, count := make([]byte, 10), 0
    for _, ch := range bytes {
        if (ch <= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') {
            word = append(word, ch)
        } else {
            if _, ok := words[string(word)]; ok {
                words[string(word)]++
            } else {
                words[string(word)] = 1
            }
            word, count = make([]byte, 10), count+1
        }
    }
    println("Alls words: ",count)
    println("Unique words: ", len(words))
}

Автор: maxim1000 25.10.2012, 15:57

ещё стоит проверить, одинаковые ли алгоритмы
если Perl, например, использует хеш-контейнер, имеет смысл его использовать во всех языках

Автор: disputant 25.10.2012, 16:51

Приведенный исходник C# - 172 тика. C++ с исправленными ошибками - 130 тиков. (Visual Studio 2010)

Но если отказаться от string'ов и этой жуткой проверки, то примерно 89 тиков

Код


inline bool alpha(int c)
{
    return (unsigned int)(c-'a') <= (unsigned int)('z'-'a');
}

struct lesschar
{
    bool operator()(char* const& s1,  char* const& s2)
    {
        return strcmp(s1,s2) < 0;
    }
};

map<char*, unsigned int, lesschar> words;
map<char*, unsigned int, lesschar>::iterator cur;

......

    t1 = clock();
    strlwr(text);

    for(char *c = text, *e = text;;)
    {
        while(*c && !alpha(*c)) ++c;
        if (*c == 0) break;
        e = c;
        while(alpha(*e)) e++;
        char save = *e;
        *e = 0;
        wCount++;
        words[c]++;
        if (save == 0) break;
        c = e + 1;
    }
    t2 = clock();

Как я понимаю, если задача получить именно список слов с частотами, а не конкретно map, то можно и еще ускориться...

P.S. В 3.1 STL еще не было smile

Автор: _Y_ 26.10.2012, 15:46

14SatanA88, подумал попробовать, но не нашел файла данных, т.е. самого текста. Где он лежит?

Автор: disputant 26.10.2012, 15:51

Цитата(_Y_ @ 26.10.2012, 15:46)

14SatanA88, подумал попробовать, но не нашел файла данных, т.е. самого текста. Где он лежит?

Ну, я, например, взял http://webreading.ru/conv/do_txt.php?name=/books/sf_/sf/king_stephen_the_stand

Автор: 14SatanA88 26.10.2012, 16:39

Цитата

Аттача-то и не подвезли... небось не заархивировал, прежде чем аттачить?

аттач подвез. там исходные коды всего что я понаписал, выходной и выходной файлы

Цитата

В почти таком же бородатом Borland c++ 5.02 (кстати, посоветуйте компилятор под Windows)

наверное, стоит сказать, на какой машине проверялись коды:
i7, 6Gb, Win7

Цитата

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

disputant, Вам отдельное спасибо за приведенный пример. Было бы превосходно, если бы Вы вкратце написали суть алгоритма. И о map я считал, что в данной задаче это идеальный вариант.

Автор: disputant 27.10.2012, 07:10

Цитата(14SatanA88 @ 26.10.2012, 16:39)

disputant, Вам отдельное спасибо за приведенный пример. Было бы превосходно, если бы Вы вкратце написали суть алгоритма. И о map я считал, что в данной задаче это идеальный вариант.

Суть алгоритма - раз мы все равно втянули весь текст в память, зачем его копировать? Сразу весь преобразовали в нижний регистр, и пошли сканировать в нем слова, обрезая их (все равно между словами что-то есть, что можно безболезненно превратить в 0), так что каждое слово просто представлено указателем на место в памяти. map хранит эти указатели, но сравнивает их между собой лексикографически, как строки. Как минимум избавляемся от массы накладных расходов string.

С заменой map сильно не думал, но можно попробовать взять что-то не такое универсальное, но быстрое - например, какую-нибудь хэш-таблицу, или, например, матрицу 26x27 по первым двум буквам, а в ней какие-то списки или еще что - все-таки слова обычно достаточно короткие... В общем, тут уже надо поэкспериментировать. Первый напрашивающийся вариант - собрать все в один вектор и отсортировать - из-за большого количества повторений может и не обогнать map (так что для разных текстов могут быть оптимальны разные варианты).

Автор: volatile 28.10.2012, 00:29

Цитата(Silent @ 25.10.2012, 15:45

)

"за державу обидно" (за С++ то есть).

Ха, да уж, как это С++ на последнем месте оказался?
(хотя если постараться, все можно.)

Спасибо disputant, поддержал державу.

Язык С++, тем и хорош, что можно ускоряться бесконечно.

Автор: 14SatanA88 28.10.2012, 21:11

Спасибо за ответы касательно Си. Хотелось бы еще увидеть что-то относительно других ЯП.

Автор: volatile 28.10.2012, 23:46

Решил я тоже за державу свои 5 копеек внести.

Цитата(14SatanA88 @ 26.10.2012, 16:39

)

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

Ну что-ж, раз любые средства, давайте попробуем.

За основу взял алгоритм disputantа, заменил стандартный мап, на бустовский хеш-анордеред.

Код


#include <vector>
#include <algorithm>
#include <boost/unordered_map.hpp>
#include <boost/functional/hash.hpp>
#include <stopwatch.h>

static stopwatch timer (0); // Таймер с высоким разрешением.

// -------------------------------------------------------------------------------------
namespace fast {

inline bool isalpha (char c)
{
   return (u8)(c-'a') <= (u8)('z'-'a');
}

// Вообще-то так делать нехорошо. Но в данном случае, позволим себе =)
inline char tolower (char c)
{
    return c | 0x20;
}

} // namespace fast
// -------------------------------------------------------------------------------------

// Небольшой класс, чтобы запихать его в бустовский хеш.
class pchar
{
public:
   pchar (const char * p) : p_(p) {}
   
   bool operator < (const pchar & r) const
   {
      return strcmp (p_, r.p_ ) < 0;
   }

   bool operator == (const pchar & r) const
   {
      return (*p_ == *r.p_) 
         ? strcmp (p_ + 1, r.p_ + 1) == 0
         : 0;
   }
   const char * get_p () const { return p_; }

private:
   const char * p_;
};

// -------------------------------------------------------------------------------------
// хеш
struct phash : std::unary_function <pchar, ui>
{
    ui operator () (pchar str) const
    {
        ui hash = 0;
        for (const char* p = str.get_p(); *p; ++ p)
        {
           hash = (hash << 3) ^ *p;
        }
        return hash;
    }
};
// -------------------------------------------------------------------------------------
// сортировка для красивого вывода, в замеряемом времени она не участвует.
struct sorter
{
   bool operator () (const std::pair <pchar, ui> & p1, 
                     const std::pair <pchar, ui> & p2 ) const
   {
      if (p1.second != p2.second)
         return p1.second > p2.second;
      return p1.first < p2.first;
   }
};

// -------------------------------------------------------------------------------------

void go (char * text)
{
   timer.restart (); // Запускаем таймер

   boost::unordered_map <pchar, unsigned int, phash> words;

   ui word_count = 0;
   bool alpha_prev = 0;
   char *begin;

   // Агоритм disputant'а. Убрал только strlwr(text). Он в процессе будет приводить к нижнему регистру.
   // Остальные изменения, в принципе дали не много. оставил просто последний вариант.

   for (char *p = text, b; b = *p; ++ p)
   {
      if (alpha_prev != fast::isalpha (*p = fast::tolower (b)))
      {
         if (!alpha_prev)
         {
            begin = p;
         }
         else
         {
            *p = 0;
            ++ word_count;
            ++ words [begin];
         }
         alpha_prev = !alpha_prev;
      }
   }
   if (alpha_prev)
   {
      ++ word_count;
      ++ words [begin];
   }

   timer.pause (); // Останавливаем таймер

   _pr (_T("Всего слов      =%9d\n"), word_count);
   _pr (_T("Уникальных слов =%9d\n"), words.size());
   _pr (_T("Время (миллисекунды) =%6.1f\n"), timer.get_time_us () / 1000.0);


   FILE * f = fopen ("output.txt", "wt");
   if (!f)
   {
       _pr (_T("Файл output.txt невозможно открыть\n"));
       return;
   }
   
   // Дальше идет сортировка по частоте использования для красивого вывода.
   std::vector <std::pair <pchar, ui> > vec (words.begin (), words.end ());
   std::sort (vec.begin (), vec.end (), sorter ());
   ui len = 1 + (ui) log10 (vec.front().second + .5);  
   
   for (std::vector <std::pair <pchar, ui> >::iterator cur = vec.begin(); 
        cur != vec.end(); ++ cur)
   {
      fprintf (f, "%*u %s\n", len, cur->second, cur->first);
   }
   
   fclose (f);
}

Итого такие результаты:
Буду писать в процентах, чтобы голову не забивать, цифры все равно у всех разные. За 100% взял самый быстрый показатель ТС

Цитата(14SatanA88 @ 25.10.2012, 00:36

)

Perl (среднее время = 224 ms)

Код


Питон оригинальный не тронутый........................ 695.5%
Perl оригинальный не тронутый......................... 100.0%
С++ оригинальный не тронутый, но собранный с верными
    ключами. (все дальнейшие собраны так-же) .........  90.4%
С++ от disputant......................................  65.4%
С++ с бустовским хешем................................  21.8%

Была мысль еще свой хеш-мап написать быстренько, простенький, но заточенный под это дело, но подумал что и так не плохо.
(может еще напишу, если настроение будет.)
Еще неплохо бы собрать на интеловском компилере.
Так что резервы у С++ еще есть. =)
14SatanA88, могу выложить егзешник, если запустите на своем "калиброванном" компе.

Цитата(14SatanA88 @ 28.10.2012, 21:11

)

относительно других ЯП.

14SatanA88, Другие языки пока отдыхают. smile

Автор: 14SatanA88 29.10.2012, 13:24

volatile, премного благодарен Вам за проделанную работу. Если Вы еще под настроение напишете свой хеш, с блэкджеком и плюшками, будет вообще круто.

Цитата

Другие языки пока отдыхают

я чего завел вообще тему. предмет разговора был в том, что якобы java быстрее всего сделает сабж. я же предположил что perl будет быстрее (честно признаюсь, на момет разговора вообще perl знал только по работе с regexp). ну и потом мне стало интересно, и я понаписал то что смог smile

P.S. Еще вернусь к тому, о чем спрашивал: посоветуйте компилятор для C++ под Win7