Bessere Lösung für iter_pare_sum() ???

[jens]

Weiß jemand wie man iter_pare_sum() besser machen kann?

Finde die Lösung mit skip dumm.

Code: Alles auswählen

def iter_window(g, window_size):
    """
    interate over 'g' bit-by-bit and yield a window with the given 'window_size' width.

    >>> for v in iter_window([1,2,3,4], window_size=2): v
    [1, 2]
    [2, 3]
    [3, 4]
    >>> for v in iter_window([1,2,3,4,5], window_size=3): v
    [1, 2, 3]
    [2, 3, 4]
    [3, 4, 5]

    >>> for v in iter_window([1,2,3,4], window_size=2):
    ...    v
    ...    v.append(True)
    [1, 2]
    [2, 3]
    [3, 4]
    """
    values = collections.deque(maxlen=window_size)
    for value in g:
        values.append(value)
        if len(values) == window_size:
            yield list(values)


def iter_pare_sum(data):
    """
    >>> def g(data):
    ...     for i in data: yield i
    >>> list(iter_pare_sum(g([5,5,10,10,4,4,10,10,5,5])))
    [20, 8, 20, 10]

    >>> list(iter_pare_sum([5,10,10,4,4,10,10,5,5,10]))
    [20, 8, 20, 10]

    >>> list(iter_pare_sum([5,4,10,11,5,4,21,22,2,1]))
    [21, 9, 43, 3]

    >>> list(iter_pare_sum([
    ... 5,5,10,10,5,5,
    ... 5,                # <- resync 1
    ... 8,8,5,5,10,10,
    ... 10,               # <- resync 2
    ... 7,7,5,5,10,10,2,2,3,3
    ... ]))
    [20, 10, 10, 16, 10, 20, 14, 10, 20, 4, 6]

    resync      ^           ^
    """
    skip = True
    for previous, current, next_value in iter_window(data, window_size=3):
        if skip:
            skip = False
            continue
        skip = True
        diff1 = abs(previous - current)
        diff2 = abs(current - next_value)
        if diff1 < diff2:
            yield previous + current
        else:
            yield current + next_value


if __name__ == "__main__":
    import doctest
    print doctest.testmod()

Es geht darum, das immer die Summe des am näher liegenden Pärchen gemacht wird. Wenn sich ein Ausreißer dazwischen schummelt, soll es danach wieder mit den besten Pärchen weiter gehen...

EDIT: Funktion iter_window bei gepackt. Um die geht es allerdings nicht. Gern auch eine Lösung ohne dem.

[EyDu]

Code: Alles auswählen

def iter_pare_sum(data):
    for previous, current, next_value in itertools.islice(iter_window(data, window_size=3), 1):
        diff1 = abs(previous - current)
        diff2 = abs(current - next_value)

        if diff1 < diff2:
            yield previous + current
        else:
            yield current + next_value

[jens]

Das tut's nicht. Aber gute Idee, so geht's:

Code: Alles auswählen

...
    for previous, current, next_value in itertools.islice(iter_window(data, window_size=3), 1, None, 2):
...

[EyDu]

Klar. Hatte das zweite ``skip = True`` vollkommen übersehen.

[pillmuncher]

Sofern ich die Aufgabe richtig verstanden habe und sofern diese Funktionen vordefiniert sind:

Code: Alles auswählen

def compose(f, *gs):
    def composed(x):
        x = f(x)
        for g in gs:
            x = g(x)
        return x
    return composed

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

def paired(iterable):
    iterable = iter(iterable)
    return izip(iterable, iterable)

könnte man es so machen:

Code: Alles auswählen

paired_pairwise = compose(paired, pairwise)

def sum_nearest_neighbor(iterable):
    """
    >>> def g(data):
    ...     for i in data: yield i
    >>> list(sum_nearest_neighbor(g([5,5,10,10,4,4,10,10,5,5])))
    [20, 8, 20, 10]

    >>> list(sum_nearest_neighbor([5,10,10,4,4,10,10,5,5,10]))
    [20, 8, 20, 10]

    >>> list(sum_nearest_neighbor([5,4,10,11,5,4,21,22,2,1]))
    [21, 9, 43, 3]

    >>> list(sum_nearest_neighbor([
    ... 5,5,10,10,5,5,
    ... 5,                # <- resync 1
    ... 8,8,5,5,10,10,
    ... 10,               # <- resync 2
    ... 7,7,5,5,10,10,2,2,3,3
    ... ]))
    [20, 10, 10, 16, 10, 20, 14, 10, 20, 4, 6]

    resync      ^           ^
    """
    for (a, b), (c, d) in paired_pairwise(iterable):
        if abs(b - c) < abs(c - d):
            yield b + c
        else:
            yield c + d

if __name__ == "__main__":
    import doctest
    print doctest.testmod()

@jens: Hier sieht man gleich, dass das erste Element aus iterable überhaupt nicht verwendet wird. Bei dir ist das ebenfalls so, man sieht es nur nicht sofort. Ist das Absicht? Falls nicht, könnte man es statt dessen so machen:

Code: Alles auswählen

def sum_nearest_neighbor(iterable):
    """..."""
    first_pair_selected = False
    for (a, b), (c, d) in paired_pairwise(iterable):
        first_pair_selected = abs(a - b) < abs(b - c)
        if first_pair_selected:
            yield a + b
        else:
            yield b + c
    if first_pair_selected:
        yield c + d

Die Ergebenisse wäre dann natürlich andere:

Code: Alles auswählen

[10, 20, 8, 20, 10]
[9, 21, 9, 43, 3]
[10, 20, 10, 16, 10, 20, 20, 14, 10, 20, 4, 6]

Allerdings stellt sich dann immer noch die Frage, was man mit Iterables mit weniger als vier Elementen macht?

[jens]

Also in meinem Falle geht es um sehr viele Werte. Ob da vorn oder hinten was fehlt ist fast egal. Doch wenn, dann wäre es besser das Werte vorn statt hinten fehlen...

[jerch]

@jens:
Wenn ich das richtig verstehe, willst Du damit ja die Halbperioden so addieren, dass Du die Bits erhältst (volle Periode). Dein resync versucht, eingestreute Halbperioden, die keine sinnvolle Information enthalten, zu eliminieren. Laut Spec darf es die ja nicht geben - wie aber damit umgehen, falls es doch auftritt? Ich glaube, Deine derzeitige Herangehensweise übersieht hierbei Bits, was zu einem Shift führt und die Daten (in Bytes) nach der Störung unbrauchbar macht. Leider hilft da auch keine simple Längenabschätzung der Störung, um den Offset des Bitsstroms zu korrigieren, da Einsen doppelt so schnell einfliegen wie die Nullen.

Ich hab keine Lösung dafür, nur frage ich mich, ob Dein resync überhaupt Sinn macht oder man mit der ersten gefundenen 1/0-Grenze eh festgelegt ist.

[jens]

Hast du alles richtig erkannt... Ich weiß auch noch nicht so ganz ob das Funktioniert. Aber Tests Zeiten, das du recht hast, Bits gehen verloren...

Es zeigt sich auch, das zwischen den beiden viel zu oft hin und her gesprungen wird. Eigentlich was die Idee, das es quasi nur einmal das richtig Paar gefunden wird und es sich dann auch quasi nicht ändert.