> def ngrams(iterable, n=2):
> if n < 1:
> raise ValueError
> t = tee(iterable, n)
> for i, x in enumerate(t):
> for j in range(i):
> next(x, None)
> return zip(*t)
def myngrams(iterable, n=2):
t = list(tee(iterable, 1))
for _ in range(n - 1):
t.extend(tee(t.pop()))
next(t[-1], None)
return zip(*t)
complexity wise it's O(N), but space complexity is O(N**2) to execute
this function,
to consume the output i.e completely iterate over zip object, the time
complexity is obviously O(N*M), and but space complexity is just
O(N*N).
---------------------------------------------------------------
In [1]: %paste
def ngrams(iterable, n=2):
if n < 1:
raise ValueError
t = tee(iterable, n)
for i, x in enumerate(t):
for j in range(i):
next(x, None)
return zip(*t)
## -- End pasted text --
In [2]: %paste
def myngrams(iterable, n=2):
t = list(tee(iterable, 1))
for _ in range(n - 1):
t.extend(tee(t.pop()))
next(t[-1], None)
return zip(*t)
## -- End pasted text --
In [3]: from itertools import *
In [4]: %timeit ngrams(range(1000), n=500)
100 loops, best of 3: 17.3 ms per loop
In [5]: %timeit myngrams(range(1000), n=500)
1000 loops, best of 3: 469 µs per loop
In [6]: %timeit list(ngrams(range(1000), n=500))
10 loops, best of 3: 21.2 ms per loop
In [7]: %timeit list(myngrams(range(1000), n=500))
100 loops, best of 3: 4.41 ms per loop
In [8]: %timeit ngrams(range(1000), n=100)
1000 loops, best of 3: 722 µs per loop
In [9]: %timeit myngrams(range(1000), n=100)
10000 loops, best of 3: 94.9 µs per loop
In [10]: %timeit list(ngrams(range(1000), n=100))
100 loops, best of 3: 2.09 ms per loop
In [11]: %timeit list(myngrams(range(1000), n=100))
1000 loops, best of 3: 1.46 ms per loop
In [12]:
-----------------------------------------------------------
Regards
Srinivas Devaki
Senior (4th year) student at Indian Institute of Technology (ISM), Dhanbad
Computer Science and Engineering Department
phone: +91 9491 383 249
telegram: @eightnoteight
--
https://mail.python.org/mailman/listinfo/python-list
