Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

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

Чтобы люди не убивались 24 часа, можно заранее объявить время публикации условий и закрыть прием решений через 3-5 часов. Как, собственно, давно и делают онлайн-площадки соревнований по программированию.

Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение

Странно, почему никто не спрашивает:
К чему эти пляски с Clang, чем вас не устроил более распространенный (и быстрый) gcc?

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

Визуализация графа социальной сети: анализ событий блогосферы перед декабрём 2011 года

Что означают вершины? Что означают ребра? Анализ betweeness и centrality графа в котором вершин больше чем ребер — очень странная идея.

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

Математическая библиотека Numbers.js

Node.js это тот же V8 что и в WebKit-браузерах. Поэтому тесты в Хроме позволяют сравнить производительность на сервере.

Математическая библиотека Numbers.js

У библиотеки 2 больших минуса:
Она похоже не прописывается просто так в window в браузере. А как бы небрежно писать в доках «With node, simply require it: var numbers = require('numbers');», и не упоминать о первом синусе, как минимум некрасиво.

Там как-то пофигистично относятся к производительности. Глянул 1-ю функцию, дальше наверное еще хуже. jsperf.com/numbers-js-sum

Почему язык Haskell так непопулярен

Без подхода — никогда не стараться оптимизировать заранее — не сделать по настоящему оптимальную программу (если нужно). Как раз мысли об оптимальности приводят к неоптимальным программам.

Передергиваете

Почему язык Haskell так непопулярен

1) Приводится аргумент что для использования в «надежном» поекте надо протестировать пакеты из Hackage. Намек на то что их никто не тестирует? В чем отличие от библиотек на других языках? Мне кажется, вероятность наличия ошибок в популярных библиотеках на Hackage очень мала.

2) «Дело в том, что имеются серьёзные риски получить неподдерживаемые исходные коды на «эзотерическом» языке программирования» — странное утверждение. Риски получить неподдерживаемый код на мейнстримных языках в разы больше.

3) «Рекомендация» в конце — я думаю стеб? :)

Играемся с изображениями в Python

Сами посудите, если у вас процессор 2ГГц, получается что на обработку 1 пикселя уходит 30 000 тактов. Как-то многовато

Играемся с изображениями в Python

OpenCV в среднем такие операции на картинке такого размера выполняет за 1 мс, без учета IO конечно.

Насколько вы подвержены тупняку, и немного holywar

Если убрать ту самую проверку на коллизии, останется 0.016, при чистом I/O 0.006, т. е. дальше некуда.

Насколько вы подвержены тупняку, и немного holywar

Финальный вариант с ограничением в 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;
}

Насколько вы подвержены тупняку, и немного holywar

С проверкой примерно 0.045.

Еще можно выкинуть unordered_map и написать свой простенький хеш открытой адресацией и линейным исследованием. Если известна нормальная верхняя оценка кол-ва возможных слов на входе, то получиться едва ли не короче, чем 2 комментариями выше.

Насколько вы подвержены тупняку, и немного holywar

проверка закоментирована, потому что в pg2600.txt нет ни одной коллизии.

Насколько вы подвержены тупняку, и немного holywar

Мод:
На моей машине ~ 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;
}

Играете ли вы в компьютерные игры?

Если часто в них играть, то да :)

Играете ли вы в компьютерные игры?

Если играете изредка, когда нечего делать — не считается.

Играете ли вы в компьютерные игры?

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

Играете ли вы в компьютерные игры?

Не в счет.

Принцип «Разделяй и властвуй», а также бесконечные потоки в Haskell

Маленькое примечание к этому типу: filter (<10) primes ->> [2,3,5,7, никогда не завершит своего выполнения, т.к. filter не знает, будут ли числа меньше 10 или нет и продолжает их искать.

Да вроде нет, filter ничем не отличается от других ленивых функций.

На тему «разделяй и властвуй» советую очень крутую книжку Ричарда Бёрда «Жемчужины проектирования алгоритмов: функциональный подход», почитать первые главы можно тут: oz.by/books/more10282958.html

Знакомимся с Fabric.js. Часть 1-я

kangax перевел свою же статью :)