Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Подсчет частоты слов в тексте 
:(
    Опции темы
14SatanA88
Дата 25.10.2012, 00:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5



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

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

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

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

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

С++ (среднее время = 646 ms)
Выделить всёРазвернуть кодкод C++ Builder
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:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
#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() != )
      {
        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)
Выделить всёРазвернуть кодкод Java
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:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
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() != ) {
          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)
Выделить всёРазвернуть кодкод Perl
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:
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
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:
<?php
$ifile "stand.txt";
$ofile "output.txt";
$fi fopen($ifile'r');
$text strtolower(fread($fifilesize($ifile)));
$time_start microtime(true);
$text preg_replace("/-/"" "$text);
$words array_count_values(str_word_count($text1));
$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)
Выделить всёРазвернуть кодPython
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:
import time
with open('stand.txt') as fi: 
    text = fi.read()
word = ''
words = {}
tWords = 0
uWords = 0
start = time.time()
for 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[word1
            else:
                words[word1
        word = ''
        
finish = time.time()
        
with open('output.txt''w') as fo:
    for 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. Судите строго.

Это сообщение отредактировал(а) 14SatanA88 - 26.10.2012, 16:27

Присоединённый файл ( Кол-во скачиваний: 23 )
Присоединённый файл  words.7z 805,58 Kb
PM MAIL ICQ   Вверх
Akina
Дата 25.10.2012, 07:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454



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


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
disputant
Дата 25.10.2012, 08:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: 2
Всего: 3



Не силен в остальных языках, на код C++ оставил впечатление "зачем просто, если можно сложно?!"
PM MAIL   Вверх
Silent
Дата 25.10.2012, 15:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 252
Регистрация: 3.10.2006

Репутация: 1
Всего: 9



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

Вот мои результаты (среднее время по пяти замерам):
Выделить всёБез подсветки
1:
2:
3:
4:
5:
6:
7:
С++        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:
Выделить всёРазвернуть кодкод C#
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:
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<stringint> words = new Dictionary<stringint>();
            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:
Выделить всёРазвернуть кодБез подсветки
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:
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))


PM MAIL   Вверх
maxim1000
Дата 25.10.2012, 15:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 33
Всего: 110



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


--------------------
qqq
PM WWW   Вверх
disputant
Дата 25.10.2012, 16:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: 2
Всего: 3



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

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

Выделить всёРазвернуть кодкод C++
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:
inline bool alpha(int c)
{
    return (unsigned int)(c-'a') <= (unsigned int)('z'-'a');
}
struct lesschar
{
    bool operator()(charconst& s1,  charconst& 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 == 0break;
        e = c;
        while(alpha(*e)) e++;
        char save = *e;
        *e = 0;
        wCount++;
        words[c]++;
        if (save == 0break;
        c = e + 1;
    }
    t2 = clock();


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

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



Это сообщение отредактировал(а) disputant - 25.10.2012, 16:52
PM MAIL   Вверх
_Y_
Дата 26.10.2012, 15:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1651
Регистрация: 27.11.2006

Репутация: 8
Всего: 34



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


--------------------
Я вот в этом поучаствовал: http://sbor-nik.appspot.com/kick.jsp?id=sbor5737960678883328 (на правах саморекламы:)
PM MAIL WWW   Вверх
disputant
Дата 26.10.2012, 15:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: 2
Всего: 3



Цитата(_Y_ @ 26.10.2012,  15:46)
14SatanA88, подумал попробовать, но не нашел файла данных, т.е. самого текста. Где он лежит?

Ну, я, например, взял тут
PM MAIL   Вверх
14SatanA88
Дата 26.10.2012, 16:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5



Цитата

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


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

Цитата

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


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

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

Цитата

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


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

disputant, Вам отдельное спасибо за приведенный пример. Было бы превосходно, если бы Вы вкратце написали суть алгоритма. И о map я считал, что в данной задаче это идеальный вариант.
PM MAIL ICQ   Вверх
disputant
Дата 27.10.2012, 07:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: 2
Всего: 3



Цитата(14SatanA88 @ 26.10.2012,  16:39)
disputant, Вам отдельное спасибо за приведенный пример. Было бы превосходно, если бы Вы вкратце написали суть алгоритма. И о map я считал, что в данной задаче это идеальный вариант.

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

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

PM MAIL   Вверх
volatile
Дата 28.10.2012, 00:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



Цитата(Silent @  25.10.2012,  15:45 Найти цитируемый пост)
 "за державу обидно" (за С++ то есть). 

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

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

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

PM MAIL   Вверх
14SatanA88
Дата 28.10.2012, 21:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5



Спасибо за ответы касательно Си. Хотелось бы еще увидеть что-то относительно других ЯП.
PM MAIL ICQ   Вверх
volatile
Дата 28.10.2012, 23:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 2
Всего: 85



Решил я тоже за державу свои 5 копеек внести.
Цитата(14SatanA88 @  26.10.2012,  16:39 Найти цитируемый пост)
здесь важна скорость работы алгоритма. то есть используем любые средства языка, лишь бы добиться максимальных показателей скорости

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

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

Выделить всёРазвернуть кодкод C++
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:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
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:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
#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 = + (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)


Выделить всёБез подсветки
1:
2:
3:
4:
5:
6:
Питон оригинальный не тронутый........................ 695.5%
Perl оригинальный не тронутый......................... 100.0%
С++ оригинальный не тронутый, но собранный с верными
    ключами. (все дальнейшие собраны так-же) .........  90.4%
С++ от disputant......................................  65.4%
С++ с бустовским хешем................................  21.8%

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

Цитата(14SatanA88 @  28.10.2012,  21:11 Найти цитируемый пост)
относительно других ЯП. 

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


PM MAIL   Вверх
14SatanA88
Дата 29.10.2012, 13:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 393
Регистрация: 13.5.2010

Репутация: 1
Всего: 5



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

Цитата

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


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

P.S. Еще вернусь к тому, о чем спрашивал: посоветуйте компилятор для C++ под Win7
PM MAIL ICQ   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.1076 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.