求一个关于日期时间间隔计算相关的算法，具体问题如下：
当前有一个比较大（上万个）日期时间的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数量庞大，同时还要涉及时间运算，算法难以达到要求，特来请教！
大家讲道理2017-04-18 09:23:33
まず私の答えを教えてください:
リーリー上記のコードの 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 をテストします
タイムフレームのサイズが変更されずに維持される場合、両方の時間で測定されたファンドの数が直線的に増加します
しかし、時間枠が 2 倍になると、2 番目の方法には 2 倍の時間がかかります
これは、@citaret の最大メソッド複雑度が O(n * timeframe)
であることを意味します。もう 1 つの点は、これら 2 つの方法の結果が同じではない場合があるということです。質問者が方法を持っていれば、その正しさを検証できます。
私が見つけた答えは正しいようですが、間違っている場合は修正してください。ありがとうございます。
より多くの人がこの問題について話し合うことを歓迎します。
私が回答した質問: Python-QA
高洛峰2017-04-18 09:23:33
データがなく、適切なプロファイルもありません。他の人がより良い解決策を持っているかどうかを確認するために、まずバージョンを提供してみましょう。
リーリー
伊谢尔伦2017-04-18 09:23:33
@dokelung は、合計 27505 個の要素を含むリスト (630,000 行の単一ログ ファイルから抽出され、複数のソース IP から集約) を使用してテストしました。私の当初の時間は 16.544873371035163 秒でした。効率は大幅に向上しましたが、それでも数秒ですが、これは 1 日あたり 1 つのファイルにすぎません。同時に、より深刻な効率の問題は、実際には関数内の要件を満たすログ行の抽出であることがわかりました。ご回答とご参加ありがとうございました。