DjangoBB LoFi version

Полная версия: свравнение в многомерном списке

Начало » Python для новичков » свравнение в многомерном списке

TITANius

Ноя. 20, 2010 12:41:01

День добрый помогите определить оптимальный алгоритм для сравнения элементов в многомерном списке.

Задача узнать количество элементов списка которые не удовлетворяют требованиям.

Например мы имеем 10 элементов списка, каждый из которых состоит из множества массивов.
Чтобы узнать количество “не совпадающих” элементов я каждый сравниваю с другими в списке:
1 с 2, 1 с 3, 1 с 4 … 1 с 10
2 с 3, 2 с 4 … 2 с 10
…
9 с 10

При 10 элементах в списке выходит 45 проверок, а если их будет 1000 ?

700 элементов проверяются 10 секунд, а хотелось бы чтобы было быстрее. Существуют ли способы сравнения элементов в списке оптимальным способом ?

кусок кода громоздкий …

from math import pow, sqrt, atan2

def distance2d(a, b):
    return sqrt(pow((a[0]-b[0]),2)+pow((a[1]-b[1]),2))

def distance3d(a, b):
	return sqrt(pow((a[0]-b[0]),2)+pow((a[1]-b[1]),2)+pow((a[2]-b[2]),2))

def normal(a, b, c):
	return ((b[0]-a[0])*(c[1]-b[1])-(b[1]-a[1])*(c[0]-b[0]))

def dot(a, b):
    return (a[0]*b[0]+a[1]*b[1]+a[2]*b[2])
  
def length(a):
	return sqrt(a[0]*a[0]+a[1]*a[1]+a[2]*a[2])

def cross(a, b):
    return [a[1]*b[2]-a[2]*b[1], a[2]*b[0]-a[0]*b[2], a[0]*b[1]-a[1]*b[0]]

def angle(a, b):
	return atan2(length(cross(a, b)), dot(a, b))

list = [[u'pPlane1.vtx[0]', [-5.5992126244689686, -13.957681553171557, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [0.0, 0.0], 1], [u'pPlane1.vtx[1]', [3.0597372275207775, -13.957681553171557, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [0.5, 0.0], 1], [u'pPlane1.vtx[4]', [3.0597372275207775, -0.45139588575212297, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [0.5, 0.77990323305130005], 1], [u'pPlane1.vtx[3]', [-5.5992126244689686, -0.45139588575212297, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [0.0, 0.77990323305130005], 1], [u'pPlane1.vtx[1]', [3.0597372275207775, -13.957681553171557, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [0.5, 0.0], 1], [u'pPlane1.vtx[2]', [11.718687079510524, -13.957681553171557, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [1.0, 0.0], 1], [u'pPlane1.vtx[5]', [11.718687079510524, -0.45139588575212297, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [1.0, 0.77990323305130005], 1], [u'pPlane1.vtx[4]', [3.0597372275207775, -0.45139588575212297, 0.0], [0.0, 0.0, 1.0], [0.0, 0.0, 0.0], [0.5, 0.77990323305130005], 1]]

UEvert = 0
tolerance3d = 0.008
tolerance2d = 1.0/1024
tolerancecolor = 1.0/256
tolerancenormal = 0.00008

lenUVSets = 1
vertexD = []

while len(list)>0:
	d = []
	for i, t in enumerate(list[1:]):
		if (distance3d(list[0][1],t[1])<tolerance3d) \
			& (angle(list[0][2], t[2])<tolerancenormal) \
			& all(distance2d(list[0][4+n],t[4+n])<tolerance2d for n in range(lenUVSets)) \
			& all(list[0][4+lenUVSets+n]==t[4+lenUVSets+n] for n in range(lenUVSets)) \
			& all(abs(list[0][3][n]-t[3][n])<tolerancecolor for n in range(3)) \
				: d.append(i)
	vertexD.append(list[0][0])
	del list[0]
	n = 0
	for i in d: del list[i-n]; n += 1
	UEvert += 1

print UEvert

Vadim

Ноя. 20, 2010 19:34:38

Я не очень понял, скольки мерный список тебе нужен и можно ли его структурировать, то есть например располагать элементы в n-мерном кубе по норме в подкубы? Уточни пожалуйста. Возможно вы имели ввиду сортировку списка? В таком случае самое простое решение представить куб как n-мерный параллелограмм и сортировать по ребрам пузырьком. Или возможно вы хотите вытащить номера элементов по их названию, в таком случае удобно представить списки в виде дерева и искать по дереву. Вообщем что значит сравнить элементы? можно задать класс узел и класс элемент, затем на его основе построить дерево, задать каждому узлу характеристику высоты и сравнивать элементы одной высоты по количеству элементов, например.

TITANius

Ноя. 20, 2010 20:03:54

Если уточнить, то … каждый элемент списка (вершина 3д модели) состоит из параметров: его название (1значение], пространственное положение (3 значения), вектор нормали (3 значения), его цвет (3 значения), расположение на текстуре 1(2 значения), расположение на текстуре 2(если она есть) и т.д.(2 значения), развернутость на текстуре 1(1 значение), развернутость на текстуре 2(если она есть) и т.д.(1 значение).

Я решил строить элемент так :,,,,,…,,…

Из списка всех вершин мне нужно удалить те, которые близки по параметрам: расположение в пространстве, вектора нормали, цвета, расположение на текстурах и развёрнутость на текстурах.

Т.е. нужно удалить продублированные (близки по параметрам) элементы списка. Сортировка думаю мало мне поможет.

P.S.: сори что так сумбурно … сложно сформулировать задачу.

Vadim

Ноя. 20, 2010 20:20:55

Окей, скажи рамки.

Попробуй задать каждую точку как отдельную особь, задать границы, потом задать функцию спаривания, при которой похожие при встрече создают одну среднюю между ними по параметрам, а затем обе исчезают, а разные не изменяются, то есть для каждого значения проверяется его близость к другому в процентах, до тех пор пока список не кончится или до тех пор пока не найдется существенное различие. Потом задавать второе поколение, и ввести характеристику изменения поколения, то есть, например разность между количеством особей в этом и прошло поколениях, тогда эта величина в итоге должна убывать. провести так , например для m точек m^2 циклов смены поколения.

Это вообщем-то мои догадки в приложении так популярных сейчас генетических алгоритмов, код предоставлю этой идеи если интересно.

TITANius

Ноя. 20, 2010 22:30:02

Если не сложно покажи код. Будет интересно посмотреть реализацию.

Vadim

Ноя. 21, 2010 16:50:10

Сравнение 2ух элементов я взял с потолка, то есть сравнивал как мне нравилось, остальное так как и задумавалось, разве что условие выхода из цикла не проверено на оптимальность, сейчас посчитаю сколько шагов без удалений дают с наибольшей вероятностью верный ответ.

import random

class point(): #Класс, задающий точку
    def __init__(self, name = '', spacepoint = [], normalvect = [], texturespoint = [], texturesdev = [],  type = 0):
            self.name = name
            self.spacepoint = spacepoint
            self.normalvect = normalvect
            self.texturespoint = texturespoint
            self.texturesdev = texturesdev
            self.type = type
    def __setitem__(self, key, value):
        try:
            self.__dict__[key] = value
        except KeyError:
            raise KeyError('Sorry, wrong key')
    def __del__(self):
        del self.name,  self.spacepoint,  self.normalvect, self.texturespoint, self.texturesdev, self.type
        del self
def pointscompare(point1, point2): #Сравнение 2ух точек, писалось от балды
    dictp1 = point1.__dict__
    dictp2 = point2.__dict__
    massaddict = []
    n1 = dictp1['name']
    n2 = dictp2['name']
    near = 0.0
    if len(n1) != 0 and len(n2) != 0:
        for i in xrange(min(len(n1), len(n2))):
            if n1[i] == n2[i]:
                near += 1.0
        pr1 = 0.0
        pr1 = (max(len(n1), len(n2))*1.0)/100
        near = near/pr1
    elif len(n1) == 0 and len(n2) == 0:
        near = 100.0
    else:
        near = 0.0
    massaddict.append(near)
    del near, pr1
    n1 = dictp1['spacepoint']
    n2 = dictp2['spacepoint']
    near = 0.0
    pointdeg = 0.0
    for i in xrange(3):
        if n2[i] != 0:
            pointdeg = (n1[i]*1.0)/(n2[i])
        elif n1[i] != 0:
            pointdeg = (1.0)/(n1[i])
        else:
            pointdeg = 1.0
        if pointdeg < 1.1 and pointdeg >0.9:
            near += 33.3
    massaddict.append(near)
    del near, pointdeg
    n1 = dictp1['normalvect']
    n2 = dictp2['normalvect']
    near = 0.0
    pointdeg = 0.0
    for i in xrange(3):
        if n2[i] != 0:
            pointdeg = (n1[i]*1.0)/(n2[i])
        elif n1[i] != 0:
            pointdeg = (n2[i]*1.0)/(n1[i])
        else :
            pointdeg = 1
        if pointdeg < 1.1 and pointdeg >0.9:
            near += 33.3
    massaddict.append(near)
    del near, pointdeg
    #Compare texturespoint and texturesdev
    n1 = dictp1['texturespoint']
    n2 = dictp2['texturespoint']
    near = 0.0
    pointdeg = 0.0
    for i in xrange(min(len(n1), len(n2))):
        if n2[i] != 0:
            pointdeg = (n1[i]*1.0)/(n2[i])
        elif n1[i] != 0 and n2[i] == 0:
            pointdeg = (1.0)/(n1[i])
        else:
            pointdeg = 1.0
        if pointdeg < 1.1 and pointdeg >0.9:
            near += 100.0/max(len(n1), len(n2))
    massaddict.append(near)
    del near, pointdeg
    n1 = dictp1['texturesdev']
    n2 = dictp2['texturesdev']
    near = 0.0
    pointdeg = 0.0
    for i in xrange(min(len(n1), len(n2))):
        if n2[i] != 0:
            pointdeg = (n1[i]*1.0)/(n2[i])
        elif n1[i] != 0:
            pointdeg = (1.0)/(n1[i])
        else:
            pointdeg = 1.0
        if pointdeg < 1.1 and pointdeg >0.9:
            near += 100.0/max(len(n1), len(n2))
    massaddict.append(near)
    del near, pointdeg
    s = 0.0
    for i in massaddict:
        s += i
    s = s/len(massaddict)
    print s
    if s > 50:
        return 1
    else:
        return 0
def population(pointlist,  stepnum): #Функция, проживаюшая stepnum поколений
    stability = 0 #Стабильность функции, то есть то число шагов подряд, за которые не произошло удалений
    for i in xrange(stepnum):
        s1 = 0
        s2 = 0
        if (stability >= (stepnum*1.0)/5): #Проверка на стабильность, в данном случак 1/5ая шагов без изменений значит выход
            return pointlist
        while s1 == s2:  #Задание 2ух случайных неповтояющихся номеров от 1 до длинны pointlist
            s1 = random.randrange(1, len(pointlist)+1)
            s2 = random.randrange(1, len(pointlist)+1)
        if pointscompare(pointlist[s1-1], pointlist[s2-1]) == 1: #Проверка элементов на совпадение
            del pointlist[s1] #Удаление одного из совпадающих элементов, тут может быть по желанию что угодно
            stability = stability - 2 #Уменьшение стабильности.
        else:
            stability +=1 # Если элементы не совпали то увеличить стабильность
    return pointlist #Конец

Строго говоря надо бы пересчитать очень много, то есть то, на сколько уменьшится стабильность это функция от числа точек и от производной от числа элементов, вообщем с математикой надо немного поиграться. На тесте с 10ю точками давало стабильный результат.
И ещё. Вообще должна быть ещё мутация элемента, то есть после изменения элементов(спаривания) должна происходить мутация каких-то случайных элементов, но в данном случае она оказалась ненужной.

Вообщем-то это можно описать биологически. Жили животные вида point и раз в неделю(например) спаривались, спаривались 2 случайные особи, так как ыбли point гермафродитами. Если особи были близки друг-другу то после спаривания одна из них умерала, а вторая продолжала искать себе партнера. А если не были близки то просто живые расходились. Так за сколь-ко то недель племя обретало такую численность, что никто уже умереть не мог.

Ага-ага, на больших значениях он совершает меньше шагов, твой совершает при n входных значениях S = n*(2+(n-1))/2 шагов, мой точно не больше этого числа.

TITANius

Ноя. 22, 2010 11:01:35

Я решил проблему попроще. Каждый элемент умножил на коэффициент допуска, па потом удалил из списка дубликаты. Работает за доли секунды.

За желание помочь спасибо :)

Андрей Светлов

Ноя. 22, 2010 13:49:39

Vadim, пишите class point(object): pass
Оператор del нужен только в одном месте - там где удаление из списка.

__del__ не только бесполезен, но может быть еще и вредным.
Это - один из самых простых способов обеспечить протечку памяти :)

Vadim

Ноя. 22, 2010 15:40:15

Спасибо, учту в слудеющий раз =)