[Benchmark]:updated - Split на C++,D,C#,Nemerle,Boo,Java,Sca
От: Андрей Хропов Россия  
Дата: 23.09.06 23:22
Оценка: 61 (6) :)
Не удержался от того, чтобы создать новую расширенную версию.

Померил с использованием таймеров (чтобы не учитывать JIT компиляцию)
Вот результаты (усреднены по 10 запускам)
(Pentium M 1,7 Dothan + 768Mb DDR333)
:

Для стандартной библиотеки (и boost как ее продолжение для C++):

  1. D(DMD) — 0.645 сек
  2. D(GDC) — 0.653 сек
  3. С#/Nemerle — 0.870 сек
  4. Boo — 1.003 сек (*)
  5. Python+Psyco — 1.451 сек
  6. Python — 2.182 сек
  7. Java/Scala — 3.470 сек
  8. C++(GCC),boost,list,is_space — 10.045 сек (**)
  9. C++(MS),boost,list,is_space — 12.708 сек (**)

* для Boo почему-то не работает Split(" "), а только Split(),
поэтому неск медленнее

** взят лучший несамодельный вариант

Самоделки :
  1. Nemerle-Tokenizer — 0.738 сек
  2. Nemerle-withLists — 0.896 сек
  3. Java-Bicycle — 1.369 сек
  4. Java-Tokenizer — 2.119 сек
  5. C++(MS),Noname2,list,functor,ref — 2.463 сек (*)
  6. Scala-Tokenizer — 2.642 сек
  7. Scala-withLists — 2.785 сек
  8. C++(GCC),VK,list,functor,val — 3.896 сек (*)

* взят наилучший из самодельных вариантов для данного компилятора

Информация(только новое относительно Re: [Benchmark] DMD быстрее всех
Автор: Андрей Хропов
Дата: 16.09.06
).

Компиляторы:
Boo — Boo Compiler version 0.7.6.2237 (CLR v2.0.50727.42)
Java — Java HotSpot(TM) Client VM (build 1.5.0_08-b03, mixed mode, sharing)
Scala — Scala compiler 2.1.6

Опции:
booc split.boo -optimize+ -o:split-boo.exe
javac split.java
scalac -Xcloselim -Xgenerics split.scala


Исходники:

Boo:

import System; import System.Diagnostics; stopwatch = Stopwatch(); stopwatch.Start(); res = 0; for i in range(1000000): res += "123 345 asdf 23453 asdfas".Split().Length; stopwatch.Stop(); Console.WriteLine("Boo: res is ${res}, ${stopwatch.Elapsed} elapsed");



Java:

import java.io.*; import java.util.*; class splitjava { public static void main(String[] args) { long start = System.nanoTime(); int res = 0; for(int i = 0;i < 1000000;i++) res += "123 345 asdf 23453 asdfas".split(" ").length; long stop = System.nanoTime(); System.out.println("Java-StdLib: res = " + res + ", " + ((double)(stop - start) / 1.0e6) + " ms elapsed"); } }



Scala:

import java.io; import java.util; object splitscala { def main(args : Array[String]) = { val start = System.nanoTime(); var res = 0; for (val i <- Iterator.range(0, 1000000)) res = res + "123 345 asdf 23453 asdfas".split(" ").length; val stop = System.nanoTime(); System.out.println("Scala-StdLib: res = " + res + ", " + ((stop - start) / 1.0e6) + " ms elapsed"); } }



Самоделки:

Nemerle-withLists/Tokenizer (взято отсюда (с) VladD2
Автор: VladD2
Дата: 21.09.06
+ космет. изменения )

using System.Console; using System.Diagnostics; module Parse { public SplitToList(this str : string) : list[string] { def loop(start, i, lst) { if (i < str.Length) match (str[i]) { | ' ' => str.Substring(start, i - start) :: loop(i + 1, i + 1, lst) | _ => loop(start, i + 1, lst) } else if (start == i) lst else [str.Substring(start, i - start)]; } loop(0, 0, []); } public Tokenize(this str : string) : System.Collections.Generic.IEnumerable[string] { def loop(start, i) { if (i < str.Length) match (str[i]) { | ' ' => yield str.Substring(start, i - start); loop(i + 1, i + 1) | _ => loop(start, i + 1) } else if (start != i) yield str.Substring(start, i - start) else () } loop(0, 0); } } ////////////////////////// Далее идут тесты ///////////////////////////////// WriteLine(Parse.SplitToList("123 345 asdf 23453 asdfas")); def stopwatch = Stopwatch(); ///////////////////////////////////////////////////////////////////////////// // Тестируем сплит написанный что называется в стиле "мама не горюй" (с динамическими списками). stopwatch.Start(); mutable count = 0; repeat(1000000) count += Parse.SplitToList("123 345 asdf 23453 asdfas").Length; stopwatch.Stop(); WriteLine($"Nemerle-withLists: res=$count, $(stopwatch.Elapsed) elapsed"); ///////////////////////////////////////////////////////////////////////////// // Тестируем токенайзер. stopwatch.Reset(); stopwatch.Start(); count = 0; repeat(1000000) foreach (_ in Parse.Tokenize("123 345 asdf 23453 asdfas")) count++; stopwatch.Stop(); WriteLine($"Nemerle-Tokenizer: res=$count, $(stopwatch.Elapsed) elapsed");




Java-Bicycle/Tokenizer (взято отсюда (с) n0name2
Автор: n0name2
Дата: 22.09.06
и подправлено чтобы было как везде )

import java.io.*; import java.util.*; class SplitNoname2 { private static int testTokenizer() { int answer = 0; for (int i = 0; i < 1000000; i++) { final List<String> list = new ArrayList<String>(); final String text = "123 345 asdf 23453 asdfas".intern(); for (final StringTokenizer strtok = new StringTokenizer(text); strtok.hasMoreTokens(); list.add(strtok.nextToken())) ; answer += list.size(); } return answer; } private static int testNoname2() throws UnsupportedEncodingException { int answer = 0; final byte space = " ".getBytes("windows-1251")[0]; for (int i = 0; i < 1000000; i++) { final List<String> array = new ArrayList<String>(); final String text = "123 345 asdf 23453 asdfas".intern();//.getBytes("windows-1251"); final int clen = text.length(); for (int c = 0, x = 0; c < clen; c++) { if (text.charAt(c) == space) { array.add( text.substring(x, c)); x = c + 1; } else if (c == clen - 1 && clen - x > 1) { array.add( text.substring(x, clen) ); } } answer += array.size(); } return answer; } public static void main(String [] args) throws UnsupportedEncodingException { long start = System.nanoTime(); int res = testTokenizer(); long stop = System.nanoTime(); System.out.println("Java-Tokenizer: res = " + res + ", " + ((double)(stop - start) / 1.0e6) + " ms elapsed"); start = System.nanoTime(); res = testNoname2(); stop = System.nanoTime(); System.out.println("Java-Noname2: res = " + res + ", " + ((double)(stop - start) / 1.0e6) + " ms elapsed"); } }



Scala-withLists/Tokenizer (взято отсюда (с) VladD2
Автор: VladD2
Дата: 21.09.06
и портировано мной на Scala )

import java.io; import java.util; import System.out._ object SplitVlad { def SplitToList(str : String) : List[String] = { def loop(start : Int, i : Int, lst : List[String] ) : List[String] = { if(i < str.length) str(i) match { case ' ' => str.substring(start, i) :: loop(i + 1, i + 1, lst); case _ => loop(start, i + 1, lst); } else if (start == i) lst; else List(str.substring(start, i)); }; loop(0, 0, Nil); } def Tokenize(str : String) = new Iterator[String]{ var start : Int = 0 var i : Int = 0 var r : String = ""; def hasNext : boolean = { if (i < str.length) str(i) match { case ' ' => r = str.substring(start, i); i = i + 1; start = i; true; case _ => i = i + 1; hasNext; } else if (start != i) { r = str.substring(start, i); start = i; true } else false } def next = r; } def main(args : Array[String]) = { // check print("SplitToList: ["); for(val s <- SplitToList("123 345 asdf 23453 asdfas") ) print(s + ","); print("]\n"); print("Tokenizer: ["); for(val s <- Tokenize("123 345 asdf 23453 asdfas") ) print(s + ","); print("]\n"); var start = System.nanoTime(); var res = 0; for (val i <- Iterator.range(0, 1000000)) res = res + SplitToList("123 345 asdf 23453 asdfas").length; var stop = System.nanoTime(); println("Scala-SplitToList: res = " + res + ", " + ((stop - start) / 1.0e6) + " ms elapsed"); start = System.nanoTime(); res = 0; for (val i <- Iterator.range(0, 1000000)) for(val s <- Tokenize("123 345 asdf 23453 asdfas") ) res = res + 1; stop = System.nanoTime(); println("Scala-Tokenizer: res = " + res + ", " + ((stop - start) / 1.0e6) + " ms elapsed"); } }



По сравнению с Nemerle мне показалось менее выразительным:
1) Генераторы реализуются довольно неизящно
2) Для рекурсивно вызываемых функций type inference не работает
3) Синтаксис pattern-matching а более громоздкий


C++: разные варианты с boost + взяты самоделки от VK
Автор: Vermicious Knid
Дата: 17.09.06
и портирована с Java отсюда (с) n0name2
Автор: n0name2
Дата: 22.09.06
+
опробованы и разными вариантами (функторы и функции, передача предикатов по ссылке и по значению):

#include <list> #include <vector> #include <string> #include <iostream> #include <boost/algorithm/string/split.hpp> #include <boost/algorithm/string/classification.hpp> #include <windows.h> // for GetTickCount using namespace std; using namespace boost::algorithm; class SplitNoname2 { public: template <class C, class P> inline static void SplitVal(C& tokens, const string& str, P is_delimiter) { size_t inpSize = str.size(); for (size_t c = 0, x = 0; c < inpSize; ++c ) { if( is_delimiter(str[c]) ) { tokens.push_back( str.substr(x,c-x) ); x = c + 1; } else if (c == inpSize - 1 && inpSize - x > 1) { tokens.push_back( str.substr(x,inpSize-x) ); } } } template <class C, class P> inline static void SplitRef(C& tokens, const string& str, const P& is_delimiter) { size_t inpSize = str.size(); for (size_t c = 0, x = 0; c < inpSize; ++c ) { if( is_delimiter(str[c]) ) { tokens.push_back( str.substr(x,c-x) ); x = c + 1; } else if (c == inpSize - 1 && inpSize - x > 1) { tokens.push_back( str.substr(x,inpSize-x) ); } } } }; class SplitVK { public: template <class C, class P> inline static void SplitVal(C& tokens, const string& str, P is_delimiter) { typename string::const_iterator it = str.begin(), token_start = it, end = str.end(); for(; it != end; ++it) { if (is_delimiter(*it)) { if (token_start != it) tokens.push_back(string(token_start, it)); ++(token_start = it); } } if (token_start != it) tokens.push_back(string(token_start, it)); } template <class C, class P> inline static void SplitRef(C& tokens, const string& str, const P& is_delimiter) { typename string::const_iterator it = str.begin(), token_start = it, end = str.end(); for(; it != end; ++it) { if (is_delimiter(*it)) { if (token_start != it) tokens.push_back(string(token_start, it)); ++(token_start = it); } } if (token_start != it) tokens.push_back(string(token_start, it)); } }; class MyIsSpace { public: inline bool operator()(char c) const { return c == ' '; } }; inline bool myIsSpace(char c){ return c == ' '; } template<class C, class Pred> inline void TestBoost( const string& testName, Pred pred ) { DWORD start = GetTickCount(); string str = "123 345 asdf 23453 asdfas"; size_t res = 0; for(int i = 0; i < 1000000; i++) { C tokens; split(tokens, str, pred); res += tokens.size(); } DWORD stop = GetTickCount(); cout << "C++,boost," << testName << ": res is " << res << ',' << stop - start << " ms elapsed\n"; } template<class Splitter, class C, class Pred> inline void Test( const string& testName, Pred pred ) { DWORD start = GetTickCount(); const string str = "123 345 asdf 23453 asdfas"; size_t res = 0; for(int i = 0; i < 1000000; i++) { C tokens; Splitter::SplitVal(tokens, str, pred ); res += tokens.size(); } DWORD stop = GetTickCount(); cout << "C++," << testName << ",val: res is " << res << ',' << stop - start << " ms elapsed\n"; start = GetTickCount(); res = 0; for(int i = 0; i < 1000000; i++) { C tokens; Splitter::SplitRef(tokens, str, pred ); res += tokens.size(); } stop = GetTickCount(); cout << "C++," << testName << ",ref: res is " << res << ',' << stop - start << " ms elapsed\n"; } int main() { TestBoost< vector<string> >("vector,is_any_of", is_any_of(" ") ); TestBoost< list<string> >("list,is_any_of", is_any_of(" ") ); TestBoost< vector<string> >("vector,is_space", is_space() ); TestBoost< list<string> >("list,is_space", is_space() ); TestBoost< vector<string> >("vector,myIsSpace", myIsSpace ); TestBoost< list<string> >("list,myIsSpace", myIsSpace ); Test< SplitVK,vector<string> >("VK,vector,function", myIsSpace); Test< SplitVK,list<string> >("VK,list,function", myIsSpace); Test< SplitNoname2,vector<string> >("Noname2,vector,function", myIsSpace); Test< SplitNoname2,list<string> >("Noname2,list,function", myIsSpace); Test< SplitVK,vector<string> >("VK,vector,functor", MyIsSpace() ); Test< SplitVK,list<string> >("VK,list,functor", MyIsSpace() ); Test< SplitNoname2,vector<string> >("Noname2,vector,functor", MyIsSpace() ); Test< SplitNoname2,list<string> >("Noname2,list,functor", MyIsSpace() ); return 0; }



а вот полные таблицы результатов для компилятора от MS(VC++ 8) и GCC (3.4.2 под MinGW):

MS:

C++,boost,vector,is_any_of: 23914 ms elapsed
C++,boost,list,is_any_of: 21801 ms elapsed
C++,boost,vector,is_space: 14842 ms elapsed
C++,boost,list,is_space: 12708 ms elapsed
C++,boost,vector,myIsSpace: 7220 ms elapsed
C++,boost,list,myIsSpace: 5298 ms elapsed
C++,VK,vector,function,val: 4887 ms elapsed
C++,VK,vector,function,ref: 4857 ms elapsed
C++,VK,list,function,val: 2594 ms elapsed
C++,VK,list,function,ref: 2613 ms elapsed
C++,Noname2,vector,function,val: 4837 ms elapsed
C++,Noname2,vector,function,ref: 4847 ms elapsed
C++,Noname2,list,function,val: 2554 ms elapsed
C++,Noname2,list,function,ref: 2534 ms elapsed
C++,VK,vector,functor,val: 4797 ms elapsed
C++,VK,vector,functor,ref: 4777 ms elapsed
C++,VK,list,functor,val: 2513 ms elapsed
C++,VK,list,functor,ref: 2514 ms elapsed
C++,Noname2,vector,functor,val: 4747 ms elapsed
C++,Noname2,vector,functor,ref: 4746 ms elapsed
C++,Noname2,list,functor,val: 2474 ms elapsed
C++,Noname2,list,functor,ref: 2463 ms elapsed

GCC:

C++,boost,vector,is_any_of: 16633 ms elapsed
C++,boost,list,is_any_of: 15893 ms elapsed
C++,boost,vector,is_space: 10515 ms elapsed
C++,boost,list,is_space: 10045 ms elapsed
C++,boost,vector,myIsSpace: 7070 ms elapsed
C++,boost,list,myIsSpace: 6329 ms elapsed
C++,VK,vector,function,val: 4737 ms elapsed
C++,VK,vector,function,ref: 4797 ms elapsed
C++,VK,list,function,val: 4076 ms elapsed
C++,VK,list,function,ref: 4036 ms elapsed
C++,Noname2,vector,function,val: 4997 ms elapsed
C++,Noname2,vector,function,ref: 4997 ms elapsed
C++,Noname2,list,function,val: 4246 ms elapsed
C++,Noname2,list,function,ref: 4256 ms elapsed
C++,VK,vector,functor,val: 4647 ms elapsed
C++,VK,vector,functor,ref: 4606 ms elapsed
C++,VK,list,functor,val: 3896 ms elapsed
C++,VK,list,functor,ref: 3946 ms elapsed
C++,Noname2,vector,functor,val: 4887 ms elapsed
C++,Noname2,vector,functor,ref: 4877 ms elapsed
C++,Noname2,list,functor,val: 4116 ms elapsed
C++,Noname2,list,functor,ref: 4196 ms elapsed

Видно, что выгоднее использовать функторы (немного) и намного выгоднее списки (для особенно для MS)

Ну и наконец tokenizer от McSeem2 8-летней давности
Автор: McSeem2
Дата: 20.09.06
выполняется у меня в среднем за

C++(MS),McSeem2 — 0.470 сек
C++(GCC),McSeem2 — 0.713 сек

но он вне зачета поскольку не создает новые строки.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.