Сравнение ЯП на примере составления "словаря"

[Егор]

С интересом прочитал дискуссию о языках программирования на этом форуме,
а также пару статей о сравнении языков.
Захотелось самому попробовать на вкус Python и Lisp.
Придумал простую учебную задачу на структуры данных.

Дан большой текст input.txt.
Нужно посчитать, сколько раз в нём встречается каждое слово.
Разделителями считаются все символы, кроме a-z и A-Z.
Заглавные буквы превращать в строчные.
Пример выходного файла output.txt:
3 9
the 5
label 2
lamp 2
Сначала записаны число различных слов и число слов с повторениями.
Слова с частотами отсортированы по частоте и лексикографически.

Был бы рад увидеть хорошие решения на Лиспе и Питоне
(или на других языках, подходящих к этой задачке).
Есть ли ассоциативные массивы в стандартных библиотеках чистого Си?

Попробовал решить на Питоне и C++.
Python - 18 строк, работает 0.8 секунды,
C++ - 50 строк, работает 0.6 секунды.
Тестировал на примере двухмегабайтного художественного текста.
В текстах программ не считал пустые строки и комментарии.

[незваный гость]

Я бы написал что-либо в таком духе (хотя и не знаю, то ли это, что Вы хотите):

def process(ifn, ofn):
  text = open(ifn, "rb").read()

  xlatetab = [" "] * 256
  for och in range(ord('a'),ord('z')+1):
    ch = chr(och)
    xlatetab[och] = ch
    xlatetab[ord(ch.upper())] = ch

  words = text.translate("".join(xlatetab)).split()
  words.sort()

  f = open(ofn, "w")
  if words:
    word = words[0]; count = 0
    for w in words:
      if w == word:
        count += 1
      else:
        print >>f, word, count
        word = w; count = 1
    print >>f, word, count
  f.close()

if __name__ == "__main__":
  process("input.txt", "output.txt")

Было бы несколько легче, если бы Вы привели свои варианты...

[Егор]

незваный гость, спасибо за пример решения и за пропаганду Питона .
Оформлю свой вариант на Питоне, используя элементы Вашего стиля.
У меня слова записываются в файл результатов по убыванию частот.

def cmp_pairs((word1, count1), (word2, count2)):
  if cmp(count2, count1) != 0:
    return cmp(count2, count1)
  return cmp(word1, word2)

def process(ifn, ofn):
  xlatetab = [" "] * 256
  for och in range(ord('a'), ord('z') + 1):
    ch = chr(och) 
    xlatetab[och] = ch 
    xlatetab[ord(ch.upper())] = ch 

  text = open(ifn, "r").read()
  words = text.translate("".join(xlatetab)).split() 
  d = dict()
  for word in words:
    d[word] = d.get(word, 0) + 1
  pairs = d.items()
  pairs.sort(cmp = cmp_pairs)
  m = sum([count for (word, count) in pairs])

  fdst = open(ofn, "w");
  print >>fdst, len(pairs), m
  for word, count in pairs:
    print >>fdst, word, count

if __name__ == "__main__": 
  process("input.txt", "output.txt")

На C++ делал приблизительно то же самое, но получилось раза в 2-3 длиннее.
Интересно бы ещё посмотреть решение на Лиспе.

[bugmaker]

Цитата:

Дан большой текст input.txt.
Нужно посчитать, сколько раз в нём встречается каждое слово.
Разделителями считаются все символы, кроме a-z и A-Z.
Заглавные буквы превращать в строчные.

Откровенно простая задача, это всё равно что сравнивать сапёрную лопатку и бульдозер для вскапывания клумбы. Объём "служебных" операций, типа всякого рода циклов и операций ввода/вывода, которые во всех языках примерно одинаковы, будет сравним с самой логикой. Попробуй вместо этого более другую задачу, например трансляцию математических формул, записаную в человечьем стиле, в вид, пригодный для вычислений на компьютере, последующую компиляцию и выполнение полученного. В зависимости от "фичастости" такого транслятора, я думаю объём кода и скорость выполнения будет разниться на порядки.

Цитата:

Был бы рад увидеть хорошие решения на Лиспе и Питоне
(или на других языках, подходящих к этой задачке).

Советую потеребить знатоков Перла. На нём должно в пару строк решаться.

Цитата:

Есть ли ассоциативные массивы в стандартных библиотеках чистого Си?

Есть. Что-то вроде такого:

struct {
  char * key;
  int value;
} assoc;
struct assoc assocar [];

Цитата:

В текстах программ не считал пустые строки и комментарии.

Считать строки вообще - неполезное развлечение. В Лисп-программу можно при желании в одну строку записать, в С - почти всю. А ещё есть obfuscated code

Цитата:

C++ - 50 строк, работает 0.6 секунды.

Ну запости сюда тоже, для "зверинца"

Вот один из вариантов на Лиспе:

(defmacro how-many (obj ha) `(values (gethash ,obj ,ha 0)))

(defmacro 2list (h) `(let ((l nil)) (progn (maphash (lambda (k v) (setq l (cons (list k v) l))) ,h) l)))

(defun count-it (obj ha) (unless (null obj) (incf (how-many obj ha))))

(defun get-words (instr words &optional cur-word)
    (let ((c (read-char instr nil)))
        (cond 
            ((null c) words)
            ((alpha-char-p c) (get-words instr words (concatenate 'string cur-word (string (char-downcase c)))))
            (t (progn (count-it cur-word words) (get-words instr words))))))
   
(let ((ostr (open "output.txt" :direction :output :if-exists :rename-and-delete :if-does-not-exist :create)))
    (dolist (x (sort 
        (2list (get-words (open "input.txt" :direction :input) (make-hash-table :test 'equal)))
        (lambda (a b) (string< (first a) (first b))))) 
    (format ostr "~A ~D~%" (first x) (second x)))
    (close ostr))
(quit)

И заодно на С:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct word {char * it; int cnt;};

int mystrcmp (char ** a, char ** b) {
    return  strcmp (*a, *b);
}

int main (int argc, char * argv []) {
    int bufsize = 1024;
    int wordsize = 256;
    int bufcnt = 0, wordcnt = 0;
    FILE * f = fopen ("input.txt", "r");
    char * buf = malloc (1024), ** words = (char **) malloc (256 * sizeof (char *));
    char inword = 0;
    int i, cnt;
    char * prev;

    buf [0] = 0;
    while (EOF != (i = fgetc (f))) {
        if (isalpha (i)) inword = 1, buf [bufcnt++] = (char) tolower (i);
        else if (inword) inword = 0, buf [bufcnt++] = 0;
        if (bufsize == bufcnt) bufsize += 1024, buf = realloc (buf, bufsize);
    }
    fclose (f);
    if (inword) inword = 0, buf [bufcnt++] = 0;
    words [0] = buf;
    bufcnt--;
    for (i = 1; i < bufcnt ; i++) {
        if (!buf [i]) words [wordcnt++] = &buf [i + 1];
        if (wordcnt == wordsize) wordsize += 256, words = realloc (words, wordsize * sizeof (char *));
    }
    qsort (words, wordcnt, sizeof (char *), (int (*)(const void*,const void*)) mystrcmp);
    inword = 1;
    cnt = 0;
    prev = "";
    for (i = 0; i < wordcnt; i++) {
        inword = strcmp (prev, words [i]);
        if (inword) {
            if (i) printf (" %i\n", cnt);
            cnt = 1;
            prev = words [i];
            printf ("%s", prev);
        } else cnt++;
    }
    printf (" %i\n", cnt);
    return 0;
}

ЗЫ Выяснили, что код на Лиспе ниже, но шире кода на Питоне

[Егор]

bugmaker, спасибо за пропаганду Лиспа и примеры.
С замечаниями согласен: упражнение простое, и считать строчки - не очень правильно.
В программах не хватает сортировки по убыванию частот, но это несложно добавить.

По поводу ассоциативных массивов - имел в виду сбалансированные бинарные деревья (например, "красно-чёрные"), для которых операции поиска, вставки и удаления занимают O(log n) времени.
Как только правильно сформулировал, так сразу и нашёл в glib.
Впрочем, эту задачку отлично решили и без деревьев.

Программа на C обработала двухмегабайтный текст за полсекунды.
В Лиспе ещё не научился включать оптимизацию, поэтому работало полминуты.
Запускал так (CMU Common Lisp): lisp -quiet -load bugmaker_textanalyse.lisp

[незваный гость]

Егор писал(а):

Как только правильно сформулировал, так сразу и нашёл в glib.

Я не уверен, что на glib корректно ссылаться, как на стандартную. Не то, чтобы она стала от этого сколь-нибудь хуже.

Егор писал(а):

Программа на C обработала двухмегабайтный текст за полсекунды.

Измерение времени работы программы -- один из самых скользких вопросов. Может быть потому, что математиков не учат экспериментированию, и, соответственно, теории оного. Некоторые вопросы, которые непременно возникают: а) какая операционная система, машина, компилятор, режимы оптимизации; 2) как измерялось время, каково разрешение таймера, как учитывались остальные процессы, происходящие в это время на компе; 3) как влияло кеширование доступа к диску, учитывалось ли оно.

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

На мой взгляд (вкус), 0.5 секунды достоверно не меряются -- я предпочитаю иметь дело с временами порядка 2-3 секунд минимум. С другой стороны, 2 мегабайта могут запросто сесть даже не в программный кеш, а в кеш жесткого диска (сейчас обычным является 8 МБ).

[bugmaker]

Цитата:

спасибо за пропаганду Лиспа и примеры.

Да на здоровье,

Цитата:

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

В Лисп-программу несложно, а вот в С - намного сложнее. Проявление низкоуровневости С.

Цитата:

В Лиспе ещё не научился включать оптимизацию, поэтому работало полминуты.

Полминуты - это много. Хотя известно, что в Лисп ввод-вывод жутко медленный из-за большой разницы в представлении байтовых массивов и строк и необходимости преобразовывать меж ними при чтении файла, всё равно много. Обычно программа занимается вводом-выводом весьма малую часть времени своей работы, поэтому ввод-вывод не торопятся оптимизировать, это просто никому не нужно. Есть специальные методы, ускоряющие ввод-вывод при необходимости, не всегда "чистые", например

(defun slurp-stream (i) (let ((seq (make-string (file-length i)))) (read-sequence seq i) seq))
(defmacro how-many (obj ha) `(values (gethash ,obj ,ha 0)))
(defun count-it (obj ha) (unless (null obj) (incf (how-many obj ha))))
(defun 2list (h) (let ((l nil)) (progn (maphash (lambda (k v) (setq l (cons (list k v) l))) h) l)))

(defun get-words (s words &optional (start 0))
    (let (
        (pos-a (position-if 'alpha-char-p s :start start))
        (pos-n (position-if-not 'alpha-char-p s :start start)))
        (cond
            ((null pos-a) words)
            ((null pos-n) (progn (count-it (string-downcase (subseq s start)) words) words))
            ((< pos-a pos-n) (progn (count-it (string-downcase (subseq s start pos-n)) words) (get-words s words pos-n)))
            (t (get-words s words pos-a)))))

(let (
    (ostr (open "output.txt" :direction :output :if-exists :rename-and-delete :if-does-not-exist :create))
    (istr (open "input.txt" :direction :input)))
    (dolist (x (sort (2list (get-words (slurp-stream istr) (make-hash-table :test #'equal))) (lambda (a b) (string-lessp (first a) (first b)))))
        (format ostr "~A ~D~%" (first x) (second x)))
    (close ostr)
    (close istr))
(quit)

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

echo '(compile-file "theprogram.lisp")(quit)' | lisp

и запускать полученый файл

lisp -quiet -noinit -load theprogram.x86f

Если нужна ещё большая оптимизация, можно воткнуть в программу такое

(declaim (optimize (speed 3) (safety 0)))

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

[незваный гость]

С с сортировкой по частотам.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
  char* word;
  int   freq;
} WORDDESCR;

int compare1(const char** w1, const char** w2) {
  return strcmp(*w1, *w2);
}

int compare2(const WORDDESCR* wd1, const WORDDESCR* wd2) {
  if (wd1->freq == wd2->freq) {
    return strcmp(wd1->word, wd2->word);
  } else {
    return wd2->freq - wd1->freq;
  }
}

void process(const char* ifn, const char* ofn) {
  FILE* f;
  long flen;
  char* text;
  char delim[256] = {0};
  int ix, iy;
  char* w;
  char **words, **pw, **wordse;
  int wordcount, wordstep, wordsize;
  WORDDESCR *descrs, *qd, *descre;

  f = fopen(ifn, "rb");
  fseek(f,0,SEEK_END); flen = ftell(f); fseek(f,0,SEEK_SET);
  text = malloc(flen+1);
  fread(text, 1, flen, f); text[flen] = 0;
  fclose(f);

  strlwr(text);

  iy = 0;
  for (ix = 1; ix < 256; ++ix) {
    if (ix < 'a' || ix > 'z') {
      delim[iy++] = ix;
    }
  }

  wordsize = wordstep = (int)(flen * 0.2);
  pw = words = malloc(wordsize * sizeof(char*));
  wordse = words + wordsize;
  for (w = strtok(text, delim); w != NULL; w = strtok(NULL, delim)) {
    if (pw >= wordse) {
      wordsize += wordstep;
      words = realloc(words, wordsize * sizeof(char*));
      wordse = words + wordsize;
      pw = wordse - wordstep;
    }
    *(pw++) = w;
  }
  wordcount = pw - words; wordse = pw;

  qsort(words, wordcount, sizeof(char*), compare1);

  descrs = malloc(wordcount * sizeof(WORDDESCR));
  w = ""; qd = descrs;
  for (pw = words; pw < wordse; ++pw) {
    if (strcmp(w, *pw) == 0) {
      ++qd[-1].freq;
    } else {
      qd->word = w = *pw; qd->freq = 1; ++qd;
    }
  }

  free(words);

  descre = qd;
  wordcount = (qd-descrs);

  qsort(descrs, wordcount, sizeof(WORDDESCR), compare2);
  
  f = fopen(ofn, "w");
  for (qd = descrs; qd < descre; ++qd) {
    fprintf(f, "%s %d\n", qd->word, qd->freq);
  }
  fclose(f);
  free(descrs); 
}

int main(int argc, char* argv[])
{
  process("input.txt", "output.txt");
  return 0;
}

process() распадается на функции естественным образом. В общем, неразбиение суть от лености, хотя в чем-либо объектном вроде C++ было бы проще. Малые примеры (одноразовые программы, пишущиеся за пятнадцать минут) в чем-то странны -- жалко тратить усилия на нормальное программирование, в частности, на структурирование. Работает себе и ладно...

[bugmaker]

Цитата:

хотя в чем-либо объектном вроде C++ было бы проще.

ИМХО сомнительно. Хотя никто примера на С++ не привёл, да и я наверное неудосужусь.

[Егор]

Последняя lisp-программа после компиляции работает 1.8 секунды, т. е. довольно быстро.

незваный гость писал(а):

Измерение времени работы программы -- один из самых скользких вопросов. ...

С замечаниями согласен. Время работы пишу ради ознакомления, не претендуя на точность или объективность.
C и C++ компилирую с опцией -O3; Питон запускаю без опций.
Процессор Pentium IV 2.80 HGz, оперативки 1 гиг.
Не знаю, насколько эффективно используется параллельность.

В обсуждаемой задачке дольше всего происходит превращение массива слов в упорядоченный словарь. Остальные операции (ввод, вывод, выделение слов, преобразования, сортировка по убыванию частот и прочее) занимают процентов 20--40 от общего времени работы.

Пусть n - общее число слов, m - число различных слов.
Если бросать слова в одну кучу, а потом сортировать, то сложность c2 * n * log(n).
Если добавлять слова в дерево, то c1 * n * log(m).
Над пробным текстом (n=400000, m=11000) эти два способа
работали приблизительно одинаковое время.

Написал ещё один вариант на C, используя гибрид быстрой и поразрядной сортировок ("3-way quicksort for strings", Sedgewick & Bentley) и выделяя память сразу по максимуму.
180 строк, работает 0.18 секунды (делал 100 итераций и делил на 100).
Наверное, к Лиспу или Питону несложно подключить такой алгоритм сортировки в качестве отдельного модуля.

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

[photon]

Егор писал(а):

Не знаю, где скачать много художественных текстов на английском.

Посмотрите здесь

[незваный гость]

Егор писал(а):

Если бросать слова в одну кучу, а потом сортировать, то сложность c2 * n * log(n). ... Если добавлять слова в дерево, то c1 * n * log(m).

Верно. Только вот для большинства слов частота сильно ограничена, и имеея $m < c_3 n $ вторая оценка превращается в $c_2 n \ln n + (c_2 \ln c_4) n$. Поэтому заметного выигрыша в скорости не дает. Зато может дать заметный проигрыш, если библиотечная сортировка работает быстрее, чем написанная руками -- а это очень частый случай. Впрочем, есть и библиотечные контейнеры тоже....

[незваный гость]

photon писал(а):

Посмотрите здесь

Только смотрите, Егор, что берете -- Проект Гутенберг содержит все, что угодно: таблицы знаков $\pi$, ДНК человека... , даже художественную литературу . Не все, что с Гутенберга, уместно рассматривать как текст.

[Егор]

photon, спасибо за ссылку.

незваный гость писал(а):

Только смотрите, Егор, что берете -- Проект Гутенберг содержит все, что угодно: таблицы знаков $\pi$, ДНК человека... , даже художественную литературу . Не все, что с Гутенберга, уместно рассматривать как текст.

Да, тут легко перепутать.

незваный гость, согласен, что $\log n$ обычно не очень отличается от $\log m$, так что эти два алгоритма (сортировка и деревья) должны быть примерно одинаковы по времени работы. Оказалось, что так оно и есть.

Собираюсь ещё напрячь знатока Перла, как подсказал bugmaker, и попробовать специальные деревья для работы со строками.

[Егор]

Добавил ещё решение на C через TST ("ternary search trie"). Работает очень резво, как и "3-way string qsort" (сортировка Сэджвика-Бентли). Видимо, узлы TST лучше всего хранить большими блоками (как в std::queue), но ради упрощения написал выделение памяти по максимуму.

В программе на Лиспе написал разбиение на слова без рекурсии (и добавил в конце сортировку пар). Теперь выполняется быстрее, но своего времени потратил немало.

Сравнение пар на Питоне можно записать кратко:

def cmp_pairs((str1, cnt1), (str2, cnt2)):
  return cmp(cnt2, cnt1) or cmp(str1, str2)

На Перле сравнение и разбинение на слова ещё чуть короче. К сожалению, не смог привлечь знатока Перла.

Для измерения времени написал в программах цикл - исполнять 10 раз, и потом делил результаты на 10. При оценке объёма программ решил считать пустые строки (тут, наверное, любой подход субъективен).

Вот программы, вместе со скриптом-тестером на Питоне.

Для тестирования скачал с gutenberg.org несколько больших текстов на английском:
Bible - King James Bible,
Shakespeare - The Complete Works of William Shakespeare,
Thesaurus - Roget's Thesaurus of English Words and Phrases,
Ulysses - Ulysses, by James Joyce.
Вот эти тексты, утоптанные RARом.

Получились такие результаты:
\begin{tabular}{|l|r|r|r|r|r|r|} \cline{1-5} \textbf{Input files} & Shakespeare & Bible & Thesaurus & Ulysses \\ \cline{1-5} size (bytes) & 5582655 & 4445260 & 2801695 & 1561677 \\ \cline{1-5} n (words) & 928012 & 793877 & 197768 & 270556 \\ \cline{1-5} m (dict's size) & 23683 & 12876 & 34977 & 29127 \\ \cline{1-5}\hline \textbf{Programs} &\multicolumn{4}{|c|}{time (sec)} & size & lines \\ \hline C, TST & 0.25 & 0.17 & 0.13 & 0.13 & 3674 & 151 \\ \hline C, 3-way str qsort & 0.49 & 0.36 & 0.15 & 0.16 & 4518 & 176 \\ \hline C, qsort & 1.02 & 0.78 & 0.24 & 0.28 & 2599 & 98 \\ \hline CPP, map & 1.56 & 1.06 & 0.62 & 0.63 & 1847 & 75 \\ \hline CPP, sort & 5.72 & 4.75 & 1.32 & 1.56 & 2186 & 86 \\ \hline Lisp, hash & 4.10 & 3.25 & 1.74 & 1.58 & 1229 & 39 \\ \hline Perl, hash & 1.80 & 1.23 & 1.27 & 1.16 & 707 & 30 \\ \hline Perl, sort & 3.96 & 3.12 & 1.15 & 1.48 & 771 & 34 \\ \hline Python, dict & 1.70 & 1.21 & 1.11 & 1.03 & 717 & 30 \\ \hline Python, sort & 2.70 & 2.08 & 0.82 & 1.04 & 871 & 37 \\ \hline \end{tabular}