datetime - 关于一个日期时间间隔计算相关的算法(Python)

Question

求一个关于日期时间间隔计算相关的算法，具体问题如下：
当前有一个比较大（上万个）日期时间的list（时间递增但无规律），假设 dt=[
'2015-01-02 10:21:02',
'2015-01-02 10:21:02'
'2015-01-02 10:21:03'
'2015-01-02 10:21:04'
'2015-01-02 10:21:06'
'2015-01-02 10:21:10'
'2015-01-02 10:21:11'
'2015-01-02 10:21:13'
'2015-01-02 10:22:00'
'2015-01-02 10:22:12'
... ...
]
给定一个时间间隔timeframe（假设4s），现在问题是：求在给定连续时间间隔内，list中最多项数目。

最简单的方法是依次对于list中每个项x，向后查找直至大于timeframe+x的项并统计个数。但由于这个list数量庞大，同时还要涉及时间运算，算法难以达到要求，特来请教！

Answer 1

먼저 답변을 주세요.

으아악

위 코드의 경우 datetime 및 timedelta을 가져와야 합니다.

이것은 O(n) 접근 방식이며, n은 timestrs의 개수입니다.

코드가 좀 보기 흉해서 나중에 수정하겠습니다. 하지만 속도와 정확성을 비교하기 위해 몇 가지 실험을 했습니다. 실험에 사용한 전체 코드는 다음과 같습니다.

으아악

포함

• 타이밍을 위한 매우 멋진 데코레이터: simpletimer

  • func을 장식하고 실행하는 데 걸린 시간을 인쇄합니다.

• 임의의 테스트 결과를 생성하는 기능: gentimestrs

  • count 시간 문자열 테스트 데이터를 생성하며, 각 데이터의 시간 간격은 delta

  이하의 임의의 정수입니다.

• 다음 findmax과 findmax2은 각각 저의 접근 방식과 @citaret의 접근 방식입니다(관심 있으신 분들은 인터페이스를 흉내내서 자신만의 기능을 추가하셔도 좋고, 질문하시는 분도 자신의 독창적인 접근 방식을 사용하셔도 됩니다) 비교), simpletimer를 시간에 맞춰 사용하세요.

• 테스트 시 먼저 테스트 애셋을 생성한 후 funclst

에서 비교할 기능을 실행합니다.

실행 예시는 다음과 같습니다.

으아악

다음은 몇 가지 결과입니다.

timeframe==5을 사용하여 자금 금액을 1000, 10000, 100000으로 테스트하세요

으아악

timeframe==10을 사용하여 자금 금액을 1000, 10000, 100000으로 테스트하세요

으아악

1. 기간 크기를 그대로 유지하면 두 번 모두 시험 자금 수가 선형적으로 증가합니다

2. 그런데 기간이 두 배로 늘어나면 두 번째 방법은 두 배의 시간이 걸립니다

이는 @citaret의 최대 메소드 복잡도가 O(n * timeframe)

이 되어야 함을 의미합니다.

또 다른 점은 이 두 가지 방법의 결과가 서로 다를 수 있다는 점입니다. 질문자가 방법이 있으면 정확성을 확인할 수 있습니다.

제가 알아낸 답변이 맞는 것 같은데, 틀린 부분이 있으면 정정해 주세요. 감사합니다!

더 많은 사람들이 이 문제에 대해 논의하는 것을 환영합니다.

---

내가 답변한 질문: Python-QA

Answer 2

데이터도 없고 좋은 프로필도 없습니다. 다른 사람들이 더 나은 솔루션을 가지고 있는지 먼저 버전을 제공하겠습니다.

으아악

Answer 3

@dokelung은 총 27505개의 요소가 포함된 목록(630,000줄의 단일 로그 파일에서 추출되고 여러 소스 IP에서 집계됨)을 사용하여 테스트했는데 원래 시간은 16.544873371035163초가 걸렸습니다. . 효율성이 많이 향상되었습니다. 비록 그 규모는 여전히 초 단위지만, 이것은 하루에 하나의 파일에 불과합니다. 동시에 더 심각한 효율성 문제는 실제로 함수 내의 요구 사항을 충족하는 로그 라인을 추출하는 것임을 알게 되었습니다. 답변해 주시고 참여해 주셔서 감사합니다!