[Numpy-discussion] List/location of consecutive integers

Pierre GM pgmdevlist@gmail....
Fri May 22 15:15:19 CDT 2009


On May 22, 2009, at 12:31 PM, Andrea Gavana wrote:

> Hi All,
>
>    this should be a very easy question but I am trying to make a
> script run as fast as possible, so please bear with me if the solution
> is easy and I just overlooked it.
>
> I have a list of integers, like this one:
>
> indices = [1,2,3,4,5,6,7,8,9,255,256,257,258,10001,10002,10003,10004]
>
>> From this list, I would like to find out which values are consecutive
> and store them in another list of tuples (begin_consecutive,
> end_consecutive) or a simple list: as an example, the previous list
> will become:
>
> new_list = [(1, 9), (255, 258), (10001, 10004)]


Josef's and Chris's solutions are pretty neat in this case. I've been  
recently working on a more generic case where integers are grouped  
depending on some condition (equals, differing by 1 or 2...). A  
version in pure Python/numpy, the `Cluster` class is available in  
scikits.hydroclimpy.core.tools (hydroclimpy.sourceforge.net).  
Otherwise, here's a Cython version of the same class.
Let me know if it works. And I'm not ultra happy with the name, so if  
you have any suggestions...


cdef class Brackets:
     """
     Groups consecutive data from an array according to a clustering  
condition.

     A cluster is defined as a group of consecutive values differing  
by at most the
     increment value.

     Missing values are **not** handled: the input sequence must  
therefore be free
     of missing values.

     Parameters
     ----------
     darray : ndarray
         Input data array to clusterize.
     increment : {float}, optional
         Increment between two consecutive values to group.
         By default, use a value of 1.
     operator : {function}, optional
         Comparison operator for the definition of clusters.
         By default, use :func:`numpy.less_equal`.


     Attributes
     ----------
     inishape
         Shape of the argument array (stored for resizing).
     inisize
         Size of the argument array.
     uniques : sequence
         List of unique cluster values, as they appear in  
chronological order.
     slices : sequence
         List of the slices corresponding to each cluster of data.
     starts : ndarray
         Lists of the indices at which the clusters start.
     ends : ndarray
         Lists of the indices at which the clusters end.
     clustered : list
         List of clustered data.


     Examples
     --------
     >>> A = [0, 0, 1, 2, 2, 2, 3, 4, 3, 4, 4, 4]
     >>> klust = cluster(A,0)
     >>> [list(_) for _ in klust.clustered]
     [[0, 0], [1], [2, 2, 2], [3], [4], [3], [4, 4, 4]]
     >>> klust.uniques
     array([0, 1, 2, 3, 4, 3, 4])

     >>> x = [ 1.8, 1.3, 2.4, 1.2, 2.5, 3.9, 1. , 3.8, 4.2, 3.3,
     ...       1.2, 0.2, 0.9, 2.7, 2.4, 2.8, 2.7, 4.7, 4.2, 0.4]
     >>> Brackets(x,1).starts
     array([ 0,  2,  3,  4,  5,  6,  7, 10, 11, 13, 17, 19])
     >>> Brackets(x,1.5).starts
     array([ 0,  6,  7, 10, 13, 17, 19])
     >>> Brackets(x,2.5).starts
     array([ 0,  6,  7, 19])
     >>> Brackets(x,2.5,greater).starts
     array([ 0,  1,  2,  3,  4,  5,  8,  9, 10,
     ...    11, 12, 13, 14, 15, 16, 17, 18])
     >>> y = [ 0, -1, 0, 0, 0, 1, 1, -1, -1, -1, 1, 1, 0, 0, 0, 0, 1,  
1, 0, 0]
     >>> Brackets(y,1).starts
     array([ 0,  1,  2,  5,  7, 10, 12, 16, 18])

     """

     cdef readonly double increment
     cdef readonly np.ndarray data
     cdef readonly list _starts
     cdef readonly list _ends

     def __init__(Brackets self, object data, double increment=1,
                  object operator=np.less_equal):
         """
         """
         cdef int i, n, ifirst, ilast, test
         cdef double last
         cdef list starts, ends
         #
         self.increment = increment
         self.data = np.asanyarray(data)
         data = np.asarray(data)
         #
         n = len(data)
         starts = []
         ends = []
         #
         last = data[0]
         ifirst = 0
         ilast = 0
         for 1 <= i < n:
             test = operator(abs(data[i] - last), increment)
             ilast = i
             if not test:
                 starts.append(ifirst)
                 ends.append(ilast-1)
                 ifirst = i
             last = data[i]
         starts.append(ifirst)
         ends.append(n-1)
         self._starts = starts
         self._ends = ends

     def __len__(self):
         return len(self.starts)

     property starts:
         #
         def __get__(Brackets self):
             return np.asarray(self._starts)

     property ends:
         #
         def __get__(Brackets self):
             return np.asarray(self._ends)

     property sizes:
         #
         def __get__(Brackets self):
             return np.asarray(self._ends) - np.asarray(self._firsts)


     property slices:
         #
         def __get__(Brackets self):
             cdef int i
             cdef list starts = self._starts, ends = self._ends
             cdef list slices = []
             for 0 <= i < len(starts):
                 slices.append(slice(starts[i], ends[i]+1))
             return slices

     property clustered:
         #
         def __get__(self):
             cdef int i
             cdef list starts = self._starts, ends = self._ends
             cdef list groups = []
             cdef np.ndarray data = self.data
             for 0 <= i < len(starts):
                 groups.append(data[starts[i]:ends[i]+1])
             return groups

     property uniques:
         def __get__(self):
             return self.data[self.starts]

     def grouped_slices(self):
         """
     Returns a dictionary with the unique values of ``self`` as keys,  
and a list
     of slices for the corresponding values.

     See Also
     --------
     Brackets.grouped_limits
         that does the same thing
         """
         # Define shortcuts
         cdef int i, ifirst, n = len(self)
         cdef list starts = self._starts, ends = self._ends
         cdef np.ndarray data = self.data
         # Define new variables
         cdef list seen = []
         cdef double value
         cdef dict grouped = {}
         for 0 <= i < n:
             ifirst = starts[i]
             value = data[ifirst]
             if not (value in seen):
                 grouped[value] = []
                 seen.append(value)
             grouped[value].append(slice(ifirst, ends[i]+1))
         return grouped

     def grouped_limits(self):
         """
     Returns a dictionary with the unique values of ``self`` as keys,  
and a list
     of tuples (starting index, ending index) for the corresponding  
values.

     See Also
     --------
     Cluster.grouped_slices
         """
         # Define shortcuts
         cdef int i, ifirst, n = len(self)
         cdef list starts = self.starts, ends = self.ends
         cdef np.ndarray data = self.data
         # Define new variables
         cdef list seen = []
         cdef double value
         cdef dict grouped = {}
         for 0 <= i < n:
             ifirst = starts[i]
             value = data[ifirst]
             if not (value in seen):
                 grouped[value] = []
                 seen.append(value)
             grouped[value].append((ifirst, ends[i]+1))
         for k in grouped:
             grouped[k] = np.asarray(grouped[k])
         return grouped






More information about the Numpy-discussion mailing list