Python 에서 순서 표 원리 와 실현 방법 에 대한 상세 한 설명

본 논문 의 사례 는 Python 에서 순서 표 의 원리 와 실현 방법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
Python 의 순서 표
Python 의 list 와 tuple 두 가지 유형 은 순서 표 의 실현 기술 을 사용 하여 순서 표 의 모든 성질 을 가지 고 있 습 니 다.
tuple 은 변 하지 않 는 형식,즉 변 하지 않 는 순서 표 이기 때문에 내부 상 태 를 바 꾸 는 어떠한 조작 도 지원 하지 않 으 며,다른 측면 에 서 는 list 의 성질 과 유사 합 니 다.
list 의 기본 실현 기술
Python 표준 유형 list 는 요소 개수 가 변 하 는 선형 표 로 요 소 를 추가 하고 삭제 할 수 있 으 며 각종 작업 에서 기 존 요소 의 순서(즉,순서 유지)를 유지 할 수 있 으 며 다음 과 같은 행위 특징 도 가지 고 있 습 니 다.

아래 표 시 된(위치)의 효율 적 인 요소 에 대한 방문 과 업 데 이 트 를 바탕 으로 시간 복잡 도 는 O(1)여야 한다.
이 특징 을 만족 시 키 기 위해 서 는 순서 표 기술 을 사용 하여 표 의 요 소 는 연속 적 인 저장 구역 에 저장 해 야 한다.

요 소 를 임의로 가입 할 수 있 고 요 소 를 계속 가입 하 는 과정 에서 표 대상 의 표지(함수 id 가 얻 은 값)는 변 하지 않 습 니 다.
이 특징 을 만족 시 키 기 위해 요소 저장 소 를 교체 할 수 있 고 저장 소 를 교체 할 때 list 대상 의 표지 id 가 변 하지 않도록 분리 식 실현 기술 만 사용 할 수 있 습 니 다.

Python 의 공식 실현 에서 list 는 분리 식 기술 로 이 루어 진 동적 순서 표 이다.이것 이 바로 list.append(x)(또는 list.insert(len(list),x),즉 꼬리 부분 삽입)이 지정 한 위치 에 요 소 를 삽입 하 는 것 보다 효율 이 높 은 이유 입 니 다.
《데이터 구조 와 알고리즘 Python 언어 묘 사》주 종 연 저
Python 의 공식 실현 에서 list 는 다음 과 같은 전략 을 사용 합 니 다.빈 표(또는 작은 표)를 만 들 때 시스템 은 8 개의 요 소 를 수용 할 수 있 는 저장 소 를 분배 합 니 다.삽입 작업(insert 또는 append)을 수행 할 때 요소 저장 소 가 가득 차 면 4 배 큰 저장 소 를 바 꿉 니 다.그러나 이때 시계 가 이미 매우 크다(현재 밸브 값 은 50000)면 전략 을 바 꾸 고 배 를 더 하 는 방법 을 사용한다.이러한 변경 정책 을 도입 하 는 방식 은 너무 많은 남 은 저장 위치 가 나타 나 지 않도록 하기 위해 서 이다.
Python 의 공식 실현 에서 list 는 다음 과 같은 전략 을 사용 합 니 다.

  /* 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);
  /* check for integer overflow */
  if (new_allocated > PY_SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
  } else {
    new_allocated += newsize;
  }

python 순서 표 추가 삭제 실현

class shunxubiao:
  def __init__(self,length):#length        ，              
    self.length=length
    self.data=[] #data       
    self.biao=-1 #    
  def weikong(self):#             
    if self.biao==-1:
      return True
    else:
      return False
  def mande(self):#           
    if self.biao+1==self.length:
      return True
    else:
      return False
  def qingkong(self):
    if not self.weikong():
      self.data=[]
      self.biao=-1
  def geshu(self):
    return self.biao+1
  def chazhao(self,x):#        
    return self.data[x]
  def chazhao1(self,x):#        
    if self.weikong():
      print('   ')
      return -1
    for i in range(self.biao+1):
      if self.data[i]==x:
       return i
       break
       print('        ')
  def biaoweijia(self,x): #           
    if self.mande():
      print('biaoyiman')
    else:
     self.data.append(x)
    self.biao+=1
  def charu(self,index,x):#     index    x  
    if self.mande():
      print('biayiman')
    elif index<0 or index>self.biao-1:
      print('bunengcharu')
    else:
      for i in range(self.biao,index-1):
        self.data[i+1]=self.data[i]
        self.data[index-1]=x
      self.biao+=1
  def shanchu(self,x):#      x
    if self.weikong():#       
      print('kongde,bunengshanchu')
    index=-1# index  x   
    for i in (self.data):
      index+=1
      if i == x:
        break
    for i in range(index,self.biao-1):# x              
      self.data[i]=self.data[i+1]
    self.biao-=1
c=shunxubiao(6)
c.data=[2,4,5,6]
c.biao=3
c.weikong()
print(c.chazhao(2))#    2    
print(c.chazhao1(4))#        
c.biaoweijia(7)#      
print(c.data)
print(c.biao)
c.charu(3,9)
print(c.data)
print(c.biao)
c.shanchu(7)
print(c.data)
print(c.biao)

출력 결과:
[2, 4, 5, 6, 7] 4 [2, 4, 5, 6, 7] 5 [2, 4, 5, 6, 7] 4
생각:왜 9 를 추가 하지 않 았 고 7 을 삭제 하지 않 았 을 까?
더 많은 파 이 썬 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있다.
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.