Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #24822
| Path | csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail |
|---|---|
| Return-Path | <miheer.dew@gmail.com> |
| 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; 'context': 0.05; 'objects,': 0.07; 'omit': 0.07; 'dict': 0.09; 'integers': 0.09; 'to:addr:python.list': 0.09; 'to:addr:tim.thechases.com': 0.09; 'to:name:tim chase': 0.09; 'cc:addr:python-list': 0.10; 'assume': 0.11; '(direct': 0.16; 'arbitrarily': 0.16; 'dictionaries': 0.16; 'disk.': 0.16; 'means.': 0.16; 'range.': 0.16; 'received:209.85.216.53': 0.16; 'wrote:': 0.17; 'stefan': 0.17; 'tim': 0.18; '>>>': 0.18; 'module': 0.19; 'define': 0.20; 'sort': 0.21; 'large,': 0.22; 'parse': 0.22; "i'd": 0.22; 'example': 0.23; 'matching': 0.23; 'cc:no real name:2**0': 0.24; 'cc:2**1': 0.24; 'cc:addr:python.org': 0.25; 'header:In-Reply-To:1': 0.25; 'first,': 0.27; 'transition': 0.27; 'message-id:@mail.gmail.com': 0.27; '>>>>': 0.29; 'chase': 0.29; 'large.': 0.29; 'could': 0.32; 'right?': 0.33; 'subject:data': 0.33; 'received:google.com': 0.34; 'generic': 0.35; 'pm,': 0.35; 'received:209.85': 0.35; 'something': 0.35; 'there': 0.35; 'depends': 0.36; 'should': 0.36; 'too': 0.36; 'two': 0.37; 'rather': 0.37; 'received:209': 0.37; 'received:209.85.216': 0.37; 'subject:: ': 0.38; 'store': 0.38; 'mean': 0.38; 'things': 0.38; 'header:Received:5': 0.40; 'help': 0.40; 'identify': 0.61; 'between': 0.63; 'different': 0.63; 'information': 0.63; 'more': 0.63; 'reached': 0.65; 'jul': 0.65; 'obtained': 0.71; 'state.': 0.71; 'grow': 0.74; 'upper': 0.75; 'subject:Best': 0.91 |
| DKIM-Signature | v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=S327SntBH9t7VncI1U6WI4zyoIk83utRSMM0pyG9fk8=; b=fSKS7v626ziUAzprGsBpQJDpJ5+I37BdoI7FihxzOeaRzJv0c9WK473NLlBFk8Nn3C 0Tv+xUk0ECPgJeENo88kirGeoKYJb9UZ94kmnSf8GBlf5TXZyh8L2wQXRHO1D4mcPWha e2QpA4owvgcu5QoMduS4zdlmzURErKIcDhIqpBwqyYiJ76FIyh8K6ybVmnMzmbjed4yK VKYWgsGn+kNXmaZREjn70uB9w7ShV2nkrQKXTYZXKOKFufgjIWy8RrFd+XRrwpgzJy3A lRzXPSQ/9UDXrFI6nBKEzeR0Bba6QQ39SG/9ZlHjg9YYcF4S99AztB/ttWnT6GiaFii8 QeZA== |
| MIME-Version | 1.0 |
| In-Reply-To | <4FF3044A.9060206@tim.thechases.com> |
| References | <CACA+676A=G=3+wvaHw3H0LAo2cghztXo4+9ORR73CXBOOpW0ZQ@mail.gmail.com> <jsukoe$aui$1@dough.gmane.org> <CACA+677Kz_6OnYpQQz7MLqdikD_Oe1XHGm8EDjZM+kwH35T2Aw@mail.gmail.com> <4FF3044A.9060206@tim.thechases.com> |
| Date | Tue, 3 Jul 2012 20:38:05 +0530 |
| Subject | Re: Best data structure for DFS on large graphs |
| From | Miheer Dewaskar <miheer.dew@gmail.com> |
| To | Tim Chase <python.list@tim.thechases.com> |
| Content-Type | text/plain; charset=ISO-8859-1 |
| Cc | python-list@python.org, Stefan Behnel <stefan_ml@behnel.de> |
| X-BeenThere | python-list@python.org |
| X-Mailman-Version | 2.1.12 |
| Precedence | list |
| List-Id | General discussion list for the Python programming language <python-list.python.org> |
| List-Unsubscribe | <http://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 | <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1747.1341328088.4697.python-list@python.org> (permalink) |
| Lines | 51 |
| NNTP-Posting-Host | 2001:888:2000:d::a6 |
| X-Trace | 1341328088 news.xs4all.nl 6875 [2001:888:2000:d::a6]:59987 |
| X-Complaints-To | abuse@xs4all.nl |
| Xref | csiph.com comp.lang.python:24822 |
Show key headers only | View raw
On Tue, Jul 3, 2012 at 8:10 PM, Tim Chase <python.list@tim.thechases.com> wrote: > On 07/03/12 08:39, Miheer Dewaskar wrote: >> On Tue, Jul 3, 2012 at 4:53 PM, Stefan Behnel <stefan_ml@behnel.de> wrote: >>> >>> Miheer Dewaskar, 03.07.2012 13:11: >>>> I am not sure,but if there are large number of states Dictionaries wont >>>> help much right? >>> >>> Dicts are fast for lookup, not for searching. >>> >> What do you mean by searching in the context of Dicts? > > It took me a while to parse Stefan's post, and I *think* he means > that key-indexing (direct lookup) is fast O(1), and that by > "searching" he means something like "find all keys/values matching > property $FOO" such as between a range. > > One of the important things you omit is how you define "large". Is > this a couple thousand? Hundreds of thousands? Millions? I want it to be a generic Game solver.So the number of states depends on the game. For a simple tic-tac-toe the upper bound is 3^9 states.But for more complex games it could be much larger. I would like to assume that the number of states can grow arbitrarily large. > Also, what sort of information are you keeping in the state? Just > available transitions? Or do you want additional metadata? If it's > just transition mappings (A->B) rather than complex objects, I'd try > using a dict first, and if it's too large, I'd reach for the > "anydbm" module to store them to disk. The state just has 'state data'.The transitions are obtained by functions analyzing the state. So that I should not be able to identify between two same states that have been reached by different means. For example in the tic-tac-toe game the states can be a 3x3 box of integers 0 -> unoccupied 1 -> x 2-> o ( (2,0,1), o - x (1,1,0), -> x x - (2,0,0) ) o - - -- Miheer Dewaskar
Back to comp.lang.python | Previous | Next | Find similar | Unroll thread
Re: Best data structure for DFS on large graphs Miheer Dewaskar <miheer.dew@gmail.com> - 2012-07-03 20:38 +0530
csiph-web