Python: pop() probleem

[Verwijderd]

Beste tweakers

Voor een practicum van informatica moeten wij een programma schrijven.
Daarbij moet er uit een set een random waarde geselecteerd, verwijdert en teruggegeven worden.
Ideaal voor de pop()-functie zou je denken, maar dit levert bij mij problemen op, omdat het om een
of andere reden altijd de "eerste" waarde uit de set pakt dus helemaal niet random.
Ik werk met python 2.7, bij voorbaat dank

uit de pythondocumentatie:
s.pop() remove and return an arbitrary element from s; raises KeyError if empty

set1 = {(5,2),(4,5),(7,8),(9,5)}
set1.pop()
=> geeft altijd eerst (5,2), dan (4,5) enzo verder

[FrameWork.]

Komt het wellicht doordat je geen parameter meegeeft aan pop?

Uit de documentatie (2.7.4):

Remove the item at the given position in the list, and return it. If no index is specified, a.pop() removes and returns the last item in the list.

Bron

[ValHallASW]

Verwijderd schreef op zaterdag 04 mei 2013 @ 12:27:
s.pop() remove and return an arbitrary element from s; raises KeyError if empty

An arbitrary element betekent dat het 'een' (verder niet gedefiniëerd, maar dus óók niet als 'random' gedefiniëerd!) element. Dat komt omdat een set een lijst van unieke elementen is, zonder volgorde (je kunt bv. niet set1[0] opvragen).

Het makkelijkste is om je set naar een list te converteren, en dáár .pop() op aan te roepen, met een random index:

code:

>>> [].pop.__doc__
'L.pop([index]) -> item -- remove and return item at index (default last).\nRaises IndexError if list is empty or index is out of range.'
>>> import random
>>> random.randint.__doc__
'Return random integer in range [a, b], including both end points.\n        '

[Verwijderd]

FrameWork. schreef op zaterdag 04 mei 2013 @ 12:32:
Komt het wellicht doordat je geen parameter meegeeft aan pop?

Uit de documentatie (2.7.4):


[...]


Bron

Neen, hier lag het niet aan, omdat dit het geval is voor lijsten (ik was hier ook een tijdje achter aan het zoeken ).

@VallHallACW bedankt het heeft mijn probleem opgelost . Wel een beetje onduidelijk geschreven
vind ik zo, maar bedankt voor de verheldering

[CyBeR]

Verwijderd schreef op zaterdag 04 mei 2013 @ 12:27:
Ideaal voor de pop()-functie zou je denken, maar dit levert bij mij problemen op, omdat het om een
of andere reden altijd de "eerste" waarde uit de set pakt dus helemaal niet random.

En dat zou ook helemaal niet random moeten zijn want dan werkt het hele principe van een ordered list niet meer.

Pop werkt namelijk in combinatie met push. Push zet items in je lijst, Pop haalt ze er weer uit. In welke volgorde ligt aan het soort lijst: FIFO (first in, first out: eerst gepushte item wordt als eerst gepopt) of LIFO (last in, first out: laatst gepushte item wordt als eerst gepopt.)

Random poppen heeft ook z'n nut maar dat moet je wel even expliciet doen dan.

[Blubber]

Verwijderd schreef op zaterdag 04 mei 2013 @ 12:27:
Beste tweakers

Voor een practicum van informatica moeten wij een programma schrijven.
Daarbij moet er uit een set een random waarde geselecteerd, verwijdert en teruggegeven worden.
Ideaal voor de pop()-functie zou je denken, maar dit levert bij mij problemen op, omdat het om een
of andere reden altijd de "eerste" waarde uit de set pakt dus helemaal niet random.
Ik werk met python 2.7, bij voorbaat dank

uit de pythondocumentatie:
s.pop() remove and return an arbitrary element from s; raises KeyError if empty

set1 = {(5,2),(4,5),(7,8),(9,5)}
set1.pop()
=> geeft altijd eerst (5,2), dan (4,5) enzo verder

Jij gebruikt een set, dat type heeft (net zoals in de wiskunde) geen ordering semantiek. De volgorde van de elementen is dus simpelweg niet gedefinieerd (dus ook niet random, want dat impliceert dat er een volgorde is!). Als je pop() gebruikt krijg je een arbitrair element terug volgende de documentatie.

Het element dat pop returned is afhankelijk van het type. Een set is namelijk een dictionry waarbij de values als key gebruikt worden. Wat pop returned is afhankelijk van de hash van de elementen, en dat is afhankelijk van het type. Bij integers is de hash het getal zelf, bij objecten (zoals tuples) het geheugenadres. Je kunt de hash zien met de hash() functie (e.g. hash(2) = 2).

Er is nooit een manier om dingen ongesorteerd op te slaan, in de praktijk zal die set() het element met de laagste hash() returnen, maar dat is dus afhankelijk van het type en de volgorde van object creatie!

Lang verhaal kort, jouw set heeft geen volgorde. Zoals hierboven genoemd kun je beter een list gebruiken en die (al dan niet) in-place shufflen.

Edit: bij nader inzien, dit is denk ik mooier:

Python:

import random
set1 = {(5,2),(4,5),(7,8),(9,5)}
random.sample(set1, 1)

[ Voor 29% gewijzigd door Blubber op 06-05-2013 10:07 ]

[djc]

Blubber schreef op maandag 06 mei 2013 @ 09:49:
Het element dat pop returned is afhankelijk van het type. Een set is namelijk een dictionry waarbij de values als key gebruikt worden. Wat pop returned is afhankelijk van de hash van de elementen, en dat is afhankelijk van het type. Bij integers is de hash het getal zelf, bij objecten (zoals tuples) het geheugenadres. Je kunt de hash zien met de hash() functie (e.g. hash(2) = 2).

Dat is niet helemaal waar. De Python-implementatie van een set lijkt op de implementatie van dict, maar dan min of meer zonder values (dus alleen de keys). En bij objecten is de hash *niet* het geheugenadres; het idee van de hash is dat verschillende objecten met dezelfde waarde dezelfde hash zouden moeten krijgen. Daarmee is gebruik van het adres in geheugen dus ongeschikt als algoritme voor hash(). Bijvoorbeeld:

Python:

>>> hash(1)
1
>>> hash(13)
13
>>> hash('abc')
1453079729188098211
>>> c = 'abc'
>>> hash(c)
1453079729188098211
>>> id(c)
140515314644912

(Laten zien dat een ander str-object met dezelfde waarde een andere geheugenadres kan krijgen is iets lastiger, door de string interning-functionaliteit in CPython.)

Overigens ben ik het wel met je eens dat de random.sample() oplossing hier het netst lijkt.

[Blubber]

djc schreef op maandag 06 mei 2013 @ 11:25:
[...]
Dat is niet helemaal waar. De Python-implementatie van een set lijkt op de implementatie van dict, maar dan min of meer zonder values (dus alleen de keys). En bij objecten is de hash *niet* het geheugenadres; het idee van de hash is dat verschillende objecten met dezelfde waarde dezelfde hash zouden moeten krijgen. Daarmee is gebruik van het adres in geheugen dus ongeschikt als algoritme voor hash(). Bijvoorbeeld:

Python:

>>> hash(1)
1
>>> hash(13)
13
>>> hash('abc')
1453079729188098211
>>> c = 'abc'
>>> hash(c)
1453079729188098211
>>> id(c)
140515314644912

Je hebt inderdaad gelijk, hash() is niet gelijk aan het geheugen adres. Maar dat was niet echt mijn punt.

[ Voor 39% gewijzigd door Blubber op 06-05-2013 12:36 ]