Pull to refresh

Comments 94

Молодец, вы доказали что python все же лучше
UFO just landed and posted this here
А время написания скрипта?
личные качества автора
какая разница лучше он или нет?
вы питон используете, чтобы доказать, что он лучше? если это так, то у меня для вас плохие новости
просто быстренько писалось, можно и из std::cin читать
UFO just landed and posted this here
Как это быстрее? На мой взгляд значительно быстрее написать используя потоковый итератор istream_iterator( std::cin) — в качестве начала и istream_iterator() — в качестве конца.
Ну, например, С++-ные потоки в over9000 раз медленнее сишных :)
Тестирование проведите, удивитесь.
Ой щас за PHP заминусуют…
<?php 
$file = file_get_contents('pg2600.txt');
preg_match_all("/[a-zA-Z]+/", $file, $matches);
$result = array_count_values($matches[0]);
var_dump($result);

Не полный скрипт, извините, повторюсь
$n = 2;
$file = file_get_contents('pg2600.txt');
preg_match_all("/[a-zA-Z]+/", $file, $matches);
$result = array_count_values($matches[0]);
$result = array_filter($result, function($el) use ($n) {
	if ($el == $n) return true;
	return false;
});
var_dump($result);

Метрики де? )
Обозначь размер пиписьки, перед тем, как мериться ))
выполнилось за 0m0.379s
Мухаха! PHP:
$ time php test.php
0.2706310749054
real 0m0.421s
user 0m0.000s
sys 0m0.031s

$start = microtime(TRUE);

$n = 5;

$words = file_get_contents('pg2600.txt');
$result = str_word_count($words, 1);
$result = array_keys(array_count_values($result), $n);

echo microtime(TRUE) - $start;


Пример test3.py
real 0m0.816s
user 0m0.529s
sys 0m0.171s
Вы не выводите слова, и считаете, что знаки препинания — это тоже часть слова.
str_word_count не считает знаки препинания. RTFM — php.net/manual/en/function.str-word-count.php (For the purpose of this function, 'word' is defined as a locale dependent string containing alphabetic characters, which also may contain, but not start with "'" and "-" characters)

С выводом — да, моя промашка:
0.3365650177002
real 0m0.422s
user 0m0.000s
sys 0m0.015s

И обновлённый код:
$start = microtime(TRUE);

$n = 5;

$words = file_get_contents('pg2600.txt');
$result = str_word_count($words, 1);
$result = array_keys(array_count_values($result), $n);
print_r($result);

echo microtime(TRUE) - $start;
Кстати о результатах

time php regexp.php

real 0m0.652s
user 0m0.582s
sys 0m0.062s
Еще раз о результатах, чуть пофикшенный код
$n = 5;
$file = file_get_contents('pg2600.txt');
preg_match_all("/\w+/", $file, $matches);
$result = array_count_values($matches[0]);
$result = array_filter($result, function($el) use ($n) {
	return $el == $n;
});
var_dump($result);

и python скрипт из поста

$ time php regexp.php && time python regexp.py
real 0m0.503s
user 0m0.419s
sys 0m0.071s

real 0m0.464s
user 0m0.424s
sys 0m0.025s
if x in d:
    d[x] += 1
else:
    d[x] = 1

d.setdefault(x, 0) += 1


[k for k,v in d.items() if v == n]

[k for k,v in d.iteritems() if v == n]
Как человек, только начинающий изучать питон, извиняюсь заранее, но мне интерпретатор выдал:
d.setdefault(x, 0) += 1
SyntaxError: can't assign to function call
Да, тут у меня тупняк случился)
Хотя со списками, например, работает:
d.setdefault(x, []).append(something)
import re
from collections import Counter

n = 5

c = Counter(re.findall(r'\w+', open("pg2600.txt", "r").read()))

print repr([k for k, v in c.items() if v == n])

UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
В качестве имхо, это победитель по читабельности из всего что тут видел (не понял только haskell).

Во-первых, лаконично, хотя это и не было целью, например, do/end до {|w| ....} не сокращался. Мало переменных. Нет не относящегося к делу ритуального мусора вроде 'local $/'. Из минусов: ответ не выводится, n не используется :)

На втором месте питоны.
Вообще-то тут была правильная программа на Perl, вот её отформатированная версия:
use strict;
use feature ":5.12";

my $n = shift @ARGV;

my %words;
while (<>) {
  $words{$_}++ for /(\w+)/g;
}

say for grep { $words{$_} == $n } keys %words


1. Программа почти на оригинальном английском языке написана + именно так на Perl и надо писать последние лет 5 точно )))
2. Это уже полноценная утилита которой можно пользоваться в терминале, а не недосткрипт с захардкоденными значениями
3. Работает быстрее чем Ruby и Python версии, да и по потреблению памяти если сравнить, думаю победит.

А своё отношение отношение к неадекватному восприятия мира автором поста я выразил тут
Тело функции на Haskell просто читайте с конца :)
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Вообще — классическая задача на MapReduce.

Мой вариант (не факт что быстрый):
#!/usr/bin/env python
import re

N = 5

with open('pg2600.txt', 'r') as f:
    word_list = re.findall(r'\w+', f.read())

def reduce_func(x, y):
	for key in y:
		x[key] = x.get(key, 0) + y[key]
	return x

mr_result = reduce(reduce_func, map(lambda x: {x: 1}, word_list))

print filter(lambda x: mr_result[x] == N, mr_result.keys())
Ооо, меньше секунды :) Тоже неплохо
UFO just landed and posted this here
#include <iostream>
#include <stdio.h>
#include <unordered_map>
#include <sys/time.h>

using namespace std;
bool delimiter[255] = {false};
unordered_map<string, int> mmap;
int main(int argc, const char * argv[])
{
    int N = 5;
    if (argc > 1)
    {
        N = atoi(argv[1]);
    }
    
    FILE * pFile = fopen("pg2600.txt", "r");
    
    struct timeval tv;
    gettimeofday(&tv,NULL);
    long startTime = tv.tv_sec * 1e6 + tv.tv_usec;
    
    char delim[] = {' ', ';', '!', ',', '.', ':', '\n', '\r', '?', '"', '(', ')', '\'', '-', '*'};
    for (int i = 0; i < sizeof(delim) / sizeof(char); i++)
    {
        delimiter[delim[i]] = true;
    }
    
    fseek (pFile , 0 , SEEK_END);
    long lSize = ftell (pFile);
    rewind (pFile);
    char * text = new char[lSize];
    fread(text, sizeof(char), lSize, pFile);
    long pos = 0, begin = 0, end = 0;
    
    while (pos < lSize)
    {
        if (delimiter[text[pos]])
        {
            pos++;
            continue;
        }
        begin = pos++;
        while (pos < lSize)
        {
            end = pos;
            if (delimiter[text[pos]])
            {
                pos++;
                break;
            }
            pos++;
        }
        string str(text + begin, text + end);
        mmap[str]++;
    }
    unordered_map<string, int>::iterator b = mmap.begin(), e = mmap.end();
    int count = 0;
    for (; b != e; b++)
    {
        if (b->second == N)
        {
            printf("%s, ", b->first.c_str());
            count++;
        }
    }
    
    gettimeofday(&tv,NULL);
    long endtime = tv.tv_sec * 1e6 + tv.tv_usec;
    printf("\nTotal: %d\nTime: %f\n",count, ((double)(endtime - startTime)) / 1e6);
    return 0;
}



Если я правильно понял задание.
Сборка release(-Os)
Time: ~ 0.06 сек
Ну, зависит от системы, видимо :)
Мод:
На моей машине ~ 0.031
Делал правда почти час, наверное потому что до этого весь день писал на яве и питоне… :)
#include <iostream>
#include <stdio.h>
#include <unordered_map>
#include <sys/time.h>
#include <cstring>

using namespace std;
typedef unsigned long long ull;
#define UM ((1ULL << 32) - 1ULL)

bool delimiter[255] = {false};

char *text;

int main(int argc, const char * argv[])
{
    int N = 5;
    if (argc > 1)
    {
        N = atoi(argv[1]);
    }
    
    FILE * pFile = fopen("pg2600.txt", "r");
    
    struct timeval tv;
    gettimeofday(&tv,NULL);
    long startTime = tv.tv_sec * 1e6 + tv.tv_usec;
    
    char delim[] = {' ', ';', '!', ',', '.', ':', '\n', '\r', '?', '"', '(', ')', '\'', '-', '*'};
    for (int i = 0; i < sizeof(delim) / sizeof(char); i++)
    {
        delimiter[delim[i]] = true;
    }
    
    fseek (pFile , 0 , SEEK_END);
    long lSize = ftell (pFile);
    rewind (pFile);
    text = new char[lSize];
    fread(text, sizeof(char), lSize, pFile);
    long pos = 0, begin = 0, end = 0;
    
    class sHash {
    public:
        size_t operator()(const ull &str) const {
            return str >> 32;
        }
    };

    class sEquals {
    public:
    	bool operator()(const ull& s1, const ull& s2) const {
    		// return strcmp(text + (s1 & UM), text + (s2 & UM)) == 0;
    		return true;
    	}
    };

    unordered_map<ull, int, sHash, sEquals> mmap(100000);

    while (pos < lSize)
    {
    	char c = text[pos];
        if (delimiter[c])
        {
        	text[pos] = 0;
            pos++;
            continue;
        }
        int hash = c - 64;
        int p = 1;
        begin = pos++;
        while (pos < lSize)
        {
            end = pos;
            c = text[pos];
            if (delimiter[c])
            {
            	text[pos] = 0;
                pos++;
                break;
            }
            p *= 59;
            hash += p * (c - 64);
            pos++;
        }
        mmap[(((ull)hash) << 32) | ((ull)begin)]++;
    }

    int count = 0;
    for (auto &b : mmap)
    {
        if (b.second == N)
        {
            printf("%s, ", text + (b.first & UM));
            count++;
        }
    }
    
    gettimeofday(&tv,NULL);
    long endtime = tv.tv_sec * 1e6 + tv.tv_usec;
    printf("\nTotal: %d\nTime: %f\n",count, ((double)(endtime - startTime)) / 1e6);
    return 0;
}
проверка закоментирована, потому что в pg2600.txt нет ни одной коллизии.
Если уже затачивать только под pg26000.txt, чего бы сразу ответ не захардкодить?
С проверкой примерно 0.045.

Еще можно выкинуть unordered_map и написать свой простенький хеш открытой адресацией и линейным исследованием. Если известна нормальная верхняя оценка кол-ва возможных слов на входе, то получиться едва ли не короче, чем 2 комментариями выше.
Финальный вариант с ограничением в 65535 различных слова.
0.032 в среднем.
Код
#include <iostream>
#include <stdio.h>
#include <unordered_map>
#include <sys/time.h>
#include <cstring>
#include <cstdlib>

using namespace std;
typedef unsigned long long ull;
#define UM ((1ULL << 32) - 1ULL)
#define MSIZE (1 << 16) * 2
#define MM ((MSIZE >> 1) - 1)

bool delimiter[255] = {false};

int *mmap = (int*) calloc(MSIZE, sizeof(int));
char *text;

int main(int argc, const char * argv[])
{
    int N = 5;
    if (argc > 1)
    {
        N = atoi(argv[1]);
    }
    
    FILE * pFile = fopen("pg2600.txt", "r");
    
    struct timeval tv;
    gettimeofday(&tv,NULL);
    long startTime = tv.tv_sec * 1e6 + tv.tv_usec;
    
    char delim[] = {' ', ';', '!', ',', '.', ':', '\n', '\r', '?', '"', '(', ')', '\'', '-', '*'};
    for (int i = 0; i < sizeof(delim) / sizeof(char); i++)
    {
        delimiter[delim[i]] = true;
    }
    
    fseek (pFile , 0 , SEEK_END);
    long lSize = ftell (pFile);
    rewind (pFile);
    text = new char[lSize];
    fread(text, sizeof(char), lSize, pFile);
    long pos = 0, begin = 0, end = 0;

    while (pos < lSize)
    {
    	char c = text[pos];
        if (delimiter[c])
        {
        	text[pos] = 0;
            pos++;
            continue;
        }
        int hash = c - 64;
        int p = 1;
        int begin = pos;
        pos++;
        while (pos < lSize)
        {
            c = text[pos];
            if (delimiter[c])
            {
            	text[pos] = 0;
                pos++;
                break;
            }
            p *= 59;
            hash += p * (c - 64);
            pos++;
        }
        int i = (hash & MM) * 2;
        for (;;)
        {
        	if (mmap[i] == 0 || strcmp(text + begin, text + mmap[i]) == 0) {
        		mmap[i] = begin;
        		mmap[i + 1]++;
        		break;
        	}
        	i -= 2;
        	if (i < 0) i = MSIZE - 2;
        }
    }
    int count = 0;
    for (int i = 1; i < MSIZE; i += 2)
    {
        if (mmap[i] == N)
        {
            printf("%s, ", text + mmap[i - 1]);
            count++;
        }
    }
    
    gettimeofday(&tv,NULL);
    long endtime = tv.tv_sec * 1e6 + tv.tv_usec;
    printf("\nTotal: %d\nTime: %f\n",count, ((double)(endtime - startTime)) / 1e6);
    return 0;
}

Если убрать ту самую проверку на коллизии, останется 0.016, при чистом I/O 0.006, т. е. дальше некуда.
Выполняется долго ( у меня real 0m1.379s ), зато время написания — 60сек (:
#!/bin/sh
cat pg2600.txt | tr ' .,?:;' '\n' | sort | uniq -c | grep '^\s*5\s'
Чуть поправленный вариант test2.pl:
perl -le'while(<>){$h{$_}++ for /\w+/g };print for grep {$h{$_}==5}keys %h'
Тоже свой вариант закину:
#!/usr/bin/env perl
use strict;

open my $fh, "<", "./input_file.txt" or die $!;
my $str = do {local $/; <$fh> };
my $n = 5;

my %h;
$h{$1}++ while $str =~ /(\w+)/g;

my $res;
for my $w (keys %h) {
    $res .= "$w, " if $h{$w} == $n;
}

print "$res\n";

Время написания 3мин.
Скорость его выполнения на моей машине:
real    0m0.427s
user    0m0.413s
sys     0m0.013s


Скорость выполнения test3.py на моей машине:
real    0m0.567s
user    0m0.544s
sys     0m0.021s

Время написания 10 мин

require('fs').readFile('pg2600.txt', 'utf-8', function (error, text) {
    var N = 50,
        matches = {},
        item,
        k,
        len,
        result;

    result = text.match(/\w+/ig);

    for (k = 0, len = result.length; k < len; k += 1) {
        matches[result[k]] = (matches[result[k]] || 0) + 1;
    }

    for (item in matches) {
        if (matches[item] === N) {
            console.log(item + " :: " + matches[item]);
        }
    }
});


Время выполение:

real	0m0.464s
user	0m0.428s
sys	0m0.035s


Я не понял, почему на perl'е писали по полчаса такой дохленький скриптик? Язык в этом виноват? :)

Кстати, интересно еще потребление памяти уж посмотреть кроме скорости.
судя по коду, человек при этом его (Perl) еще и изучал =)

а вообще оба языка, как Python, так и Perl, предназначены для быстрой разработки
public class App 
{
    public static void main( String[] args ) throws IOException
    {
        Map<String, Holder> words = new HashMap<>(20000);
        Pattern p = Pattern.compile("\\w+", Pattern.CASE_INSENSITIVE);
        int n = Integer.parseInt(args[1]);
        
        try (BufferedReader in = new BufferedReader(new FileReader(args[0]), 6000)) {
	  try (PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out, 6000))) {
            
            String line = null;
            while(( line = in.readLine()) != null ) {
                Matcher m = p.matcher(line);
                while(m.find()) {
                    Holder holder = words.get(m.group());
                    if (holder != null) {
                        holder.num++;
                        if (holder.num == n) {
                            out.println(m.group());
                        }
                    } else {
                        words.put(m.group(), new Holder());
                    }
                }
            }
        }}
        
    }
    
    private static class Holder {
      
      int num = 1;
      
    }
}


Команда исполнения:
time java -cp ./target/classes/ com.qitsoft.warandpeace.App /home/serj/Documents/pg2600.txt 5


Результат:
real    0m0.257s
user    0m0.388s
sys     0m0.024s
#!/usr/bin/perl
$N=5;$,=", ";print(grep{$Y{$_}==$N}keys(do{($X=do{open X,'<pg2600.txt';local$/;<X>})=~s/(\w+)/$Y{$1}++/ge;\%Y}))
Должен быть чуток быстрее.
#!/usr/bin/env perl

my $n = 5;
my %words;

open FH,'<','/tmp/pg2600.txt';
local $/;
while (<FH>) { $words{$_}++ for (split /\W+/) };

print '['.(join ", ", grep {$words{$_} == $n} keys %words).']';
То же время, но компактней.
#!/usr/bin/env perl

my $n = 5;
my %words;
$,=', ';

open FH,'<','/tmp/pg2600.txt';
local $/;
$words{$_}++ for (split /\W+/, <FH>);
print (grep {$words{$_} == $n} keys %words);
В join только ", " заменить на ', '. Незначительная экономия, но это-ж дело принципа! :)
write only однострочник:

perl -E 's/(\w+)/$c{$1}++/ge while<>;say join$/,grep{$c{$_}==5}keys%c' <input_file.txt
еще короче
perl -E 's/(\w+)/$c{"$1 "}++/ge for<>;say grep{$c{$_}==5}%c' <input_file.txt
IcedCoffeeScript
fs = require("fs")
re = /\w+/ig
N = 5

await fs.readFile "input_file.txt", "utf8", defer err, data

words = {}
while word = re.exec(data)?[0]
  words[word] = (words[word] || 0) + 1

for word, count of words
  console.log(word) if N == count

from collections import Counter
import re
n = 5
f = open('pg2600.txt', 'r')
text = f.read().lower()
f.close()
c = Counter(re.findall(r'\w+', text))
print repr([word for word in c if c[word] == n])


0.292u 0.039s 0:00.33 96.9% 0+0k 0+0io 0pf+0w

На той же машине test2.py ровно столько же.
Встречаются два еврея:
— Слышал я «Битлз», не понравилось. Картавят, фальшивят… Что людям в них нравится?!
— А где ты их слышал?
— Да мне Мойша напел…
И, всё-таки, Perl — лучший язык для составления стенограмм.
#test3.py
def test1():
    n = 5
    with open("./pg2600.txt", "r") as f:
        s = f.read()
    d={}
    for x in re.findall(r'\w+',s):
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    print repr([k for k,v in d.items() if v == n])
#чуть модифицированный test3.py
def test2():
    n = 5
    with open("./pg2600.txt", "r") as f:
        s = f.read()
    d=defaultdict(int)
    for x in re.findall(r'\w+',s):
        d[x] += 1
    print repr([k for k,v in d.items() if v == n])


test1 : 0.518
test2 : 0.468
Решение на генераторах:
import sys
import re
from collections import defaultdict

n     = int(sys.argv[1])
fname = sys.argv[2]
d     = defaultdict(int)
regex = re.compile(r'\w+')

with open(fname, 'rb') as f:
    for line in f:
        for match in regex.finditer(line):
            d[match.group()] += 1

print '\n'.join((k for k, v in d.iteritems() if v == n))

Моё:   0,65s user 0,01s system 99% cpu 0,663 total
test3: 0,37s user 0,02s system 97% cpu 0,401 total
Я правильно понял, результат работы программы должен быть таким:

Интересно, как вы представляете себе проверку результата при использовании данного снимка окна? Точнее, процедуру проверки я представляю, а вот человека, желающего ей заняться — нет.

Кстати, ни одно из представленных решений не выдаст такого результата, все пишут в stdout. Это вообще как получено?
Предлагаю вам запустить варианты автора поста, результат вывода его скриптов извне вообще сложно анализировать, жалко он не осветил как он сам правильность вывода данных проверял.
Что?! Формат [word, word2, word3] или ['word', 'word2', 'word3'], конечно, не является идеалом (если надо сравнивать их между собой, то удобнее просто
word
word1
word2
: то, что можно скормить sort, а затем diff). Но это дело исправляется двумя заменами на sed. Сделать такое со снимком окна, да ещё и пожатом (habrastorage оставляет только 800px по ширине), гораздо сложнее.

У меня, кстати, есть сильное подозрение, что результаты реально не проверялись за исключением беглого просмотра: скрипт на perl выдаёт очевидную чушь, потому и отмечен как неправильный, остальные выдают несортированный список, да ещё и в разных форматах. Если бы результаты проверялись полностью, автор наверняка бы выбрал более удобный формат представления.
Haskell, по‐видимости, имеет формат "word" "word1". Не проверял.

Ещё одно свидетельство, что результаты автором не проверялись: решение на Haskell делает все буквы маленькими перед тем, как начать их обрабатывать. Остальные так не делают.
Я просто открыл текст в текстовом редакторе, и вбил несколько случайных слов из списка в окне в поиск и убедился, что они встречаются 5 (например) раз.

> Это вообще как получено?
MessageBox… а что?
В таких случаях отправляют текст в какой‐нибудь pastebin. Ни в коем случае не делают снимок MessageBox: с ним нельзя нормально работать. Никто не скажет, должен ли быть результат именно таким, потому что это слишком сложно проверить.

По‐моему, вы вообще единственный, кому здесь пришло в голову использовать какой‐либо GUI для вывода результатов.

Это вообще как получено?
MessageBox… а что?
Это не ответ. Здесь все показывают сам скрипт.
> Здесь все показывают сам скрипт.
Я только уточнил, правильно ли я понял суть задачи. Хотя да, правильнее было бы просто скопировать результат текстом.
n=666
['Mary']

Кажется, Лев Николаевич что-то хотел нам сказать. =)
еще две мэри написаны как MARY
Не с проста, ох не с проста! )))
Очень интересное наблюдение… не проверял, но интересное…
а там 2012 12 21 или что-то подобное, кстати не фигурировало ни разу?
import string
from collections import defaultdict


def main():
    n = 5
    s = '.-;:,/\'"?!()*\n'
    tr = string.maketrans(s, ' '*len(s))
    f = string.translate(open('pg2600.txt').read().lower(), tr)
    acc = defaultdict(int)
    for i in f.split():
        acc[i] += 1
    for k,v in acc.iteritems():
        if v == n:
            print k

main()

➜ wp time python2 test1.py > o
python2 test1.py > o 0.18s user 0.05s system 97% cpu 0.236 total
Ох, перловщик все на свете к регуляркам сведет, даже спор.
Я вас, наверное, удивлю, но автор-питонист, решил эту задачу тоже при помощи регулярок =)
Подозреваю, претензия была к тому, что в качестве линейки выбрали не скрипт для cron job-а, не демона, не обработку xml, не мат-задачку, не что-то с GUI, не ООП, а именно парсинг текстового файла. То, для чего perl создавался.
Именно:

«Дальше меня спросили, как в python обстоят дела с регулярными выражениями,»
Решение на Golang. Выведет слова, которые встречаются больше 1000 раз.

package main

import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strings"
	"unicode"
)

const (
	fileName = "input_file.txt"
	N        = 1000
)

func main() {
	wordsMap := make(map[string]int)
	file, err := os.Open(fileName)
	if err != nil {
		log.Fatal(err)
	}
	defer file.Close()

	scanner := bufio.NewScanner(file)
	for scanner.Scan() {
		str := scanner.Text()
		words := strings.Fields(str)
		for _, word := range words {
			word := strings.TrimRightFunc(strings.ToLower(word), unicode.IsPunct)
			if len(word) > 0 {
				if _, ok := wordsMap[word]; ok {
					wordsMap[word] += 1
				} else {
					wordsMap[word] = 1
				}
			}
		}
	}

	if err := scanner.Err(); err != nil {
		log.Fatal(err)
	}

	for word, count := range wordsMap {
		if count > N {
			fmt.Println(word, ":", count)
		}
	}
}


На MacBook Air 1.8 ГГц Intel Core i5
real	0m0.337s
user	0m0.325s
sys	0m0.009s

Sign up to leave a comment.

Articles

Change theme settings