4
\$\begingroup\$

I need to count the number of ways to partition an array into two contiguous arrays such that those arrays contain exactly same set of items.

Suppose A = [4, 1, 1, 2, 4, 2, 4, 1]. If you pass this array to the function, it needs to return 2. (Those subarrays are [4, 1, 1, 2] & [4, 2, 4, 1] and [4, 1, 1, 2, 4] & [2, 4, 1].)

Suppose A = [1, 5, 1]. If you pass this array to the function, it needs to return 0.

My code given below. Is there any better way to do this?

def solve(A):    
    count = 0
    for i in range(1, len(A)-1/2):

        left = A[:i]
        right = A[i:]

        left[:i].sort()
        right[i:].sort()

        if set(left) == set(right):
            count += 1
    return count
\$\endgroup\$
  • 1
    \$\begingroup\$ Note that for each unique item, the leftmost occurrence needs to be in the left partition and the rightmost occurrence in the right partition. Therefore the rightmost left occurrence and leftmost right occurrence place bounds on the partition location; any location between these is permissible. \$\endgroup\$ – Ben Voigt Feb 8 '15 at 21:38
4
\$\begingroup\$

Your current approach is going to be very slow because you're slicing the each time and then that is followed by an unnecessary sort calls and ultimately you call set() on both of the lists.

Slicing a list is very slow, because it requires creating an array of new references(pointers) to the items of the original array. To fix that we can use collections.deque here, ie. start with two deques first. First one is going be a deque(say full_deque) of the list passed to the array and second one will be empty(say current_deque). And now during the loop we simply pop the leftmost item from the full_deque and append it to the current_deque, these are O(1) operations for a deque so we will save a lot of time. And then simply call set() on both deques and compare those sets:

from collections import deque

def solve_deque(seq):
    count = 0
    full_deque = deque(seq)
    current_deque = deque()
    for _ in xrange(len(seq)):
        current_deque.append(full_deque.popleft())
        if set(current_deque) == set(full_deque):
            count += 1
    return count

The above operation is around 7 times faster than your version:

>>> A = [random.randint(0, 100) for _ in xrange(1000)]
>>> %timeit solve(A)
10 loops, best of 3: 74.4 ms per loop
>>> %timeit solve_deque(A)
100 loops, best of 3: 11.3 ms per loop

But for bigger list it is still not good enough as the set() calls in each loop are expensive.

>>> A = [random.randint(0, 100) for _ in xrange(10**5)]
>>> %timeit solve_deque(A)
1 loops, best of 3: 1min 26s per loop

To improve this even further we need to approach this differently, and one such approach is to use a Counter. Similar to deque we maintain two Counters here: 1. full_counter: Contains count of the initial list items 2. current_counter: Contains counts of items seen so far. Apart from these we are also going to maintain two sets here: 1. full_keys: Initial unique items from the list 2. current_keys: Unique items seen so far.

Here during the loop we are going to increment the count of current item in current_counter and decrease its count from the full_counter. But we can't compare these counters, so that's where the 2 sets come in. Firstly add current item to the current_keys set and then check if the count of current item is equal to 0 in full_counter and if it is then we can remove this item from the full_keys set and then simply compare these two sets:

from collections import Counter

def solve_counter(seq):
    count = 0
    full_counter = Counter(seq)
    current_counter = Counter()
    full_keys = set(seq)
    current_keys = set()

    for item in seq:
        current_counter[item] += 1
        full_counter[item] -= 1
        current_keys.add(item)
        if full_counter[item] == 0:
            full_keys.remove(item)
        count += full_keys == current_keys
    return count

Timings:

>>> A = [random.randint(0, 100) for _ in xrange(1000)]
>>> %timeit solve_counter(A)
1000 loops, best of 3: 764 µs per loop
>>> A = [random.randint(0, 100) for _ in xrange(10**5)]
>>> %timeit solve_counter(A)
10 loops, best of 3: 109 ms per loop

Few other points:

  • The recommended way to get both item and the index is to use enumerate() rather than using range() with indexing. Also in Python 2 range() returns a list, so unless you actually need a list always use xrange().

  • Use upper case variable names(A) only for module level constants, that applies to the function arguments as well, we can use num_list or seq instead of A here.

  • left[:i].sort() and right[i:].sort() are useless, slice on Python lists returns a new shallow copy. So, here you created two new lists first, sorted them and then threw them away. To sort left and right, simply do left.sort() and rigth.sort().

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ your implementation seems to O(nlog(n)) but it's not, and that is because you are taking values over 0...100, so if you increase the range of values, you can clearly observe that your algo is still O(n^2 log(n)) \$\endgroup\$ – eightnoteight Feb 9 '15 at 19:40
2
\$\begingroup\$

Your algorithm's complexity is \$\mathcal{O}(n^2 \log(n))\$, (extra \$\log(n)\$ is from sets), but this problem can be easily solved within the complexity of \$\mathcal{O}(n \log(n))\$.

The key thing to observe is that if we go on to add the elements in a set, at some point the size of set doesn't increase....

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# pylint: disable=C0111


def solve(arr):
    fhalf = set()
    prefl, i = 0, 0

    for x in xrange(len(arr)):
        fhalf.add(arr[x])
        if len(fhalf) != prefl:
            prefl = len(fhalf)
            i = x
    w = i
    shalf = set()
    for x in xrange(len(arr) - 1, i, -1):
        shalf.add(arr[x])
        if len(shalf) == prefl:
            w = x
            break
    return max(w - i, 0)


def main():
    print solve([1, 5, 1, 5, 1])
    print solve([4, 1, 1, 2, 4, 2, 4, 1])


main()

Times

In [12]: arr = [randint(0, 100) for _ in xrange(10**3)]

In [13]: %timeit solve(arr)
1 loops, best of 3: 303 ms per loop

In [14]: %timeit solve_nlogn(arr)
1000 loops, best of 3: 502 µs per loop

In [19]: arr = [randint(0, 100) for _ in xrange(10**4)]

In [20]: %timeit solve_nlogn(arr)
100 loops, best of 3: 3.64 ms per loop

In [21]: arr = [randint(0, 100) for _ in xrange(10**5)]

In [22]: %timeit solve_nlogn(arr)
10 loops, best of 3: 34.4 ms per loop

In [23]: 

My Pentium went dead even for the \$10^4\$ data so I don't have benchmarks of your algorithm. for >= \$10^4\$

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can improve this a bit more by taking items from the left into the left set until its size increases, then from the right into the right set until its size passes the size of the left set, then from the left until it catches up, until they meet in the middle. \$\endgroup\$ – Ben Voigt Feb 8 '15 at 21:43
  • \$\begingroup\$ @BenkVoigt that's another cool way to solve this problem, thanks \$\endgroup\$ – eightnoteight Feb 9 '15 at 19:44
  • \$\begingroup\$ @BenVoigt - I missed your comment there, but even that is too much, you can do it in \$O(n)\$ if you just find the global set of values, the left most span that covers the set, and the right-most span that covers the set. The number of elements between them represents the number of ways to split the data. I answered it that way too. Note that I found dict to be faster than set() \$\endgroup\$ – rolfl Feb 10 '15 at 20:35
  • \$\begingroup\$ @rolfl: That's exactly what I described in a comment to the question. Presumably the improvement from O(n lg n) to O(n) is from using dict rather than set... and combining my single-pass approach with that should be even faster. As in, my approach is done in the same number of operations it takes you to finish your step #1. \$\endgroup\$ – Ben Voigt Feb 10 '15 at 20:44
  • \$\begingroup\$ Once the sets have met in the middle, though, @BenVoigt - you would then have to ensure that, while both sets are the same size, that they also contain the same contents... not a big deal, but needs doing. \$\endgroup\$ – rolfl Feb 10 '15 at 20:49
1
\$\begingroup\$

First, your range definition is a little strange, the -1/2 is unnecessary. It should be len(A) instead of len(A)-1/2. In python range excludes the second element, so range(1,3) is [1,2].

Sorting the two array is an unnecessary overhead since you are creating sets of them anyways.

This is my suggestion:

def solve(A):    
    count = 0
    for i in range(1, len(A)):
        if set(A[:i]) == set(A[i:]):
            count += 1
    return count
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

I have read the other suggestions with interest, and, as a person who is somewhat new to Python, I was wondering whether I was understanding them all correctly. The suggestions I see are clearly significantly better than your current code, but are missing an alternative algorithm that would make the performance significantly faster.

The solution is attainable in \$O(n)\$ time.

Alternative

Conceptually, the problem is simple:

  1. get a collection of all the actual values in the set. This requires a single scan of the entire input array.
  2. find the size of the left-most portion of the array that contains the entire set.
  3. find the size of the right-most portion that also contains the entire set.
  4. if the left and right spans do not overlap, then there is at least one solution. The actual number of solutions is the number of members between the left and right spans (plus 1).

By using a dict to contain the collection of distinct values used in the input array, you get O(1) performance (on average, slightly worse in the event that the dictionary key values become congested - which in this input example is very unlikely.

By combining the identification of the left-portion with the full scan, you can reduce the number of iterations (though it is still \$O(n)\$).

Here's the resulting code:

def countParts(num):
    distinctVal = {}
    size = 0
    left = 0
    for idx, val in enumerate(num):
        distinctVal[val] = 1
        if len(distinctVal) > size:
            left = idx
            size = len(distinctVal)

    for right in xrange(len(num) - 1, left, -1):
        distinctVal.pop(num[right], None)
        if len(distinctVal) == 0:
            return right - left
    return 0

Note that, in the above code, the key features are that it uses the enumerate mechanism to get both the index and value from the input array. This allows us to identify the left-most index of the data that contains the complete set. That set is found by resetting the left pointer each time there's a new distinct value.

Once it has fully scanned the input, it then starts from the right side, and removes each distinct value it finds from the distinctVal. When the dict is empty, it means we have covered the entire distinct set of values.

The difference between the end of the left set, and the start of the right set, is the number of solutions that are possible.

Performance

I compared the performance of my algorithm with that of Ashwini's. The solution I propose is about 40 times faster, for larger inputs, and about 10 times faster for smaller ones. This makes me believe that the time-complexity of my solution has a reduced dimension somewhere, compared to the other. I am not exactly sure why it is so much faster, or what that dimension is.... Here's how I tested them all.... note that your solution effectively does not complete the larger test cases... it's simply not scalable enough.

First, though, the results:

AP We have 1 splits from source 10
RL We have 1 splits from source 10
AP We have 6 splits from source 15
RL We have 6 splits from source 15
AP We have 8922 splits from source 10000
RL We have 8922 splits from source 10000
AP We have 98848 splits from source 100000
RL We have 98848 splits from source 100000
AP We have 987404 splits from source 1000000
RL We have 987404 splits from source 1000000
AP We have 0 splits from source 100000
RL We have 0 splits from source 100000
[27.986757040023804, 27.898667097091675, 27.68735098838806]
[0.6999490261077881, 0.7145471572875977, 0.701956033706665]

AP is Ashwini's post/solution, and RL is my solution.

The actual code that produced the output is:

import random
import timeit

from collections import Counter

def solve_counter(seq):
    count = 0
    full_counter = Counter(seq)
    current_counter = Counter()
    full_keys = set(seq)
    current_keys = set()

    for item in seq:
        current_counter[item] += 1
        full_counter[item] -= 1
        current_keys.add(item)
        if full_counter[item] == 0:
            full_keys.remove(item)
        count += full_keys == current_keys
    return count

def countParts(num):
    distinctVal = {}
    size = 0
    left = 0
    for idx, val in enumerate(num):
        distinctVal[val] = 1
        if len(distinctVal) > size:
            left = idx
            size = len(distinctVal)

    for right in xrange(len(num) - 1, left, -1):
        distinctVal.pop(num[right], None)
        if len(distinctVal) == 0:
            return right - left
    return 0

cases = [
        [1,2,3,4,5,5,4,3,2,1],
        [1,2,3,4,5,1,2,3,4,5,5,4,3,2,1],
        [random.randint(0, 100) for _ in xrange(10**4)],
        [random.randint(0, 100) for _ in xrange(10**5)],
        [random.randint(0, 1000) for _ in xrange(10**6)],
        [random.randint(0, 10000) for _ in xrange(10**5)]
    ]

for todo in cases:
    # print "OP We have {} splits from source {}".format(solve(todo), len(todo))
    print "AP We have {} splits from source {}".format(solve_counter(todo), len(todo))
    print "RL We have {} splits from source {}".format(countParts(todo), len(todo))

print timeit.repeat("for todo in cases: solve_counter(todo)", "from __main__ import cases,solve_counter", number=3)
print timeit.repeat("for todo in cases: countParts(todo)", "from __main__ import cases,countParts", number=3)

Review

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can do away with the test on len(distinctVal) and just test whether distinctVal doesn't yet contain the key val (either distinctVal[val] == 0, or however contains is tested in python) \$\endgroup\$ – Ben Voigt Feb 10 '15 at 20:58
  • \$\begingroup\$ The first len(...) could be replaced with a check, but the second one relies on the len(...) shrinking over time. \$\endgroup\$ – rolfl Feb 10 '15 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.