Please help explain the experienced speed diff


  • 0
    G

    Hi there,
    I have run into TLE with my first solution that used a set for memorizing ugly numbers we have seen:
    '''
    def mySuperUglyNumber(n, primes):
    uglies, h, haveSeen = [],[1], set()
    while len(uglies) < n:
    act = heapq.heappop(h)
    for p in primes:
    if act * p not in haveSeen:
    heapq.heappush(h, p * act)
    haveSeen.add(act * p)
    uglies.append(act)
    return uglies[n-1]
    '''
    Then I have come up with another approach that gets rid of the set and which was supposed to run a lot faster.
    '''
    def mySuperUglyNumber2(n, primes):
    uglies, h = [],[(1,1)]
    while True:
    act = heapq.heappop(h)
    for p in primes:
    if p >= act[1]:
    heapq.heappush(h, (p * act[0],p))
    uglies.append(act[0])
    if len(uglies) == n: return uglies[-1]
    '''
    It did solve more test cases. Nevertheless, when I compared the performance of the generator solution and the above two these seem to perform fairly close to one another (sometimes the second solution got worse running time).

    I would appreciate any insightful comment on what is really going on with this second solution.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.