LINUX.ORG.RU

Задачка на самый быстрый подсчет встречаемости слов

 


2

2

Привет,

По мотивам темы: Различия между macOS и GNU/Linux

Есть файлик. Вот он: https://disk.yandex.ru/d/XaavsEkOvCT4HQ

Нужно пройтись по файлику и посчитать встречаемость каждого слова в тексте. Словом считается любая последовательность букв от a до z. Регистр нужно привести к одному. Любой другой символ прерывает слово.

Результат записать в другой файл в формате: <количество> <слово>. Например, текст: «cat, cat, cat». Ответ будет такой: «3 cat». Также, слова при выводе нужно отсортировать по их встречаемости.

Например первые несколько строк вывода из приведенного выше файла будут такими:

3343241 the
1852717 and
1715705 of
1560152 to
1324244 a

Дополнительное условие, нужно, чтобы ваша программа отрабатывала быстрее, чем за 7 секунд на Core i5-4690 @ 3.7 GHz.

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

Вроде как BceM_IIpuBeT хотел поучаствовать. Может еще кто-то присоединится.

Я свою штуку написал. Отрабатывает примерно за 5 секунд на Мак-мини 2012-го года, core i7 @ 2,3 GHz.

★★★★★

Последнее исправление: hibou (всего исправлений: 1)

При всём уважении и т. д., а где, собственно, твой код решения под соответствующей лицензией? Если я пропустил чего, то поправь меня, пожалуйста.

anonymous
()

Отрабатывает примерно за 5 секунд

time echo '2 10000000 ^ p'|dc

а вот так за сколько отрабатывает?

anonymous
()

Language: Italian

Character set encoding: UTF-8

Ты что-то не то кинул

BceM_IIpuBeT ★★☆☆☆
()

Отрабатывает примерно за 5 секунд

От начала загрузки файла? Давай без примерно, ты же не секундмером мерил. Запукс программы и её завершение в виде time ./app показывай

LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от LINUX-ORG-RU

Это сейчас оно упирается в «у кого диск и память быстрее». Потому, что обычные структуры данных почти во всех нормальных языках оптимизировали по самые помидоры.

На ddr4 в 4 канал и 1 канал ddr3 один и тот же код будет с одинаковой скоростью работать?

system-root ★★★★★
()
Ответ на: комментарий от system-root

Надо исходники всех тестов и всте тестирующие на всех машинах прогоняют все тесты, тот когд который на всех машинах выдаст лучшее для машины время и победит

LINUX-ORG-RU ★★★★★
()
Ответ на: комментарий от anonymous

Попробовал notepad++ подсчитать количество «the»

notepad++ еще не подсчитал количество вхождений «the».
Догадываюсь почему …

anonymous
()
Ответ на: комментарий от anonymous

notepad++ еще не подсчитал количество вхождений «the».

Вывалился в crash …

Современные технологии они такие ...
anonymous
()
Ответ на: комментарий от anonymous

Интересно какой редактор с таким файлом может работать нормально?
Когда-то разработал несложный текстовый редактор, который строки грузил в tree, так ему хоть 100000000 строк подавай, все ok …

anonymous
()
Ответ на: комментарий от anonymous

Нужно составить словарь, а потом его отсортировать и записать.

BceM_IIpuBeT ★★☆☆☆
()
Ответ на: комментарий от anonymous

Интересно какой редактор с таким файлом может работать нормально?

А ибн Emacs умеет с такими текстовыми файлами работать?

anonymous
()

Предлагаю расширить задачу.

Получить словарь и записать результат в таблицу СУБД … /СУБД потестировать/

anonymous
()
Ответ на: комментарий от anonymous

Предлагаю расширить задачу.

Ныне вот по трудоемкости штук пятьсот таких задач решаю

Загрузка данных из любой конфигурации 1С 7.7 без использования самой 1С в свою иерархическую базу 

Данные любой базы 1С 7.7 или 8.x по существу являются псевдо деревом.
Это будет использовано как для тестирования своего API, так и для возможности загрузки данных в конфигурацию 1С 8.3.
Эту задачу без внимания не оставлю, но ни как не в ближайшие дни.
Пожалуй возвращусь к ней при разработке API для работы с текстом … /то что предоставляет Microsoft, … - СЛЕЗЫ!/

anonymous
()

Словом считается любая последовательность букв от a до z

è, più и т.п. негодуют.

vvn_black ★★★★★
()

кароче я задрался бороться с borrow checkerом на расте, кто хочет может подхватить и исправить ошибки

#![feature(exclusive_range_pattern)]
use std::collections::hash_map::Entry::{Occupied, Vacant};
use std::collections::HashMap;
use std::fs;

fn main() {
    let file = fs::read_to_string("huge.txt").unwrap();
    let word = String::new();
    let mut result: HashMap<String, i32> = HashMap::new();
    for mut letter in &mut file.chars() {
        if letter.is_ascii() {
            letter = letter.to_lowercase().next().unwrap();
        }
        let mut word = word.clone();
        match letter {
            'a'..'z' => {
                word.push(letter);
            }
            _ => {
                let val = match result.entry(word) {
                    Occupied(entry) => entry.into_mut(),
                    Vacant(entry) => entry.insert(0),
                };
                *val += 1;
            }
        }
    }
    for (i, j) in result {
        println!("{}\t{}", i, j);
    }
}
anonymous
()

чтобы ваша программа отрабатывала быстрее, чем за 7 секунд

Изи

<?php
$words = str_word_count(strtolower(file_get_contents('./huge.txt')), 1);
$count = array_count_values($words);
arsort($count, SORT_NUMERIC);
file_put_contents('./res.txt', print_r($count, true));
~/s/ct ❯❯❯ time php8.0 count.php

________________________________________________________
Executed in    6,53 secs   fish           external
   usr time    4,92 secs  775,00 micros    4,92 secs
   sys time    1,59 secs  288,00 micros    1,59 secs

Intel Core i7-8750H 4.1GHz

Кстати, кто-то гонит

  'the' => 3327272,
  'and' => 1826748,
  'of' => 1711781,
  'to' => 1536721,
  'a' => 1307257,

Я попробовал grep -oi the huge.txt|wc -l и rg --count-matches -i -w the huge.txt везде разные результаты, ЛОЛ. Как проверить-то надёжно?

no-such-file ★★★★★
()
Ответ на: комментарий от anonymous

если упирается в диск

Даже на пыхе чтение+запись занимают меньше секунды.

no-such-file ★★★★★
()
Ответ на: комментарий от no-such-file

Ты читер, ты библиотечные функции вызываешь.

anonymous
()
Ответ на: комментарий от no-such-file

Я тупой и не читаю доки.

<?php
setlocale(LC_ALL, 'C');
$text = str_replace(['-', "'"], ' ', strtolower(file_get_contents('./huge.txt')));
$words = str_word_count($text, 1);
$count = array_count_values($words);
arsort($count, SORT_NUMERIC);
file_put_contents('./res2.txt', var_export($count, true));
  'the' => 3343241,
  'and' => 1852717,
  'of' => 1715705,
  'to' => 1560152,
  'a' => 1324244,

Но в норматив всё ещё укладывается

~/s/ct ❯❯❯ time php8.0 count.php

________________________________________________________
Executed in    6,82 secs   fish           external 
   usr time    4,96 secs  681,00 micros    4,95 secs 
   sys time    1,85 secs  361,00 micros    1,85 secs 
no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от no-such-file

у меня вывалилось

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 336191496 bytes) in /Users/tho/Developer/freqc/builddir/main.php on line 2

anonymous
()

но эта задача явно уже исследована вдоль и поперёк.

xmikex ★★★★
()
Последнее исправление: xmikex (всего исправлений: 1)
Ответ на: комментарий от no-such-file

И правильно делают.

$ time php words.php
PHP Fatal error:  Allowed memory size of 134217728 bytes exhausted (tried to allocate 336191496 bytes) in php/words.php on line 3

real    0m0.011s
user    0m0.006s
sys     0m0.005s
anonymous
()
Ответ на: комментарий от Rost
$ time perl -ne '$h{lc($1)}++ while (/([A-Za-z]+)/gc); END { printf "$h{$_} $_\n" for (sort {$h{$b} <=> $h{$a}} keys(%h)) }' huge.txt | head
3343241 the
1852717 and
1715705 of
1560152 to
1324244 a
956926 in
933954 i
781286 he
713514 that
690876 was

real    0m18.868s
user    0m18.812s
sys     0m0.057s

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

anonymous
()
Ответ на: комментарий от LINUX-ORG-RU

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

WitcherGeralt ★★
()
Ответ на: комментарий от Keltir

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

WitcherGeralt ★★
()

кароче

use std::collections::hash_map::Entry::{Occupied, Vacant};
use std::collections::HashMap;
use std::fs::File;
use std::io::Read;
use std::iter::FromIterator;

fn main() {
    let mut file_content = Vec::new();
    let mut file = File::open("huge.txt").expect("Unable to open file");
    file.read_to_end(&mut file_content).expect("Unable to read");
    let mut word = String::new();
    let mut result: HashMap<String, i32> = HashMap::new();
    for letter in &mut file_content {
        if letter.is_ascii() {
            *letter = letter.to_ascii_lowercase();
        }
        match letter {
            97..=122 => {
                word.push(*letter as char);
            }
            _ => {
                let val = match result.entry(word) {
                    Occupied(entry) => entry.into_mut(),
                    Vacant(entry) => entry.insert(1),
                };
                *val += 1;
                word = String::new();
            }
        }
    }
    let mut result = Vec::from_iter(result);
    result.sort_by(|&(_, a), &(_, b)| a.cmp(&b));
    for (i, j) in result {
        println!("{}\t{}", i, j);
    }
}

отрабатывает за 4.5 секунды у меня

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.