LINUX.ORG.RU

Вопрос по коду

 


1

3

Есть вот код который считает кол-во повторений слов из файла и пишет результат в файл вопрос почему долго выполняется? https://www.dropbox.com/sh/bjo8wlqs6tlfh1s/AABJi7XBW02Z9RTPNKdjh5GMa?dl=0

Перемещено leave из general



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

Ответ на: комментарий от i-rinat

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

Gremlin_
() автор топика
Ответ на: комментарий от i-rinat

Если бы это было тестовое задание

так это оно и есть

vvviperrr ★★★★★
()

Мимотредонечитальный ответ : ИМХО, лучше так (с питона на кресты адаптируй сам, дам подсказку - std::map. А вообще - почитай про STL-е контейнеры)

with open(file_name, 'r') as f:
  content = f.read()
words = content.split(' ')
count = {}
for word in words:
  if word not in count.keys():
    count[word] = 0
  count[word]++

Как минимум - читаемость выше. Да и сложность не большая вроде (если крестовая реализация не имеет фатальных недостатков).

Судя по http://stackoverflow.com/questions/222658/multiset-map-and-hash-map-complexity - крестовый эквивалент заимеет сложность O(N * log(N)) Подсказка - std::map.

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

Без бустопараши куда приятней. А вообще конечно адовый топик.

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

чтобы не только по пробелами разелять.

Это, конечно, благородная цель, но ограничение 256 символами всё опошляет.

tailgunner ★★★★★
()

Вот так люди толком не изучив C, начинают пытаться что-то писать на плюсах.

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

Цикл надо до 128 вообще, иначе поломается utf8 :)

По хорошему, можно (и нужно) руками прописать таблицу разделителей, но в данном случае цикл - ибо лень.

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

Есть же регулярки и collections.Counter:

#!/usr/bin/python3
import re
from collections import Counter

data = open('bigtestfile.txt').read().lower()
c = Counter(re.findall(r'\w+-?\w+', data))

for word,n in c.most_common():
    suf = 'а'  if n%10 in [2,3,4] and n%100 not in [12,13,14]  else  ''
    print('%s встречается %i раз%s' % (word.rjust(20), n, suf))

Это если по-простому. 3.5 секунды на файл ТСа.

anonymous
()
Ответ на: комментарий от Gremlin_
#include <string>
#include <iostream>
#include <fstream>
#include <list>
#include <map>
#include <sys/time.h>

int main() {
	struct timeval initTime;
	gettimeofday(&initTime, NULL);
	int initMinis = initTime.tv_sec * 1000 + initTime.tv_usec / 1000;

	std::ifstream file;
	file.open("bigtestfile.txt");
	std::list<std::string> words;
	std::string word;
	while (file >> word) {
		words.push_back(word);
	}
	file.close();
	
	struct timeval readedTime;
	gettimeofday(&readedTime, NULL);
	int readedMinis = readedTime.tv_sec * 1000 + readedTime.tv_usec / 1000;

	std::cout << "Readed\n";
	std::map<std::string, int> counts;
	for (std::list<std::string>::iterator it = words.begin(); it != words.end(); it++) {
		std::string word = *it;
		if (counts.find(word) == counts.end()) {
			std::cout << word << "\n";
			counts.insert(std::pair<std::string, int>(word, 0));
		}
		counts[word]++;
	}
	
	struct timeval readyTime;
	gettimeofday(&readyTime, NULL);
	int readyMinis = readyTime.tv_sec * 1000 + readyTime.tv_usec / 1000;

	for (std::map<std::string, int>::iterator it = counts.begin(); it != counts.end(); it++) {
		std::cout << it->first << " " << it->second << "\n";
	}

	std::cout << "Read time : " << readedMinis - initMinis << " ms\nCount time : " << readyMinis - readedMinis << " ms\n";
}

Вот крестовый быдлокод.

Read time : 1874 ms
Count time : 4293 ms

Ну, примерно такие цифры.

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

Против 10 в твоём примере. И это не считая того, что я не стал выбирать, какой map-подобный контейнер здесь лучше - просто прихерачил map

alex4321
()
Ответ на: комментарий от i-rinat

Можно вопрос - что за скрытый смысл ты нашёл в моём разгильдяйстве? А то лень вчитываться. Ускорения какие-то, кадры...

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

Да юзай, мне-то что. А про контейнеры, наверное, таки почитай - начерта велосипедить, если задача ложится на них?

alex4321
()

И если тебе только результат нужен, вот:

grep -Poi '[a-zа-я]+' bigtestfile.txt | sort | uniq -c > bigresult.txt
:)

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

Хм, оно должно тормозить в сравнении с

if word in counts
?

Вроде же под капотом в случае dict-а то же самое, не? Или я туплю?

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

Хм, оно должно тормозить

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

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

Офтоп, конечно, но на вот этом коде я не заметил существенной разницы. Сперва кажется, что один из способов чуть быстрее, но стоит поменять вызовы местами, как иллюзия пропадает.

Почему 40 миллионов? Потому, что в данный момент большая часть моей оперативки забита всяким виртуальным дерьмом =)

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

Ваше время чтения из файла почти 2 секунды - это файл 55 мегабайт? Потому что у меня чтение этого файла занимает 184 секунды

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

Да было бы классно,только вначале надо качнуть баш

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

tmp$ time ./wc < bigtestfile.txt >result

real 0m0.802s user 0m0.785s sys 0m0.016s

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

//////////////////////////////////
#define WORD_TAB_SIZE 1024
#define WORD_MAX_LENGTH 1024
#define ISALNUM(c) (isalpha (c) || (c) == '_')

typedef struct word_st {
    struct word_st *next;
    int   counter;
    char  str[];
}word_t;

word_t *words[WORD_TAB_SIZE] = {0};
///////////////////////////////////////////////////////////
unsigned str_hash (char *str)
{
    unsigned int idx = 0;

    while (*str) {
        idx = (idx * 31) + (unsigned int) *str++;
    }
    return (idx % WORD_TAB_SIZE);
}

word_t *word_new (char *str)
{
    int len = strlen (str) + 1;
    word_t *w;

    w = malloc (sizeof (word_t) + len);
    strcpy (w->str, str);
    w->counter = 1;
    w->next = NULL;
    return w;
}

void word_count (char *str)
{
    int idx = str_hash (str);
    word_t *prev, *cur;
    int cmp;

    for (prev = NULL, cur = words[idx];
         cur != NULL;
         prev = cur, cur = cur->next) {

        cmp = strcmp (cur->str, str);
        if (cmp < 0)
            break;
        if (cmp == 0) {
            cur->counter++;
            return;
        }
    }
    cur = word_new (str);
    if (prev != NULL) {
        cur->next = prev->next;
        prev->next = cur;
    } else {
        cur->next = words[idx];
        words[idx] = cur;
    }
}

void words_report ()
{
    word_t *w;
    int i;

    for (i = 0; i < WORD_TAB_SIZE; i++) {

        for (w = words[i]; w != NULL; w = w->next) {
            printf ("%20s\t%d\n", w->str, w->counter);
        }
    }
}

int main ()
{
    char word[WORD_MAX_LENGTH];
    enum { STATE_INIT, STATE_WORD} state = STATE_INIT;
    int c, idx;

    idx = 0;
    while ((c = fgetc (stdin)) != EOF) {
        
        switch (state) {
            case STATE_INIT:
                if (ISALNUM (c)) {
                    word[idx++] = tolower (c);
                    state = STATE_WORD;
                }
                break;

            case STATE_WORD:
                if (!ISALNUM (c)) {
                    word[idx] = 0;
                    word_count (word);
                    idx = 0;
                    state = STATE_INIT;
                } else if (idx < WORD_MAX_LENGTH - 1) {
                    word[idx++] = tolower (c);
                }
                break;
        }
    }

    if (state == STATE_WORD) {
        word[idx] = 0;
        word_count (word);
    }
    words_report ();
    return 0;
}
anonymous
()
Ответ на: комментарий от anonymous

Офтоп, конечно, но на вот этом коде я не заметил существенной разницы. Сперва кажется, что один из способов чуть быстрее, но стоит поменять вызовы местами, как иллюзия пропадает.

Эээ. У меня вот так:

<dictionary-keyiterator object at 0x7f4a9b6b7940>
Without: 41
<listiterator object at 0x7f4a9b7ab450>
With.keys():  424051
i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

А ышо вот:

<dict_keyiterator object at 0x7f1679f34908>
Without: 51
<dict_keyiterator object at 0x7f1679f34908>
With.keys():  51

При том, что даже если в одной из функций поменять количество элементов или их значения, а так же начало их нумерации через enumerate(range(), start), то адреса объектов всё равно будут совпадать.

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

нет 55 мб,может комп тормозит? посмотрите какое время выдаст моя программа

Gremlin_
() автор топика
Ответ на: комментарий от alex4321

вот время на плюсах: Read time : 216000 ms

Count time : 382895 ms

программа чуть изменена , смотри вконце файла закомментированна

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

Тебе уже ничего не поможет, раз подобная прога у тебя сотни секунд выполняется. Выбери себе другую профессию.

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

Засуньте

Предлагаю проигнорировать этого господина. Пусть сам разбирается или идет в макдак работать с таким гонором.

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