Question

我最近试图解决在俄亥俄的一些任务,我发现,解决办法似乎很复杂:O(nlog n),但我认为,某些投入(例如第1参数为0和pairs,是很长的零件清单)。

它还有三个层次的<条码>。我认为,它可以优化,但此时我无法优化它,我可能只是缺少一些显而易见的事情。

因此,问题基本上如下:

鉴于分类账清单( Values),该功能必须退还符合以下标准的指数奶制品数量:

lets assume single index pair is a tuple like (index1, index2),

then values[index1] == complementary_diff - values[index2] is true,

Example: If given a list like [1, 3, -4, 0, -3, 5] as values and 1 as complementary_diff, the function should return 4 (which is the length of the following list of indexes pairs: [(0, 3), (2, 5), (3, 0), (5, 2)]).

这正是我迄今为止所做的,它应当尽最大努力,但正如我所说的那样,在某些情况下,尽管其复杂性已接近O(nlog n),它仍然能够运行非常缓慢。 (如悲观复杂度为O(n^2))。

def complementary_pairs_number (complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        try:
            value_key[item].append(index)
        except (KeyError,): # the item has not been found in value_key s keys
            value_key[item] = [index]
    key_pairs = set() # key pairs are unique by nature
    for pos_value in value_key: # iterate through keys of value_key dictionary
        sym_value = complementary_diff - pos_value
        if sym_value in value_key: # checks if the symmetric value has been found
            for i1 in value_key[pos_value]: # iterate through pos_values  indexes
                for i2 in value_key[sym_value]: # as above, through sym_values
                    # add indexes  pairs or ignore if already added to the set
                    key_pairs.add((i1, i2))
                    key_pairs.add((i2, i1))
    return len(key_pairs)

For the given example it behaves like that:

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5])
4

如果看看该法典如何“被保留”或“简化”,请让我知道。

我不敢肯定,如果你认为是最佳办法,请让我知道。

EDIT: I have corrected the example (thanks, unutbu!).

Answer 1

I think this improves the complexity to O(n):

value_key.setdefault(item,[]).append(index) is faster than using the try..except blocks. It is also faster than using a collections.defaultdict(list). (I tested this with ipython %timeit.)
The original code visits every solution twice. For each pos_value in value_key, there is a unique sym_value associated with pos_value. There are solutions when sym_value is also in value_key. But when we iterate over the keys in value_key, pos_value is eventually assigned to the value of sym_value, which make the code repeat the calculation it has already done. So you can cut the work in half if you can stop pos_value from equaling the old sym_value. I implemented that with a seen = set() to keep track of seen sym_values.
The code only cares about len(key_pairs), not the key_pairs themselves. So instead of keeping track of the pairs (with a set), we can simply keep track of the count (with num_pairs). So we can replace the two inner for-loops with
```
num_pairs += 2*len(value_key[pos_value])*len(value_key[sym_value])
```
或“unique diagonal”案的一半,pos_ Value = sym_ Value/。





def complementary_pairs_number(complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        value_key.setdefault(item,[]).append(index)
    # print(value_key)
    num_pairs = 0
    seen = set()
    for pos_value in value_key: 
        if pos_value in seen: continue
        sym_value = complementary_diff - pos_value
        seen.add(sym_value)
        if sym_value in value_key: 
            # print(pos_value, sym_value, value_key[pos_value],value_key[sym_value])
            n = len(value_key[pos_value])*len(value_key[sym_value])
            if pos_value == sym_value:
                num_pairs += n
            else:
                num_pairs += 2*n
    return num_pairs

Answer 2

您不妨研究功能性方案拟订的分部分,如减少等。

Often times, nested array logic can be simplified by using functions like reduce, map, reject, etc.

例如(在javascript中)检查了头巾。我在沙尔没有可怕的智慧,因此我不知道他们拥有哪些图书馆。

Answer 3

I think (some or all of) these would help, but I m not sure how I would prove it yet.

1) Take values and reduce it to a distinct set of values, recording the count of each element (O(n))

2) Sort the resulting array. (n log n)

3) If you can allocate lots of memory, I guess you might be able to populate a sparse array with the values - so if the range of values is -100 : +100, allocate an array of [201] and any value that exists in the reduced set pops a one at the value index in the large sparse array.

4) 如果符合你的条件,你想要检查的任何价值现在都必须根据x---------------------关系,看看该指数是否存在价值。

5)如不可靠地指出的,它分三维度,因此,如果{a,b}是一对一对一对一对一,就如{b,a}。

Answer 4

我认为,你可以通过将algebra部分与搜索和使用更衣的数据结构分开来改进。

填写清单,从清单中每个项目的互补副手中删除。
```
resultlist[index] = complementary_diff - originallist[index]
```
你们可以使用地图或简易通道。 - ;O(n)。
参看原名单是否载有清单。
- 这里,如果有一份解冻清单,你实际上将获得O(n^2),因为你可以最终查找清单中每个项目的原清单。
- 然而,组织你的数据的方法比这更明显。如果您的原始名单为sorted,则其检索时间将减少到O(nlogn + nlogn) = O(nlogn),nlogn,按此类型计算;nlogn,按元件次检索。
- If you wanted to be even smarter you can make your list in to a dictionary(or hash table) and then this step becomes O(n + n) = O(n), n to build the dictionary and 1 * n to search each element in the dictionary. (*EDIT: * Since you cannot assume uniqueness of each value in the original list. You might want to keep count of how many times each value appears in the original list.)

因此,现在,你获得O(n)全时运行时间。

Using your example:

1, [1, 3, -4, 0, -3, 5],

Generate the result list:
```
>>> resultlist
[0, -2, 5, 1, 4, -4].
```
我们现在寻求:
- 将原清单压缩为字典。我选择将原名单指数作为数值,因为这个数值似乎与你再次感兴趣的一个侧面数据一样。
```
>>> original_table
{(1,0), (3,1), (-4,2), (0,3), (-3,4), (5,5)}
```
- For each element in the result list, search in the hash table and make the tuple:
```
(resultlist_index, original_table[resultlist[resultlist_index]])
```
  这应当像你所找到的解决办法一样。
Now you just find the length of the resulting list of tuples.

现在,这部法律是:

example_diff = 1
example_values = [1, 3, -4, 0, -3, 5]
example2_diff = 1
example2_values = [1, 0, 1]

def complementary_pairs_number(complementary_diff, values):
    """
        Given an integer complement and a list of values count how many pairs
        of complementary pairs there are in the list.
    """
    print "Input:", complementary_diff, values
    # Step 1. Result list
    resultlist = [complementary_diff - value for value in values]
    print "Result List:", resultlist

    # Step 2. Flatten into dictionary
    original_table = {}
    for original_index in xrange(len(values)):
        if values[original_index] in original_table:
            original_table[values[original_index]].append(original_index)
        else:
            original_table[values[original_index]] = [original_index]
    print "Flattened dictionary:", original_table

    # Step 2.5 Search through dictionary and count up the resulting pairs.
    pair_count = 0
    for resultlist_index in xrange(len(resultlist)):
        if resultlist[resultlist_index] in original_table:
            pair_count += len(original_table[resultlist[resultlist_index]])
    print "Complementary Pair Count:", pair_count

    # (Optional) Step 2.5 Search through dictionary and create complementary pairs. Adds O(n^2) complexity.
    pairs = []
    for resultlist_index in xrange(len(resultlist)):
        if resultlist[resultlist_index] in original_table:
            pairs += [(resultlist_index, original_index) for original_index in
                original_table[resultlist[resultlist_index]]]
    print "Complementary Pair Indices:", pairs

    # Step 3
    return pair_count

if __name__ == "__main__":
    complementary_pairs_number(example_diff, example_values)
    complementary_pairs_number(example2_diff, example2_values)

Output:

$ python complementary.py
Input: 1 [1, 3, -4, 0, -3, 5]
Result List: [0, -2, 5, 1, 4, -4]
Flattened dictionary: {0: 3, 1: 0, 3: 1, 5: 5, -4: 2, -3: 4}
Complementary Pair Indices: [(0, 3), (2, 5), (3, 0), (5, 2)]
Input: 1 [1, 0, 1]
Result List: [0, 1, 0]
Flattened dictionary: {0: [1], 1: [0, 2]}
Complementary Pair Count: 4
Complementary Pair Indices: [(0, 1), (1, 0), (1, 2), (2, 1)]

感谢!

Answer 5

修改了@unutbu提供的解决办法:

这个问题可以缩小到比较这2个字典:

价值观

pre-computed dictionary for (complementary_diff - 价值观[i])

def complementary_pairs_number(complementary_diff, 价值观):
    value_key = {} # dictionary storing indexes indexed by 价值观
    for index, item in enumerate(价值观):
        value_key.setdefault(item,[]).append(index)

    answer_key = {} # dictionary storing indexes indexed by (complementary_diff - 价值观)
    for index, item in enumerate(价值观):
        answer_key.setdefault((complementary_diff-item),[]).append(index)

    num_pairs = 0
    print(value_key)
    print(answer_key)
    for pos_value in value_key: 
        if pos_value in answer_key: 
            num_pairs+=len(value_key[pos_value])*len(answer_key[pos_value])
    return num_pairs

友情链接