☰

» »

Python iskanje podvojenih vrednosti

Python iskanje podvojenih vrednosti

Isotropic ::

imam tole kodo
db['nodes'].sort(key=lambda x: x[1])

i=0
j=0
while i < len(db['nodes']):
  current = db['nodes'][i]
  j = i+1
  while j < len(db['nodes']):
    elem = db['nodes'][j]
    if current[1:] == elem[1:]:
      db['nodes'].remove(elem)
      db['duplicates'].append([current[0], elem[0]])
      print ('found match %d - %d' % (current[0], elem[0] ))
    elif current[1] < elem[1]:
      break
    j += 1
  i += 1


posamezni zapisi v db[nodes][i] so tipa [int, float, float, float], kjer so float x,y,z koordinate. le-te moram primerjati ter odstraniti podvojena stevila.

no, problem pa je, da mi ne najde duplikatov, kjer sta i in j zaporedni stevili (oznaki pozicije v db[nodes][]), vse ostale, ki so bili obicajno z razmakom 2, pa najde -- zanimivo, da se pregrize skozi loop v cca. 2s, v primerjavi z prejsnjo verzijo, kjer sem imel for, xrange in je trajalo 10min...
ko sem dal j+=1 v if zanko, mi je pa loope 0,1,2,3 naredil takoj, za ostale je pa trajalo (ko sem prekinil po minuti, sta bila i in j (3,4) ).


kaksne ideje?

BlueRunner ::

Napaka je v tvoji kodi. Ko izvedeš "db['nodes'].remove(elem)", to med drugim pomeni, da bo db['nodes'][j] sedaj kazal na naslednji element v polju, saj si trenutnega ravnokar izbrisal. Na koncu zanke pa si j povečal še za ena, kar pomeni, da si naslednjega po vrsti preprosto preskočil.

Nariši si na list papirja vsebino polja pred remove, vsebino polja po remove in kam kaže polje[j] pred remove, po remove in po remove ter += 1.

Imaš dve možnosti:
- popravi kodo tako, da boš pri brisanju naredil tudi j -= 1
- popravi kodo tako, da boš naredil j += 1 samo, če ne brišeš

...

Zgodovina sprememb…

Isotropic ::

hvala!
lahko pogledas se tole na hitro in poves, ce najdes kaksen performance hog, ker je rabila tale pa cca. 10-15min za isto zadevo (proti 2 sekundama). samo na hitro prosim.

for i in xrange(len(db['nodes'])):
  for j in xrange(len(db['nodes'])):
    if db['nodes'][i][1] == db['nodes'][j][1] and i != j:
      if db['nodes'][i][2] == db['nodes'][j][2]:
        if db['nodes'][i][3] == db['nodes'][j][3]:
          db['duplicates'].append([i, j])
          print('Found match: %d -> %d' % (i+1, j+1) )
    elif db['nodes'][i][1] < db['nodes'][j][1]:
      break


vem, da ne delata cisto iste zadeve (ta ne brise), ampak ok. a jo upocasni to, da se velikokrat sklicujem na db['nodes'][i][]? (bi moral narediti temp = db['nodes'][i])?

Zgodovina sprememb…

BlueRunner ::

Samo dve vprašanji:

Ali so elementi v db['nodes'] slučajno že urejeni po [1]? Ne da se mi razmišljati, ampak glede na "elif db['nodes'][i][1] < db['nodes'][j][1]" in gled na "db['nodes'].sort(key=lambda x: x[1])" iz provega posta, se mi zdi, da so...

Če slučajno niso, ali moraš ohraniti vrstni red elementov v db['nodes']?

Zgodovina sprememb…

Isotropic ::

so sortirani ja - da bi skripta sla hitreje skozi.
vrstni red (prvi int) rabim, ker jim bom potem pri zapisu v file samo posodobil zaporedno stevilko (zdaj ko je brisano, je 1,2,4,5,6,10..., mora pa biti zaporedno).
takrat bom samo sortiral po intu in napisal nove vrednosti zanj (int)

BlueRunner ::

"db['nodes'].sort(key=lambda x: x[1])" s tem si jih uredil naraščajoče po prvem float. Kar se mi ne sklada s tem, da praviš, da so urejeni po int (to bi bilo urejanje po x[0] in ne x[1].

Ampak, če so res urejeni po x[1], potem je to že 80% rešitve. Samo izkoristi urejenost.

i = 0
count = len(db['nodes'])
while i < (count - 1):
  j = i + 1
  while (j < count) and (db['nodes'][i][1] == db['nodes'][j][1]):
    if (db['nodes'][i][2] == db['nodes'][j][2]) and (db['nodes'][i][3] == db['nodes'][j][3]):
      db['duplicates'].append([i, j]) 
      print('Found match: %d -> %d' % (i+1, j+1) )
    j += 1
  i = j


Ja, pa upoštevaj, da to pišem na suho...

Zgodovina sprememb…

Isotropic ::

ne, mene je zanimalo, kaj v tej skripti upocasnjuje delovanje?
for i in xrange(len(db['nodes'])):
  for j in xrange(len(db['nodes'])):
    if db['nodes'][i][1] == db['nodes'][j][1] and i != j:
      if db['nodes'][i][2] == db['nodes'][j][2]:
        if db['nodes'][i][3] == db['nodes'][j][3]:
          db['duplicates'].append([i, j])
          print('Found match: %d -> %d' % (i+1, j+1) )
    elif db['nodes'][i][1] < db['nodes'][j][1]:
      break


ker dosti delam na podobnih primerih pa mi ni jasno, kaj naj bi bilo tukaj pocasnega (razen tega, da lahko nebi loopal skozi tocke, za katere ze vemo, da so podvojene, ampak ok, to ni veliko).
je na splosno tak nacin dela (xrange, for...) pocasnejsi, so if pocasni...?

Zgodovina sprememb…

BlueRunner ::

Morda to, da je logično zgrešena...

Tvoja skripta bo opravila reda 1 + 2 + 3 + 4 + 5 + ... + N korakov, moja pa samo reda N korakov. Večji kot bo N - število elementov, bolj bo tvoja počasna.

Isotropic ::

aha hvala.
kako stejes te korake? je to tista O(n) notacija ali kaj?

BlueRunner ::

Pusti tisto notacijo, če nisi na faksu... Jaz te zadeve delam preprosto tako, da vzamem v roke svinčnik in papir. Če je preveč za pisati, potem nekaj delam narobe.

Sicer to pomeni, da včasih kisknem, ampak bolj redko.

Čisto na suho pogledano tvoja skripta mislim, da sploh ne najde duplikatov... Če mi daš 15 minut pa lahko preverim splošno pravilnost.

Zgodovina sprememb…

Isotropic ::

edit: disregard please
sem nasel napako.

Zgodovina sprememb…

BlueRunner ::

Uh, najprej naj popravim svojo prvo napako... Na papir sem narobe napisal iskanje duplikatov, če imaš zaporedje že urejeno po x[1]. Pravilna koda je spodaj:

i = 0
j = 1
count = len(list)
while j < count:
  if (list[j][1] == list[i][1]) and (list[j][2] == list[i][2]) and (list[j][3] == list[i][3]):
    #db['duplicates'].append([i, j]) 
    print('Found match: %d -> %d' % (i+1, j+1) )
  else:
    i = j
  j += 1

Zgodovina sprememb…

BlueRunner ::

Pa še cel test, ki sem ga na hitro spisal... Iz njega je videti razliko. Sedaj pa ne vem, če si dejansko želel imeti vse kombinacije, ali pa samo smiselne. Še vedno pa lahko "nesmiselne" ustvariš naknadno tako, da za vse moje najdene samo dodaš še (x, y) -> (y, x).

#!/usr/bin/python

nodes = [
  [0, 1.0, 1.0, 1.0],
  [1, 1.0, 1.1, 1.1],
  [2, 1.0, 1.1, 1.1],
  [3, 1.1, 1.2, 0.1],
  [4, 2.0, 1.2, 0.1],
  [5, 2.0, 1.2, 0.1],
  [6, 2.0, 1.2, 0.1] ]

def dupes1(list):
  for i in xrange(len(list)):
    for j in xrange(len(list)):
      if list[i][1] == list[j][1] and i != j:
        if list[i][2] == list[j][2]:
          if list[i][3] == list[j][3]:
            #db['duplicates'].append([i, j])
            print('Found match: %d -> %d' % (i+1, j+1) )
      elif list[i][1] < list[j][1]:
        break

def dupes2(list):
  i = 0
  j = 1
  count = len(list)
  while j < count:
    if (list[j][1] == list[i][1]) and (list[j][2] == list[j][2]) and (list[j][3] == list[i][3]):
      #db['duplicates'].append([i, j]) 
      print('Found match: %d -> %d' % (i+1, j+1) )
    else:
      i = j
    j += 1

print("dupes1")
dupes1(nodes)

print("dupes2")
dupes2(nodes)

Isotropic ::

se tale problem:
tocke, ki sem jih iskal prej, predstavljajo koordinate trikotnikov. ko sem jih ene par izbrisal, ker so bile podvojene (dve tocki na istem mestu), sem jih mogel urediti po vrsti, ker ne sme biti lukenj vmes (1,2,4..). sedaj bom moral posodobiti se definicije trikotnikov, vendar si pa ne predstavljam ravno, kako naj sledim, katere tocke so bile izbrisane.

imam takle seznam dupes
[[6012, 6014], 
 [6349, 6351], 
 [9650, 9652], 
 [13437, 13439], 
 [13702, 13704, 13706], 
 [13703, 13705, 13707]]

[0] je original, ostale so duplikati, lahko jih je vec, kot je razvidno, a max. 2 do sedaj.

edino, kar si lahko zamislim, je da bi sel gledat, kje velja db['dupes'][i][j] > tocka
kjer je tocka posamezno krajisce trikotnika, dupes pa zgornja tabela. potem bi pa sel se enkrat skozi celo db[dupes] tabelo, izvrsil len(db['dupes][i][1:]) nad vsako vrstico, dokler nebi prisel do ustreznega polja. potem bi od tocke odstel dobljeno vrednost.

kaksna boljsa ideja?
mislil sem nekaj narediti tudi seznam tock (db[nodes]) ter ga posodabljati glede na brisane tocke, samo to nebi bilo dobro, ker bi moral za vsako izbrisano tocko pomasnjsati vsa polja za njo za 1.

glede zgornjega posta: polni popravi ne dela, ga lahko izbrisete.

Zgodovina sprememb…

BlueRunner ::

Če so bili duplikati tole:
[ [0, 1], [0, 2], [3, 4],... ]

Potem je rezultat končnih indeksov tole:
[ 0, 3, 5, 6,... ]
ker so bili 1, 2, 4,... Izpuščeni kot odvečni.

Potem pa se samo še sprehodiš preko vseh trikotnikov in z bisekcijo (uporabi funkcijo bisect_left) menjaš koordinate.

Trikotniki[... ] = tocke[bisect_left(trikotniki[... ])]

Nov indeks za točko je preprosto njen indeks v urejenem seznamu. Seznam pa naj bo urejen zato, ker je iskanje z bisekcijo optimalna metoda iskanja.

Zgodovina sprememb…

  • polepsal: Mavrik ()

Isotropic ::

ne razumem.
lahko pokazes na primeru (uporabe funkcije)?
ce je trikotnik podan z (13702, 13707, 6014)

in so duplikati
[[6012, 6014], 
[6349, 6351], 
[9650, 9652], 
[13437, 13439], 
[13702, 13704], 
[13702, 13706], 
[13703, 13705], 
[13703, 13707]]


po moji teoriji index najprej zamenjas z [0] iste vrstice, potem pa odstejes pozicijo iz enumerate (ker se je toliko tock nad njo izbrisalo).
novi indexi bi tako bili (13698, 13699, 6012) ob danih duplikatih.
ce pa indexa ni v tabeli duplikatov, pa najdes prvega vecjega in potem isto odstejes (to morem se preverit)

Zgodovina sprememb…

BlueRunner ::

Recimo nekaj takšnega:
#!/usr/bin/python

from bisect import bisect_left

nodes = [
  [0, 1.0, 1.0, 1.0],
  [1, 1.0, 1.1, 1.1],
  [2, 1.0, 1.1, 1.1],
  [3, 1.1, 1.2, 0.1],
  [4, 2.0, 1.2, 0.1],
  [5, 2.0, 1.2, 0.1],
  [6, 2.0, 1.2, 0.1] ]

triangles = [
  [0, 1, 3],
  [1, 3, 4],
  [1, 4, 6] ]

def dupes(list):
  dupes = []
  i = 0
  j = 1
  count = len(list)
  while j < count:
    if (list[j][1] == list[i][1]) and (list[j][2] == list[j][2]) and (list[j][3] == list[i][3]):
      yield [i, j]
      print "Duplicate %d -> %d" % (i, j)
    else:
      i = j
    j += 1


dupe_index = set([dupe[1] for dupe in dupes(nodes)])
node_index = [node[0] for node in nodes if node[0] not in dupe_index]

print "Before:", triangles
triangles = [[bisect_left(node_index, n) for n in tr] for tr in triangles]
print "After: ", triangles

Isotropic ::

hvala, dela!:D
edino, kar sem moral narediti, je spremeniti "n+1" v bisect_left, ker se vozlisca pac zacnejo z 1.
se take bolj advanced zadeve najdejo v kaksni knjigi? jaz imam learning python, 3ed in tega ni notri (ta je za py 2.5).

Zgodovina sprememb…

BlueRunner ::

Take "bolj advanced" zadeve niso stvar programskega jezika ampak bazičnega znanja programiranja - matematika in matematična logika, algoritmi, ... Jezik je pa samo orodje, da potem računalniku pojasniš kakšen postopek naj izvede.

"[[bisect_left(node_index, n) for n in tr] for tr in triangles]"

se v slovenščini zapiše kot: "za vsako vrednost starega indeksa točke v vseh trikotnikih najdi njen nov indeks v polju obstoječih točk in jo zamenjaj z novo vrednostjo".

Ko pogruntaš kaj želiš narediti, potem ni več nobena umetnost to zapisati v sintakso nekega drugega jezika, ki ga znaš govoriti. Angleščino, Python ali pa C.

Ko pogruntaš kako narediti dekonstrukcijo problema na manjše korake in nato optimalno rešiti vsak posamezen korak, postaneš dober programer. Kako se tega naučiti, pa vprašaj koga drugega. Jaz še sam zase ne vem, kdaj mi je to prišlo v kri.

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Resne težave z razumevanjem osnov programiranja (strani: 1 2 )

Oddelek: Programiranje		8016284 (12796) RatedR
»

Predstavitev dvojiškega drevesa z seznamom

Oddelek: Programiranje		141892 (1492) ktka
»

Python - pomoč!

Oddelek: Programiranje		71181 (1017) lknix
»

[Python] učenje

Oddelek: Programiranje		372646 (1943) Isotropic
»

python problem

Oddelek: Programiranje		131442 (1182) Isotropic

Več podobnih tem