] Binary search question
"Emile van Sebille" wrote
BIG SNIP
And even at 1000 entries, the list creation slowed right
down - about 10 seconds, but the searches even for "-5" were
still around a second.
So 'in' looks pretty effective t
hon.org
>> Subject: Re: [Tutor] Binary search question
>>
>> "Emile van Sebille" wrote
>>
>>>BIG SNIP
>>
>> And even at 1000 entries, the list creation slowed right
>> down - about 10 seconds, but the searches even for "-5&q
On Sat, Apr 24, 2010 at 10:48 AM, Alan Gauld wrote:
>
> "Steven D'Aprano" wrote
>
>>> Interestingly on my PC with Python 3.1:
>>> >>> data = list(range(1000))
>>> >>> 999 in data
>>>
>>> takes an apparently constant, sub second time.
>>
>> With respect Alan, timing operations by eye is pr
> -Original Message-
> From: tutor-bounces+bermanrl=cfl.rr@python.org [mailto:tutor-
> bounces+bermanrl=cfl.rr@python.org] On Behalf Of Alan Gauld
> Sent: Friday, April 23, 2010 7:41 PM
> To: tutor@python.org
> Subject: Re: [Tutor] Binary search question
>
"Steven D'Aprano" wrote
Interestingly on my PC with Python 3.1:
>>> data = list(range(1000))
>>> 999 in data
takes an apparently constant, sub second time.
With respect Alan, timing operations by eye is pretty lame, what did you
do, count your heartbeats? :)
Sure, but I was surpri
On Sat, 24 Apr 2010 10:37:15 am Steven D'Aprano wrote:
> For the record, here's some timing benchmarks to see how badly it
> turned out:
[...]
> 0.0346097946167
> 0.461233854294
> 3.04955101013
> 5.70547604561
>
> For comparison, here's the timing on a plain binary search:
Oops, I hit send too soo
On Sat, 24 Apr 2010 09:41:05 am Alan Gauld wrote:
> "Emile van Sebille" wrote
>
> >> For completeness sake, on a 1 item list, using the in operator
> >> takes *in the worst case* around 7 seconds.
> >
> > Well on my system checking for the last element of a 100k item list
> > returns true almo
On Sat, 24 Apr 2010 09:11:21 am Robert Berman wrote:
> Wow. I feel I have just been b…h slapped across the face.
There's no need to be so sensitive.
> I think
> Hugo’s test results pretty much confirmed ‘in’ is not the way to go
If that is the *only* thing you have learned from this email threa
"Emile van Sebille" wrote
For completeness sake, on a 1 item list, using the in operator
takes *in the worst case* around 7 seconds.
Well on my system checking for the last element of a 100k item list
returns true almost upon hitting the enter key. Surely 7 seconds for a
list 1/10th the
"Robert Berman" wrote
But, even though my years of experience using Python is less than 4 I would be
reluctant to use 'in' just based on what I have been reading from those who
took the time to answer my post. Just my $0.02 worth.
It depends, if you are transmitting the data across a slow ne
On Sat, 24 Apr 2010 07:21:13 am Alan Gauld wrote:
> "Emile van Sebille" wrote
>
> > It's expensive enough that for a list this size I'd convert it to a
> > dict and use in on that. eg,
> >
> > a = range(10)
> > d = dict(zip(a,a))
>
> Surely that would depend on how often you do the search?
>
From: tutor-bounces+bermanrl=cfl.rr@python.org
[mailto:tutor-bounces+bermanrl=cfl.rr@python.org] On Behalf Of Ricardo
Aráoz
Sent: Friday, April 23, 2010 6:33 PM
To: Hugo Arts
Cc: tutor@python.org; Emile van Sebille
Subject: Re: [Tutor] Binary search question
Hugo Arts wrote:
On Fri, Apr
> -Original Message-
> From: tutor-bounces+bermanrl=cfl.rr@python.org [mailto:tutor-
> bounces+bermanrl=cfl.rr@python.org] On Behalf Of Hugo Arts
> Sent: Friday, April 23, 2010 5:55 PM
> To: Emile van Sebille
> Cc: tutor@python.org
> Subject: Re: [Tutor] B
On 4/23/2010 2:55 PM Hugo Arts said...
For completeness sake, on a 1 item list, using the in operator
takes *in the worst case* around 7 seconds.
:)
Well on my system checking for the last element of a 100k item list
returns true almost upon hitting the enter key. Surely 7 seconds for a
Hugo Arts wrote:
> On Fri, Apr 23, 2010 at 11:33 PM, Emile van Sebille wrote:
>
>> On 4/23/2010 2:21 PM Alan Gauld said...
>>
>>> "Emile van Sebille" wrote
>>>
It's expensive enough that for a list this size I'd convert it to a
dict and use in on that. eg,
a = r
On Fri, Apr 23, 2010 at 11:33 PM, Emile van Sebille wrote:
> On 4/23/2010 2:21 PM Alan Gauld said...
>>
>> "Emile van Sebille" wrote
>>>
>>> It's expensive enough that for a list this size I'd convert it to a
>>> dict and use in on that. eg,
>>>
>>> a = range(10)
>>> d = dict(zip(a,a))
>>>
>>
On 4/23/2010 2:21 PM Alan Gauld said...
"Emile van Sebille" wrote
It's expensive enough that for a list this size I'd convert it to a
dict and use in on that. eg,
a = range(10)
d = dict(zip(a,a))
Surely that would depend on how often you do the search? If its a one
off occurence I'd ex
"Emile van Sebille" wrote
It's expensive enough that for a list this size I'd convert it to a dict
and use in on that. eg,
a = range(10)
d = dict(zip(a,a))
Surely that would depend on how often you do the search?
If its a one off occurence I'd expect the overhead of zipping
and co
"Hugo Arts" wrote
A binary search requires data to be sorted, but works in O(log n), so
It will always be faster than a naive linear search like the in
operator performs.
Being picky but 'in' could be faster if the item searched for happens
to be very near the front of the list. "Always" is
Thank you all for your ideas and suggestions. The detailed explanations were
most useful.
Robert Berman
What you don't see with your eyes, don't invent with your mouth.
___
Tutor maillist - Tutor@python.org
To unsubscribe or change subscript
On Fri, Apr 23, 2010 at 5:29 PM, Emile van Sebille wrote:
>
>
> It's expensive enough that for a list this size I'd convert it to a dict and
> use in on that. eg,
>
> a = range(10)
> d = dict(zip(a,a))
>
> 5 in d
>
you will want to nuance that statement just a little. If you're going
to
On 4/23/2010 7:05 AM Robert Berman said...
Hi,
Given a list, list1 having 100,000 non repeating, sorted integers , which of
the following methods is fastest to find an item fully understanding the item
may or may not be in the list: The binary search method which is the standard
search for such
On Fri, Apr 23, 2010 at 4:05 PM, Robert Berman wrote:
> Hi,
>
> Given a list, list1 having 100,000 non repeating, sorted integers , which of
> the following methods is fastest to find an item fully understanding the item
> may or may not be in the list: The binary search method which is the stand
Robert Berman wrote:
Hi,
Given a list, list1 having 100,000 non repeating, sorted integers , which of
the following methods is fastest to find an item fully understanding the item
may or may not be in the list: The binary search method which is the standard
search for such a small sample size,
Hi,
Given a list, list1 having 100,000 non repeating, sorted integers , which of
the following methods is fastest to find an item fully understanding the item
may or may not be in the list: The binary search method which is the standard
search for such a small sample size, or the more python type
25 matches
Mail list logo
