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

Померил с использованием таймеров (чтобы не учитывать 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>>