Quantcast

Get item from set

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Get item from set

foobar31415
Hi group,

I have a very simple about sets. This is a minimal example:

#!/usr/bin/python
class x():
        def __init__(self, y):
                self.__y = y
        def __eq__(self, other):
                return self.__y == other.__y
        def __hash__(self):
                return hash(self.__y)

a = x("foo")
s = set([x("bar"), x("moo"), a])
z = x("foo")
print("z = ", z)
print(s)
for i in s:
        print(i, i == a, i is a, i == z, i is z)

The problem is: two instances of x() are equal (__eq__ returns true),
but they are not identical. I have an equal element ("z"), but want to
get the *actual* element ("a") in the set. I.d. in the above example,
i'd like something like:

print(s.getelement(z) is a)
True

Is there something like the "getelement" function? How can I do what I want?

Kind regards,
Johannes

--
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$[hidden email]>
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

foobar31415
Johannes Bauer schrieb:

> Is there something like the "getelement" function? How can I do what I want?

One side note: The obvious trivial solution:

def findset(s, e):
        for i in s:
                if e == i:
                        return i
        return None

is because of its complexity of O(n) against the native O(log n) out of
the question...

Kind regards,
Johannes

--
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$[hidden email]>
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Peter Otten
In reply to this post by foobar31415
Johannes Bauer wrote:

> I have a very simple about sets. This is a minimal example:

> The problem is: two instances of x() are equal (__eq__ returns true),
> but they are not identical. I have an equal element ("z"), but want to
> get the *actual* element ("a") in the set. I.d. in the above example,
> i'd like something like:
>
> print(s.getelement(z) is a)
> True
>
> Is there something like the "getelement" function? How can I do what I
> want?

Here's a trick to find the actual element. I think Raymond Hettinger posted
an implementation of this idea recently, but I can't find it at the moment.

class X:
    def __init__(self, y):
        self.__y = y
    def __eq__(self, other):
        try:
            return self.__y == other.__y
        except AttributeError:
            return NotImplemented
    def __hash__(self):
        return hash(self.__y)

a = X("foo")
s = set([X("bar"), X("moo"), a])
z = X("foo")

class Grab:
    def __init__(self, value):
        self.search_value = value
    def __hash__(self):
        return hash(self.search_value)
    def __eq__(self, other):
        if self.search_value == other:
            self.actual_value = other
            return True
        return False

assert a == z
assert a is not z
grab = Grab(z)
grab in s
assert grab.actual_value is a

Peter
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

foobar31415
Peter Otten schrieb:

> class Grab:
>     def __init__(self, value):
>         self.search_value = value
>     def __hash__(self):
>         return hash(self.search_value)
>     def __eq__(self, other):
>         if self.search_value == other:
>             self.actual_value = other
>             return True
>         return False
>
> assert a == z
> assert a is not z
> grab = Grab(z)
> grab in s
> assert grab.actual_value is a

Wow, this is truly amazing! I'd never have come up with that solution.
Just wonderful, thank you very much! :-))

Kind regards,
Johannes

--
"Meine Gegenklage gegen dich lautet dann auf bewusste Verlogenheit,
verlästerung von Gott, Bibel und mir und bewusster Blasphemie."
         -- Prophet und Visionär Hans Joss aka HJP in de.sci.physik
                         <48d8bf1d$0$7510$[hidden email]>
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

bearophileHUGS
In reply to this post by Peter Otten
Peter Otten:

> [...] I think Raymond Hettinger posted
> an implementation of this idea recently, but I can't find it at the moment.
> [...]
> class Grab:
>     def __init__(self, value):
>         self.search_value = value
>     def __hash__(self):
>         return hash(self.search_value)
>     def __eq__(self, other):
>         if self.search_value == other:
>             self.actual_value = other
>             return True
>         return False
>
> assert a == z
> assert a is not z
> grab = Grab(z)
> grab in s
> assert grab.actual_value is a

That's very nice, and I may add to my tricks. Probably Raymond has
more brain than me :-)

But some other times you may accept to change the class and the set/
dict, making it tell apart the keys only when they are different
object:

class Some(object):
    def __init__(self, y):
        self._y = y
    def __eq__(self, other):
        return self is other
    def __hash__(self):
        return hash(self._y)

Now your set/dict keeps all the instances, even when they contain the
same _y.

Bye,
bearophile
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Aahz
In reply to this post by Peter Otten
In article <gt1kb7$jqg$03$[hidden email]>,
Peter Otten  <[hidden email]> wrote:
>
>Here's a trick to find the actual element. I think Raymond Hettinger posted
>an implementation of this idea recently, but I can't find it at the moment.

Your code is inverted from Raymond's:

http://code.activestate.com/recipes/499299/

class _CaptureEq:
    'Object wrapper that remembers "other" for successful equality tests.'
    def __init__(self, obj):
        self.obj = obj
        self.match = None
    def __eq__(self, other):
        result = (self.obj == other)
        if result:
            self.match = other
        return result
    # support hash() or anything else needed by __ contains__
    def __getattr__(self, name):  
        return getattr(self.obj, name)

def get_equivalent(container, item, default=None):
    '''Gets the specific container element matched by: "item in container".

    Useful for retreiving a canonical value equivalent to "item".  For
    example, a caching or interning application may require fetching a
    single representativ e instance from many possible equivalent
    instances).

    >>> get_equivalent(set([1, 2, 3]), 2.0)       # 2.0 is equivalent to 2
    2
    >>> get_equivalent([1, 2, 3], 4, default=0)
    0
    '''
    t = _CaptureEq(item)
    if t in container:
        return t.match
    return default
--
Aahz ([hidden email])           <*>         http://www.pythoncraft.com/

"If you think it's expensive to hire a professional to do the job, wait
until you hire an amateur."  --Red Adair
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Terry Reedy
In reply to this post by foobar31415
Johannes Bauer wrote:

> Hi group,
>
> I have a very simple about sets. This is a minimal example:
>
> #!/usr/bin/python
> class x():
> def __init__(self, y):
> self.__y = y
> def __eq__(self, other):
> return self.__y == other.__y
> def __hash__(self):
> return hash(self.__y)
>
> a = x("foo")
> s = set([x("bar"), x("moo"), a])
> z = x("foo")
> print("z = ", z)
> print(s)
> for i in s:
> print(i, i == a, i is a, i == z, i is z)
>
> The problem is: two instances of x() are equal (__eq__ returns true),
> but they are not identical. I have an equal element ("z"), but want to
> get the *actual* element ("a") in the set. I.d. in the above example,
> i'd like something like:
>
> print(s.getelement(z) is a)
> True
>
> Is there something like the "getelement" function? How can I do what I want?

No. but you pratically wrote it: in your code, when i == z, then i is
the element you want.

def getelement(sset, item):
   for i in sset:
     if i == item: return i

The only use for this is see, though, is getting the representative of
an equivalence class from any member thereof.

tjr

--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Peter Otten
In reply to this post by Aahz
Aahz wrote:

> In article <gt1kb7$jqg$03$[hidden email]>,
> Peter Otten  <[hidden email]> wrote:
>>
>>Here's a trick to find the actual element. I think Raymond Hettinger
>>posted an implementation of this idea recently, but I can't find it at the
>>moment.
>
> Your code is inverted from Raymond's:

I can't see the inversion.
 
> http://code.activestate.com/recipes/499299/

Thanks for providing the reference.

Peter

--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Raymond Hettinger-2
In reply to this post by bearophileHUGS
[[hidden email]]

> But some other times you may accept to change the class and the set/
> dict, making it tell apart the keys only when they are different
> object:
>
> class Some(object):
>     def __init__(self, y):
>         self._y = y
>     def __eq__(self, other):
>         return self is other
>     def __hash__(self):
>         return hash(self._y)
>
> Now your set/dict keeps all the instances, even when they contain the
> same _y.

David Mertz suggested something like this in one of his Developer
Works
articles.  Essentially, he was describing an IdentityDict or
IdentitySet.

I don't really see how those would be useful in regular python.
Why treat equal but not identical objects as distinct in an
environment where you have so little control over object identity?

>>> s = IdentitySet(['abc'])
>>> e = 'ab' + 'c'   # distinct element, equal to 'abc', but not identical
>>> e in s
False

For the most part, we can't even count on equal integers having the
same identity:

>>> x = 1000
>>> y = 1001 - 1
>>> [id(o) for o in (x, y)]
[16675616, 16676240]

I'm curious about your use cases for the Some() class in conjunction
with a dict or set.


Raymond
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Aahz
In reply to this post by Peter Otten
In article <gt8v37$kib$03$[hidden email]>,
Peter Otten  <[hidden email]> wrote:

>Aahz wrote:
>> In article <gt1kb7$jqg$03$[hidden email]>,
>> Peter Otten  <[hidden email]> wrote:
>>>
>>>Here's a trick to find the actual element. I think Raymond Hettinger
>>>posted an implementation of this idea recently, but I can't find it at the
>>>moment.
>>
>> Your code is inverted from Raymond's:
>
>I can't see the inversion.

You were wrapping the objects inserted into the set; Raymond's trick
involved only wrapping the comparison object.  It's therefore much more
convenient.
--
Aahz ([hidden email])           <*>         http://www.pythoncraft.com/

"If you think it's expensive to hire a professional to do the job, wait
until you hire an amateur."  --Red Adair
--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Peter Otten
Aahz wrote:

> In article <gt8v37$kib$03$[hidden email]>,
> Peter Otten  <[hidden email]> wrote:
>>Aahz wrote:
>>> In article <gt1kb7$jqg$03$[hidden email]>,
>>> Peter Otten  <[hidden email]> wrote:
>>>>
>>>>Here's a trick to find the actual element. I think Raymond Hettinger
>>>>posted an implementation of this idea recently, but I can't find it at
>>>>the moment.
>>>
>>> Your code is inverted from Raymond's:
>>
>>I can't see the inversion.
>
> You were wrapping the objects inserted into the set; Raymond's trick
> involved only wrapping the comparison object.  It's therefore much more
> convenient.

I think you are misreading my code. I took the items (of class X) as they
were specified by the OP.

The reason I changed their __eq__() method is not that I did not understand
Raymond's trick, but rather a quirk in the set's item lookup:

>>> class A(object):
...     def __init__(self, value):
...             self.value = value
...     def __hash__(self):
...             return hash(self.value)
...     def __eq__(self, other):
...             return self.value == other.value
...
>>> item = A("a")
>>> container = map(A, "abc")
>>> from get_equivalent import get_equivalent
TestResults(failed=0, attempted=0)

get_equivalent() is Raymond's implementation from the recipe. Let's try it:

>>> get_equivalent(container, item)
<__main__.A object at 0x2091e50>
>>> _ is not item
True

Works. Now the same with a set:

>>> container = set(container)
>>> print get_equivalent(container, item)
None

Oops.

wanted in some_list

performs wanted.__eq__(candidate)

where candidate is an item in the list.

wanted in some_set

tries

candidate.__eq__(wanted)

first. You must ensure that this fails in an orderly manner for

wanted.__eq__(candidate)

to be tried at all:

>>> def __eq__(self, other):
...     if not isinstance(other, A):
...             return NotImplemented
...     return self.value == other.value
...
>>> A.__eq__ = __eq__
>>> print get_equivalent(container, item)
<__main__.A object at 0x2091e50>
>>> _ is not item
True

Peter

--
http://mail.python.org/mailman/listinfo/python-list
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Get item from set

Aahz
In article <gt9t62$g6f$00$[hidden email]>,
Peter Otten  <[hidden email]> wrote:

>Aahz wrote:
>> In article <gt8v37$kib$03$[hidden email]>,
>> Peter Otten  <[hidden email]> wrote:
>>>Aahz wrote:
>>>> In article <gt1kb7$jqg$03$[hidden email]>,
>>>> Peter Otten  <[hidden email]> wrote:
>>>>>
>>>>>Here's a trick to find the actual element. I think Raymond Hettinger
>>>>>posted an implementation of this idea recently, but I can't find it at
>>>>>the moment.
>>>>
>>>> Your code is inverted from Raymond's:
>>>
>>>I can't see the inversion.
>>
>> You were wrapping the objects inserted into the set; Raymond's trick
>> involved only wrapping the comparison object.  It's therefore much more
>> convenient.
>
>I think you are misreading my code. I took the items (of class X) as they
>were specified by the OP.
>
>The reason I changed their __eq__() method is not that I did not understand
>Raymond's trick, but rather a quirk in the set's item lookup:

Gotcha -- thanks for the explanation!
--
Aahz ([hidden email])           <*>         http://www.pythoncraft.com/

"If you think it's expensive to hire a professional to do the job, wait
until you hire an amateur."  --Red Adair
--
http://mail.python.org/mailman/listinfo/python-list
Loading...