Re: generate De Bruijn sequence memory and string vs lists

Path	csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder3.xlned.com!newsfeed.xs4all.nl!newsfeed4a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path	<vincent@vincentdavis.com>
X-Original-To	python-list@python.org
Delivered-To	python-list@mail.python.org
X-Spam-Status	OK 0.003
X-Spam-Evidence	'H': 0.99; 'S': 0.00; 'string': 0.09; 'append': 0.09; 'compact': 0.09; 'occurrences': 0.09; 'subject:string': 0.09; 'cc:addr:python-list': 0.11; 'jan': 0.12; 'wrote': 0.14; '(something': 0.16; '23,': 0.16; 'gmail.': 0.16; 'less,': 0.16; 'index': 0.16; 'wrote:': 0.18; 'replacing': 0.19; 'thu,': 0.19; 'seems': 0.21; 'memory': 0.22; 'cc:addr:python.org': 0.22; 'issue,': 0.24; 'cc:2**0': 0.24; '>': 0.26; 'equivalent': 0.26; 'header:In-Reply-To:1': 0.27; 'function': 0.29; 'am,': 0.29; 'message-id:@mail.gmail.com': 0.30; 'url:mailman': 0.30; 'ok.': 0.31; 'url:python': 0.33; 'guess': 0.33; 'received:209.85': 0.35; 'subject:lists': 0.35; 'received:google.com': 0.35; 'i.e.': 0.36; 'sequence': 0.36; 'url:listinfo': 0.36; 'url:org': 0.36; 'received:209': 0.37; 'sure': 0.39; 'url:mail': 0.40; 'dave': 0.60; 'length': 0.61; 'more': 0.64; 'holding': 0.65; 'angel': 0.91
X-Google-DKIM-Signature	v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=LSt4MHK+xftX/pvUqew/vKs+kdqzMxS+T4gnSuMmXoc=; b=acbtB8fRbq7PEy5dyOoVBicCyEuj/Eq9q+h/y5nLTqIMMrSn5qLPPfoFk5XLYFiu1U 8Dp6C/9YWKQpUT/hUPVXle6unS+k4CXzkDXHsVBnKVwco1BT1GEZQQJQv2IO7oqwnWZS 5Ej/1xmV3ujrS0lXkZBOmLlNVOK3TDm7MtzOkmbel5GsYJPF8qucPCjXloDWB/6gxnID 8JO3wa06oLzLErhbzr6b01shtJ/V8N//XTKxO92Kefezy0BUo5PnECWhpT+Ox/AHouwj KDKbhOQ3xcEP9QfLYxRzfads6JWJivBTQp1wzzliKpq2d7V+a0KbHQnakGPOyH97xGPb oJ7Q==
X-Gm-Message-State	ALoCoQkiWWvhmw5GTaedaAMKuf4WmjEDrf0Xpoq52xFN1gAYRCyvNv+FsLbjPzHFfNuJl578PsHm
X-Received	by 10.182.48.130 with SMTP id l2mr7559648obn.44.1390497061156; Thu, 23 Jan 2014 09:11:01 -0800 (PST)
MIME-Version	1.0
In-Reply-To	<lbrf82$fb3$1@ger.gmane.org>
References	<CALyJZZVU+j64Jn7fqqzLmwW+KcM=43UMKjo=HW7umnq8MSP2Uw@mail.gmail.com> <lbrf82$fb3$1@ger.gmane.org>
From	Vincent Davis <vincent@vincentdavis.net>
Date	Thu, 23 Jan 2014 11:10:41 -0600
Subject	Re: generate De Bruijn sequence memory and string vs lists
To	Dave Angel <davea@davea.name>
Content-Type	multipart/alternative; boundary=089e0160b3dc64551304f0a6530b
Cc	"python-list@python.org" <python-list@python.org>
X-BeenThere	python-list@python.org
X-Mailman-Version	2.1.15
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.5903.1390500573.18130.python-list@python.org> (permalink)
Lines	88
NNTP-Posting-Host	2001:888:2000:d::a6
X-Trace	1390500573 news.xs4all.nl 2954 [2001:888:2000:d::a6]:33477
X-Complaints-To	abuse@xs4all.nl
Xref	csiph.com comp.lang.python:64626

Show key headers only | View raw

[Multipart message — attachments visible in raw view] - view raw

On 1/23/14, 10:18 AM, Dave Angel wrote:
> (something about your message seems to make it unquotable)

Not sure why the message was not quotable. I sent it using gmail.

On 1/23/14, 10:18 AM, Dave Angel wrote:
> 64gig is 4^18, so you can forget about holding a string of size 4^50

I guess I will have to buy more memory or be happy with less, 4**17 would
be ok.

On 1/23/14, 10:18 AM, Dave Angel wrote:
> If memory size is your issue,  why not make the function a
>   generator,  by replacing the append with a yield?

I plan to use the sequence as an index to count occurrences of sequences of
length n. A generator is equivalent to using itertools.permutations (i
think that the right itertool). My thought is that I don't have to store
each individual (sub)sequence since the De Brujin sequence contains all of
them. i.e. it is a compact representation of every sequence generated by
itertools.permutations.

Vincent Davis

On Thu, Jan 23, 2014 at 10:18 AM, Dave Angel <davea@davea.name> wrote:
>
>  Vincent Davis <vincent@vincentdavis.net> Wrote in message:
> >
> (something about your message seems to make it unquotable)
>
> 64gig is 4^18, so you can forget about holding a string of size 4^50
>
> If memory size is your issue,  why not make the function a
>  generator,  by replacing the append with a yield?
>
>
> --
> DaveA
>
> --
> https://mail.python.org/mailman/listinfo/python-list

Back to comp.lang.python | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: generate De Bruijn sequence memory and string vs lists Vincent Davis <vincent@vincentdavis.net> - 2014-01-23 11:10 -0600
  Re: generate De Bruijn sequence memory and string vs lists Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2014-01-24 21:29 +1300
    Re: generate De Bruijn sequence memory and string vs lists Vincent Davis <vincent@vincentdavis.net> - 2014-01-24 07:20 -0600
    Re: generate De Bruijn sequence memory and string vs lists Greg Ewing <greg.ewing@canterbury.ac.nz> - 2014-01-25 18:11 +1300

csiph-web