Pythonリストで日付を数える最適な/最速の方法

Question

私は日付のリストを持っており、目標は各日付の出現を数えることです元のリストに表示される順序を維持しながら。次の例を考えてみましょう：

リストonly_datesは次のようになります。

[datetime.date(2017, 3, 9), datetime.date(2017, 3, 10), datetime.date(2017, 3, 10), datetime.date(2017, 3, 11)] 

私はgroupbyを使用しようとしています：

import itertools 
day_wise_counts = [(k, len(list(g))) for k, g in itertools.groupby(only_dates)] 
print(str(day_wise_counts)) 

これは

[(datetime.date(2017, 3, 10), 1), (datetime.date(2017, 3, 9), 1), (datetime.date(2017, 3, 10), 1), (datetime.date(2017, 3, 11), 1)] 

を印刷し、私はこのことを理解しています最終的に各日付オブジェクトが異なるものとして扱われているために起こります1つはグループ化します。

私は、出力があることを期待していた：私は必ずしもタプルのリストを捜しているわけではない

[(datetime.date(2017, 3, 9), 1), (datetime.date(2017, 3, 10), 2), (datetime.date(2017, 3, 11), 1)] 

。元の日付の順序が維持されている限り、辞書の出力でも十分です。 （OrderedDict多分）。

どうすればこの問題を解決できますか？

更新：複数のアプローチがあり、すべてうまくいく可能性があります。しかし、私は、大量のデータに対してこの操作を行うつもりであることを述べておきたいと思います。あなたの解決策が実行時間の面で最適なものであれば、それは素晴らしいことでしょう。可能であれば、回答/コメントを編集してください。

更新2：データサイズは、100万行にもなります。

Answer 1

確かに、あなたはOrderedDictを使用することができます。

from collections import OrderedDict 
import datetime 

inp = [datetime.date(2017, 3, 9), datetime.date(2017, 3, 10), 
     datetime.date(2017, 3, 10), datetime.date(2017, 3, 11)] 

odct = OrderedDict() 
for item in inp: 
    try: 
     odct[item] += 1 
    except KeyError: 
     odct[item] = 1 

print(odct) 

印刷した：

OrderedDict([(datetime.date(2017, 3, 9), 1), 
      (datetime.date(2017, 3, 10), 2), 
      (datetime.date(2017, 3, 11), 1)]) 

をあなたはまた、彼らがしているので、ここで、タイミングを求めて：

from collections import OrderedDict, Counter 
import datetime 
import random 

# Functions 

def ordereddict(inp): 
    odct = OrderedDict() 
    for item in inp: 
     try: 
      odct[item] += 1 
     except KeyError: 
      odct[item] = 1 
    return odct 


def dawg(inp): 
    cnts=Counter(inp) 
    seen=set() 
    return [(e, cnts[e]) for e in inp if not (e in seen or seen.add(e))] 


def chris1(inp): 
    return [(item, inp.count(item)) for item in list(OrderedDict.fromkeys(inp))] 


def chris2(inp): 
    c = Counter(inp) 
    return [(item,c[item]) for item in list(OrderedDict.fromkeys(inp))] 


# Taken from answer: https://stackoverflow.com/a/23747652/5393381 
class OrderedCounter(Counter, OrderedDict): 
    'Counter that remembers the order elements are first encountered' 

    def __repr__(self): 
     return '%s(%r)' % (self.__class__.__name__, OrderedDict(self)) 

    def __reduce__(self): 
     return self.__class__, (OrderedDict(self),) 


# Timing setup 
timings = {ordereddict: [], dawg: [], chris1: [], chris2: [], OrderedCounter: []} 
sizes = [2**i for i in range(1, 20)] 

# Timing 
for size in sizes: 
    func_input = [datetime.date(2017, random.randint(1, 12), random.randint(1, 28)) for _ in range(size)] 
    for func in timings: 
     res = %timeit -o func(func_input) # if you use IPython, otherwise use the "timeit" module 
     timings[func].append(res) 

とプロット：

%matplotlib notebook 

import matplotlib.pyplot as plt 
import numpy as np 

fig = plt.figure(1) 
ax = plt.subplot(111) 

for func in timings: 
    ax.plot([2**i for i in range(1, 20)], 
      [time.best for time in timings[func]], 
      label=str(func.__name__)) 
ax.set_xscale('log') 
ax.set_yscale('log') 
ax.set_xlabel('size') 
ax.set_ylabel('time [seconds]') 
ax.grid(which='both') 
ax.legend() 
plt.tight_layout() 

私はPython-3.5でタイムアウトしました。 Counterを使用するアプローチは、python-2.x（Python-3.xに最適化されたCounter）で少し遅くなる可能性があります。また、chris2とdawgのアプローチは（ほとんどの時間差がないため）互いにオーバーラップします。

@Chris_RandsとOrderedCounterの最初のアプローチを除いて、アプローチは非常によく似ており、主にリストの重複数に依存します。

これは主に1.5-2の違いです。私は3つの「高速」アプローチの間に100万アイテムのリアルタイムの差異を見つけることができませんでした。あなたがユニークなのOrderedDict由来リストを反復処理AAリスト内包でlist.count()を使用することができ

Answer 2

は、日付を命じた：

import datetime 
from collections import OrderedDict 

lst = [datetime.date(2017, 3, 9), datetime.date(2017, 3, 10), datetime.date(2017, 3, 10), datetime.date(2017, 3, 11)] 

[(item,lst.count(item)) for item in list(OrderedDict.fromkeys(lst))] 
# [(datetime.date(2017, 3, 9), 1), (datetime.date(2017, 3, 10), 2), (datetime.date(2017, 3, 11), 1)] 

または同様にcollections.Counter代わりのlist.countを使用して：

from collections import Counter 

c = Counter(lst) 

[(item,c[item]) for item in list(OrderedDict.fromkeys(lst))] 
# [(datetime.date(2017, 3, 9), 1), (datetime.date(2017, 3, 10), 2), (datetime.date(2017, 3, 11), 1)] 

または使用をOrderedCounter。

編集：優良ベンチマーク@MSeifertを参照してください。

Answer 3

カウンタを使用してuniqify元のリストをカウントしてカウントを追加しながら順序を維持することができます。

考える：

>>> dates=[datetime.date(2017, 3, 9), datetime.date(2017, 3, 10), datetime.date(2017, 3, 10), datetime.date(2017, 3, 11)] 

あなたが行うことができます。

from collections import Counter 

cnts=Counter(dates) 
seen=set() 
>>> [(e, cnts[e]) for e in dates if not (e in seen or seen.add(e))] 
[(datetime.date(2017, 3, 9), 1), (datetime.date(2017, 3, 10), 2), (datetime.date(2017, 3, 11), 1)] 

---

更新

をあなたはまた、カウンターを並べ替えることができ、元のリストの順にキーを使って、そのリストの日付（X）の最初のエントリのインデックスを取得する関数：

sorted([(k,v) for k,v in Counter(dates).items()], key=lambda t: dates.index(t[0])) 

（この速度は、あなたのリストがどのように注文したか、順不同に相関している...）

---

誰かがはtimeitを言いました！ （Pythonの2.7上の）

from __future__ import print_function 
import datetime 
from collections import Counter 
from collections import OrderedDict 

def dawg1(dates): 
    seen=set() 
    cnts=Counter(dates) 
    return [(e, cnts[e]) for e in dates if not (e in seen or seen.add(e))] 

def od_(dates):  
    odct = OrderedDict() 
    for item in dates: 
     try: 
      odct[item] += 1 
     except KeyError: 
      odct[item] = 1 
    return odct 

def lc_(lst): 
    return [(item,lst.count(item)) for item in list(OrderedDict.fromkeys(lst))]  

def dawg2(dates): 
    return sorted([(k,v) for k,v in Counter(dates).items()], key=lambda t: dates.index(t[0]))  

if __name__=='__main__': 
    import timeit 
    dates=[datetime.date(2017, 3, 9), datetime.date(2017, 3, 10), datetime.date(2017, 3, 10), datetime.date(2017, 3, 11)]*100000 
    for f in (dawg, od_, lc_,sort_): 
     print(" {:^10s}{:.4f} secs {}".format(f.__name__, timeit.timeit("f(dates)", setup="from __main__ import f, dates", number=100),f(dates))) 

プリント：

dawg1 10.7253 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 
    od_ 21.8186 secs OrderedDict([(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)]) 
    lc_ 17.0879 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 
dawg2 8.6058 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)]0000)] 

PyPy：

dawg1 7.1483 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 
    od_ 4.7551 secs OrderedDict([(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)]) 
    lc_ 27.8438 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 
dawg2 4.7673 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 

パイソン3.6ここ

が大きく、例えば（40万日付）といくつかのタイミングは次のとおりです。

dawg1 3.4944 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 
    od_ 4.6541 secs OrderedDict([(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)]) 
    lc_ 2.7440 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 
dawg2 2.1330 secs [(datetime.date(2017, 3, 9), 100000), (datetime.date(2017, 3, 10), 200000), (datetime.date(2017, 3, 11), 100000)] 

ベスト。