binary:split = O(size^2)

begemot_sun

unread,

Nov 17, 2017, 7:58:01 AM11/17/17

to Erlang по-русски

Кстати, кто не знал binary:split/3 имеет квадратичную какую-то зависимость времени исполнения от размера данных. Я в шоке.

Тестовый пример:

1> A = « «"this_is_email", 10» || _ <- lists:seq(1,100000)».

«"this_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis"...»

2> timer:tc(fun()-> binary:split(A, «10», [ global ]) end).

{89907,

[«"this_is_email"»,«"this_is_email"»,

«"this_is_email"»,«"this_is_email"»,«"this_is_email"»,

«"this_is_emai"...»,«"this_is_"...»,«"this"...»,

«...»|...]}

3> B = iolist_to_binary([A,A,A,A,A]).

«"this_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis_is_email\nthis"...»

4> timer:tc(fun()-> binary:split(B, «10», [ global ]) end).

{1346013,

[«"this_is_email"»,«"this_is_email"»,

«"this_is_email"»,«"this_is_email"»,«"this_is_email"»,

«"this_is_emai"...»,«"this_is_"...»,«"this"...»,

«...»|...]}

5> 1346013 / 89907.

14.97117020921619

Проверялось в

Erlang/OTP 18 [erts-7.3.1] [source-25741fd] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false]

что в 20 версии я не знаю.

Danil A. Zagoskin

unread,

Nov 17, 2017, 10:05:41 AM11/17/17

to Erlang по-русски

В OTP 20.0 подергал по нескольку раз, средние (на глаз) времена имеют отношение ровно 25.

Т.е. подтверждаю квадратичность global на 20.

--
Вы получили это сообщение, поскольку подписаны на группу "Erlang по-русски".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес erlang-russian+unsubscribe@googlegroups.com.
Чтобы отправлять сообщения в эту группу, отправьте письмо на электронный адрес erlang-russian@googlegroups.com.
Чтобы настроить другие параметры, перейдите по ссылке https://groups.google.com/d/optout.

Sergey Prokhorov

unread,

Nov 18, 2017, 8:54:47 AM11/18/17

to Erlang по-русски

Попробовал бенчмарк сделать, заодно добавил re:split.

http://tryerl.seriyps.ru/#id=d1f3

Результаты для запуска на одном большом бинаре размером N или для X запусков на бинаре размером N / X хоть и различаются, но не квадратично.

Возможно что дело в аллокации памяти, но точно не в алгоритме поиска.

пятница, 17 ноября 2017 г., 13:58:01 UTC+1 пользователь begemot_sun написал:

Sergey Loguntsov

unread,

Nov 18, 2017, 10:02:32 AM11/18/17

to erlang-...@googlegroups.com

> Возможно что дело в аллокации памяти, но точно не в алгоритме поиска.

в любом случае, даже аллоцируя память время должно быть O(N), а не увеличиваться в степенной зависимости.

18 ноября 2017 г., 16:54 пользователь Sergey Prokhorov <seri...@gmail.com> написал:

--
Вы получили это сообщение, поскольку подписаны на одну из тем в группе "Erlang по-русски".
Чтобы отменить подписку на эту тему, перейдите по ссылке https://groups.google.com/d/topic/erlang-russian/2omdlZpGX00/unsubscribe.
Чтобы отменить подписку на эту группу и все ее темы, отправьте письмо на электронный адрес erlang-russian+unsubscribe@googlegroups.com.

Reply all

Reply to author

Forward