LINUX.ORG.RU

Сортировать и синхронизировать массивы

 , ,


0

1

Имеются 2 массива данных I(e,t) в виде 2 троек 1-мерных массивов одинаковой длины: t1, e1, I1 и t2, e2, I2. (Точнее, это — группы в открытых HDF-файлах f1['data/t'], f1['data/e'], f1['data/i'] и f2['data/t'], f2['data/e'], f2['data/i']). Данные отсортированны по возрастанию e, затем по возрастанию t. e и t образуют регулярную сетку с шагами ~0.001 и 1. I задана не во всех узлах. Повторяющихся узлов нет.

Требуется проверить, совпадают ли массивы I1 и I2. Оба файла содержат одинаковый набор пар e-t. Но из-за ошибок округления часть изначально совпадавших e немного отличается. Поэтому данные в I2 перетасованы относительно I1 — одинаковые индексы необязательно соответствуют одинаковым значениям e и t.

Имеется питоновская библиотека для чтения этих файлов, h5py. Есть ли какой-то штатный способ быстро отсортировать I2, вначале сравнивая t как целые числа, а затем e — как дробные с заданной погрешностью (скажем, абсолютная погрешность 1e-3)? Реализовать это сам я могу, но вдруг есть готовое?

Можно ли получить искомое, применив numpy.sort к list( zip( t1, e2, I2 ) ) ? Как там задать погрешность? Или есть что-то получше?

Пока сделал так:

#!/usr/bin/python3
from sys import argv
import h5py
import numpy as np

f1, f2 = h5py.File( argv[1],'r' ), h5py.File( argv[2],'r' ) 
I1, I2 = np.array(f1['data/i']), np.array(f2['data/i'])
t1, t2 = np.array(f1['data/t']), np.array(f2['data/t'])
e1, e2 = np.ma.round(np.array(f1['data/e']), 7), np.ma.round(np.array(f2['data/e']), 7)

j1, j2 = np.lexsort( (e1, t1) ), np.lexsort( (e2, t2) )

a1 = np.stack( ( t1[j1], e1[j1], I1[j1] ), axis=-1 )
a2 = np.stack( ( t2[j2], e2[j2], I2[j2] ), axis=-1 )

print( ( a1 == a2 ).all() )

Или так:

#!/usr/bin/python3
from sys import argv
import h5py
import numpy as np

f1, f2 = h5py.File( argv[1],'r' ), h5py.File( argv[2],'r' ) 
I1, I2 = np.array(f1['data/i']), np.array(f2['data/i'])
t1, t2 = np.array(f1['data/t']), np.array(f2['data/t'])
e1, e2 = np.array(f1['data/e']), np.array(f2['data/e'])

j1, j2 = np.lexsort( (e1, t1) ), np.lexsort( (e2, t2) )

print( ( t1[j1] == t2[j2] ).all() and
       ( abs(e1[j1] - e2[j2]) < 0.0000001 ).all() and
       ( abs(I1[j1] - I2[j2]) < 1 ).all() )

★★★

Последнее исправление: olegd (всего исправлений: 4)
Ответ на: комментарий от slovazap

по-моему данные всё-же

одномерные (как я понял задачу).

И мне кажется ошибка сидит здесь в особенности питона

a1 = numpy.array([ ( t1[j1[l]], e1[j1[l]], I1[j1[l]] ) for l in range(len(j1)) ])
a2 = numpy.array([ ( t2[j2[l]], e2[j2[l]], I2[j2[l]] ) for l in range(len(j2)) ])

я в питоне не силен, но если j1 и j2 индексы исходных линейных массивов, то в IDL-e оно бы сразу отработало.

Но я согласен с Доном slovazap в том, что там только полный перебор (впрочем, всякие тривиальные проверки могут очень сильно сократить время, особенно в случае разных массивов)

sshestov ★★
()
Ответ на: по-моему данные всё-же от sshestov

по-моему данные всё-же одномерные (как я понял задачу)

Как можно это написать, а на 2 строки ниже привести код с тройками?

Эта задача по нечёткому сравнению двух наборов трёхмерных точек.

slovazap ★★★★★
()
Ответ на: по-моему данные всё-же от sshestov

И мне кажется ошибка сидит здесь в особенности питона

Какая ошибка? Эти строки нужны были, чтобы объединять 3 линейных массива в один 3х200 000, чтобы проще было сравнивать. Этот шаг был очень медленным, да, поэтому я заменил всё на numpy.stack().

если j1 и j2 индексы исходных линейных массивов, то в IDL-e оно бы сразу отработало.

j1 и j2 — массивы индексов изначальных массивов, в каком порядке расставить их элементы, чтобы было отсортировано. Генерируются numpy.lexsort()

Но я согласен с Доном slovazap в том, что там только полный перебор (впрочем, всякие тривиальные проверки могут очень сильно сократить время, особенно в случае разных массивов)

Проверка исходит из предположения, что оба файла содержат одну таблицу, отличающуюся только порядком расположения троек и иногда последним знаком в колонке «e». (А если отличий больше, далее разбирать нет смысла.) Каждой тройке в файле f1 соответствует ровно одна тройка в файле f2. И чтобы не сравнивать каждую тройку f1 с каждой тройкой f2 (что будет медленно, если нет готовой библиотеки), я сперва сортирую их готовой библиотекой, а потом сравниваю только тройки с одинаковым индексом. Шаг по t строго 1, шаг по e не менее 0.000001 (реально около 0.001), повторений быть не должно.

Можно было бы и не объединять 3 в 1. Просто переставить элементы в каждом линейном массиве в соответствии с результатами сортировки: I1 = I1[j1] Но для меня нагляднее одно сравнение (a1 == a2).all(), чем 3 одинаковых (I1 == I2).all(); (e1 == e2).all(); (t1 == t2).all()

Единственная проблема — я обеспечил совпадение e1 и e2 при помощи round( decimals=7 ). Теоретически, могут попасться 2 числа, которые округлятся в разные стороны. Что делать с этим?

Пока приходит в голову только не объединять и смотреть (abs(e1-e2) < 0.0000001).all()

olegd ★★★
() автор топика
Ответ на: комментарий от slovazap

ну я имел ввиду

что размер массива N, а не N*N. Сложность то алгоритма растет как N^2 (или N^4 во втором случае, что многовато). А то, что там 2 или 3 координаты у каждого элемента, это сложности вообще не добавляет.

sshestov ★★
()
Ответ на: комментарий от slovazap

Эта задача по нечёткому сравнению двух наборов трёхмерных точек.

Да. Но из-за условия, что каждая пара e-t должна встречаться строго по одному разу в обоих файлах (а если нет — проверка не пройдена), а возможные e и t образуют конечную сетку, задача упрощается.

С учётом написанного в постах выше, я пришел к следующему решению. Сортировать тройки по целому t (т.е. без погрешностей); затем по дробному e (т.к. шаг больше погрешностей, а при равном t e уникальны); после чего сравнивать целые столбцы (t1==t2).all(), а дробные (abs(e1-e2)<epsE).all() и (abs(I1-I2)<epsI).all(). Если есть несоответствия в столбцах t и e, значит наборы точек разные, и сравнивать нельзя. Если для I тоже нет несоответствия, значит массивы совпадают.

Огрехи в логике есть?

olegd ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.