|
|
|
|
|
|
| Author |
Message |
Dan Bishop
*nix forums addict
Joined: 24 Feb 2005
Posts: 91
|
 Posted: Tue Jul 18, 2006 2:49 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Summercoolness@gmail.com wrote:
| Quote: | it seems that range() can be really slow:
....
if i in range (0, 10000):
|
This creates a 10,000-element list and sequentially searches it. Of
course that's gonna be slow. |
|
| Back to top |
|
 |
Leif K-Brooks
*nix forums Guru Wannabe
Joined: 22 Feb 2005
Posts: 132
|
| Posted: Tue Jul 18, 2006 2:59 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Summercoolness@gmail.com wrote:
| Quote: | or is there an alternative use of range() or something similar that can
be as fast?
|
You could use xrange:
leif@ubuntu:~$ python -m timeit -n10000 "1 in range(10000)"
10000 loops, best of 3: 260 usec per loop
leif@ubuntu:~$ python -m timeit -n10000 "1 in xrange(10000)"
10000 loops, best of 3: 0.664 usec per loop |
|
| Back to top |
|
|
Dan Bishop
*nix forums addict
Joined: 24 Feb 2005
Posts: 91
|
| Posted: Tue Jul 18, 2006 3:09 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Leif K-Brooks wrote:
| Quote: | Summercoolness@gmail.com wrote:
or is there an alternative use of range() or something similar that can
be as fast?
You could use xrange:
leif@ubuntu:~$ python -m timeit -n10000 "1 in range(10000)"
10000 loops, best of 3: 260 usec per loop
leif@ubuntu:~$ python -m timeit -n10000 "1 in xrange(10000)"
10000 loops, best of 3: 0.664 usec per loop
|
That's only because you're choosing a number that's early in the list.
~$ python -m timeit -n10000 "1 in xrange(10000)"
10000 loops, best of 3: 1.22 usec per loop
~$ python -m timeit -n10000 "9999 in xrange(10000)"
10000 loops, best of 3: 1.24 msec per loop
That's *milliseconds*, not microseconds. |
|
| Back to top |
|
|
John Machin
*nix forums Guru
Joined: 19 Feb 2005
Posts: 608
|
| Posted: Tue Jul 18, 2006 3:09 am Post subject:
Re: range() is not the best way to check range?
|
|
|
On 18/07/2006 12:41 PM, Summercoolness@gmail.com wrote:
| Quote: | it seems that range() can be really slow:
the following program will run, and the last line shows how long it ran
for:
import time
startTime = time.time()
a = 1.0
for i in range(0, 30000):
if i in range (0, 10000):
a += 1
if not i % 1000: print i
print a, " ", round(time.time() - startTime, 1), "seconds"
---------------------------------
the last line of output is
---------------------------------
10001.0 22.8 seconds
so if i change the line
if i in range (0, 10000):
to
if i >= 0 and i < 10000:
the the last line is
10001.0 0.2 seconds
so approximately, the program ran 100 times faster!
or is there an alternative use of range() or something similar that can
be as fast?
|
Some things to try:
1a. Read what the manual has to say about the range() function ... what
does it produce?
1b. Read what the manual has to say about time.time() and time.clock().
Change over to using time.clock(). Change the round(...., 1) to (say) 4.
Alternatively, use something like this:
print "%.1f ... %.4f seconds" % (a, time.clock() - startTime)
1c. Repeat the two ways that you tried already.
2. First alternative:
Do this:
test_range = range(10000)
*once*, just after "a = 1.0".
and change your if test to
if i in test_range:
3. Now change that to:
test_range = set(range(10000))
4. Now forget about test_range, and change your if test to this:
if 0 <= i < 10000:
HTH,
John |
|
| Back to top |
|
|
Sreeram Kandallu
*nix forums addict
Joined: 02 Jun 2006
Posts: 58
|
| Posted: Tue Jul 18, 2006 3:24 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Summercoolness@gmail.com wrote:
| Quote: | so if i change the line
if i in range (0, 10000):
to
if i >= 0 and i < 10000:
[snip;]
is there an alternative use of range() or something similar that can
be as fast?
|
you've found that alternative yourself! just use the comparison operators...
in fact, you can write a little more compact as:
if 0 <= i < 10000 :
[sreeram;] |
|
| Back to top |
|
|
Grant Edwards
*nix forums Guru
Joined: 21 Feb 2005
Posts: 1227
|
| Posted: Tue Jul 18, 2006 4:13 am Post subject:
Re: range() is not the best way to check range?
|
|
|
On 2006-07-18, Summercoolness@gmail.com <Summercoolness@gmail.com> wrote:
| Quote: | it seems that range() can be really slow:
the following program will run, and the last line shows how long it ran
for:
import time
startTime = time.time()
a = 1.0
for i in range(0, 30000):
if i in range (0, 10000):
a += 1
if not i % 1000: print i
print a, " ", round(time.time() - startTime, 1), "seconds"
|
| Quote: | or is there an alternative use of range() or something similar that can
be as fast?
|
Creating and then searching a 10,000 element list to see if a
number is between two other numbers is insane.
Using xrange as somebody else suggested is also insane.
If you want to know if a number is between two other numders,
for pete's sake use the comparison operator like god intended.
if 0 <= i <= 10000:
--
Grant Edwards grante Yow! ANN JILLIAN'S HAIR
at makes LONI ANDERSON'S
visi.com HAIR look like RICARDO
MONTALBAN'S HAIR! |
|
| Back to top |
|
|
tactics40@gmail.com
*nix forums beginner
Joined: 13 Jun 2006
Posts: 33
|
| Posted: Tue Jul 18, 2006 4:56 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Grant Edwards wrote:
| Quote: | for pete's sake use the comparison operator like god intended.
if 0 <= i <= 10000:
|
I'm assuming you used Python's compound comparison as opposed to the
C-style of and'ing two comparisons together to emphasize the fact it is
god's chosen way of doing this  |
|
| Back to top |
|
|
Marc 'BlackJack' Rintsch
*nix forums Guru Wannabe
Joined: 03 Mar 2005
Posts: 146
|
| Posted: Tue Jul 18, 2006 7:27 am Post subject:
Re: range() is not the best way to check range?
|
|
|
In <1153198570.592653.203310@h48g2000cwc.googlegroups.com>, tac-tics
wrote:
| Quote: | Grant Edwards wrote:
for pete's sake use the comparison operator like god intended.
if 0 <= i <= 10000:
I'm assuming you used Python's compound comparison as opposed to the
C-style of and'ing two comparisons together to emphasize the fact it is
god's chosen way of doing this
|
Pete doesn't like to be called god in public. ;-)
Ciao,
Marc 'BlackJack' Rintsch |
|
| Back to top |
|
|
Nick Craig-Wood
*nix forums Guru Wannabe
Joined: 23 Feb 2005
Posts: 104
|
| Posted: Tue Jul 18, 2006 8:30 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Grant Edwards <grante@visi.com> wrote:
| Quote: | Creating and then searching a 10,000 element list to see if a
number is between two other numbers is insane.
Using xrange as somebody else suggested is also insane.
|
Aye to both
| Quote: | If you want to know if a number is between two other numders,
for pete's sake use the comparison operator like god intended.
if 0 <= i <= 10000:
|
Sets are pretty fast too, and have the advantage of flexibility in
that you can put any numbers in you like
$ python2.4 -m timeit -s 's=range(0,10000); i=5000' 'i in s'
1000 loops, best of 3: 228 usec per loop
$ python2.4 -m timeit -s 's=set(range(0,10000)); i=5000' 'i in s'
1000000 loops, best of 3: 0.312 usec per loop
$ python2.4 -m timeit -s 'i=5000' '0 <= i < 10000'
1000000 loops, best of 3: 0.289 usec per loop
The below prints
range) That took 21.512 seconds: result 10001.0
set) That took 0.023 seconds: result 10001.0
comparison) That took 0.024 seconds: result 10001.0
.............................................................
import time
start = time.time()
a = 1.0
for i in range(0, 30000):
if i in range(0, 10000):
a += 1
dt = time.time() - start
print "range) That took %.3f seconds: result %s" % (dt, a)
start = time.time()
a = 1.0
mine = set(range(0, 10000))
for i in range(0, 30000):
if i in mine:
a += 1
dt = time.time() - start
print "set) That took %.3f seconds: result %s" % (dt, a)
start = time.time()
a = 1.0
mine = set(range(0, 10000))
for i in range(0, 30000):
if 0 <= i < 10000:
a += 1
dt = time.time() - start
print "comparison) That took %.3f seconds: result %s" % (dt, a)
--
Nick Craig-Wood <nick@craig-wood.com> -- http://www.craig-wood.com/nick |
|
| Back to top |
|
|
Paul Boddie
*nix forums Guru Wannabe
Joined: 20 Feb 2005
Posts: 222
|
| Posted: Tue Jul 18, 2006 9:22 am Post subject:
Re: range() is not the best way to check range?
|
|
|
John Machin wrote:
[...]
| Quote: | Some things to try:
1a. Read what the manual has to say about the range() function ... what
does it produce?
|
Indeed. Still, the addition of a __contains__ method to range (and
xrange) would permit acceptable performance for the code given. Perhaps
this is a convenience worth considering for future Python releases.
Paul |
|
| Back to top |
|
|
Andy Dingley
*nix forums beginner
Joined: 19 Mar 2006
Posts: 11
|
| Posted: Tue Jul 18, 2006 10:54 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Summercoolness@gmail.com wrote:
| Quote: | it seems that range() can be really slow:
if i in range (0, 10000):
|
RTFM on range()
You're completely mis-using it here, using it with an if ... in ...
test. The purpose of range() in Python is as loop control, not
comparisons! It's not a SQL BETWEEN statement.
Although you _can_ do this (you've done it!) you've also found that
it's slow. Many people would argue that even using range() for loop
control is unusably slow. |
|
| Back to top |
|
|
Leif K-Brooks
*nix forums Guru Wannabe
Joined: 22 Feb 2005
Posts: 132
|
| Posted: Tue Jul 18, 2006 11:09 am Post subject:
Re: range() is not the best way to check range?
|
|
|
Grant Edwards wrote:
| Quote: | Using xrange as somebody else suggested is also insane.
|
Sorry about that, I somehow got the misguided notion that xrange defines
its own __contains__, so that it would be about the same speed as using
comparison operators directly. I figured the OP might have a better
reason for wanting to use range() than his post mentioned -- perhaps the
range to check was being passed from a function, and it would be easier
to pass an object than a tuple of lower and upper bound -- but since
xrange does looping for a membership test, my suggestion was indeed insane. |
|
| Back to top |
|
|
John Machin
*nix forums Guru
Joined: 19 Feb 2005
Posts: 608
|
| Posted: Tue Jul 18, 2006 11:55 am Post subject:
Re: range() is not the best way to check range?
|
|
|
On 18/07/2006 7:22 PM, Paul Boddie wrote:
| Quote: | John Machin wrote:
On 18/07/2006 12:41 PM, Summercoolness@gmail.com wrote:
it seems that range() can be really slow:
[...]
Some things to try:
1a. Read what the manual has to say about the range() function ... what
does it produce?
Indeed. Still, the addition of a __contains__ method to range (and
xrange) would permit acceptable performance for the code given. Perhaps
this is a convenience worth considering for future Python releases.
|
range() and xrange() are functions. You are suggesting that 2
*functions* should acquire a __contains__ method each? I trust not.
Perhaps you meant that the acquisitors should be the objects that those
functions return.
range() returns a list. Lists already have a __contains__ method. It's
been getting a fair old exercising in the last few hours, but here we go
again:
| Quote: | python -mtimeit -s"x=range(30000)" "x.__contains__(40000)"
1000 loops, best of 3: 1.09 msec per loop |
| Quote: | python -mtimeit -s"x=range(30000)" "40000 in x"
1000 loops, best of 3: 1.09 msec per loop |
| Quote: | python -mtimeit -s"x=range(30000)" "x.__contains__(1)"
1000000 loops, best of 3: 0.434 usec per loop |
| Quote: | python -mtimeit -s"x=range(30000)" "1 in x"
1000000 loops, best of 3: 0.137 usec per loop |
A __contains__ method for xrange objects? The case of x in xrange(lo,
hi) is met by lo <= x < hi. IMHO, anyone who wants x in xrange(lo, hi,
step) should be encouraged to do the necessary algebra themselves; I
wouldn't suggest that any core dev time be wasted on implementing such
folderol.
In any case, isn't the *whole* xrange gizmoid on GvR's I-wish-I-hadn't list?
Cheers,
John |
|
| Back to top |
|
|
Paul Boddie
*nix forums Guru Wannabe
Joined: 20 Feb 2005
Posts: 222
|
| Posted: Tue Jul 18, 2006 12:24 pm Post subject:
Re: range() is not the best way to check range?
|
|
|
John Machin wrote:
| Quote: |
range() and xrange() are functions. You are suggesting that 2
*functions* should acquire a __contains__ method each? I trust not.
|
Well, range is a function in the current implementation, although its
usage is similar to that one would get if it were a class, particularly
a subclass of list or one providing a list-style interface. With such a
class, you could provide a __contains__ method which could answer the
question of what the range contains based on the semantics guaranteed
by a range (in contrast to a normal list).
| Quote: | Perhaps you meant that the acquisitors should be the objects that those
functions return.
|
The whole point was to avoid expanding the range into a list.
[...]
| Quote: | A __contains__ method for xrange objects? The case of x in xrange(lo,
hi) is met by lo <= x < hi. IMHO, anyone who wants x in xrange(lo, hi,
step) should be encouraged to do the necessary algebra themselves; I
wouldn't suggest that any core dev time be wasted on implementing such
folderol.
|
Sure, you could always implement your own class to behave like an
existing range and to implement the efficient semantics proposed above.
| Quote: | In any case, isn't the *whole* xrange gizmoid on GvR's I-wish-I-hadn't list?
|
Yes, he wants range to return an iterator, just like xrange more or
less does now. Given that xrange objects support __getitem__, unlike a
lot of other iterators (and, of course, generators), adding
__contains__ wouldn't be much of a hardship. Certainly, compared to
other notational conveniences bounced around on the various development
lists, this one would probably provide an order of magnitude
improvement on the usual bang per buck development ratio.
Paul |
|
| Back to top |
|
|
Stefan Behnel
*nix forums addict
Joined: 18 Apr 2005
Posts: 81
|
| Posted: Tue Jul 18, 2006 12:42 pm Post subject:
Re: range() is not the best way to check range?
|
|
|
Andy Dingley wrote:
| Quote: | The purpose of range() in Python is as loop control,
|
No, the purpose of range() is to create a list, as the docs state.
http://docs.python.org/lib/built-in-funcs.html
"""
range(...) - This is a versatile function to create lists containing
arithmetic progressions.
"""
Stefan |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Sat Nov 22, 2008 12:01 am | All times are GMT
|
|
Computers 2007 | Loans | Outsourcing | Web Games | Personal Loans
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
|
|
Other DeniX Solutions sites:
Unix/Linux blog |
electronics forum |
medicine forum |
science forum |
|
|
Privacy Policy
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Programming
»
python
