0

昇順の値のリストがあるとします。ただし、ある時点で値がラップされます。

2, 4, 6, 9, 12, 15, 34, -2, 1, 4, 5, 7, ...

期間が 2^n であることを知っている場合、n の値によっては、組み込み関数があるか、上記の値を並べ替えて、すべての数値が昇順になるようにする高速な方法があります (数値が可能なようなものであると仮定します)。 )?

4

4 に答える 4

5

list.sort()十分に速いかもしれません。CPython では、 Timsortを使用して実装されます。これは、平均よりも優れた方法であなたのようなケースを処理する必要があります (最初の段階では、あなたのケースとまったく同じように、既に並べ替えられた数値の実行を探しています)。

于 2012-04-26T21:56:23.423 に答える
2

予想される出力は、質問を理解するのに役立ちます。私は、他の解決策とは異なる望ましい解決策を推測しました。他の誰かがこの解釈のより簡潔な解決策を見つけることができるかもしれません。

出力は 2, 4, 6, 9, 12, 15, 34, 62, 65, 68, 69, ... つまり、-2 から始まるすべての値が 64 だけ上にシフトされます。

最初に、周期のサイズを 64 と推測します。これは、たとえば、隣接する要素の最も負の差を調べ、2 のべき乗に切り上げることによって行うことができます。最初にすべての値を使用できない場合、これは不可能な場合があります。

period = 64

def unwrap(seq):
    it = iter(seq)
    try:
        lastitem = next(it)
    except StopIteration:
        return
    yield lastitem
    shift = 0
    for item in it: 
        if item < lastitem:
            shift += period
        yield item + shift
        lastitem = item

ジェネレーターではなくリストが必要な場合は、使用できます

result = list(unwrap(original_list))
于 2012-04-27T00:20:34.303 に答える
0 
>>> sorted([5, 2, 3, 1, 4])
[1, 2, 3, 4, 5]

>>> a = [5, 2, 3, 1, 4]
>>> a.sort()
于 2012-04-26T21:57:21.730 に答える
0

すべての値を昇順にしたい場合、それはソートです：

>>> sorted([2, 4, 6, 9, 12, 15, 34, -2, 1, 4, 5, 7])
[-2, 1, 2, 4, 5, 6, 7, 9, 12, 15, 34]

連続した数字が間隔を空けてラップしているという知識に基づいて並べ替えを最適化しようとしていますか、それとも別の質問をしていますか?

于 2012-04-26T21:56:31.843 に答える