如何根据来自不同列表的数字将数字标签分配给列表/系列/数组中的所有元素？

Question

我有两个列表，其中包含两个系列的数字，例如：

A = [1.0, 2.9, 3.4, 4.2, 5.5....100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]

我想根据列表 B 中的元素是否落在列表 A 的（任何）区间内来创建另一个标签列表。像这样：

C = [group_1, group_1, group_1, group_1, group_2, group_2, group_3]

即1.1、1.2、1.3、2.5 都落在列表 A 的 1.0 - 2.9 区间内，因此属于 group_1； 3.0、3.1 都落在 2.9 - 3.4 的区间内，因此是 group_2；和 5.2 落在 4.2 - 5.5 的区间内，因此 group_3 等..

列表 B 中的数字落在列表 A 的哪个区间并不重要，关键是以连续的方式对列表 B 中的所有元素进行分组/标记。

原始数据很大，因此无法手动为列表 B 中的元素分配标签/组。感谢任何帮助。

Answer 1

你可以试试这个

O(n)

解决方案（假设两个列表都排序并且一个数字必须在

A

中的间隔之一）：

A = [1.0, 2.9, 3.4, 4.2, 5.5, 100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]

grp = 0
i1, i2 = iter(A), iter(B)
a, b = next(i1), next(i2)

out = []
while True:
    try:
        if a < b:
            a = next(i1)
            grp += 1
        else:
            out.append(grp)
            b = next(i2)
    except StopIteration:
        break

print(out)

印花：

[1, 1, 1, 1, 2, 2, 4]

Answer 2

因此，假设

A

已排序，您可以使用二进制搜索，它已经在（相当笨拙的）模块中的 python 标准库中附带了二进制搜索

bisect

：

>>> A = [1.0, 2.9, 3.4, 4.2, 5.5]
>>> B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]
>>> [bisect.bisect_left(A, b) for b in B]
[1, 1, 1, 1, 2, 2, 4]

这需要

O(N * logN)

时间。

注意，请注意阅读文档以及当

bisect_left

中的值等于

bisect_right

中的值时

B

和

A

的行为方式，以及不会掉落到任何地方的物品的行为方式。

Answer 3

您可以根据这个代码在

O(len(B))

中回答：

C= [0]*len(B)
i, j = 0, 0

while i < len(B):
    if (B[i] > A[j] and B[i] < A[j+1]):
        C[i] = j
        i += 1
    else:
        j += 1

Answer 4

我认为

itertools.groupby

带有一个微小的可变“关键功能”类会很合适（特别是如果需求会改变或者你需要其他地方的模式）：

import itertools

class IntervalIndexResolver:
    def __init__(self, thresholds):
        self._intervals = list(itertools.pairwise(thresholds))
        self._index = 0

    def __call__(self, number):
        while not self._is_in_current_interval(number):
            self._index += 1
        return self._index

    def _is_in_current_interval(self, number):
        lo, hi = self._intervals[self._index]
        return lo <= number <= hi

A = [1.0, 2.9, 3.4, 4.2, 5.5, 100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]

key = IntervalIndexResolver(A)
for group_key, group_items in itertools.groupby(B, key):
    print(f'{group_key}: {", ".join(str(i) for i in group_items)}')

"""Output:
0: 1.1, 1.2, 1.3, 2.5
1: 3.0, 3.1
3: 5.2
"""

这种方法是 O(N_A + N_B) 给定先决条件：

• A 和 B 已排序

• A[0] < B[0]

• A[-1] > B[-1]

您可以通过二进制搜索

__call__

中的正确索引来删除这些先决条件，而不是假设后面的某个索引“肯定”是正确的。然而，复杂度会上升到 O(N_B × log N_A)。

Answer 5

试试这个：

import numpy as np


A = [1.0, 2.9, 3.4, 4.2, 5.5, 100.3]
B = [1.1, 1.2, 1.3, 2.5, 3.0, 3.1, 5.2]
A_arr = np.array(A)
B_arr = np.array(B)
C = [np.searchsorted(A_arr, b) for b in B_arr]
print(C)
>>>
[1, 1, 1, 1, 2, 2, 4]