Best search algorithm to find condition within a range
Dave Angel
davea at davea.name
Tue Apr 7 20:38:15 EDT 2015
On 04/07/2015 06:35 PM, jonas.thornvall at gmail.com wrote:
> Den tisdag 7 april 2015 kl. 21:27:20 UTC+2 skrev Ben Bacarisse:
>> Ian Kelly <ian.g.kelly at gmail.com> writes:
>>
>>> On Tue, Apr 7, 2015 at 12:55 PM, Terry Reedy <tjreedy at udel.edu> wrote:
>>>> On 4/7/2015 1:44 PM, Ian Kelly wrote:
>>>>
>>>>>>>> def to_base(number, base):
>>>>>
>>>>> ... digits = []
>>>>> ... while number > 0:
>>>>> ... digits.append(number % base)
>>>>> ... number //= base
>>>>> ... return digits or [0]
>>>>> ...
>>>>>>>>
>>>>>>>>
>>>>>>>> to_base(2932903594368438384328325832983294832483258958495845849584958458435439543858588435856958650865490,
>>>>>>>> 429496729)
>>>>>
>>>>> [27626525, 286159541, 134919277, 305018215, 329341598, 48181777,
>>>>> 79384857, 112868646, 221068759, 70871527, 416507001, 31]
>>>>> About 15 microseconds.
>>>>
>>>>
>>>> % and probably // call divmod internally and toss one of the results.
>>>> Slightly faster (5.7 versus 6.1 microseconds on my machine) is
>>>
>>> Not on my box.
>>>
>>> $ python3 -m timeit -s "n = 1000000; x = 42" "n % x; n // x"
>>> 10000000 loops, best of 3: 0.105 usec per loop
>>> $ python3 -m timeit -s "n = 1000000; x = 42" "divmod(n,x)"
>>> 10000000 loops, best of 3: 0.124 usec per loop
>>
>> I get similar results, but the times switch over when n is large enough
>> to become a bignum.
>>
>> --
>> Ben.
>
> I am not sure you guys realised, that althoug the size of the factors to muliply expands according to base^(exp+1) for each digitplace the number of comparissons needed to reach the digit place (multiple of base^exp+1) is constant with my approach/method.
>
Baloney.
But even if it were true, a search is slower than a divide.
--
DaveA
More information about the Python-list
mailing list