aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorHans Bolinder <[email protected]>2019-02-12 11:23:34 +0100
committerHans Bolinder <[email protected]>2019-02-12 11:23:34 +0100
commit03ede8910696037c60874a345fd5a9a7c99c5b48 (patch)
tree2212a1921426b8fa53990be91002d8795b89795e
parentb5fa09f0dd9bd37b0d98a667aa8fcccc727853fd (diff)
parent485713afa0d2481e93882bc386aebb06a49c04bc (diff)
downloadotp-03ede8910696037c60874a345fd5a9a7c99c5b48.tar.gz
otp-03ede8910696037c60874a345fd5a9a7c99c5b48.tar.bz2
otp-03ede8910696037c60874a345fd5a9a7c99c5b48.zip
Merge branch 'maint'
* maint: Optimize calendar:gregorian_days_to_date/1
-rw-r--r--lib/stdlib/src/calendar.erl39
-rw-r--r--lib/stdlib/test/calendar_SUITE.erl14
2 files changed, 41 insertions, 12 deletions
diff --git a/lib/stdlib/src/calendar.erl b/lib/stdlib/src/calendar.erl
index bb5d450cd6..3a083d9fda 100644
--- a/lib/stdlib/src/calendar.erl
+++ b/lib/stdlib/src/calendar.erl
@@ -529,24 +529,41 @@ valid_date({Y, M, D}) ->
%% day_to_year(DayOfEpoch) = {Year, DayOfYear}
%%
-%% The idea here is to first guess a year, and then adjust. Although
-%% the implementation is recursive, at most 1 or 2 recursive steps
+%% The idea here is to first set the upper and lower bounds for a year,
+%% and then adjust a range by interpolation search. Although complexity
+%% of the algorithm is log(log(n)), at most 1 or 2 recursive steps
%% are taken.
-%% If DayOfEpoch is very large, we need far more than 1 or 2 iterations,
-%% since we just subtract a yearful of days at a time until we're there.
%%
-spec day_to_year(non_neg_integer()) -> {year(), day_of_year()}.
day_to_year(DayOfEpoch) when DayOfEpoch >= 0 ->
- Y0 = DayOfEpoch div ?DAYS_PER_YEAR,
- {Y1, D1} = dty(Y0, DayOfEpoch, dy(Y0)),
+ YMax = DayOfEpoch div ?DAYS_PER_YEAR,
+ YMin = DayOfEpoch div ?DAYS_PER_LEAP_YEAR,
+ {Y1, D1} = dty(YMin, YMax, DayOfEpoch, dy(YMin), dy(YMax)),
{Y1, DayOfEpoch - D1}.
--spec dty(year(), non_neg_integer(), non_neg_integer()) ->
+-spec dty(year(), year(), non_neg_integer(), non_neg_integer(),
+ non_neg_integer()) ->
{year(), non_neg_integer()}.
-dty(Y, D1, D2) when D1 < D2 ->
- dty(Y-1, D1, dy(Y-1));
-dty(Y, _D1, D2) ->
- {Y, D2}.
+dty(Min, Max, _D1, DMin, _DMax) when Min == Max ->
+ {Min, DMin};
+dty(Min, Max, D1, DMin, DMax) ->
+ Diff = Max - Min,
+ Mid = Min + (Diff * (D1 - DMin)) div (DMax - DMin),
+ MidLength =
+ case is_leap_year(Mid) of
+ true -> ?DAYS_PER_LEAP_YEAR;
+ false -> ?DAYS_PER_YEAR
+ end,
+ case dy(Mid) of
+ D2 when D1 < D2 ->
+ NewMax = Mid - 1,
+ dty(Min, NewMax, D1, DMin, dy(NewMax));
+ D2 when D1 - D2 >= MidLength ->
+ NewMin = Mid + 1,
+ dty(NewMin, Max, D1, dy(NewMin), DMax);
+ D2 ->
+ {Mid, D2}
+ end.
%%
%% The Gregorian days of the iso week 01 day 1 for a given year.
diff --git a/lib/stdlib/test/calendar_SUITE.erl b/lib/stdlib/test/calendar_SUITE.erl
index df62c0921d..c6d9dbca4a 100644
--- a/lib/stdlib/test/calendar_SUITE.erl
+++ b/lib/stdlib/test/calendar_SUITE.erl
@@ -24,6 +24,7 @@
-export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1,
init_per_group/2,end_per_group/2,
gregorian_days/1,
+ big_gregorian_days/1,
gregorian_seconds/1,
day_of_the_week/1,
day_of_the_week_calibrate/1,
@@ -36,13 +37,16 @@
-define(START_YEAR, 1947).
-define(END_YEAR, 2012).
+-define(BIG_START_YEAR, 20000000).
+-define(BIG_END_YEAR, 20000020).
+
suite() -> [{ct_hooks,[ts_install_cth]}].
all() ->
[gregorian_days, gregorian_seconds, day_of_the_week,
day_of_the_week_calibrate, leap_years,
last_day_of_the_month, local_time_to_universal_time_dst,
- iso_week_number, system_time, rfc3339].
+ iso_week_number, system_time, rfc3339, big_gregorian_days].
groups() ->
[].
@@ -67,6 +71,14 @@ gregorian_days(Config) when is_list(Config) ->
MaxDays = calendar:date_to_gregorian_days({?END_YEAR, 1, 1}),
check_gregorian_days(Days, MaxDays).
+%% Tests that date_to_gregorian_days and gregorian_days_to_date
+%% are each others inverses from ?BIG_START_YEAR-01-01 up to ?BIG_END_YEAR-01-01.
+%% At the same time valid_date is tested.
+big_gregorian_days(Config) when is_list(Config) ->
+ Days = calendar:date_to_gregorian_days({?BIG_START_YEAR, 1, 1}),
+ MaxDays = calendar:date_to_gregorian_days({?BIG_END_YEAR, 1, 1}),
+ check_gregorian_days(Days, MaxDays).
+
%% Tests that datetime_to_gregorian_seconds and
%% gregorian_seconds_to_date are each others inverses for a sampled
%% number of seconds from ?START_YEAR-01-01 up to ?END_YEAR-01-01: We check