Python에서 정렬된 목록에 항목 삽입

Python에서 정렬된 목록에 항목 삽입

메소드 중 하나가 정렬된 목록에 새 항목을 삽입하는 클래스를 만들고 있습니다.항목이 정렬된 목록에서 수정된(정렬된) 위치에 삽입됩니다.다음 이외의 기본 제공 목록 기능 또는 메서드를 사용할 수 없습니다.[],[:],+,그리고.len그래도.이 부분이 저에게 정말 혼란스러운 부분입니다.

이 문제를 해결하는 가장 좋은 방법은 무엇입니까?

이등분 모듈의 삽입 함수를 사용합니다.

import bisect 
a = [1, 2, 4, 5] 
bisect.insort(a, 3) 
print(a)

산출량

[1, 2, 3, 4, 5] 

더 복잡한 사용법은 다음을 참조하십시오.key에 대한 매개 변수.insort방법

import bisect
a = [{"key": 1}, {"key": 3}]
bisect.insort(a, {"key": 2}, key=lambda x: x["key"])
print(a)

산출량

[{"key": 1}, {"key": 2}, {"key": 3}]

힌트 1: 바이섹트 모듈에서 파이썬 코드를 연구할 수 있습니다.

힌트 2: 목록 삽입에 슬라이싱을 사용할 수 있습니다.

>>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']

당신은 이등분 모듈을 사용해야 합니다.또한 bisect.insort_left를 사용하기 전에 목록을 정렬해야 합니다.

그것은 꽤 큰 차이입니다.

>>> l = [0, 2, 4, 5, 9]
>>> bisect.insort_left(l,8)
>>> l
[0, 2, 4, 5, 8, 9]

timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000)
    1.2235019207000732

timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000)
    0.041441917419433594

저는 지금 알고리즘을 배우고 있는데, 바이섹트 모듈이 어떻게 쓰는지 궁금합니다.다음은 이분법을 사용하는 정렬된 목록에 항목을 삽입하는 것에 대한 이분법 모듈의 코드입니다.

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.
    If x is already in a, insert it to the right of the rightmost x.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid+1
    a.insert(lo, x)

인위적인 제한이 없는 경우 의 설명에 따라 를 사용해야 합니다.하지만, 로서Velda댓글에 언급된 대부분의 실제 문제는 순수한 숫자를 정렬하는 것 이상입니다.

다행히도, 언급된 바와 같이.drakenation솔루션은 비교 가능한 모든 개체에 적용됩니다.예를들면,bisect.insort()또한 를 구현하는 사용자 지정 데이터 클래스와 함께 작동합니다.__lt__():

from bisect import insort

@dataclass
class Person:
    first_name: str
    last_name: str
    age: int

    def __lt__(self, other):
        return self.age < other.age

persons = []

insort(persons, Person('John', 'Doe', 30))
insort(persons, Person('Jane', 'Doe', 28))
insort(persons, Person('Santa', 'Claus', 1750))

# [Person(first_name='Jane', last_name='Doe', age=28), Person(first_name='John', last_name='Doe', age=30), Person(first_name='Santa', last_name='Claus', age=1750)]

그러나 튜플의 경우 임의의 키로 정렬하는 것이 바람직할 것입니다.기본적으로 튜플은 첫 번째 항목(이름), 다음 항목(성) 순으로 정렬됩니다.

솔루션으로 추가 키 목록을 관리할 수 있습니다.

from bisect import bisect

persons = []
ages = []

def insert_person(person):
    age = person[2]
    i = bisect(ages, age)
    persons.insert(i, person)
    ages.insert(i, age)
    
insert_person(('John', 'Doe', 30))
insert_person(('Jane', 'Doe', 28))
insert_person(('Santa', 'Claus', 1750))

공식 솔루션:의 설명서는 다음과 같이 사용할 수 있도록 사용자 지정 클래스에서 이 기능을 구현하는 방법을 설명합니다.

>>> s = SortedCollection(key=itemgetter(2))
>>> for record in [
...         ('roger', 'young', 30),
...         ('angela', 'jones', 28),
...         ('bill', 'smith', 22),
...         ('david', 'thomas', 32)]:
...     s.insert(record)

>>> pprint(list(s))         # show records sorted by age
[('bill', 'smith', 22),
 ('angela', 'jones', 28),
 ('roger', 'young', 30),
 ('david', 'thomas', 32)]

다음은 예제가 작동하는 데 필요한 클래스의 관련 발췌문입니다.기본적으로,SortedCollection 항목 목록과 병렬로 추가 키 목록을 관리하여 새 튜플(및 해당 키)을 삽입할 위치를 확인합니다.

from bisect import bisect_left

class SortedCollection(object):

    def __init__(self, iterable=(), key=None):
        self._given_key = key
        key = (lambda x: x) if key is None else key
        decorated = sorted((key(item), item) for item in iterable)
        self._keys = [k for k, item in decorated]
        self._items = [item for k, item in decorated]
        self._key = key
        
    def __getitem__(self, i):
        return self._items[i]

    def __iter__(self):
        return iter(self._items)
        
    def insert(self, item):
        'Insert a new item.  If equal keys are found, add to the left'
        k = self._key(item)
        i = bisect_left(self._keys, k)
        self._keys.insert(i, k)
        self._items.insert(i, item)

참고:list.insert()게다가bisect.insort()복잡도가 O(n)입니다.따라서, 언급된 바와 같이.nz_21정렬된 목록을 수동으로 반복하여 올바른 위치를 찾는 것도 복잡성 측면에서 마찬가지입니다.사실 파이썬의 팀소트는 최악의 경우 O(n log(n))의 복잡성을 가지고 있기 때문에 새로운 값을 삽입한 후 배열을 정렬하는 것도 괜찮을 것입니다.그러나 완전성을 위해 이진 검색 트리(BST)는 O(log(n) 시간 내에 삽입할 수 있습니다.

이것은 당신에게 가능한 해결책입니다.

a = [15, 12, 10]
b = sorted(a)
print b # --> b = [10, 12, 15]
c = 13
for i in range(len(b)):
    if b[i] > c:
        break
d = b[:i] + [c] + b[i:]
print d # --> d = [10, 12, 13, 15]

# function to insert a number in an sorted list


def pstatement(value_returned):
    return print('new sorted list =', value_returned)


def insert(input, n):
    print('input list = ', input)
    print('number to insert = ', n)
    print('range to iterate is =', len(input))

    first = input[0]
    print('first element =', first)
    last = input[-1]
    print('last element =', last)

    if first > n:
        list = [n] + input[:]
        return pstatement(list)
    elif last < n:
        list = input[:] + [n]
        return pstatement(list)
    else:
        for i in range(len(input)):
            if input[i] > n:
                break
    list = input[:i] + [n] + input[i:]
    return pstatement(list)

# Input values
listq = [2, 4, 5]
n = 1

insert(listq, n)

음, 이것을 하는 방법은 여러 가지가 있습니다. 여기 내장된 파이썬 함수를 정렬()하여 동일하게 할 수 있는 간단한 순진한 프로그램이 있습니다.

def sorted_inserter():
list_in = []
n1 = int(input("How many items in the list : "))

for i in range (n1):
    e1 = int(input("Enter numbers in list : "))
    list_in.append(e1)
print("The input list is : ",list_in)


print("Any more items to be inserted ?")
n2 = int(input("How many more numbers to be added ? : "))
for j in range (n2):
    e2= int(input("Add more numbers : "))
    list_in.append(e2)
    list_sorted=sorted(list_in)
    print("The sorted list is: ",list_sorted)
    

sorted_inserter()

출력은

목록에 있는 항목 수: 4

목록에 숫자 입력: 1

목록에 숫자 입력: 2

목록에 숫자 입력: 123

목록에 번호 입력: 523

입력 목록은 [1, 2, 123, 523]입니다.

삽입할 항목이 더 있습니까?

추가할 숫자가 몇 개입니까? : 1

숫자 추가: 9

정렬된 목록은 [1, 2, 9, 123, 523]입니다.

첫 두 요소가 때는 이 요소를 하면 됩니다.key의 파라미터bisect.insort기능은 다음과 같습니다.

import bisect 

class B:
    pass

a = [(1, B()), (2, B()), (3, B())] 
bisect.insort(a, (3, B()), key=lambda x: x[0]) 
print(a)

다음을 제외하고는lambda세번 매개 기다니합능의 세 합니다.bisect.insort 코드가 코가던기를 .TypeError기능이 튜플의 두 번째 요소를 기본적으로 비교할 수 없는 타이 브레이커로 비교하려고 하기 때문입니다.

목록을 추가하고 정렬된 목록에 값을 삽입하는 가장 좋은 방법은 다음과 같습니다.

 a = [] num = int(input('How many numbers: ')) for n in range(num):
     numbers = int(input('Enter values:'))
     a.append(numbers)

 b = sorted(a) print(b) c = int(input("enter value:")) for i in
 range(len(b)):
     if b[i] > c:
         index = i
         break d = b[:i] + [c] + b[i:] print(d)`

언급URL : https://stackoverflow.com/questions/8024571/insert-an-item-into-sorted-list-in-python