What is the point of follow up "If this function is called many times, how would you optimize it"?


  • 1
    G

    Besides the discussion whether it's meaningful or not,
    is there any programming room to "optimize" such a problem?

    Caching the result of last call of reverse(n) to prepare the same call of reverse(n) to be called again?

    Forgive me if the question is dumb. But please detail the answer.

    Thanks.


  • 0
    D

    I use this way for optimization. It should be faster if called many many times, but the result on leetcode is almost the same as straight forward one.
    The idea is to use a 256-entry (8 bits) lookup table, which is generated by other means and copied.
    Then we check the lookup table four times to get the result.

    class Solution:
        def __init__(self):
            # lookup table
            self.table = [0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240, 8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248, 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244, 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252, 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50, 178, 114, 242, 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250, 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246, 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254, 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81, 209, 49, 177, 113, 241, 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249, 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245, 13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253, 3, 131, 67, 195, 35, 163, 99, 227, 19, 147, 83, 211, 51, 179, 115, 243, 11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251, 7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247, 15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255]
    
        # @param n, an integer
        # @return an integer
        def reverseBits(self, n):
            # use lookup table to reverse
            result = self.table[n & 0xff]
            for _ in range(3):
                result <<= 8
                n >>= 8
                result += self.table[n & 0xff]
            return result
    

Log in to reply
 

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