Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9157509

Browse files
Faster merge of overlapping intervals
1 parentfea52e8 commit9157509

File tree

4 files changed

+33
-12
lines changed

4 files changed

+33
-12
lines changed

‎CHANGELOG.md‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,12 @@
11
#Changelog
22

3+
##2.6.2 (not yet released)
4+
5+
###Changed
6+
- Improve performance of`Interval` creation and union for large disjunctions of overlapping intervals.
7+
8+
9+
310
##2.6.1 (2025-05-25)
411

512
###Added

‎portion/interval.py‎

Lines changed: 20 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -53,21 +53,29 @@ def __init__(self, *intervals):
5353
# Sort intervals by lower bound, closed first.
5454
self._intervals.sort(key=lambdai: (i.lower,i.leftisBound.OPEN))
5555

56-
i=0
5756
# Try to merge consecutive intervals
58-
whilei<len(self._intervals)-1:
57+
new_intervals= []
58+
i=0
59+
whilei<len(self._intervals):
5960
current=self._intervals[i]
60-
successor=self._intervals[i+1]
6161

62-
ifself.__class__._mergeable(current,successor):
62+
# Keep merging with consecutive intervals while possible
63+
whilei+1<len(self._intervals):
64+
# `current' is either self._intervals[i] or the result of
65+
# the last merge operation in this loop.
66+
successor=self._intervals[i+1]
67+
68+
ifnotself.__class__._mergeable(current,successor):
69+
break
70+
71+
# Merge current with successor
6372
ifcurrent.lower==successor.lower:
6473
lower=current.lower
6574
left= (
6675
current.left
6776
ifcurrent.left==Bound.CLOSED
6877
elsesuccessor.left
6978
)
70-
7179
else:
7280
lower=min(current.lower,successor.lower)
7381
left= (
@@ -87,12 +95,13 @@ def __init__(self, *intervals):
8795
current.rightifupper==current.upperelsesuccessor.right
8896
)
8997

90-
union=Atomic(left,lower,upper,right)
91-
self._intervals.pop(i)# pop current
92-
self._intervals.pop(i)# pop successor
93-
self._intervals.insert(i,union)
94-
else:
95-
i=i+1
98+
current=Atomic(left,lower,upper,right)
99+
i+=1
100+
101+
new_intervals.append(current)
102+
i+=1
103+
104+
self._intervals=new_intervals
96105

97106
@classmethod
98107
deffrom_atomic(cls,left,lower,upper,right):

‎pyproject.toml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ build-backend = "hatchling.build"
44

55
[project]
66
name ="portion"
7-
version ="2.6.1"
7+
version ="2.6.2-pre1"
88
license = {text ="LGPLv3" }
99
authors = [{name ="Alexandre Decan",email ="alexandre.decan@lexpage.net" }]
1010
description ="Python data structure and operations for intervals"

‎tests/test_interval.py‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -66,6 +66,11 @@ def test_creation_issue_19(self):
6666
# https://github.com/AlexandreDecan/python-intervals/issues/19
6767
assertP.Interval(P.empty(),P.empty())==P.empty()
6868

69+
deftest_merge_consecutive(self):
70+
i=P.Interval(P.closed(0,2),P.closed(1,4),P.closed(3,5))
71+
asserti==P.closed(0,5)
72+
assertlen(i._intervals)==1
73+
6974
deftest_bounds(self):
7075
i=P.openclosed(1,2)
7176
asserti.left==P.OPEN

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp