From f4916887e09a2bc9b0301ce0751e2e5b057cb592 Mon Sep 17 00:00:00 2001 From: Aleksandr Erofeev Date: Thu, 17 Jan 2013 18:21:23 +0400 Subject: Fix bug in queue:out/1, queue:out_r/1 that makes it O(N^2) in worst case Running out and out_r one after another many times will copy one list back and forth if another is empty. Change r2f and f2r to copy only half of big list so such cases will happen more rarely --- lib/stdlib/src/queue.erl | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) (limited to 'lib') diff --git a/lib/stdlib/src/queue.erl b/lib/stdlib/src/queue.erl index afe917b151..bc1bd06534 100644 --- a/lib/stdlib/src/queue.erl +++ b/lib/stdlib/src/queue.erl @@ -472,22 +472,24 @@ init(Q) -> drop_r(Q). -compile({inline, [{r2f,1},{f2r,1}]}). -%% Move all but two from R to F, if there are at least three +%% Move half of elements from R to F, if there are at least three r2f([]) -> {[],[]}; r2f([_]=R) -> {[],R}; r2f([X,Y]) -> {[X],[Y]}; -r2f([X,Y|R]) -> - {[X,Y],lists:reverse(R, [])}. +r2f(List) -> + {FF,RR} = lists:split(length(List) div 2 + 1, List), + {FF,lists:reverse(RR, [])}. -%% Move all but two from F to R, if there are enough +%% Move half of elements from F to R, if there are enough f2r([]) -> {[],[]}; f2r([_]=F) -> {F,[]}; f2r([X,Y]) -> {[Y],[X]}; -f2r([X,Y|F]) -> - {lists:reverse(F, []),[X,Y]}. +f2r(List) -> + {FF,RR} = lists:split(length(List) div 2 + 1, List), + {lists:reverse(RR, []),FF}. -- cgit v1.2.3