Speeding up the implementation of Stochastic Gradient Ascent in Python

[Chris Angelico]

On Thu, Jan 18, 2018 at 7:19 AM, Ned Batchelder <ned at nedbatchelder.com> wrote:
> On 1/17/18 2:45 PM, Chris Angelico wrote:
>>
>> On Thu, Jan 18, 2018 at 6:28 AM, Ned Batchelder <ned at nedbatchelder.com>
>> wrote:
>>>
>>> You'll have to replace random.choice() with
>>> random.choice(list(...)), since you can't random.choice from a set.
>>>
>> Side point: why can't you? You can random.sample from a set, but
>> random.choice requires a sequence. It seems perfectly sane to ask for
>> a random element from a set.
>>
>>
>
> You'd have to ask Raymond Hettinger I guess.  random.sample works on a set
> because it starts with:
>
>         if isinstance(population, _Set):
>             population = tuple(population)
>
> So sample() is willing to listify (tuplify?) your set for you, but choice()
> is not.
>

Ah. So it's just as inefficient. (I should have looked.)

So I guess what we really need is some lower-level support. There's no
way in Python to pick a random element from a set in O(1) time. It
could be done in O(n) time and O(1) space by iterating through the set
until you hit the chosen random index, but you can't just say "grab me
one of those".

ChrisA