Определить интервалы с определенными значениями

Следующий код должен дать вам результат, который вы просили:

oninterval = False
dd = {}
keys = d.keys()
keys.sort()
start_key, first_val = keys[0], d[keys[0]]

for k in keys:
    v = float(d[k])
    if oninterval:
        cur_list.append(v)
        if not int(v) <= 70: # interval ends
            oninterval = False
            dd[(start_key,k)] = cur_list
    else:
        if int(v) <= 70:
            cur_list = [first_val, v]
            oninterval = True
        else:
            start_key, first_val = k, v

if oninterval: dd[(start_key, keys[-1])] = cur_list

Редактировать:

Расширенная дробь кода для принятия первого или последнего элемента со значением y ‹= 70 и обработки значений y как чисел с плавающей запятой.

По причинам, которые я не могу полностью объяснить, эта проблема загипнотизировала меня. Но я думаю, что наконец-то выкинул это из своей системы. Во-первых, основное, чистое и простое решение:

intervals = [[]]
prev = None
sorted_items = sorted(d.iteritems())
for k, v in sorted_items:
    if v <= 70:
        ext = (k,) if (intervals[-1] or prev is None) else (prev, k)
        intervals[-1].extend(ext)
    elif intervals[-1]:
        intervals[-1].append(k)
        intervals.append([])
    prev = k

if not intervals[-1]:
    intervals.pop()

print dict(((iv[0], iv[-1]), [d[k] for k in iv]) for iv in intervals)

Достаточно просто абстрагироваться от приведенного выше, чтобы создать итератор:

def iter_intervals(vals, filter_f, _nil=object()):
    prev = _nil
    interval = []
    for x in vals:
        if filter_f(x):
            ext = (x,) if (interval or prev is _nil) else (prev, x)
            interval.extend(ext)
        elif interval:
            interval.append(x)
            yield interval
            interval = []
        prev = x
    if interval: 
        yield interval

intervals = iter_intervals(d.iteritems(), lambda x: x[1] <= 70)
print dict(((iv[0][0], iv[-1][0]), [v for k, v in iv]) for iv in intervals)

Но это должно хранить много состояния. Интересно, есть ли способ сделать меньше этого...

def iter_intervals(vals, filter_f, _nil=object()):
    iters = itertools.tee(itertools.chain((_nil,), vals, (_nil,)), 3)
    next(iters[1]); next(iters[2]); next(iters[2])
    triplets = itertools.izip(*iters)
    interval = set()
    for p, curr, n in triplets:
        if filter_f(curr):
            interval.update((p, curr, n))
        elif interval:
            interval.discard(_nil)
            yield sorted(interval)
            interval = set()
    if interval:
        interval.discard(_nil)
        yield sorted(interval)

intervals = iter_intervals(d.iteritems(), lambda x: x[1] <= 70)
print dict(((iv[0][0], iv[-1][0]), [v for k, v in iv]) for iv in intervals)

Сделав это, теперь более очевидно, как адаптировать решение ninjagecko, чтобы избежать проблемы просмотра вперед/назад, которая заставляла его сохранить список:

def framed_intervals(points, filter_f, _nil=object()):
    iters = itertools.tee(itertools.chain((_nil,), points, (_nil,)), 3)
    next(iters[1]); next(iters[2]); next(iters[2])
    triplets = itertools.izip(*iters)
    for below, group in itertools.groupby(triplets, lambda x: filter_f(x[1])):
        if below:
            interval = set(itertools.chain.from_iterable(group))
            interval.discard(_nil)   # or continue if None in interval to
            yield sorted(interval)   # drop incomplete intervals

intervals = framed_intervals(d.iteritems(), lambda x: x[1] <= 70)
print dict(((iv[0][0], iv[-1][0]), [v for k, v in iv]) for iv in intervals)

Вот несколько подробное решение:

import collections

values = [(0, '92'), (11, '70'), (43, '77'), (44, '76'), (61, '77'), (64, '69'),
   (68, '67'), (84, '68'), (93, '87'), (108, '81'), (141, '74')]
d = collections.OrderedDict(values)

def intervals(d, n):
    result = collections.OrderedDict()
    interval = list()
    lastk, lastv, startk = None, None, None
    for k, v in d.iteritems():
        if int(v) > n:
            if startk is not None:
                interval.append(int(d[k]))
                result[(startk, k)] = interval
                interval = list()
                startk = None
        else:
            if lastv:
                interval.append(int(d[lastk]))
                startk = lastk
            interval.append(int(d[k]))
        lastk, lastv = k, int(v) > n
    return result


if __name__ == '__main__':
    print intervals(d, 70)

Когда я запускаю это, он печатает:

OrderedDict([((0, 43), [92, 70, 77]), ((61, 93), [77, 69, 67, 68, 87])])

что является желаемым результатом.

примечание: в вашем словаре есть строковые значения, а не значения типа int. В вашем примере вы можете иметь в виду ‹=, а не ‹.

Итак, чтобы более четко сформулировать вашу проблему, вы:

• Иметь упорядоченный список точек (x,y)
• Иметь пороговое значение T
• Требуется найти все последовательные прогоны точек p_i,...,p_j, такие, что конечные точки > T, а другие точки — нет; то есть все участки, где точки «впадают и выходят» из пороговой линии. (Обратите внимание, что такие запуски могут перекрываться, например, [71,70,{71],70,71})

Алгоритм будет следующим:

from itertools import *

def dippingIntervals(points, threshold=70):
    yBelowThreshold = lambda i: points[i][1]<=threshold

    for below,g in groupby(range(len(points)), yBelowThreshold):
        if below:
            interval = list(g)
            start,end = interval[0],interval[-1]
            if start>0 and end<len(points)-2:     #modify if "open" intervals also desired
                yield points[start-1 : end+2]

Демо:

>>> d = [(0, 92), (11, 70), (43, 77), (44, 76), (61, 77), (64, 69), (68, 67), (84, 68), (93, 87), (108, 81), (141, 74)]
>>> pprint(list( dippingIntervals(d) ))
[((0, 92), (11, 70), (43, 77)),
 ((61, 77), (64, 69), (68, 67), (84, 68), (93, 87))]

Вы можете без особых хлопот обработать данные, например, чтобы получить их в нужном формате, измените приведенную выше функцию следующим образом:

... yield (start,end), {xy[1] for xy in points[start-1 : end+2]}

Недостатком этого метода является то, что он не работает с итераторами; следующее будет работать на итераторах и является более "классическим" способом сделать это:

def getY(point):
    return point[1]

def dippingIntervals(points, threshold=70, key=getY):
    """
        Returns runs of points whose y-values dip below intervals
        >>> list( dippingIntervals([71,70,74,64,64,70,71], key=lambda x:x) )
        [(71, [70], 74), 
         (74, [64, 64, 70], 71)]
    """
    def match(point):
        return key(point)<=threshold

    lastP = None
    for p in points:
        if lastP==None:
            lastP = p
            continue

        if not match(lastP) and match(p):
            start = lastP
            R = [p]
        elif match(lastP) and match(p):
            R += [p]
        elif match(lastP) and not match(p):
            end = p
            yield start,R,end

        lastP = p