|
Hinnavaatlus
:: Foorum
:: Uudised
:: Ärifoorumid
:: HV F1 ennustusvõistlus
:: Pangalink
:: Telekavad
:: HV toote otsing
|
|
| autor |
|
Popp
Kreisi kasutaja
liitunud: 22.02.2006
|
12.04.2010 14:16:59
Python list |
|
|
Oletame, et mul on list, mis koosneb tupletest:
[(1, 2), (1, 3), (2, 3)]
Looks väikese arutelu, mille tulemusena ehk selguks kuidas on võimalik kõige kiiremini eemaldada sealt listist juhuslikult valitud elemente
Klassikaliselt näeks asi välja umbes niimoodi:
list = list(itertools.combinations(range(1,4), 2))
while len(list) > 1:
tuple = (random.randint(1, 4)), (random.randint(1, 4))
while tuple in list:
list.remove(tuple)
|
Antud näites koosneb list 3st elemendist, probleem tekib aga siis kui neid on näiteks 10 miljonit. Mind huvitab milline on kõige kiirem arvutusviis
|
|
| Kommentaarid: 67 loe/lisa |
Kasutajad arvavad: |
   |
:: |
0 :: |
1 :: |
54 |
|
| tagasi üles |
|
 |
telefoon
HV vaatleja
liitunud: 05.05.2003
|
|
12.04.2010 16:40:58
|
|
|
| Aga miks mitte genereerida suvaline täisarv vahemikus [0,listi pikkus) ja eemaldada vastav element?
|
|
| Kommentaarid: 7 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
0 :: |
7 |
|
| tagasi üles |
|
|
troglodyte
Kreisi kasutaja
liitunud: 09.08.2002
|
|
12.04.2010 18:39:36
|
|
|
Ma ei usu, et sa saad listist kiiremini kuidagi elemente eemaldada kui list.remove funktsiooni kasutades. Ainuke variant mida mina näen on keerulisemate andmestruktuuride kasutamine.
_________________
ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn |
|
| Kommentaarid: 34 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
0 :: |
34 |
|
| tagasi üles |
|
|
incx
HV kasutaja
liitunud: 10.11.2001
|
|
12.04.2010 18:58:10
Re: Python list |
|
|
while tuple in list:
list.remove(tuple) |
asemel võiks pigem olla
for i in range(list.count(tuple)):
list.remove(tuple) |
Ja tegelikult Pythoni built-in-ide overridemine üldiselt on ebaviisakas, mylist ja mytuple oleks parem stiil
Aga jah, listist elementide väljakorjamine kipub üldiselt lineaarse keerukusega olema, iga asja jaoks ikka vastav tööriist. http://wiki.python.org/moin/TimeComplexity kah abiks vahest. Rohkem eriti kommenteerida ei oskagi, ülesandepüstituses ikka väga palju lahti jäetud ja umbmääraselt kirjeldatud, kasvõi see, et kas list võib korduvaid väärtusi sisaldada.
_________________
I have never understood the female capacity to avoid a direct answer to any question.
-- Spock, "This Side of Paradise", stardate 3417.3 |
|
| Kommentaarid: 20 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
0 :: |
20 |
|
| tagasi üles |
|
|
Popp
Kreisi kasutaja
liitunud: 22.02.2006
|
|
13.04.2010 17:38:16
|
|
|
| troglodyte kirjutas: |
| Ma ei usu, et sa saad listist kiiremini kuidagi elemente eemaldada kui list.remove funktsiooni kasutades. Ainuke variant mida mina näen on keerulisemate andmestruktuuride kasutamine. |
Milliseid struktuure siin mõeldud on?
| incx kirjutas: |
| kas list võib korduvaid väärtusi sisaldada. |
Mõtlesin küll, et sai kõik välja öeldud, mis vaja. List ei tohi sisaldada korduvaid väärtusi (combinations funktsioon genereerib unikaalsed väärtused)
Ma ise mõtlesin, et peale igat kustutamist listi suurus mälus vist ei vähene. Kahjuks mul riistvaralähedase programmeerimisega kogemused puuduvad ehk keegi teab mismoodi võiks mälu kasutust optimeerida.
|
|
| Kommentaarid: 67 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
1 :: |
54 |
|
| tagasi üles |
|
|
troglodyte
Kreisi kasutaja
liitunud: 09.08.2002
|
|
13.04.2010 20:33:06
|
|
|
| Popp kirjutas: |
| Milliseid struktuure siin mõeldud on? |
Hash map (pythoni dict), igasugused puud (binary tree, red-black tree jms).
| Popp kirjutas: |
Mõtlesin küll, et sai kõik välja öeldud, mis vaja. List ei tohi sisaldada korduvaid väärtusi (combinations funktsioon genereerib unikaalsed väärtused)
|
Miks sul seal while tuple in list: list.remove(tuple) on? Ma lugesin sellest alguses välja, et list võiks korduvaid väärtusi sisaldada.
_________________
ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn |
|
| Kommentaarid: 34 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
0 :: |
34 |
|
| tagasi üles |
|
|
andreie
HV vaatleja
liitunud: 09.09.2006
|
|
14.04.2010 15:57:20
Re: Python list |
|
|
| Popp kirjutas: |
Oletame, et mul on list, mis koosneb tupletest:
Antud näites koosneb list 3st elemendist, probleem tekib aga siis kui neid on näiteks 10 miljonit. Mind huvitab milline on kõige kiirem arvutusviis |
Sõltuvalt sellest, kui palju kirjeid eemaldamisele kuulub, võib olla kõige odavam hoopis pidada täiendavat listi eemaldatud elementidest koos indeksitega.
_________________
Unix survives only because everyone else has done so badly. |
|
| Kommentaarid: 5 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
0 :: |
5 |
|
| tagasi üles |
|
|
Popp
Kreisi kasutaja
liitunud: 22.02.2006
|
|
14.04.2010 18:10:04
|
|
|
troglodyte, List ei sisalda ühtki korduvat väärtust.
andreie, samuti ei ole eemaldatud elementide eraldi listis hoidmine mõttekas minu arvates. Eemaldamisele kuuluvad lõpuks kõik elemendid
|
|
| Kommentaarid: 67 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
1 :: |
54 |
|
| tagasi üles |
|
|
matik
HV kasutaja
liitunud: 28.05.2008
|
|
15.04.2010 03:57:58
|
|
|
kui seal pole ühtegi korduvat väärtust, siis võiks olla map (dict) isegi kiirema indekseerimisega.
>>> mydict = {(1,2):None, (3,4):None}
>>> del mydict[(1,2)]
>>> mydict
{(3, 4): None}
samas ma pole kindel, kas tuplet hashitakse...
10 miljoni rea puhul võid teha oma andmetüübi 2 väljaga, ja üle kirjutada classi __hash__ meetodi
vt http://docs.python.org/reference/datamodel.html#object.__hash__
| tsitaat: |
| Ma ise mõtlesin, et peale igat kustutamist listi suurus mälus vist ei vähene. Kahjuks mul riistvaralähedase programmeerimisega kogemused puuduvad ehk keegi teab mismoodi võiks mälu kasutust optimeerida. |
pythonis saad sa forseerida garbage collecti, kui väga vaja on ja mälukasutus liiga suur on peale listide tühjendamist
>>> import gc
>>> gc.collect()
|
|
| tagasi üles |
|
|
troglodyte
Kreisi kasutaja
liitunud: 09.08.2002
|
|
15.04.2010 10:33:05
|
|
|
| matik kirjutas: |
| samas ma pole kindel, kas tuplet hashitakse... |
Tuple on hashitav, kui kõik tuple elemendid on hashitavad.
_________________
ph'nglui mglw'nafh Cthulhu R'lyeh wgah'nagl fhtagn |
|
| Kommentaarid: 34 loe/lisa |
Kasutajad arvavad: |
|
:: |
0 :: |
0 :: |
34 |
|
| tagasi üles |
|
|
|
:: KKK
:: otsing 
:: statistika
:: kasutajate nimekiri
:: kasutajate grupid
:: registreeri
teata moderaatorile
