Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #62297

Re: Struggling for inspiration with lists

Show key headers only | View raw

----- Original Message -----
> Hi
> 
> I have a list of data that presents as:
> 
> timestamp: value
> 
> Timestamps are used solely to determine the sequence of items in the
> list.
> 
> I want to find the longest repeated sequence of values in the list.
> Example, in the following list:
> 
> data = { 0: "d", 1: "x", 2: "y", 3: "t", 4: "d", 5: "y", 77: "g"' 78:
> "h", 79: "x", 80: "y", 206: "t", 210: "d", 211: "x" }
> 
> I would pull out the sequence x-y-t-d (starting at 1 and 79)
> 
> I need to keep the timestamp / data association because I need to
> generate output that identifies (a) the longest repeated sequence (b)
> how
> many elements in the longest repeated sequence (c) at what timestamps
> each occurrence started.
> 
> I'm not sure of the best way, programatically, to aproach this task,
> which means I'm unsure whether eg a list of tuples ( time, data ) or
> an
> OrderedDict keyed on the timestamp is the best starting point.
> 
> I can make a list of tuples using:
> 
> d = [ (k,v) for k,v in data ]
> 
> and with the list of tuples, I can do something like:
> 
> d.sort( key=lambda tup: tup[0] )
> 
> max_start_a = 0
> max_start_b = 0
> max_len = 0
> i = 0
> 
> while i < len( d ):
> 
>   j = i + 1
> 
>   while j < len( d ):
> 
>     o = 0
> 
>     while j+o < len( d ) and d[i+o][1] == d[j+o][1]:
> 
>       o += 1
> 
>       if o > max_len:
> 
>         max_len = 0
>         max_start_a = i
>         max_start_b = j
> 
>     j += 1
> 
>   i += 1
> 
> print d[max_start_a][0], d[max_start_b][0], max_len
> 
> Is there a better way to do this?
> 
> --
> Denis McMahon, denismfmcmahon@gmail.com

Hi,

Depends on what you're meaning by better.
If you mean quicker, it seems there is an algorithm in O(n). http://stackoverflow.com/questions/11090289/find-longest-repetitive-sequence-in-a-string
You'll need a little bit of work to move from dict / to string / to dict but that shouldn't be a problem.

If you didn't mean quicker, I have no idea. If your current code is working, I don't see how it would such wrong that you'd need to change it.

JM


-- IMPORTANT NOTICE: 

The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

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

Thread

Re: Struggling for inspiration with lists Jean-Michel Pichavant <jeanmichel@sequans.com> - 2013-12-18 13:38 +0100

csiph-web