Сравните список массивов для перекрытия

Question

У меня есть список списков массивов вида [a, [b, c, d]], что-то вроде

dataset = [[1, array[1, 2, 3, 4]], [0.5, array[2, 2, 3, 5]], [1.5, array[4, 3, 2, 1]], ...]

Я хочу сравнить каждый массив и определить количество совпадений между ними. В приведенном выше примере это будет означать идентификацию [[1, массив [1, 2, 3, 4]], [0.5, массив [2, 2, 3, 5] , ...]]. Я забочусь о перекрывающихся ценностях и положении.

Если перекрывается более некоторого порога (скажем, 1/3), я хочу исключить из набора данных значение с более низким коэффициентом. В приведенном выше примере это будет второй массив с 0,5 вместо 1.

Для приведенного выше списка результат будет:

 [[1, array[1, 2, 3, 4]], [1.5, array[4, 3, 2, 1]], ...]

Мне удалось собрать Решение (ниже), но это очень медленно. Я уверен, что есть лучший способ приблизиться к этому, я просто не уверен, что это такое.

survivors = dataset
for i, pair in enumerate(dataset):
        keep_arr = [veto_duplicate(pair, dup) for dup in survivors]
        survivors = list(compress(survivors,keep_arr))
return survivors

def veto_duplicate(path1, path2):
        fractional_overlap = sum(path1[1] == path2[1])/len(path1[1])
        if fractional_overlap > 0.25 and fractional_overlap < 1:
                        if path1[0] < path2[0]:
                                return False
                        else:
                                return True
        else:
                return True

Если бы кто-то мог предложить более быстрый способ сделать это, я был бы очень признателен.

edit

Все внутренние массивы такой же размер. Конечный результат не должен содержать массивов, которые перекрываются. Если есть три (или более) массива с перекрытием, я просто хочу сохранить один с самым высоким коэффициентом.

Answer 1

Вот несколько более быстрое решение. Надеюсь, это поможет:

dataset = [[1, np.array([1, 2, 3, 4])], [0.5, np.array([2, 2, 3, 5])], [1.5, np.array([4, 3, 2, 1])]]
#sort dataset by first element
dataset.sort(key=lambda x:x[0])
#unnormalize threshold to reduce division everytime
threshold = 1/3 * len(dataset[0][1])
survivors = dataset.copy()
id_to_del = []
for i, pair in enumerate(dataset):
    for dup in dataset[i+1:]:
        if sum(pair[1]==dup[1])>threshold:
            id_to_del.append(i)
            break

for i in id_to_del:
    del(survivors[i])
#converting to numpy and deleting might be faster if list is too long, but requires reformatting:
#survivors = np.delete(np.array(survivors), id_to_del, axis=0)

Вывод:

[[1, array([1, 2, 3, 4])], [1.5, array([4, 3, 2, 1])], ...]