Доброго времени суток, хабр!
Моим основным ЯП является D. Всегда понимал, что он будет проигрывать C++ из-за сборщика, каких-то высокоуровневых плюшек и т.д. Но никогда не доходили руки проверить насколько. Решил написать простенький классификатор (даже не помню метод как называется) и проверить. Результат меня приятно удивил: версия C++ отработала за 5.47 сек, версия D — за 5.55 сек. «0.08 сек при обработке файла в 74Мб это не так уж и много» — подумал я. Но, на всякий случай, решил попробовать собрать код на D с помощью gdc (dmd как frontend, gnu backend) и тут уже в душу закрались сомнения, что я всё сделал правильно: код отработал за 4.01 сек, что более чем на 20% быстрее версии на С++. Решил собрать с помощью ldc2 (dmd frontend, llvm backend): 2.92(!!) сек. Тут я решил разобраться.
Превым делом запустил valgrind —tool=callgrind для C++ версии. Как и следовало ожидать на чтение файла уходит бОльшая часть времени.
К сожаления для версии dmd valgrind не смог отработать, и завершился ошибкой illegal hardware instruction, видимо ребята из DigitalMars наколдовали с асемблером сильно, но для gdc и ldc2 всё сработало, как для версии С++.
Хоть и valgrind не demangle’ит имена D функций, зато есть маленький хак: callgrind.out.NNN пропускаем через этот инструмент и получаем нормальные имена (не все, но большую часть). И прошу прощения за gdb, версия 7.9.1-13.fc22 полностью поддерживает demangle D кода.
Осознал я, что рано радоваться, нужно выяснить время выполнения непосредственно алгоритма. И раз уж на то пошло, попробовать различные варианты алгоритма:
- минимальный — создаются классификаторы, точки в классах не сохраняются
- с сохранением точек и слиянием классов (изначальный алгоритм с изначальной настройкой плодил много классов)
Пара слов по поводу алгоритма: я не ставил задачи написать хороший классификатор и правильно его настроить, просто тестовый код.
Результаты в секундах, в скобочках отношение к С++ коду:
| c++ g++ | d dmd | d gdc | d ldc2 | |
|---|---|---|---|---|
| 1 | 0.577 | 1.797 (3.11) | 0.999 (1.73) | 0.583 (1.01) |
| 2 | 0.628 | 2.272 (3.617) | 1.217 (1.937) | 0.898 (1.429) |
Второй вариант алгоритма активней использует сборщик мусора (который я никак не настраивал). Лучший результат выдал, конечно же, ldc2 — в полтора раза медленей С++ при активной сборке мусора, что, в итоге, не так уж и плохо. И даже очень хорошо, если сравнивать полное время выполнения программы (5.4 сек для C++ против 2.9 сек для D на ldc2).
Естественно, для чистоты эксперимента, код я никак специально не оптимизировал и сделал максимально эквивалентным.
import std.stdio; import std.math; import std.format; import std.datetime; //version=COLLECT_MEASURES; //version=MERGE_CLASSES; struct Measure { float x=0, y=0; auto opBinary(string op)( auto ref const Measure m ) const if( op == "+" || op == "-" ) { mixin( "return Measure( x " ~ op ~ " m.x, y " ~ op ~ " m.y );" ); } auto opBinary(string op)( float m ) const if( op == "*" || op == "/" ) { mixin( "return Measure( x " ~ op ~ " m, y " ~ op ~ " m );" ); } } unittest { auto a = Measure(1,3); auto b = Measure(4,5); auto add = a + b; assert( add.x == 5 && add.y == 8 ); auto dif = a - b; assert( dif.x == -3 && dif.y == -2 ); auto mlt = a * 3; assert( mlt.x == 3 && mlt.y == 9 ); auto div = b / 2; assert( div.x == 2 && div.y == 2.5 ); } float sqr( float v ) { return v * v; } float dist( ref const Measure a, ref const Measure b ) { return sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) ); } class Class { Measure mean; size_t N; version(COLLECT_MEASURES) Measure[] measures; this( in Measure m ) { mean = m; N = 1; version(COLLECT_MEASURES) measures ~= m; } void append( in Measure m ) { mean = ( mean * N + m ) / ( N + 1 ); N++; version(COLLECT_MEASURES) measures ~= m; } void merge( const Class m ) { mean = ( mean * N + m.mean * m.N ) / ( N + m.N ); N += m.N; version(COLLECT_MEASURES) measures ~= m.measures; } } unittest { auto cls = new Class( Measure(1,2) ); assert( cls.mean.x == 1 && cls.mean.y == 2 ); assert( cls.N == 1 ); cls.append( Measure(3,4) ); assert( cls.mean.x == 2 && cls.mean.y == 3 ); assert( cls.N == 2 ); } class Classifier { public: Class[] list; float ncls_dist; this( float mdist ) { ncls_dist = mdist; } void classificate( ref const Measure m ) { float min_dist = float.max; Class near_cls; foreach( i; list ) { float d = dist( m, i.mean ); if( d < min_dist ) { min_dist = d; near_cls = i; } } if( min_dist < ncls_dist ) near_cls.append(m); else list ~= new Class(m); } void mergeClasses() { Class[] uniq; l: foreach( cls; list ) { foreach( trg; uniq ) if( dist( cls.mean, trg.mean ) < ncls_dist ) { trg.merge( cls ); continue l; } uniq ~= cls; } list = uniq; } } Measure[] readMeasuresFromFile( string name ) { auto file = File( name, "r" ); Measure[] list; foreach( line; file.byLine() ) { Measure tmp; formattedRead( line, "%f %f", &tmp.x, &tmp.y ); list ~= tmp; } return list; } void main( string[] args ) { auto measures = readMeasuresFromFile( args[1] ); StopWatch sw; sw.start(); auto clsf = new Classifier(3); foreach( m; measures ) clsf.classificate(m); version(MERGE_CLASSES) clsf.mergeClasses(); sw.stop(); writeln( "work time: ", sw.peek.nsecs / 1_000_000_000.0f ); foreach( cls; clsf.list ) writefln( "[%f, %f]: %d", cls.mean.x, cls.mean.y, cls.N ); }
#include <vector> #include <cmath> #include <cfloat> #include <iostream> #include <fstream> #include <sstream> #include <string> #include <cassert> #include <ctime> using namespace std; //#define COLLECT_MEASURES //#define MERGE_CLASSES class Measure { public: float x, y; Measure(): x(0), y(0) {} Measure( float X, float Y ): x(X), y(Y) {} Measure( const Measure& m ): x(m.x), y(m.y) {} Measure operator+( const Measure& m ) const { return Measure( x + m.x, y + m.y ); } Measure operator-( const Measure& m ) const { return Measure( x - m.x, y - m.y ); } Measure operator*( float v ) const { return Measure( x * v, y * v ); } Measure operator/( float v ) const { return Measure( x / v, y / v ); } }; void test_Measure() { Measure a(1,3); Measure b(4,5); auto add = a + b; assert( add.x == 5 && add.y == 8 ); auto dif = a - b; assert( dif.x == -3 && dif.y == -2 ); auto mlt = a * 3; assert( mlt.x == 3 && mlt.y == 9 ); auto div = b / 2; assert( div.x == 2 && div.y == 2.5 ); } inline float sqr( float v ) { return v * v; } float dist( const Measure& a, const Measure& b ) { return sqrt( sqr(a.x - b.x) + sqr(a.y - b.y) ); } class Class { public: Measure mean; size_t N; #ifdef COLLECT_MEASURES vector<Measure> measures; #endif Class( const Measure& m ): mean(m) { N = 1; #ifdef COLLECT_MEASURES measures.push_back(m); #endif } void append( const Measure& m ) { mean = ( mean * N + m ) / ( N + 1 ); N++; #ifdef COLLECT_MEASURES measures.push_back(m); #endif } void merge( const Class& m ) { mean = ( mean * N + m.mean * m.N ) / ( N + m.N ); N += m.N; #ifdef COLLECT_MEASURES measures.insert(measures.end(), m.measures.begin(), m.measures.end()); #endif } }; void test_Class() { auto cls = Class( Measure(1,2) ); assert( cls.mean.x == 1 && cls.mean.y == 2 ); assert( cls.N == 1 ); cls.append( Measure(3,4) ); assert( cls.mean.x == 2 && cls.mean.y == 3 ); assert( cls.N == 2 ); } class Classifier { public: vector<Class*> list; float ncls_dist; Classifier( float mdist ): ncls_dist(mdist) {} void classificate( const Measure& m ) { float min_dist = FLT_MAX; Class* near_cls; for( auto i = list.begin(); i != list.end(); ++i ) { float d = dist( m, (*i)->mean ); if( d < min_dist ) { min_dist = d; near_cls = *i; } } if( min_dist < ncls_dist ) near_cls->append(m); else list.push_back( new Class(m) ); } void mergeClasses() { vector<Class*> uniq; l: for( auto cls = list.begin(); cls != list.end(); ++cls ) { bool is_uniq = true; for( auto trg = uniq.begin(); trg != uniq.end(); ++trg ) { if( dist( (*cls)->mean, (*trg)->mean ) < ncls_dist ) { (*trg)->merge( **cls ); delete (*cls); is_uniq = false; } if( !is_uniq ) break; } if( is_uniq ) uniq.push_back( *cls ); } list = uniq; } ~Classifier() { for( auto i = list.begin(); i != list.end(); ++i ) delete *i; } }; vector<Measure> readMeasuresFromFile( char* name ) { ifstream file( name ); vector<Measure> list; for( string line; getline(file, line); ) { istringstream in( line ); Measure tmp; in >> tmp.x >> tmp.y; list.push_back( tmp ); } return list; } void runTests() { test_Measure(); test_Class(); } int main( int argc, char* args[] ) { //runTests(); auto measures = readMeasuresFromFile( args[1] ); clock_t start = clock(); auto clsf = new Classifier(3); for( auto i = measures.begin(); i != measures.end(); ++i ) clsf->classificate( *i ); #ifdef MERGE_CLASSES clsf->mergeClasses(); #endif clock_t end = clock(); cout << "work time: " << double(end - start) / CLOCKS_PER_SEC << endl; for( auto i = clsf->list.begin(); i != clsf->list.end(); ++i ) cout << "[" << (*i)->mean.x << ", " << (*i)->mean.y << "]: " << (*i)->N << endl; delete clsf; }
import std.stdio; import std.string; import std.exception; import std.random; import std.math; double normal( double mu=0.0, double sigma=1.0 ) { static bool deviate = false; static float stored; if( !deviate ) { double max = cast(double)(ulong.max - 1); double dist = sqrt( -2.0 * log( uniform( 0, max ) / max ) ); double angle = 2.0 * PI * ( uniform( 0, max ) / max ); stored = dist * cos( angle ); deviate = true; return dist * sin( angle ) * sigma + mu; } else { deviate = false; return stored * sigma + mu; } } struct vec { float x, y; } vec randomVec( in vec m, in vec s ) { return vec( normal(m.x, s.x), normal(m.y, s.y) ); } auto generate( size_t[vec] classes ) { vec[] ret; foreach( pnt, count; classes ) { auto tmp = new vec[]( count ); foreach( i, ref t; tmp ) t = randomVec( pnt, vec(1,1) ); ret ~= tmp; } return ret; } import std.getopt; void main( string[] args ) { uint k; getopt( args, "count-multiplier|c", &k ); enforce( args.length == 2, format( "wrong number of arguments: use %s <output_file>", args[0] ) ); auto f = File( args[1], "w" ); scope(exit) f.close(); auto vs = generate( [ vec(-8,8): 20 * k, vec(4,0) : 10 * k, vec(-6,-8) : 15 * k ] ); foreach( v; vs.randomSample(vs.length) ) f.writeln( v.x, " ", v.y ); }
g++ -O2 -std=c++11 cls.cpp -o cls_cpp && echo "c++ g++ builded" dmd -O -release cls.d -ofcls_d_dmd && echo "d dmd builded" ldc2 -O2 -release cls.d -ofcls_d_ldc2 && echo "d ldc2 builded" gdc -O2 cls.d -o cls_d_gdc && echo "d gdc builded"
DMD64 D Compiler v2.067.1
GNU gdb (GDB) Fedora 7.9.1-13.fc22
LDC — the LLVM D compiler (0.15.2-beta1)
PS. В языках Rust и Go не силён, если кто-нибудь захочет написать эквивалентный код (для полноты эксперимента) буду рад вставить результаты сюда.
ссылка на оригинал статьи http://habrahabr.ru/post/261201/
Добавить комментарий