Вставить элемент в отсортированный по регистру список в Python

Question

У меня есть список строк, которые уже отсортированы в регистро-независимом порядке. Я хотел бы вставить новую строку в список. Один из способов сделать это, чтобы добавить элемент, а затем отсортировать список, например, так:

myList.append('Something') 
myList.sort(key=lambda s: s.lower()) 

Но мне было интересно, если есть способ просто вставить элемент в правильном положении без повторной сортировки все это ,

Я нашел этот вопрос: Insert an item into a sorted list in Python. Он указывает на модуль bisect Python. Но этот модуль не похож, что он может поддерживать нечувствительность к регистру.

---

Edit: Я проверял несколько ответов, перечисленных здесь.

• Добавление предмета в конец и сортировка всего списка (как предложено в исходном вопросе) была самой медленной.
• Ответ Moinuddin Quadri был быстрее, чем сортировка всего списка, но он все еще был довольно медленным из-за запуска lower() на каждый элемент в списке.
• Ответ Стефана Похмана был на порядок быстрее, чем сортировка всего списка.
• Ответ Джареда Гогуена был самым быстрым для повторных вставок. В первый раз, однако, он запускает lower() на каждый элемент.

Это был близкий звонок, чтобы принять ответ. В конце концов, я пошел с ответом Стефана Похмана, потому что он был лучшим для одноразовой вставки, и доступ к результирующему списку не требует доступа к переменной-члену. Однако варианты использования различаются, поэтому обязательно изучите все ответы.

Answer 1

Это хорошая возможность практиковать снова бинарный поиск (или просто скопировать & пасты & изменить bisect.insort, что я и сделал):

def insort_case_insensitive(a, x): 
    key = x.lower() 
    lo, hi = 0, len(myList) 
    while lo < hi: 
     mid = (lo + hi) // 2 
     if key < a[mid].lower(): 
      hi = mid 
     else: 
      lo = mid + 1 
    a.insert(lo, x) 

Демо:

myList = ['a', 'b', 'c', 'd', 'e'] 
for x in 'A', 'B', 'C', 'D', 'E': 
    insort_case_insensitive(myList, x) 
print myList 

Печать:

['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E'] 

Это O (n), просто например append + sort будет, но только из-за a.insert(lo, x) в конце. Который мертв-прост и сделан на C, так что это супер быстро. Бинарный поиск, конечно, требует только шагов O (log n), так что это тоже очень быстро. Метод append + sort вызовет .lower() для всех элементов и сравните их, причем оба из них намного медленнее. Первое решение MoinuddinQuadri также намного медленнее из-за вызова .lower() на все элементы.

См. Мой другой ответ для сравнительного сравнения.

Answer 2

Вы можете использовать bisect.bisect на нижнем регистре отсортированного списка, как:

from bisect import bisect 
my_list = ["aa", "bb", "Dd", "ee"] 
insert_string = "CC" 

#     convert all the items in list to lower case for 
#    v finding the correct location via. bisect 
index = bisect([i.lower() for i in my_list], insert_string.lower()) 
#    bisect based on lower-cased string for^
#    case-insensitive behavior 

my_list.insert(index, insert_string) 

где обновляется содержание my_list будет:

['aa', 'bb', 'CC', 'Dd', 'ee'] 

Answer 3

Я никогда не работал с Bisect, но вот мой удар на него. Первая функция, которую я беру непосредственно из bisect страницы, которые связаны между собой:

def index(a, x): 
    'Locate the leftmost value exactly equal to x' 
    i = bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
     return i 
    raise ValueError 

def insert_into_sorted(char, my_list): 
    marker = chr(ord(char) + 1) 
    spot = index(my_list, marker) 
    my_list[spot:spot] = char 
    return my_list 

x = ['a', 'b', 'd', 'e'] 

insert_into_sorted('c', x) 

>>['a', 'b', 'c', 'd', 'e'] 

Answer 4

Основываясь на комментарии от OP, так как КИ, чтобы сохранить промежуточный список для хранения нижних накладных строк (одного рабочих); это может быть достигнуто:

from bisect import bisect 
my_list = ["aa", "bb", "Dd", "ee"] 

lower_list = [i.lower() for i in my_list] # list of lower-cased strings. 
              # one time operation 
insert_string = "CC" # word to insert 

# find index based on lower-cased list 
index = bisect(lower_list, insert_string.lower()) 

my_list.insert(index, insert_string) # insert word in original list 
lower_list.insert(index, insert_string.lower()) # insert lower-cased word 
                # in lower-cased list 

где окончательное значение my_list будет lower_list будет:

>>> my_list # original list 
['aa', 'bb', 'CC', 'Dd', 'ee'] 

>>> lower_list 
['aa', 'bb', 'cc', 'dd', 'ee'] 

Здесь мы рассекает список в нижнем регистре слов, чтобы найти индекс и на основе index, вставляя строку в исходный список.

Answer 5

Вы можете создать свой собственный тип, чтобы инкапсулировать это поведение (в сочетании с bisect, как предложено в другом ответе).

from bisect import bisect 

class CaseInsensitiveSortedList: 
    def __init__(self, iterable): 
     self.with_case = list(sorted(iterable, key=lambda s: s.lower())) 
     self.without_case = [s.lower() for s in self.with_case] 

    def insert_in_order(self, s): 
     s_lower = s.lower() 
     index = bisect(self.without_case, s_lower) 
     self.without_case.insert(index, s_lower) 
     self.with_case.insert(index, s) 


test_list = CaseInsensitiveSortedList(['a', 'B', 'cd', 'E', 'fff']) 

test_list.insert_in_order('D') 
print(test_list.with_case) # ['a', 'B', 'cd', 'D', 'E', 'fff'] 

test_list.insert_in_order('ee') 
print(test_list.with_case) # ['a', 'B', 'cd', 'D', 'E', 'ee', 'fff'] 

Вы можете расширить list непосредственно и сделать это немного «более естественным» или делать все, что вы хотите с ним. Это просто идея избежать вызова str.lower для каждого элемента для каждой вставки.

Answer 6

Я вижу, что вы добавили результаты теста к вам. Я сделал несколько тестов, а сейчас и получить аналогичную картину:

Insorting 20000 words: 
80.224 seconds with insort_sorting 
    0.166 seconds with insort_own_binary_search 
70.294 seconds with insort_lower_all 
    0.094 seconds with insort_keep_lower 

Ты несколько неправильно о быстром двух, хотя. С большим количеством вставок моя становится быстрее. Примерно в два раза быстрее:

Insorting 1000000 words: 
92.712 seconds with insort_own_binary_search 
173.577 seconds with insort_keep_lower 

Это потому, что O (журнал N) времени для поиска индекса становится незначительным, а время доминирует время O (N) для insert вызовов. И мое решение имеет только один из них, в то время как другое решение имеет два.

Другим отличием является сложность пространства, сохраняя дополнительный список пониженных версий всех строк, не так хорош.

Вот мой бенчмаркинг код:

import random, string, time 

#-------------------------------------------------------------- 
def insort_sorting(a, x): 
    a.append(x) 
    a.sort(key=str.lower) 
#-------------------------------------------------------------- 
def insort_own_binary_search(a, x): 
    key = x.lower() 
    lo, hi = 0, len(myList) 
    while lo < hi: 
     mid = (lo + hi) // 2 
     if key < a[mid].lower(): 
      hi = mid 
     else: 
      lo = mid + 1 
    a.insert(lo, x) 
#-------------------------------------------------------------- 
from bisect import bisect 
def insort_lower_all(a, x): 
    index = bisect([i.lower() for i in a], x.lower()) 
    a.insert(index, x) 
#-------------------------------------------------------------- 
from bisect import bisect 
def insort_keep_lower(a, x, lower=[]): 
    x_lower = x.lower() 
    index = bisect(lower, x_lower) 
    a.insert(index, x) 
    lower.insert(index, x_lower) 
#-------------------------------------------------------------- 

# Generate random words  
words = [''.join(random.choice(string.ascii_letters) for _ in range(10)) 
     for _ in range(20000)] 
#   for _ in range(1000000)] 

# Compare the solutions 
print 'Insorting', len(words), 'words:' 
reference = None 
for insort in insort_sorting, insort_own_binary_search, insort_lower_all, insort_keep_lower: 
#for insort in insort_own_binary_search, insort_keep_lower: 
    t0 = time.time() 
    myList = [] 
    for word in words: 
     insort(myList, word) 
    print '%7.3f seconds with %s' % (time.time() - t0, insort.__name__) 
    if reference is None: 
     reference = myList 
    else: 
     assert myList == reference