在Python列表中计算日期的最优/最快方法

Question

在Python列表中计算日期的最优/最快方法

6

我有一个日期列表，目标是计算每个日期的出现次数同时保持它们在原始列表中的顺序。考虑以下例子：

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)]

我理解这是因为在分组时，每个日期对象最终被视为不同的对象。

我原本期望输出结果为：

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

我不一定需要一个元组列表。只要原始日期的顺序保持不变，字典输出也可以满足要求。（可能是OrderedDict）。如何实现这一点？更新：有可能会提出多种方法，而且都能很好地工作。但我应该提到，我将为大量数据执行此操作。因此，如果您的解决方案在运行时间方面最优，则会很好。如果可以，请相应地编辑您的答案/评论。更新2：数据大小可以达到100万行。

- Ravindra S

如果您正在使用Python-2.x，您可以查看此问题：https://dev59.com/uVsW5IYBdhLWcg3wDzrs，了解如何创建有序计数器。不幸的是，在Python-3.x中这种方法不再适用（除了3.6版本，其中`dict`默认保持其顺序）。 - MSeifert

如果你说“我将处理大量数据”，那么我们要处理的大小（以及大约重复的百分比）是多少？ - MSeifert

可能是重复的问题：如何获取项目计数字典但保持它们出现的顺序？ - Chris_Rands

@MSeifert对问题进行了更新。 - Ravindra S

@Chris_Rands 这并没有解决性能需求。 - Ravindra S

@PaleBlueDot 这仍然是一个重复的问题，但这里的答案更好。如果有必要，那个问题可以链接到这个问题上，我会让管理员来决定。 - Chris_Rands

3个回答

2

您可以使用list.count()方法，结合列表推导式遍历由有序唯一日期的OrderedDict派生的列表：

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的出色基准测试。

- Chris_Rands

看起来不错。+1 如果可以，请解决一下性能方面的问题。 - Ravindra S

2

您可以使用计数器来计算，然后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！

以下是一个更大的例子（400,000个日期）的计时：

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)))

Python 2.7 的输出结果：

 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)]

Python 3.6：

 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)]

最好的。

- dawg

看起来不错。请查看我关于性能的问题更新。+1 - Ravindra S

1

点赞是因为你在这个解决方案中付出了很多，但我认为使用sorted不好，因为它可能无法保留原始顺序。此外，你的基准测试非常有用，因为它探索了不同的Python版本，但MSeifert探索了更多的参数空间。 - Chris_Rands

@Chris_Rands：谢谢。sorted版本使用原始列表的索引，那么它如何不保留原始顺序呢？它将像使用任何其他方法一样可预测地保留顺序。 - dawg

@dawg 抱歉，我错过了你的自定义排序键！ - Chris_Rands

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MSeifert · Accepted Answer

确实，你可以使用一个 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://dev59.com/Nn_aa4cB1Zd3GeqP8dWK#23747652
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上可能会慢一些（Counter是为Python-3.x优化的）。此外，chris2和dawg方法互相重叠（因为它们之间几乎没有时间差异）。

因此，除了@Chris_Rands的第一种方法和OrderedCounter之外，这些方法表现非常相似，大多数取决于列表中重复项的数量。

这主要是1.5-2倍的差异。我在三种“快速”方法中找不到任何真正的1百万项之间的实时差异。