7

append() を使用して構築されている Python v2.7 リストの複雑さの順序は何ですか? Pythonリストは二重にリンクされているため、一定の複雑さですか、それとも単一にリンクされているため、線形の複雑さですか? 単独でリンクされている場合、最初から最後までの順序でリストの値を提供する反復からリストを線形時間で作成するにはどうすればよいですか?

例えば：

def holes_between(intervals):
  # Compute the holes between the intervals, for example:
  #     given the table: ([ 8,  9] [14, 18] [19, 20] [23, 32] [34, 49])
  #   compute the holes: ([10, 13] [21, 22] [33, 33])
  prec = intervals[0][1] + 1 # Bootstrap the iteration
  holes = []
  for low, high in intervals[1:]:
    if prec <= low - 1:
      holes.append((prec, low - 1))
    prec = high + 1
  return holes
4

1 に答える 1

23

Python の時間計算量list.append()は O(1) です。Python WikiのTime Complexity リストを参照してください。

内部的には、python リストはポインターのベクトルです。

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

ベクターは必要に応じてオーバーアロケーションでサイズ変更され、ob_item追加の償却された O(1) コストが得られます。

/* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

これにより、Python リストが動的配列になります。

于 2013-02-27T20:39:48.540 に答える