PooH
мое ЛЯ-ЛЯ - исключительно из опыта. работа с листами, в питоне очень медленная когда кол-во элементов идет на тысячи.
ZZZ
действительно быстро - не знал. спасибо, возьму на вооружение.
test157Я про словари
мое ЛЯ-ЛЯ - исключительно из опыта. работа с листами, в питоне очень медленная когда кол-во элементов идет на тысячи.
chars = u'qwertyuiopasdfghjklzxcvbnm_01234567890'
def create_word():
w = u''
for n in range(random.randint(3, 13)):
w += random.choice(chars)
return w
def create_list_of_words(count_of_words):
l = []
for i in xrange(count_of_words):
bisect.insort(l, create_word())
return l
t = time.time()
create_list_of_words(100000)
print time.time() - t
t = time.time()
l = []
for i in xrange(100000):
l.append(create_word())
print time.time() - t
test157Вы же проверяете только время создания списка, естественно простое добавление в конец списка будет быстрее, чем поиск места в списке и вставка туда.
хм, что то странное. я сейчас проверил код с бисектом и он 4 раза медленнее нежели прямиком со с листом. что я делаю не так?
test157Да, держит отсортированным. Скорость держится за счет двоичного поиска. Грубо говоря: она бьет список пополам - заданный элемент находится или в одной половине или в другой, дальше она бьет пополам половину и так далее. За счет этого получается сложность O(log n), при обычном поиске в списке сложность будет линейной
не могу понять - как оно точно работает.
1. я так понимаю оно просто постоянно держит список отсортированным, и засчет этого обеспечивается более высокая скорость?
test157При вставке элемент вставляется сразу в нужную позиции
2. есть ли разница от обычного sorted тогда?
test157если в списке уже есть такой элемент первая вставит новый элемент после старого, вторая перед
3. и в чем отличае insort_right и insort_left? оба оставляют список отсортированным.
test157это если хотите искать только в части списка, lo и hi задают элементы между которыми будет произведен поиск
4. и что дают - lo, hi - параметры?
если в списке уже есть такой элемент первая вставит новый элемент после старого, вторая переда в чем различие? если элементы ОДИНАКОВЫЕ - какая разница ДО или ПОСЛЕ он поставится?
test157У вас могут в списке храниться объекты с переопределеным методом __cmp__, при этом при сравнении они будут одинаковые, а сами объекты различаться. Например, пусть у меня объект класса Command или его наследника, у которого есть атрибут порядок исполнения, и в __cmp__ я сравниваю этот порядок. При этом сами команды разные.если в списке уже есть такой элемент первая вставит новый элемент после старого, вторая переда в чем различие? если элементы ОДИНАКОВЫЕ - какая разница ДО или ПОСЛЕ он поставится?
test157Ну вот для этого как раз и две функции. Может я хочу если приоритет одинаковый сначала выполнять те команды что были добавлены раньше, или наоборот. И зависимо от этого буду использовать для вставки или insort_right или insort_left. Хотя, действительно, нужно такое довольно редко. Если вам это не важно пользуйте insort и не ломайте голову ;)
так ведь бисект возьмет результат от переопределенного метода __cmp__ и если объекты не равны (т.е. CPM вернет не ноль), то уже все понятно с ними - а если равны, то он поставит ДО или ПОСЛЕ в зависимости от функции лефт или райт.