Path: csiph.com!optima2.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!newsfeed.straub-nv.de!feed.xsnews.nl!fbe002.ams.xsnews.nl!ecngs!feeder.ecngs.de!border1.nntp.ams1.giganews.com!nntp.giganews.com!newsfeed.xs4all.nl!newsfeed8.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <ethan@stoneleaf.us>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.002
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'matches': 0.07; 'type,': 0.07; 'api': 0.09; 'dict': 0.09; 'from:addr:ethan': 0.09; 'from:addr:stoneleaf.us': 0.09; 'from:name:ethan furman': 0.09; 'lookup': 0.09; 'message-id:@stoneleaf.us': 0.09; '8bit%:32': 0.16; 'defer': 0.16; 'keys.': 0.16; 'mapping,': 0.16; 'subject:Mapping': 0.16; 'subject:key': 0.16; 'wrote:': 0.16; 'any,': 0.18; 'basically': 0.18; 'matching': 0.23; 'header:In- Reply-To:1': 0.24; 'header:User-Agent:1': 0.26; "skip:' 10": 0.28; 'behaviour': 0.29; 'hash': 0.29; '~ethan~': 0.29; 'candidate': 0.31; "can't": 0.32; 'problem': 0.33; "d'aprano": 0.33; 'instances': 0.33; 'steven': 0.33; 'mapping': 0.35; 'to:addr :python-list': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'received:10': 0.37; 'really': 0.37; 'requirement': 0.37; 'list.': 0.37; 'to:addr:python.org': 0.40; 'subject:with': 0.40; 'your': 0.60; 'lose': 0.63; 'due': 0.65; 'skip:\xe2 10': 0.70; 'application?': 0.84; 'received:10.1.10': 0.84
Date: Wed, 15 Jul 2015 23:31:08 -0700
From: Ethan Furman <ethan@stoneleaf.us>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Mapping, with sequence as key, wildcard and subsequence matching
References: <mailman.552.1437011478.3674.python-list@python.org> <55a72c8b$0$1671$c3e8da3$5496439d@news.astraweb.com> <85fv4oveb2.fsf@benfinney.id.au>
In-Reply-To: <85fv4oveb2.fsf@benfinney.id.au>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.20+
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.561.1437028279.3674.python-list@python.org>
Lines: 33
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1437028279 news.xs4all.nl 2853 [2001:888:2000:d::a6]:50291
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:93901

On 07/15/2015 10:53 PM, Ben Finney wrote:
> Steven D'Aprano <steve@pearwood.info> writes:

>> You can't use a dict for the mapping, not unless you're smarter than
>> me, due to the requirement to hash the keys.
>
> Dang. It's the mapping that I really need to solve, I think. A mapping
> that has a custom “does this candidate match any existing key” and
> “return the value for this key” to defer to the matching behaviour
> described above.
>
> Are those the ‘__contains__’, ‘__getitem__’ methods? What actually is
> the API of a mapping type, that would need to be customised for this
> application?

The problem is that potential key matches are found by hashes, and the hash of

   ('value1', ANY, 'next_value')

and

   ('value1, 'value2', 'next_value')

and

   ('value1', 'value3', 'next_value')

will not and cannot be the same.

If you fiddle with your object such that all instances hash to the same value then you lose the O(1) lookup for the dict -- you basically have a list.

--
~Ethan~