1-line Python O(N^2)


  • 4
    V

    Update:

    1-line solution as suggested by @StefanPochmann

    def numberOfBoomerangs(self, points):
        return sum(
            n * (n - 1)
            for x1, y1 in points
            for n in collections.Counter(
                (x1 - x2) ** 2 + (y1 - y2) ** 2
                for x2, y2 in points).values())
    

    Old:

    Just for fun:

    def numberOfBoomerangs(self, points):
        dist = lambda (x1, y1, x2, y2): (x1 - x2) ** 2 + (y1 - y2) ** 2
        
        return sum(
            n * (n - 1)
            for x1, y1 in points
            for n in collections.Counter(dist((x1, y1, x2, y2)) for x2, y2 in points).values())
    

    Here is a more clear version:

    def numberOfBoomrangs(self, points):
        nums = 0
        for x1, y1 in points:
            distance = collections.defaultdict(int)
            for x2, y2 in points:
                dx = abs(x2 - x1)
                dy = abs(y2 - y1)
                d = dx * dx + dy * dy
                distance[d] += 1
    
            nums += sum(n * (n-1) for n in distance.values())
        return nums
    

  • 0
    T

    @voiceup one mistake line: dy = abs(y2 - x1)


  • 0
    V

    @tdd1000

    Thank you for the catch! Just fixed it.


  • 0

    Could make it a one-liner by ditching dist, it doesn't help much anyway. And no point using abs before squaring.

    def numberOfBoomerangs(self, points):
        return sum(
            n * (n - 1)
            for x0, y0 in points
            for n in collections.Counter((x - x0)**2 + (y - y0)**2
                                         for x, y in points).values())

  • 0
    V

    @StefanPochmann
    Yeah you are right.

    Initially I was thinking using something like x * x + y * y to achieve better performance than x ** 2 + y ** 2. Although they are virtually the same thing, I believe in the benchmark the first expression is considerably faster in Python. I don't know how I got so dumb and ended up writing the lambda expression in that way (abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)...

    Another consideration is to make the second line shorter and arguably more readable.

    In retrospection, I think I actually like your 1-line version, and will edit my post..


  • 0

    @voiceup said in 1-line Python O(N^2):

    I believe in the benchmark the first expression is considerably faster in Python

    What benchmark? You mean submitting here? That varies a lot even with the exact same code. How much faster was it, in how many attempts?

    I just tried this, where they look about the same:

    >>> timeit(lambda: Counter(x*x for x in xrange(10000)), number=1000)
    3.3120313425821735
    >>> timeit(lambda: Counter(x**2 for x in xrange(10000)), number=1000)
    3.3315958179443044
    

    Also, the stuff other than the multiplication is responsible for most of the time. And even the pure thing looks pretty much the same:

    >>> timeit('x * x', 'x = 42', number=10**7)
    0.35808611698361403
    >>> timeit('x**2', 'x = 42', number=10**7)
    0.3640849920255249
    

  • 0
    V

    @StefanPochmann

    Interesting, here is what I got:

    # Python 2.7.12
    >>> timeit('x * x', 'x = 42', number=10**7)
    0.4510629177093506
    >>> timeit('x ** 2', 'x = 42', number=10**7)
    0.7093241214752197
    
    
    # Python 3.5.2
    >>> timeit('x * x', 'x = 42', number=10**7)
    0.5049805610033218
    >>> timeit('x ** 2', 'x = 42', number=10**7)
    3.6540668540110346
    

    It's very surprising to me that:

    1. python2 is faster than python3 in this operation consistently
    2. my benchmark result is quite different from yours
    3. python3 seems to do worse optimization on exponential operations.

  • 0

    @voiceup Quite interesting, yes, especially how very slow Python 3 is with x ** 2. My above tests were with Python 2 because that's what LeetCode uses. Now I ran some more tests:

    Python 2.7.11:

    >>> [int(100 * timeit('x * x', 'x = 42', number=10**7)) for _ in range(10)]
    [36, 35, 35, 36, 38, 36, 35, 35, 35, 35]
    >>> [int(100 * timeit('x**2', 'x = 42', number=10**7)) for _ in range(10)]
    [36, 35, 37, 36, 35, 36, 36, 35, 35, 36]
    

    Python 3.5.1:

    >>> [int(100 * timeit('x * x', 'x = 42', number=10**7)) for _ in range(10)]
    [48, 48, 48, 47, 48, 48, 48, 48, 48, 50]
    >>> [int(100 * timeit('x**2', 'x = 42', number=10**7)) for _ in range(10)]
    [194, 190, 196, 184, 198, 183, 194, 187, 196, 188]
    

  • 0
    M

    @StefanPochmann Thanks for your help, and I'm a beginner of Python. I do not understand how to use "for in" like this. Could you pls explain the syntax.
    PS:I know use "for...in.." like this:
    def numberOfBoomerangs(self, points):
    return sum([sum(n*(n-1) for n in collections.Counter([(x1-x2)**2 + (y1-y2)**2
    for x2, y2 in points]).values())
    for x1, y1 in points])


Log in to reply
 

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