Здравствуйте, FR, Вы писали:
АХ>>А так напиши универсальный split и запости сюда результаты. FR>Вот такой не универсальный и наколенный вариант
Твой вариант работает не совсем правильно — попробуй два пробела подряд во входной строке написать.
Кроме того твой тест это чистой воды мухлеж. Если не пересоздавать, а очищать vector на кажой итерации, то бустовский вариант тоже ускорится раза в четыре.
Ниже более универсальный вариант. Вместо std::vector принимает любой контейнер с push_back, вместо строки принимает любой контейнер с последовательным константным итератором.
template <class C, class S, class P>
inline void split(C & c, const S & str, P & is_delimiter)
{
bool next_token = false;
typename S::const_iterator it = str.begin(), end = str.end(), token_start = it;
for(; it != end; ++it)
{
if (next_token)
{
next_token = false;
token_start = it;
}
if (is_delimiter(*it))
{
if (token_start != it)
c.push_back(S(token_start, it));
next_token = true;
}
}
if (!next_token && (token_start != it))
c.push_back(S(token_start, it));
}
Вот на таком тесте у меня этот вариант отрабатывает даже чуть быстрее твоего варианта(на нормальном тесте чуть медленнее, тестировалось на vc7.1 + dinkumware stl):
inline bool is_space(const char c)
{
return c == ' ';
}
int main()
{
int r = 0;
vector<string> tokens(5);
string str("123 345 asdf 23453 asdfas");
for(int i = 0; i < 1000000; ++i)
{
tokens.erase(tokens.begin(),tokens.end());
split(tokens, str, is_space);
r += tokens.size();
}
cout << r << endl;
return 0;
}
Здравствуйте, Vermicious Knid, Вы писали:
VK>Здравствуйте, FR, Вы писали:
АХ>>>А так напиши универсальный split и запости сюда результаты. FR>>Вот такой не универсальный и наколенный вариант VK>Твой вариант работает не совсем правильно — попробуй два пробела подряд во входной строке написать.
Читай выше Все без гарантий
Хотя проверил, бустовский сплит работает также как мой, на два пробела выдает пустую строку, так что ошибка у тебя
VK>Кроме того твой тест это чистой воды мухлеж. Если не пересоздавать, а очищать vector на кажой итерации, то бустовский вариант тоже ускорится раза в четыре.
Где это там вектор пересоздается? Не было такого, у меня во всех вариантах vector<string> tokens(5); вынесен из цикла.
VK>Вот на таком тесте у меня этот вариант отрабатывает даже чуть быстрее твоего варианта(на нормальном тесте чуть медленнее, тестировалось на vc7.1 + dinkumware stl):
Здравствуйте, FR, Вы писали:
FR>Хотя проверил, бустовский сплит работает также как мой, на два пробела выдает пустую строку, так что ошибка у тебя
Да, ты прав. Просто в случае пробелов это как-то нелогично. Но если разделители запятые или что-то вроде того, то тогда действительно это имеет смысл.
Но раз уж так задумано, то тогда все еще проще, и еще слегка быстрее:
template <class C, class S, class P>
inline void split(C & c, const S & str, P & is_delimiter)
{
typename S::const_iterator it = str.begin(), token_start = it, end = str.end();
for(; it != end; ++it)
{
if (is_delimiter(*it))
{
if (token_start != it)
c.push_back(S(token_start, it));
++(token_start = it);
}
}
if (token_start != it)
c.push_back(S(token_start, it));
}
FR>Где это там вектор пересоздается? Не было такого, у меня во всех вариантах vector<string> tokens(5); вынесен из цикла.
В твоих примерах нет. Но в примерах на C# и других языках массивы то создаются заново на каждом вызове. Поэтому я согласен с Андреем Хроповым, что так корректнее сравнивать.
Re[7]: BOOST, .NET, String.Split и производительность…
Здравствуйте, CreatorCray, Вы писали:
CC>Дык библиотеки то в первую очередь надо оптимизировать. К примеру большую часть CRT можно (и нужно) переписывать с нуля с учетом производительности. Потому как тормозная она...
А это кому-то надо?
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: BOOST, .NET, String.Split и производительность…
Здравствуйте, eao197, Вы писали:
VD>>Ты прочти свое сообщение и подумай кому бы еще о KISS напомнить.
E>И кому?
Да действительно, кому?
E>Если хочешь позлословить по поводу приведенного мной кода, то это всего лишь популярное изложение части деталей реализации boost::algorithms::is_any_of. К реализации которого я не имею никакого отношения.
Что там "злословить" то? Проблема выеденного яйца не стоит. А ты тут целый трактат написал. Так что KISS.
... << RSDN@Home 1.2.0 alpha rev. 637>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: BOOST, .NET, String.Split и производительность…
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, CreatorCray, Вы писали:
CC>>Дык библиотеки то в первую очередь надо оптимизировать. К примеру большую часть CRT можно (и нужно) переписывать с нуля с учетом производительности. Потому как тормозная она...
VD>А это кому-то надо?
Иногда надо.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
FR>>Где это там вектор пересоздается? Не было такого, у меня во всех вариантах vector<string> tokens(5); вынесен из цикла.
VK>В твоих примерах нет. Но в примерах на C# и других языках массивы то создаются заново на каждом вызове. Поэтому я согласен с Андреем Хроповым, что так корректнее сравнивать.
При тех тромозах что показал бустовский сплит не принципиально
Да и добавить нормальный аллокатор вектору и строкам (хотя бы тот же boost::pool) и не будет разницы где разместить.
Re[3]: BOOST, .NET, String.Split и производительность…
Здравствуйте, Denis2005, Вы писали:
E>>По моему беглому взгляду на реализацию split-а показалось, что дело в реализации is_any_of.
D>Даже если написать примитивный предикат:
D>bool char_is_space(const char c) D>{ D> return c == ' '; D>}
D>то заместо ~20 сек., получаем ~5 сек., на VC++ 8.0.
Ну мужики, я ведь только заглянул в split и увидел большое количество копирований предиката. А дальше я не смотрел. Очень вероятно, что сам алгоритм поиска и выделения подстрок грешит таким же избыточным количеством копирований и передачи аргументов по значению.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Re: BOOST, .NET, String.Split и производительность…
A>Если взять STLPort, то результат будет лучше (циферки для AthlonXP@1916 MHz): A>MSVC 2003: 20 сек A>MSVC 2003 + STLPort 5.0: 6 сек.
A>Если применить предикат, то время с STLPort сократиться до 2 сек.
Это все равно не очень радужный результат. У меня split-'велосипед' на STL-е с MSVC 2005 и strtok, выдает ~0.7 сек.
Причем пришлось отказаться от std::string. Конечно, не очень хороший код во многих смыслах
(в частности коверкает исх. строку и раставляет указатели на полученные 'обрывки' str),
но свою задачу решает за приемлемое время.
P.S. Меня больше интересует куда исчезает принцип нулевых издержек из рекомендуемых библиотек C++?
Re[9]: BOOST, .NET, String.Split и производительность…
Здравствуйте, Андрей Хропов, Вы писали:
АХ>Здравствуйте, Denis2005, Вы писали:
АХ>Обожаю бенчмарки :)
АХ>Померил с использованием таймеров (чтобы не учитывать JIT компиляцию) АХ>Вот результаты (усреднены по 10 запускам) АХ>(Athlon XP 1700+ @ 1.5 GHZ + 512Mb DDR266) АХ>:
АХ>4) Python — 3.48 сек АХ>6) GCC + Boost — 22.5 сек
АХ>С++:
АХ>
АХ>#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;
АХ>int main()
АХ>{
АХ> DWORD start = GetTickCount();
АХ> int res = 0;
АХ> for(int i = 0; i < 1000000; i++)
АХ> {
АХ> // так корректней сравнивать, ведь в др программах мы размер не указывали
АХ> // + по моим тестам почти не повлияло на скорость/*
Нет. Так сравнивать некорректно, потому что в других языках массивы могут быть
реализованы как деки (std::deque) или списки (std::list). std::vector всегда реалочится при увеличении размера, а, например, питоновские «массивы» на самом деле списки,
поэтому, операции конкатенации для них выполняются гааараздо быстрее.
Правильнее было бы использовать std::list.
*/
АХ> vector<string> tokens;
//
АХ> split(tokens, "123 345 asdf 23453 asdfas", is_any_of(" "));
АХ> res += tokens.size();
АХ> }
АХ> DWORD stop = GetTickCount();
АХ> cout << "res is " << res << ',' << stop - start << " ms elapsed\n";
АХ> return 0;
АХ>}
АХ>
Мой вариант:
#include <list>
#include <string>
#include <iostream>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/classification.hpp>
#define OS_POSIX
#ifdef OS_WINDOWS
#include <windows.h> // for GetTickCount#else// posix#include <sys/times.h>
#endif
using namespace std;
using namespace boost::algorithm;
int main()
{
#ifdef OS_WINDOWS
DWORD start = GetTickCount();
#else
struct tms t;
clock_t start = times(&t);
#endif
int res = 0;
for(int i = 0; i < 1000000; i++)
{
list<string> tokens;
split(tokens, "123 345 asdf 23453 asdfas", is_any_of(" "));
res += tokens.size();
}
#ifdef OS_WINDOWS
DWORD stop = GetTickCount();
#else
clock_t stop = times(&t);
#endif
cout << "res is/ " << res << ',' << stop - start << " ms elapsed\n";
return 0;
}
# g++ test_with_vector.cpp
# ./a.out
res is/ 5000000,3117 ms elapsed
# g++ -O3 test_with_vector.cpp
# ./a.out
res is/ 5000000,756 ms elapsed
# g++ test_with_deque.cpp
# ./a.out
res is 5000000,2919 ms elapsed
# g++ -O3 test_with_deque.cpp
# ./a.out
res is 5000000,801 ms elapsed
# g++ test_with_list.cpp
# ./a.out
res is 5000000,2673 ms elapsed
# g++ -O3 test_with_list.cpp
# ./a.out
res is 5000000,653 ms elapsed
# python test.py
res is 5000000, 2.100000 sec elapsed
# cat /proc/cpuinfo
processor : 0
vendor_id : GenuineIntel
cpu family : 15
model : 3
model name : Intel(R) Pentium(R) 4 CPU 2.80GHz
stepping : 4
cpu MHz : 2794.054
cache size : 1024 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 1
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe pni monitor ds_cpl cid xtpr
bogomips : 5589.58
processor : 1
vendor_id : GenuineIntel
cpu family : 15
model : 3
model name : Intel(R) Pentium(R) 4 CPU 2.80GHz
stepping : 4
cpu MHz : 2794.054
cache size : 1024 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 1
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 5
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe pni monitor ds_cpl cid xtpr
bogomips : 5585.27
Здравствуйте, cattus, Вы писали:
C>/* C>Нет. Так сравнивать некорректно, потому что в других языках массивы могут быть C>реализованы как деки (std::deque) или списки (std::list). std::vector всегда реалочится при увеличении размера, а, например, питоновские «массивы» на самом деле списки, C>поэтому, операции конкатенации для них выполняются гааараздо быстрее. C>Правильнее было бы использовать std::list. C>*/
Я вообще мерил с вынесенным за цикл вектором разница небольшая, так что дело не в этом.
C># g++ test_with_list.cpp C># ./a.out C>res is 5000000,2673 ms elapsed
C># g++ -O3 test_with_list.cpp C># ./a.out C>res is 5000000,653 ms elapsed
странные у тебя какие то результаты, у меня с твоим кодом gcc3.2(mingw под WinXP) c -O3 дает res is/ 5000000,6063 ms elapsed
а gcc3.4.4(mingw под WinXP) c -O3 дает вообще res is/ 5000000,19985 ms elapsed
процессор Cel D 2.66
Здравствуйте, Андрей Хропов, Вы писали:
АХ>Здравствуйте, Denis2005, Вы писали:
АХ>Обожаю бенчмарки :)
АХ>Померил с использованием таймеров (чтобы не учитывать JIT компиляцию) АХ>Вот результаты (усреднены по 10 запускам) АХ>(Athlon XP 1700+ @ 1.5 GHZ + 512Mb DDR266) АХ>:
АХ>1) DMD — 0.775 сек АХ>2) GDC — 0.905 сек АХ>3) С#/Nemerle — 1.1 сек АХ>4) Python — 3.48 сек АХ>5) Python+Psyco — 4.12 (не ускорил!) АХ>6) GCC + Boost — 22.5 сек АХ>7) MS VC++ + Boost — 35 сек
Вот еще одно подтверждение изначальной ущербности теста. Прошу сильно не пинать за код -- я очень долго ничего не писал на Haskell'е.
module Main where
import System.CPUTime (getCPUTime)
{- меня заленило лезть в документацию и искать функцию аналогичную split,
поэтому я реализовал её сам. -}
split :: (a -> Bool) -> [a] -> [[a]]
split _ [] = []
split p l = case break p l
of { (b, []) -> [b]
; ([], _) -> [[]]
; (b, (e:[])) -> [b]
; (b, (e:ex)) -> b : (split p ex)
}
fun :: Int -> Int
fun = fun' 0
where
fun' :: Int -> Int -> Int
fun' l n | n <= 0 = l
| otherwise
= fun'
{- следующая строка вычисляется только 1 раз,
в качестве первого аргумента функции fun'
всегда передается одно и тоже значение. -}
(l + (length (split (==' ') "123 345 asdf 23453 asdfas")))
(n - 1)
main :: IO ()
main = do { begin <- getCPUTime
; putStr "Res is "
; (putStr . show . fun) 1000000
; putStr ", "
; end <- getCPUTime
; (putStr . show) (((fromInteger (end - begin)) :: Double) / (1000000000 :: Double))
; putStrLn " ms. elapsed."
}
# ghc -O3 --make main.hs
# ./a.out
Res is 5000000, 8.998 ms. elapsed.
# ghc --version | head -n1
The Glorious Glasgow Haskell Compilation System, version 6.4.1
Здравствуйте, FR, Вы писали:
FR>Здравствуйте, cattus, Вы писали:
C>>/* C>>Нет. Так сравнивать некорректно, потому что в других языках массивы могут быть C>>реализованы как деки (std::deque) или списки (std::list). std::vector всегда реалочится при увеличении размера, а, например, питоновские «массивы» на самом деле списки, C>>поэтому, операции конкатенации для них выполняются гааараздо быстрее. C>>Правильнее было бы использовать std::list. C>>*/
FR>Я вообще мерил с вынесенным за цикл вектором разница небольшая, так что дело не в этом.
C>># g++ test_with_list.cpp C>># ./a.out C>>res is 5000000,2673 ms elapsed
C>># g++ -O3 test_with_list.cpp C>># ./a.out C>>res is 5000000,653 ms elapsed
FR>странные у тебя какие то результаты, у меня с твоим кодом gcc3.2(mingw под WinXP) c -O3 дает res is/ 5000000,6063 ms elapsed FR>а gcc3.4.4(mingw под WinXP) c -O3 дает вообще res is/ 5000000,19985 ms elapsed FR>процессор Cel D 2.66
Все вопросы к реализации MinGW. И вообще, тестировать надо под нормальными операционками, а не под тормозами от дяди Билла. Попробуй другие компиляторы. Я собирал gcc-4.1.1 и gcc-3.3 - в обоих случаях результаты одинаковые, в первом случае линковалось с libstdc++.so.6, во втором - с libstdc++.so.5.
fun :: Int -> Int
fun = fun' 0
where
fun' :: Int -> Int -> Int
fun' l n | n <= 0 = l
| otherwise
= fun'
(l +
{- следующая строка вычисляется только 1 раз,
в качестве первого аргумента функции fun'
всегда передается одно и тоже значение. -}
(length (split (==' ') "123 345 asdf 23453 asdfas")))
(n - 1)